qcsrc/server/pathlib/costs.qc

   1 float pathlib_g_static(entity parent,vector to, float static_cost)
   2 {
   3     return parent.pathlib_node_g + static_cost;
   4 }
   5
   6 float pathlib_g_static_water(entity parent,vector to, float static_cost)
   7 {
   8     if(inwater(to))
   9         return parent.pathlib_node_g + static_cost * pathlib_movecost_waterfactor;
  10     else
  11         return parent.pathlib_node_g + static_cost;
  12 }
  13
  14 float pathlib_g_euclidean(entity parent,vector to, float static_cost)
  15 {
  16     return parent.pathlib_node_g + vlen(parent.origin - to);
  17 }
  18
  19 float pathlib_g_euclidean_water(entity parent,vector to, float static_cost)
  20 {
  21     if(inwater(to))
  22         return parent.pathlib_node_g + vlen(parent.origin - to) * pathlib_movecost_waterfactor;
  23     else
  24         return parent.pathlib_node_g + vlen(parent.origin - to);
  25 }
  26
  27
  28 /**
  29     Manhattan Menas we expect to move up,down left or right
  30     No diagonal moves espected. (like moving bewteen city blocks)
  31 **/
  32 float pathlib_h_manhattan(vector a,vector b)
  33 {
  34     //h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y))
  35
  36     float h;
  37     h  = fabs(a.x - b.x);
  38     h += fabs(a.y - b.y);
  39     h *= pathlib_gridsize;
  40
  41     return h;
  42 }
  43
  44 /**
  45     This heuristic consider both stright and disagonal moves
  46     to have teh same cost.
  47 **/
  48 float pathlib_h_diagonal(vector a,vector b)
  49 {
  50     //h(n) = D * max(abs(n.x-goal.x), abs(n.y-goal.y))
  51     float h,x,y;
  52
  53     x = fabs(a.x - b.x);
  54     y = fabs(a.y - b.y);
  55     h = pathlib_movecost * max(x,y);
  56
  57     return h;
  58 }
  59
  60 /**
  61     This heuristic only considers the stright line distance.
  62     Will usualy mean a lower H then G meaning A* Will speand more
  63     and run slower.
  64 **/
  65 float pathlib_h_euclidean(vector a,vector b)
  66 {
  67     return vlen(a - b);
  68 }
  69
  70 /**
  71     This heuristic consider both stright and disagonal moves,
  72     But has a separate cost for diagonal moves.
  73 **/
  74 float pathlib_h_diagonal2(vector a,vector b)
  75 {
  76     float h_diag,h_str,h,x,y;
  77
  78     /*
  79     h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
  80     h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
  81     h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))
  82     */
  83
  84     x = fabs(a.x - b.x);
  85     y = fabs(a.y - b.y);
  86
  87     h_diag = min(x,y);
  88     h_str = x + y;
  89
  90     h =  pathlib_movecost_diag * h_diag;
  91     h += pathlib_movecost * (h_str - 2 * h_diag);
  92
  93     return h;
  94 }
  95
  96 /**
  97     This heuristic consider both stright and disagonal moves,
  98     But has a separate cost for diagonal moves.
  99 **/
 100 float pathlib_h_diagonal2sdp(vector preprev,vector prev,vector point,vector end)
 101 {
 102     float h_diag,h_str,h,x,y,z;
 103
 104     //h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
 105     //h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
 106     //h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))
 107
 108     x = fabs(point.x - end.x);
 109     y = fabs(point.y - end.y);
 110     z = fabs(point.z - end.z);
 111
 112     h_diag = min3(x,y,z);
 113     h_str = x + y + z;
 114
 115     h =  pathlib_movecost_diag * h_diag;
 116     h += pathlib_movecost * (h_str - 2 * h_diag);
 117
 118     float m;
 119     vector d1,d2;
 120
 121     d1 = normalize(preprev - point);
 122     d2 = normalize(prev    - point);
 123     m = vlen(d1-d2);
 124
 125     return h * m;
 126 }
 127
 128
 129 float pathlib_h_diagonal3(vector a,vector b)
 130 {
 131     float h_diag,h_str,h,x,y,z;
 132
 133     x = fabs(a.x - b.x);
 134     y = fabs(a.y - b.y);
 135     z = fabs(a.z - b.z);
 136
 137     h_diag = min3(x,y,z);
 138     h_str = x + y + z;
 139
 140     h =  pathlib_movecost_diag * h_diag;
 141     h += pathlib_movecost * (h_str - 2 * h_diag);
 142
 143     return h;
 144 }