qcsrc/server/pathlib/costs.qc

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