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