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