qcsrc/server/pathlib/expandnode.qc

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