data/qcsrc/server/pathlib.qc

   1 #define PLF_GROUNDSNAP 1\r
   2 #define PLF_NOOPTIMIZE 2\r
   3 #define PLF_SUBPATH3D  4\r
   4 \r
   5 //#define PATHLIB_RDFIELDS\r
   6 #ifdef PATHLIB_RDFIELDS\r
   7     #define path_flags lip\r
   8 \r
   9     #define path_subpathing_size autoswitch\r
  10     #define path_subpathing_bboxexpand welcomemessage_time\r
  11 \r
  12     #define path_next swampslug\r
  13     #define path_prev lasertarget\r
  14 #else\r
  15     .entity path_next;\r
  16     .entity path_prev;\r
  17 \r
  18     .float path_subpathing_size;\r
  19     .float path_subpathing_bboxexpand;\r
  20     .float path_flags;\r
  21 #endif\r
  22 \r
  23 #define pathlib_garbagetime 120\r
  24 #define pathib_maxdivide 256\r
  25 \r
  26 .float(vector start,vector end) path_validate;\r
  27 \r
  28 float pathlib_stdproc_path_validate(vector start,vector end)\r
  29 {\r
  30     tracebox(start, self.mins, self.maxs, end, MOVE_NORMAL, self);\r
  31 \r
  32     if(vlen(trace_endpos - end) < 32)\r
  33         return 1;\r
  34 \r
  35     return 0;\r
  36 }\r
  37 \r
  38 vector pathlib_groundsnap(vector where,entity path)\r
  39 {\r
  40     float lsize;\r
  41 \r
  42     lsize = vlen(self.mins - self.maxs) * 0.25;\r
  43 \r
  44     traceline(where + ('0 0 1' * lsize) ,where - '0 0 10000',MOVE_NORMAL,self);\r
  45 \r
  46     return trace_endpos + ('0 0 1' * lsize);\r
  47 \r
  48 }\r
  49 \r
  50 entity pathlib_createpoint(entity parent,entity next,entity first,vector where)\r
  51 {\r
  52     entity point;\r
  53 \r
  54     point = spawn();\r
  55     point.classname = "path_node";\r
  56 \r
  57     if(first)\r
  58         point.owner = first;\r
  59     else\r
  60     {\r
  61         point.classname = "path_master";\r
  62         point.owner = point;\r
  63     }\r
  64 \r
  65     if(parent)\r
  66         point.path_prev = parent;\r
  67 \r
  68     if(next)\r
  69     {\r
  70         point.path_next = next;\r
  71         //point.path_nodelength = vlen(point.origin - next.origin)\r
  72     }\r
  73     else\r
  74         point.classname = "path_end";\r
  75 \r
  76     if(point.owner.path_flags & PLF_GROUNDSNAP)\r
  77         where = pathlib_groundsnap(where,parent);\r
  78 \r
  79 \r
  80     setorigin(point,where);\r
  81 \r
  82 \r
  83     return point;\r
  84 }\r
  85 \r
  86 vector pathlib_findsubpath(entity start,vector vcrash,entity end,float maxsize)\r
  87 {\r
  88     float x,y,z;\r
  89     float step;\r
  90     float dist;\r
  91     float pathlength;\r
  92     float pathlength_best;\r
  93     vector bestpoint;\r
  94     vector point;\r
  95     float zmin,zmax;\r
  96 \r
  97     pathlength_best = 1000000;\r
  98 \r
  99     step = vlen(self.maxs - self.mins) * start.owner.path_subpathing_bboxexpand;\r
 100 \r
 101     if(start.owner.path_flags & PLF_SUBPATH3D)\r
 102     {\r
 103         zmin = maxsize * -1;\r
 104         zmax = maxsize;\r
 105     }\r
 106     else\r
 107     {\r
 108         zmin = 0;\r
 109         zmax = 1;\r
 110     }\r
 111 \r
 112     for(z = zmin; z < zmax; z += step)\r
 113     for(y = -maxsize; y < maxsize; y += step)\r
 114     for(x = -maxsize; x < maxsize; x += step)\r
 115     {\r
 116 \r
 117         point_z = vcrash_z + z;\r
 118         point_x = vcrash_x + x;\r
 119         point_y = vcrash_y + y;\r
 120 \r
 121 \r
 122         if(start.owner.path_flags & PLF_GROUNDSNAP)\r
 123             point = pathlib_groundsnap(point,start);\r
 124 \r
 125         if(self.path_validate(start.origin,point))\r
 126         {\r
 127             dist = vlen(start.origin - point);\r
 128             if(dist > step)\r
 129             {\r
 130                 pathlength = dist + vlen(point - end.origin);\r
 131                 if(pathlength < pathlength_best)\r
 132                 {\r
 133                     bestpoint = point;\r
 134                     pathlength_best = pathlength;\r
 135                 }\r
 136             }\r
 137         }\r
 138 \r
 139     }\r
 140 \r
 141     if(pathlength_best != 1000000)\r
 142         return bestpoint;\r
 143 \r
 144     return vcrash;\r
 145 }\r
 146 \r
 147 float pathlib_path(entity start,entity end)\r
 148 {\r
 149     vector vcrash;\r
 150     vector subpath_point;\r
 151     entity subpoint;\r
 152 \r
 153     // Fail.\r
 154     if(start.cnt > pathib_maxdivide)\r
 155         return 0;\r
 156 \r
 157     if(self.path_validate(start.origin,end.origin))\r
 158         return 1;\r
 159 \r
 160     vcrash = trace_endpos;\r
 161 \r
 162     subpath_point = pathlib_findsubpath(start,vcrash,end,start.owner.path_subpathing_size);\r
 163 \r
 164     if(subpath_point == vcrash)\r
 165         return 0; // Fail.\r
 166 \r
 167     subpoint = pathlib_createpoint(start,end,start.owner,subpath_point);\r
 168 \r
 169     subpoint.cnt = start.cnt +1;\r
 170     start.path_next = subpoint;\r
 171     end.path_prev = subpoint;\r
 172 \r
 173     if(self.path_validate(start.origin,end.origin))\r
 174         return 1;\r
 175 \r
 176     return pathlib_path(subpoint,end);\r
 177 }\r
 178 \r
 179 void pathlib_path_optimize(entity start,entity end)\r
 180 {\r
 181     entity point,point_tmp;\r
 182     float c;\r
 183 \r
 184     point = start.path_next;\r
 185 \r
 186     while(point != end)\r
 187     {\r
 188         ++c;\r
 189         if(c > 5000)\r
 190         {\r
 191             dprint("pathlib_path_optimize runaway!\n");\r
 192             return;\r
 193         }\r
 194 \r
 195         point_tmp = point;\r
 196         point = point.path_next;\r
 197         if(self.path_validate(point_tmp.path_prev.origin,point_tmp.path_next.origin))\r
 198         {\r
 199 \r
 200             point_tmp.path_next.path_prev = point_tmp.path_prev;\r
 201             point_tmp.path_prev.path_next = point_tmp.path_next;\r
 202             remove(point_tmp);\r
 203         }\r
 204     }\r
 205 }\r
 206 \r
 207 void pathlib_deletepath(entity start)\r
 208 {\r
 209     entity e;\r
 210 \r
 211     e = findentity(start, owner, start);\r
 212     while(e)\r
 213     {\r
 214         remove(e);\r
 215         e = findentity(start, owner, start);\r
 216     }\r
 217 }\r
 218 \r
 219 void pathlib_showpath(entity start)\r
 220 {\r
 221     entity e;\r
 222     e = start;\r
 223     while(e.path_next)\r
 224     {\r
 225         te_lightning1(e,e.origin,e.path_next.origin);\r
 226         e = e.path_next;\r
 227     }\r
 228 }\r
 229 \r
 230 /**\r
 231     Run a A*-like pathing from 'from' to 'to'\r
 232 **/\r
 233 entity pathlib_makepath(vector from, vector to,float pathflags,float subpathing_size, float subpathing_bboxexpand)\r
 234 {\r
 235     entity e_start,e_end;\r
 236 \r
 237     if(!self.path_validate)\r
 238         self.path_validate = pathlib_stdproc_path_validate;\r
 239 \r
 240 \r
 241     if(subpathing_size < 10)\r
 242         subpathing_size = 500;\r
 243 \r
 244     if(subpathing_bboxexpand < 1)\r
 245         subpathing_bboxexpand = 1;\r
 246 \r
 247     e_start = pathlib_createpoint(world,world,world,from);\r
 248     e_start.path_flags = pathflags;\r
 249 \r
 250     e_start.path_subpathing_size = subpathing_size;\r
 251     e_start.path_subpathing_bboxexpand = subpathing_bboxexpand;\r
 252 \r
 253     e_start.owner = e_start;\r
 254 \r
 255     e_end = pathlib_createpoint(e_start,world,e_start,to);\r
 256     e_start.path_next = e_end;\r
 257     e_start.cnt = 0;\r
 258 \r
 259     if(!pathlib_path(e_start,e_end))\r
 260     {\r
 261         pathlib_deletepath(e_start);\r
 262         remove(e_start);\r
 263         return world;\r
 264     }\r
 265 \r
 266     pathlib_path_optimize(e_start,e_end);\r
 267 \r
 268     return e_start;\r
 269 \r
 270 }\r
 271 \r
 272 \r
 273 /* TESTING */\r
 274 void pathlib_test_think()\r
 275 {\r
 276     pathlib_showpath(self.enemy);\r
 277 \r
 278     self.nextthink = time + 0.5;\r
 279 }\r
 280 void pathlib_test_dinit()\r
 281 {\r
 282     entity path;\r
 283     entity end;\r
 284 \r
 285     if(self.target == "")\r
 286     {\r
 287         bprint("^1 ==== ERROR: pathlib_test with no target. ====\n");\r
 288         remove(self);\r
 289         return;\r
 290     }\r
 291 \r
 292     end = find(world,targetname,self.target);\r
 293     if(!end)\r
 294     {\r
 295         bprint("^1 ==== ERROR: pathlib_test with no valid target. ====\n");\r
 296         remove(self);\r
 297         return;\r
 298     }\r
 299 \r
 300     setsize(self,'-50 -50 0','50 50 50');\r
 301     path = pathlib_makepath(self.origin,end.origin, PLF_GROUNDSNAP,500,1.25);\r
 302 \r
 303     if(!path)\r
 304     {\r
 305         bprint("^1 ==== ERROR: pathlib_test pathing fail ====\n");\r
 306         remove(self);\r
 307         return;\r
 308     }\r
 309 \r
 310     self.enemy = path;\r
 311     self.think = pathlib_test_think;\r
 312     self.nextthink = time + 0.5;\r
 313 \r
 314 }\r
 315 void spawnfunc_pathlib_test()\r
 316 {\r
 317     self.think = pathlib_test_dinit;\r
 318     self.nextthink = time + 2;\r
 319 }\r