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