qcsrc/server/pathlib/costs.qc

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