qcsrc/server/pathlib/expandnode.qc

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