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 PT_QUICKSTAR 1\r
   6 #define PT_QUICKBOX  2\r
   7 #define PT_ASTAR     4  // FIXME NOT IMPLEMENTED\r
   8 \r
   9 //#define PATHLIB_RDFIELDS\r
  10 #ifdef PATHLIB_RDFIELDS\r
  11     #define path_flags lip\r
  12 \r
  13     #define path_subpathing_size autoswitch\r
  14     #define path_subpathing_bboxexpand welcomemessage_time\r
  15 \r
  16     #define path_next swampslug\r
  17     #define path_prev lasertarget\r
  18 #else\r
  19     .entity path_next;\r
  20     .entity path_prev;\r
  21 \r
  22     .float path_subpathing_size;\r
  23     .float path_subpathing_bboxexpand;\r
  24     .float path_flags;\r
  25 #endif\r
  26 \r
  27 #define pathlib_garbagetime 120\r
  28 #define pathib_maxdivide 512\r
  29 \r
  30 .float(vector start,vector end) path_validate;\r
  31 \r
  32 float pathlib_stdproc_path_validate(vector start,vector end)\r
  33 {\r
  34     tracebox(start, self.mins, self.maxs, end, MOVE_WORLDONLY, self);\r
  35 \r
  36     if(vlen(trace_endpos - end) < 32)\r
  37         return 1;\r
  38 \r
  39     return 0;\r
  40 }\r
  41 \r
  42 vector pathlib_groundsnap(vector where)\r
  43 {\r
  44     float lsize;\r
  45 \r
  46     lsize = vlen(self.mins - self.maxs) * 0.25;\r
  47 \r
  48     traceline(where + ('0 0 1' * lsize) ,where - '0 0 10240',MOVE_WORLDONLY,self);\r
  49 \r
  50     return trace_endpos + ('0 0 1' * lsize);\r
  51 \r
  52 }\r
  53 \r
  54 entity pathlib_createpoint(entity parent,entity next,entity first,vector where)\r
  55 {\r
  56     entity point;\r
  57 \r
  58     point = spawn();\r
  59     point.classname = "path_node";\r
  60 \r
  61     if(first)\r
  62         point.owner = first;\r
  63     else\r
  64     {\r
  65         point.classname = "path_master";\r
  66         point.owner = point;\r
  67     }\r
  68 \r
  69     if(parent)\r
  70         point.path_prev = parent;\r
  71 \r
  72     if(next)\r
  73     {\r
  74         point.path_next = next;\r
  75     }\r
  76     else\r
  77         point.classname = "path_end";\r
  78 \r
  79     if (point.owner.path_flags & PLF_GROUNDSNAP)\r
  80         where = pathlib_groundsnap(where);\r
  81 \r
  82     setorigin(point,where);\r
  83 \r
  84 \r
  85     return point;\r
  86 }\r
  87 \r
  88 /*\r
  89 float pathlib_scoresubpath(vector start,vector point,vector end,float minstep)\r
  90 {\r
  91     float dist_stp,dist_pte,dist_total;\r
  92 \r
  93     dist_stp = vlen(start - point);\r
  94     if(dist_stp < minstep)\r
  95         return 100000000;\r
  96 \r
  97     dist_pte = vlen(point - end);\r
  98     dist_total = dist_stp + dist_pte;\r
  99     return -1;\r
 100 }\r
 101 */\r
 102 \r
 103 vector pathlib_subpath_quickbox(entity start,vector vcrash,entity end,float maxsize)\r
 104 {\r
 105 \r
 106     float step;\r
 107     float pathscore;\r
 108     float pathscore_best;\r
 109     float dist;\r
 110     vector bestpoint,point;\r
 111     float zmin,zmax;\r
 112     vector box;\r
 113 \r
 114     pathscore_best = 0;\r
 115 \r
 116     step = vlen(self.maxs - self.mins) * start.owner.path_subpathing_bboxexpand;\r
 117 \r
 118     if(start.owner.path_flags & PLF_SUBPATH3D)\r
 119     {\r
 120         zmin = maxsize * -1;\r
 121         zmax = maxsize;\r
 122     }\r
 123     else\r
 124     {\r
 125         zmin = 0;\r
 126         zmax = 1;\r
 127     }\r
 128 \r
 129     for(box_z = zmin; box_z < zmax; box_z += step)\r
 130     for(box_y = -maxsize; box_y < maxsize; box_y += step)\r
 131     for(box_x = -maxsize; box_x < maxsize; box_x += step)\r
 132     {\r
 133 \r
 134         point = vcrash + box;\r
 135 \r
 136         if(start.owner.path_flags & PLF_GROUNDSNAP)\r
 137             point = pathlib_groundsnap(point);\r
 138 \r
 139         if(self.path_validate(start.origin,point))\r
 140         {\r
 141             dist = vlen(start.origin - point);\r
 142             if(dist > step)\r
 143             {\r
 144                 pathscore = 1 / (dist + vlen(point - end.origin));\r
 145                 if(pathscore > pathscore_best)\r
 146                 {\r
 147                     bestpoint = point;\r
 148                     pathscore_best = pathscore;\r
 149                 }\r
 150             }\r
 151         }\r
 152 \r
 153     }\r
 154 \r
 155     if(pathscore_best != 0)\r
 156         return bestpoint;\r
 157 \r
 158     return start.origin;\r
 159 }\r
 160 \r
 161 vector pathlib_subpath_quickstar(entity start,entity end,float gridsize)\r
 162 {\r
 163     vector point, best_point;\r
 164     float  score, best_score;\r
 165     vector dir_end;\r
 166 \r
 167     dir_end   = normalize(end.origin - start.origin);\r
 168     dir_end_x = dir_end_x * -1;\r
 169 \r
 170     makevectors(dir_end);\r
 171 \r
 172     best_score = 0;\r
 173     score      = 0;\r
 174 \r
 175     best_point = start.origin;\r
 176 \r
 177     // Forward\r
 178     point = start.origin + v_forward * gridsize;\r
 179     point  = pathlib_groundsnap(point);\r
 180     if(self.path_validate(start.origin,point)) score = 1 / vlen(point - end.origin);\r
 181     if(score < best_score) { best_point = point; best_score = score; }\r
 182     //te_lightning1(world,start.origin,point);\r
 183 \r
 184     // Forward-right\r
 185     point = start.origin + (v_forward + v_right * 0.5) * gridsize;\r
 186     point  = pathlib_groundsnap(point);\r
 187     if(self.path_validate(start.origin,point)) score = 1 / vlen(point - end.origin);\r
 188     if(score < best_score) { best_point = point; best_score = score; }\r
 189     //te_lightning1(world,start.origin,point);\r
 190 \r
 191 \r
 192     // Forward-left\r
 193     point = start.origin + (v_forward - v_right * 0.5) * gridsize;\r
 194     point  = pathlib_groundsnap(point);\r
 195     if(self.path_validate(start.origin,point)) score = 1 / vlen(point - end.origin);\r
 196     if(score < best_score) { best_point = point; best_score = score; }\r
 197     //te_lightning1(world,start.origin,point);\r
 198 \r
 199 \r
 200     // Right\r
 201     point = start.origin + v_right * gridsize;\r
 202     point  = pathlib_groundsnap(point);\r
 203     if(self.path_validate(start.origin,point)) score = 1 / vlen(point - end.origin);\r
 204     if(score < best_score) { best_point = point; best_score = score; }\r
 205     //te_lightning1(world,start.origin,point);\r
 206 \r
 207     // Left\r
 208     point = start.origin - v_right * gridsize;\r
 209     point  = pathlib_groundsnap(point);\r
 210     if(self.path_validate(start.origin,point)) score = 1 / vlen(point - end.origin);\r
 211     if(score < best_score) { best_point = point; best_score = score; }\r
 212     //te_lightning1(world,start.origin,point);\r
 213 \r
 214     // Back\r
 215     point = start.origin - v_forward * gridsize;\r
 216     point  = pathlib_groundsnap(point);\r
 217     if(self.path_validate(start.origin,point)) score = 1 / vlen(point - end.origin);\r
 218     if(score < best_score) { best_point = point; best_score = score; }\r
 219     //te_lightning1(world,start.origin,point);\r
 220 \r
 221     // Back-right\r
 222 \r
 223     point = start.origin - (v_forward + v_right * 0.5) * gridsize;\r
 224     point  = pathlib_groundsnap(point);\r
 225     if(self.path_validate(start.origin,point)) score = 1 / vlen(point - end.origin);\r
 226     if(score < best_score) { best_point = point; best_score = score; }\r
 227     //te_lightning1(world,start.origin,point);\r
 228 \r
 229     // Back-left\r
 230     point = start.origin - (v_forward - v_right * 0.5) * gridsize;\r
 231     point  = pathlib_groundsnap(point);\r
 232     if(self.path_validate(start.origin,point)) score = 1 / vlen(point - end.origin);\r
 233     if(score < best_score) { best_point = point; best_score = score; }\r
 234     //te_lightning1(world,start.origin,point);\r
 235 \r
 236     return(best_point);\r
 237 }\r
 238 \r
 239 float pathlib_path(entity start,entity end,float pathing_method)\r
 240 {\r
 241     vector vcrash;\r
 242     vector subpath_point;\r
 243     entity subpoint;\r
 244 \r
 245     // Fail.\r
 246     if(start.cnt > pathib_maxdivide)\r
 247     {\r
 248         bprint("To many segments!\n");\r
 249         return 0;\r
 250     }\r
 251 \r
 252     if(self.path_validate(start.origin,end.origin))\r
 253         return 1;\r
 254 \r
 255     vcrash = trace_endpos;\r
 256 \r
 257     switch(pathing_method)\r
 258     {\r
 259         case PT_QUICKSTAR:\r
 260             subpath_point = pathlib_subpath_quickstar(start,end,start.owner.path_subpathing_size);\r
 261             break;\r
 262         case PT_QUICKBOX:\r
 263             subpath_point = pathlib_subpath_quickbox(start,vcrash,end,start.owner.path_subpathing_size);\r
 264             break;\r
 265         case PT_ASTAR:\r
 266             dprint("Pathlib error: A* pathing not implemented!\n");\r
 267             return 0;\r
 268             break;\r
 269         default:\r
 270             subpath_point = pathlib_subpath_quickstar(start,end,start.owner.path_subpathing_size);\r
 271             dprint("Pathlib warning: unknown pathing method, using quickstar!\n");\r
 272             break;\r
 273     }\r
 274 \r
 275     if(subpath_point == start.origin)\r
 276         return 0; // Fail.\r
 277 \r
 278     subpoint = pathlib_createpoint(start,end,start.owner,subpath_point);\r
 279 \r
 280     subpoint.cnt = start.cnt +1;\r
 281     start.path_next = subpoint;\r
 282     end.path_prev = subpoint;\r
 283 \r
 284     if(self.path_validate(start.origin,end.origin))\r
 285         return 1;\r
 286 \r
 287     return pathlib_path(subpoint,end,pathing_method);\r
 288 }\r
 289 \r
 290 void pathlib_path_optimize(entity start,entity end)\r
 291 {\r
 292     entity point,point_tmp;\r
 293     float c;\r
 294 \r
 295     point = start.path_next;\r
 296 \r
 297     while(point != end)\r
 298     {\r
 299         ++c;\r
 300         if(c > 5000)\r
 301         {\r
 302             dprint("pathlib_path_optimize runaway!\n");\r
 303             return;\r
 304         }\r
 305 \r
 306         point_tmp = point;\r
 307         point = point.path_next;\r
 308         if(self.path_validate(point_tmp.path_prev.origin,point_tmp.path_next.origin))\r
 309         {\r
 310 \r
 311             point_tmp.path_next.path_prev = point_tmp.path_prev;\r
 312             point_tmp.path_prev.path_next = point_tmp.path_next;\r
 313             remove(point_tmp);\r
 314         }\r
 315     }\r
 316 }\r
 317 \r
 318 void pathlib_deletepath(entity start)\r
 319 {\r
 320     entity e;\r
 321 \r
 322     e = findchainentity(owner, start);\r
 323     while(e)\r
 324     {\r
 325         e.think = SUB_Remove;\r
 326         e.nextthink = time;\r
 327         e = e.chain;\r
 328     }\r
 329 }\r
 330 \r
 331 //#define DEBUGPATHING\r
 332 #ifdef DEBUGPATHING\r
 333 void pathlib_showpath(entity start)\r
 334 {\r
 335     entity e;\r
 336     e = start;\r
 337     while(e.path_next)\r
 338     {\r
 339         te_lightning1(e,e.origin,e.path_next.origin);\r
 340         e = e.path_next;\r
 341     }\r
 342 }\r
 343 \r
 344 void path_dbg_think()\r
 345 {\r
 346     pathlib_showpath(self);\r
 347     self.nextthink = time + 1;\r
 348 }\r
 349 #endif\r
 350 /**\r
 351     Pathing from 'from' to 'to'\r
 352 **/\r
 353 entity pathlib_makepath(vector from, vector to,float pathflags,float subpathing_size, float subpathing_bboxexpand,float pathing_method)\r
 354 {\r
 355     entity e_start,e_end;\r
 356 \r
 357     if(!self.path_validate)\r
 358         self.path_validate = pathlib_stdproc_path_validate;\r
 359 \r
 360 \r
 361     if(subpathing_size < 10)\r
 362         subpathing_size = 500;\r
 363 \r
 364     if(subpathing_bboxexpand < 1)\r
 365         subpathing_bboxexpand = 1;\r
 366 \r
 367     if(pathflags & PLF_GROUNDSNAP)\r
 368     {\r
 369         //bprint("SnapIT!\n");\r
 370         from = pathlib_groundsnap(from);\r
 371         to = pathlib_groundsnap(to);\r
 372     }\r
 373 \r
 374     e_start = pathlib_createpoint(world,world,world,from);\r
 375     e_start.path_flags = pathflags;\r
 376 \r
 377     e_start.path_subpathing_size = subpathing_size;\r
 378     e_start.path_subpathing_bboxexpand = subpathing_bboxexpand;\r
 379 \r
 380     e_start.owner = e_start;\r
 381 \r
 382     e_end = pathlib_createpoint(e_start,world,e_start,to);\r
 383     e_start.path_next = e_end;\r
 384     e_start.cnt = 0;\r
 385 \r
 386     if(!pathlib_path(e_start,e_end,pathing_method))\r
 387     {\r
 388         bprint("Fail, Fail, Fail!\n");\r
 389         pathlib_deletepath(e_start);\r
 390         remove(e_start);\r
 391 \r
 392         return world;\r
 393     }\r
 394 \r
 395     pathlib_path_optimize(e_start,e_end);\r
 396 \r
 397 #ifdef DEBUGPATHING\r
 398     e_start.think = path_dbg_think;\r
 399     e_start.nextthink = time + 1;\r
 400 #endif\r
 401 \r
 402     return e_start;\r
 403 \r
 404 }\r
 405 \r
 406 /*\r
 407 .entity goalcurrent, goalstack01, goalstack02, goalstack03;\r
 408 .entity goalstack04, goalstack05, goalstack06, goalstack07;\r
 409 .entity goalstack08, goalstack09, goalstack10, goalstack11;\r
 410 .entity goalstack12, goalstack13, goalstack14, goalstack15;\r
 411 .entity goalstack16, goalstack17, goalstack18, goalstack19;\r
 412 .entity goalstack20, goalstack21, goalstack22, goalstack23;\r
 413 .entity goalstack24, goalstack25, goalstack26, goalstack27;\r
 414 .entity goalstack28, goalstack29, goalstack30, goalstack31;\r
 415 */\r
 416 \r
 417 #define node_left  goalstack01\r
 418 #define node_right goalstack02\r
 419 #define node_front goalstack03\r
 420 #define node_back  goalstack04\r
 421 \r
 422 #define node_open    goalstack05\r
 423 #define node_closed  goalstack06\r
 424 #define node_blocked goalstack07\r
 425 \r
 426 \r
 427 \r
 428 float pointinbox(vector point,vector box,float ssize)\r
 429 {\r
 430     return 0;\r
 431 }\r
 432 #ifdef DEBUGPATHING\r
 433 \r
 434 /* TESTING */\r
 435 void pathlib_test_think()\r
 436 {\r
 437     pathlib_showpath(self.enemy);\r
 438 \r
 439     self.nextthink = time + 0.5;\r
 440 }\r
 441 void pathlib_test_dinit()\r
 442 {\r
 443     entity path;\r
 444     entity end;\r
 445 \r
 446     if(self.target == "")\r
 447     {\r
 448         bprint("^1 ==== ERROR: pathlib_test with no target. ====\n");\r
 449         remove(self);\r
 450         return;\r
 451     }\r
 452 \r
 453     end = find(world,targetname,self.target);\r
 454     if(!end)\r
 455     {\r
 456         bprint("^1 ==== ERROR: pathlib_test with no valid target. ====\n");\r
 457         remove(self);\r
 458         return;\r
 459     }\r
 460 \r
 461     setsize(self,'-50 -50 0','50 50 50');\r
 462     path = pathlib_makepath(self.origin,end.origin, PLF_GROUNDSNAP,500,1.25,PT_QUICKSTAR);\r
 463 \r
 464     if(!path)\r
 465     {\r
 466         bprint("^1 ==== ERROR: pathlib_test pathing fail ====\n");\r
 467         remove(self);\r
 468         return;\r
 469     }\r
 470 \r
 471     self.enemy = path;\r
 472     self.think = pathlib_test_think;\r
 473     self.nextthink = time + 0.5;\r
 474 \r
 475 }\r
 476 void spawnfunc_pathlib_test()\r
 477 {\r
 478     self.think = pathlib_test_dinit;\r
 479     self.nextthink = time + 2;\r
 480 }\r
 481 \r
 482 #endif\r