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 heuristic means we expect to move up, down left or right
  32     No diagonal moves expected. (like moving between 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  = fabs(a.x - b.x);
  39     h += fabs(a.y - b.y);
  40     h *= pathlib_gridsize;
  41
  42     return h;
  43 }
  44
  45 /**
  46     This heuristic consider both straight and diagonal moves
  47     to have the same cost.
  48 **/
  49 float pathlib_h_diagonal(vector a, vector b)
  50 {
  51     //h(n) = D * max(abs(n.x-goal.x), abs(n.y-goal.y))
  52
  53     float hx = fabs(a.x - b.x);
  54     float hy = fabs(a.y - b.y);
  55     float h = pathlib_movecost * max(hx, hy);
  56
  57     return h;
  58 }
  59
  60 /**
  61     This heuristic only considers the straight line distance.
  62     Usually means a lower H then G, resulting in A* spreading more
  63     (and running 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 straight and diagonal moves,
  72     but has a separate cost for diagonal moves.
  73 **/
  74 float pathlib_h_diagonal2(vector a,vector b)
  75 {
  76     /*
  77     h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
  78     h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
  79     h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))
  80     */
  81
  82     float hx = fabs(a.x - b.x);
  83     float hy = fabs(a.y - b.y);
  84
  85     float h_diag = min(hx,hy);
  86     float h_str = hx + hy;
  87
  88     float h =  pathlib_movecost_diag * h_diag;
  89     h += pathlib_movecost * (h_str - 2 * h_diag);
  90
  91     return h;
  92 }
  93
  94 /**
  95     This heuristic consider both straight and diagonal moves,
  96     But has a separate cost for diagonal moves.
  97 **/
  98 float pathlib_h_diagonal2sdp(vector preprev, vector prev, vector point, vector end)
  99 {
 100     //h_diagonal(n) = min(abs(n.x-goal.x), abs(n.y-goal.y))
 101     //h_straight(n) = (abs(n.x-goal.x) + abs(n.y-goal.y))
 102     //h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))
 103
 104     float hx = fabs(point.x - end.x);
 105     float hy = fabs(point.y - end.y);
 106     float hz = fabs(point.z - end.z);
 107
 108     float h_diag = min3(hx,hy,hz);
 109     float h_str = hx + hy + hz;
 110
 111     float h =  pathlib_movecost_diag * h_diag;
 112     h += pathlib_movecost * (h_str - 2 * h_diag);
 113
 114     vector d1 = normalize(preprev - point);
 115     vector d2 = normalize(prev    - point);
 116     float m = vlen(d1 - d2);
 117
 118     return h * m;
 119 }
 120
 121
 122 float pathlib_h_diagonal3(vector a, vector b)
 123 {
 124     float hx = fabs(a.x - b.x);
 125     float hy = fabs(a.y - b.y);
 126     float hz = fabs(a.z - b.z);
 127
 128     float h_diag = min3(hx,hy,hz);
 129     float h_str = hx + hy + hz;
 130
 131     float h =  pathlib_movecost_diag * h_diag;
 132     h += pathlib_movecost * (h_str - 2 * h_diag);
 133
 134     return h;
 135 }