1 #define PFL_GROUNDSNAP 1
\r
2 #define PFL_NOOPTIMIZE 2
\r
3 #define PFL_SUBPATH3D 4
\r
5 #define PT_QUICKSTAR 1
\r
6 #define PT_QUICKBOX 2
\r
7 #define PT_ASTAR 4 // FIXME NOT IMPLEMENTED
\r
9 //#define PATHLIB_RDFIELDS
\r
10 #ifdef PATHLIB_RDFIELDS
\r
11 #define path_flags lip
\r
13 #define path_subpathing_size autoswitch
\r
14 #define path_subpathing_bboxexpand welcomemessage_time
\r
16 #define path_next swampslug
\r
17 #define path_prev lasertarget
\r
22 .float path_subpathing_size;
\r
23 .float path_subpathing_bboxexpand;
\r
27 #define pathlib_garbagetime 120
\r
28 #define pathib_maxdivide 512
\r
30 .float(vector start,vector end) path_validate;
\r
32 float pathlib_stdproc_path_validate(vector start,vector end)
\r
34 tracebox(start, self.mins, self.maxs, end, MOVE_WORLDONLY, self);
\r
36 if(vlen(trace_endpos - end) < 32)
\r
42 vector pathlib_groundsnap(vector where)
\r
46 lsize = vlen(self.mins - self.maxs) * 0.25;
\r
48 traceline(where + ('0 0 1' * lsize) ,where - '0 0 10240',MOVE_WORLDONLY,self);
\r
50 return trace_endpos + ('0 0 1' * lsize);
\r
54 entity pathlib_createpoint(entity parent,entity next,entity first,vector where)
\r
59 point.classname = "path_node";
\r
62 point.owner = first;
\r
65 point.classname = "path_master";
\r
66 point.owner = point;
\r
70 point.path_prev = parent;
\r
74 point.path_next = next;
\r
77 point.classname = "path_end";
\r
79 if (point.owner.path_flags & PFL_GROUNDSNAP)
\r
80 where = pathlib_groundsnap(where);
\r
82 setorigin(point,where);
\r
89 float pathlib_scoresubpath(vector start,vector point,vector end,float minstep)
\r
91 float dist_stp,dist_pte,dist_total;
\r
93 dist_stp = vlen(start - point);
\r
94 if(dist_stp < minstep)
\r
97 dist_pte = vlen(point - end);
\r
98 dist_total = dist_stp + dist_pte;
\r
103 vector pathlib_subpath_quickbox(entity start,vector vcrash,entity end,float maxsize)
\r
108 float pathscore_best;
\r
110 vector bestpoint,point;
\r
114 pathscore_best = 0;
\r
116 step = vlen(self.maxs - self.mins) * start.owner.path_subpathing_bboxexpand;
\r
118 if(start.owner.path_flags & PFL_SUBPATH3D)
\r
120 zmin = maxsize * -1;
\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
134 point = vcrash + box;
\r
136 if(start.owner.path_flags & PFL_GROUNDSNAP)
\r
137 point = pathlib_groundsnap(point);
\r
139 if(self.path_validate(start.origin,point))
\r
141 dist = vlen(start.origin - point);
\r
144 pathscore = 1 / (dist + vlen(point - end.origin));
\r
145 if(pathscore > pathscore_best)
\r
148 pathscore_best = pathscore;
\r
155 if(pathscore_best != 0)
\r
158 return start.origin;
\r
161 vector pathlib_subpath_quickstar(entity start,entity end,float gridsize)
\r
163 vector point, best_point;
\r
164 float score, best_score;
\r
167 dir_end = normalize(end.origin - start.origin);
\r
168 dir_end_x = dir_end_x * -1;
\r
170 makevectors(dir_end);
\r
175 best_point = start.origin;
\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
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
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
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
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
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
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
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
236 return(best_point);
\r
239 float pathlib_path(entity start,entity end,float pathing_method)
\r
242 vector subpath_point;
\r
246 if(start.cnt > pathib_maxdivide)
\r
248 bprint("To many segments!\n");
\r
252 if(self.path_validate(start.origin,end.origin))
\r
255 vcrash = trace_endpos;
\r
257 switch(pathing_method)
\r
260 subpath_point = pathlib_subpath_quickstar(start,end,start.owner.path_subpathing_size);
\r
263 subpath_point = pathlib_subpath_quickbox(start,vcrash,end,start.owner.path_subpathing_size);
\r
266 dprint("Pathlib error: A* pathing not implemented!\n");
\r
269 subpath_point = pathlib_subpath_quickstar(start,end,start.owner.path_subpathing_size);
\r
270 dprint("Pathlib warning: unknown pathing method, using quickstar!\n");
\r
274 if(subpath_point == start.origin)
\r
277 subpoint = pathlib_createpoint(start,end,start.owner,subpath_point);
\r
279 subpoint.cnt = start.cnt +1;
\r
280 start.path_next = subpoint;
\r
281 end.path_prev = subpoint;
\r
283 if(self.path_validate(start.origin,end.origin))
\r
286 return pathlib_path(subpoint,end,pathing_method);
\r
289 void pathlib_path_optimize(entity start,entity end)
\r
291 entity point,point_tmp;
\r
294 point = start.path_next;
\r
296 while(point != end)
\r
301 dprint("pathlib_path_optimize runaway!\n");
\r
306 point = point.path_next;
\r
307 if(self.path_validate(point_tmp.path_prev.origin,point_tmp.path_next.origin))
\r
310 point_tmp.path_next.path_prev = point_tmp.path_prev;
\r
311 point_tmp.path_prev.path_next = point_tmp.path_next;
\r
317 void pathlib_deletepath(entity start)
\r
321 e = findchainentity(owner, start);
\r
324 e.think = SUB_Remove;
\r
325 e.nextthink = time;
\r
330 //#define DEBUGPATHING
\r
331 #ifdef DEBUGPATHING
\r
332 void pathlib_showpath(entity start)
\r
338 te_lightning1(e,e.origin,e.path_next.origin);
\r
343 void path_dbg_think()
\r
345 pathlib_showpath(self);
\r
346 self.nextthink = time + 1;
\r
350 Pathing from 'from' to 'to'
\r
352 entity pathlib_makepath(vector from, vector to,float pathflags,float subpathing_size, float subpathing_bboxexpand,float pathing_method)
\r
354 entity e_start,e_end;
\r
356 if(!self.path_validate)
\r
357 self.path_validate = pathlib_stdproc_path_validate;
\r
360 if(subpathing_size < 10)
\r
361 subpathing_size = 500;
\r
363 if(subpathing_bboxexpand < 1)
\r
364 subpathing_bboxexpand = 1;
\r
366 if(pathflags & PFL_GROUNDSNAP)
\r
368 from = pathlib_groundsnap(from);
\r
369 to = pathlib_groundsnap(to);
\r
372 e_start = pathlib_createpoint(world,world,world,from);
\r
373 e_start.path_flags = pathflags;
\r
375 e_start.path_subpathing_size = subpathing_size;
\r
376 e_start.path_subpathing_bboxexpand = subpathing_bboxexpand;
\r
378 e_start.owner = e_start;
\r
380 e_end = pathlib_createpoint(e_start,world,e_start,to);
\r
381 e_start.path_next = e_end;
\r
384 if(!pathlib_path(e_start,e_end,pathing_method))
\r
386 bprint("Fail, Fail, Fail!\n");
\r
387 pathlib_deletepath(e_start);
\r
393 pathlib_path_optimize(e_start,e_end);
\r
395 #ifdef DEBUGPATHING
\r
396 e_start.think = path_dbg_think;
\r
397 e_start.nextthink = time + 1;
\r
405 .entity goalcurrent, goalstack01, goalstack02, goalstack03;
\r
406 .entity goalstack04, goalstack05, goalstack06, goalstack07;
\r
407 .entity goalstack08, goalstack09, goalstack10, goalstack11;
\r
408 .entity goalstack12, goalstack13, goalstack14, goalstack15;
\r
409 .entity goalstack16, goalstack17, goalstack18, goalstack19;
\r
410 .entity goalstack20, goalstack21, goalstack22, goalstack23;
\r
411 .entity goalstack24, goalstack25, goalstack26, goalstack27;
\r
412 .entity goalstack28, goalstack29, goalstack30, goalstack31;
\r
415 #define node_left goalstack01
\r
416 #define node_right goalstack02
\r
417 #define node_front goalstack03
\r
418 #define node_back goalstack04
\r
420 #define node_open goalstack05
\r
421 #define node_closed goalstack06
\r
422 #define node_blocked goalstack07
\r
426 float pointinbox(vector point,vector box,float ssize)
\r
430 #ifdef DEBUGPATHING
\r
433 void pathlib_test_think()
\r
435 pathlib_showpath(self.enemy);
\r
437 self.nextthink = time + 0.5;
\r
439 void pathlib_test_dinit()
\r
444 if(self.target == "")
\r
446 bprint("^1 ==== ERROR: pathlib_test with no target. ====\n");
\r
451 end = find(world,targetname,self.target);
\r
454 bprint("^1 ==== ERROR: pathlib_test with no valid target. ====\n");
\r
459 setsize(self,'-50 -50 0','50 50 50');
\r
460 path = pathlib_makepath(self.origin,end.origin, PFL_GROUNDSNAP,500,1.25,PT_QUICKSTAR);
\r
464 bprint("^1 ==== ERROR: pathlib_test pathing fail ====\n");
\r
470 self.think = pathlib_test_think;
\r
471 self.nextthink = time + 0.5;
\r
474 void spawnfunc_pathlib_test()
\r
476 self.think = pathlib_test_dinit;
\r
477 self.nextthink = time + 2;
\r