qcsrc/server/pathlib/expandnode.qc

   1 #include "pathlib.qh"
   2 #include "utility.qh"
   3
   4 vector plib_points2[8];
   5 vector plib_points[8];
   6 float  plib_fvals[8];
   7
   8 float pathlib_expandnode_starf(entity node, vector start, vector goal)
   9 {
  10     vector where,f,r,t;
  11     float fc,c;
  12     entity nap;
  13
  14     where = node.origin;
  15
  16     f = PLIB_FORWARD * pathlib_gridsize;
  17     r = PLIB_RIGHT   * pathlib_gridsize;
  18
  19     // Forward
  20     plib_points[0] = where + f;
  21
  22     // Back
  23     plib_points[1] = where - f;
  24
  25     // Right
  26     plib_points[2] = where + r;
  27
  28     // Left
  29     plib_points[3] = where - r;
  30
  31     // Forward-right
  32     plib_points[4] = where + f + r;
  33
  34     // Forward-left
  35     plib_points[5] = where + f - r;
  36
  37     // Back-right
  38     plib_points[6] = where - f + r;
  39
  40     // Back-left
  41     plib_points[7] = where - f - r;
  42
  43     for(int i=0;i < 8; ++i)
  44     {
  45         t = plib_points[i];
  46         fc  = pathlib_heuristic(t,goal) + pathlib_cost(node, t, pathlib_gridsize);
  47         plib_fvals[i] = fc;
  48
  49     }
  50
  51     fc = plib_fvals[0];
  52     plib_points2[0] = plib_points[0];
  53     vector bp;
  54     bp = plib_points[0];
  55     int fc2 = 0;
  56     for(int i = 0; i < 8; ++i)
  57     {
  58         c = 0;
  59         nap = pathlib_nodeatpoint(plib_points[i]);
  60         if(nap)
  61             if(nap.owner == openlist)
  62                 c = 1;
  63         else
  64             c = 1;
  65
  66         if(c)
  67         if(plib_fvals[i] < fc)
  68         {
  69             bp = plib_points[i];
  70             fc = plib_fvals[i];
  71             plib_points2[fc2] = plib_points[i];
  72             ++fc2;
  73         }
  74
  75         /*
  76         nap = pathlib_nodeatpoint(plib_points[i]);
  77         if(nap)
  78         if not nap.owner == closedlist)
  79         {
  80         }
  81         */
  82     }
  83
  84     pathlib_makenode(node, start, bp, goal, pathlib_gridsize);
  85
  86     for(int i = 0; i < 3; ++i)
  87     {
  88         pathlib_makenode(node, start, plib_points2[i], goal, pathlib_gridsize);
  89     }
  90
  91     return pathlib_open_cnt;
  92 }
  93
  94 float pathlib_expandnode_star(entity node, vector start, vector goal)
  95 {
  96     vector point, where, f, r;
  97
  98     where = node.origin;
  99
 100     f = PLIB_FORWARD * pathlib_gridsize;
 101     r = PLIB_RIGHT   * pathlib_gridsize;
 102
 103     if (node.pathlib_node_edgeflags == pathlib_node_edgeflag_unknown)
 104         node.pathlib_node_edgeflags = tile_check_plus2(node.origin);
 105
 106     if(node.pathlib_node_edgeflags == pathlib_node_edgeflag_none)
 107     {
 108         LOG_TRACE("Node at ", vtos(node.origin), " not expanable");
 109         return pathlib_open_cnt;
 110     }
 111
 112     // Forward
 113     if (node.pathlib_node_edgeflags & pathlib_node_edgeflag_forward)
 114     {
 115         point = where + f;
 116         pathlib_makenode(node, start, point, goal, pathlib_movecost);
 117     }
 118
 119     // Back
 120     if (node.pathlib_node_edgeflags & pathlib_node_edgeflag_back)
 121     {
 122         point = where - f;
 123         pathlib_makenode(node, start, point, goal, pathlib_movecost);
 124     }
 125
 126     // Right
 127         if (node.pathlib_node_edgeflags & pathlib_node_edgeflag_right)
 128     {
 129         point = where + r;
 130         pathlib_makenode(node, start, point, goal, pathlib_movecost);
 131     }
 132
 133     // Left
 134     if (node.pathlib_node_edgeflags & pathlib_node_edgeflag_left)
 135     {
 136         point = where - r;
 137         pathlib_makenode(node, start, point, goal, pathlib_movecost);
 138
 139     }
 140
 141     // Forward-right
 142     if (node.pathlib_node_edgeflags & pathlib_node_edgeflag_forwardright)
 143     {
 144         point = where + f + r;
 145         pathlib_makenode(node, start, point, goal, pathlib_movecost_diag);
 146     }
 147
 148     // Forward-left
 149     if (node.pathlib_node_edgeflags & pathlib_node_edgeflag_forwardleft)
 150     {
 151         point = where + f - r;
 152         pathlib_makenode(node, start, point, goal, pathlib_movecost_diag);
 153
 154     }
 155
 156     // Back-right
 157     if (node.pathlib_node_edgeflags & pathlib_node_edgeflag_backright)
 158     {
 159         point = where - f + r;
 160         pathlib_makenode(node, start, point, goal, pathlib_movecost_diag);
 161     }
 162
 163     // Back-left
 164     if (node.pathlib_node_edgeflags & pathlib_node_edgeflag_backleft)
 165     {
 166         point = where - f - r;
 167         pathlib_makenode(node, start, point, goal, pathlib_movecost_diag);
 168     }
 169
 170     return pathlib_open_cnt;
 171 }
 172
 173 float pathlib_expandnode_octagon(entity node, vector start, vector goal)
 174 {
 175     vector point,where,f,r;
 176
 177     where = node.origin;
 178
 179     f = PLIB_FORWARD * pathlib_gridsize;
 180     r = PLIB_RIGHT   * pathlib_gridsize;
 181
 182     // Forward
 183     point = where + f;
 184     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 185
 186     // Back
 187     point = where - f;
 188     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 189
 190     // Right
 191     point = where + r;
 192     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 193
 194     // Left
 195     point = where - r;
 196     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 197
 198     f = PLIB_FORWARD * pathlib_gridsize * 0.5;
 199     r = PLIB_RIGHT   * pathlib_gridsize * 0.5;
 200
 201     // Forward-right
 202     point = where + f + r;
 203     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 204
 205
 206     // Forward-left
 207     point = where + f - r;
 208     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 209
 210
 211     // Back-right
 212     point = where - f + r;
 213     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 214
 215     // Back-left
 216     point = where - f - r;
 217     pathlib_makenode(node, start, point, goal, pathlib_movecost);
 218
 219     return pathlib_open_cnt;
 220 }
 221
 222 float pathlib_expandnode_box(entity node, vector start, vector goal)
 223 {
 224     vector v;
 225
 226     for(v.z = node.origin.z - pathlib_gridsize; v.z <= node.origin.z + pathlib_gridsize; v.z += pathlib_gridsize)
 227     for(v.y = node.origin.y - pathlib_gridsize; v.y <= node.origin.y + pathlib_gridsize; v.y += pathlib_gridsize)
 228     for(v.x = node.origin.x - pathlib_gridsize; v.x <= node.origin.x + pathlib_gridsize; v.x += pathlib_gridsize)
 229     {
 230         //if(vlen(v - node.origin))
 231             pathlib_makenode(node,start,v,goal,pathlib_movecost);
 232     }
 233
 234     return pathlib_open_cnt;
 235 }