data/qcsrc/server/pathlib.qc

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