data/qcsrc/server/pathlib/costs.qc

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