1 void pathlib_deletepath(entity start)
5 e = findchainentity(owner, start);
14 //#define PATHLIB_NODEEXPIRE 0.05
15 const float PATHLIB_NODEEXPIRE = 20;
17 void dumpnode(entity n)
19 n.is_path_node = false;
24 entity pathlib_mknode(vector where,entity parent)
28 node = pathlib_nodeatpoint(where);
32 mark_error(where, 60);
39 node.think = SUB_Remove;
40 node.nextthink = time + PATHLIB_NODEEXPIRE;
41 node.is_path_node = true;
42 node.owner = openlist;
43 node.path_prev = parent;
46 setsize(node, '0 0 0', '0 0 0');
48 setorigin(node, where);
49 node.medium = pointcontents(where);
50 pathlib_showsquare(where, 1 ,15);
58 float pathlib_makenode_adaptive(entity parent,vector start, vector to, vector goal,float cost)
61 float h,g,f,doedge = 0;
64 ++pathlib_searched_cnt;
66 if(inwater(parent.origin))
68 dprint("FromWater\n");
69 pathlib_expandnode = pathlib_expandnode_box;
70 pathlib_movenode = pathlib_swimnode;
77 pathlib_expandnode = pathlib_expandnode_box;
78 pathlib_movenode = pathlib_walknode;
82 dprint("LandToLoand\n");
83 //if(edge_check(parent.origin))
86 pathlib_expandnode = pathlib_expandnode_star;
87 pathlib_movenode = pathlib_walknode;
92 node = pathlib_nodeatpoint(to);
95 dprint("NodeAtPoint\n");
98 if(node.owner == openlist)
100 h = pathlib_heuristic(node.origin,goal);
101 g = pathlib_cost(parent,node.origin,cost);
104 if(node.pathlib_node_g > g)
106 node.pathlib_node_h = h;
107 node.pathlib_node_g = g;
108 node.pathlib_node_f = f;
110 node.path_prev = parent;
114 best_open_node = node;
115 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
116 best_open_node = node;
122 where = pathlib_movenode(parent.origin, to, 0);
124 if (!pathlib_movenode_goodnode)
126 //pathlib_showsquare(where, 0 ,30);
127 //pathlib_showsquare(parent.origin, 1 ,30);
128 dprint("pathlib_movenode_goodnode = 0\n");
132 //pathlib_showsquare(where, 1 ,30);
134 if(pathlib_nodeatpoint(where))
136 dprint("NAP WHERE :",vtos(where),"\n");
137 dprint("not NAP TO:",vtos(to),"\n");
138 dprint("NAP-NNAP:",ftos(vlen(to-where)),"\n\n");
144 if (!tile_check(where))
146 dprint("tile_check fail\n");
147 pathlib_showsquare(where, 0 ,30);
152 h = pathlib_heuristic(where,goal);
153 g = pathlib_cost(parent,where,cost);
157 node = findradius(where,pathlib_gridsize * 0.5);
160 if(node.is_path_node == true)
163 if(node.owner == openlist)
165 if(node.pathlib_node_g > g)
167 //pathlib_movenode(where,node.origin,0);
168 //if(pathlib_movenode_goodnode)
170 //mark_error(node.origin + '0 0 128',30);
171 node.pathlib_node_h = h;
172 node.pathlib_node_g = g;
173 node.pathlib_node_f = f;
174 node.path_prev = parent;
179 best_open_node = node;
180 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
181 best_open_node = node;
190 node = pathlib_mknode(where, parent);
191 node.pathlib_node_h = h;
192 node.pathlib_node_g = g;
193 node.pathlib_node_f = f;
196 best_open_node = node;
197 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
198 best_open_node = node;
203 entity pathlib_getbestopen()
210 ++pathlib_bestcash_hits;
211 pathlib_bestcash_saved += pathlib_open_cnt;
213 return best_open_node;
216 node = findchainentity(owner,openlist);
223 ++pathlib_bestopen_seached;
224 if(node.pathlib_node_f < bestnode.pathlib_node_f)
233 void pathlib_close_node(entity node,vector goal)
236 if(node.owner == closedlist)
238 dprint("Pathlib: Tried to close a closed node!\n");
242 if(node == best_open_node)
243 best_open_node = world;
245 ++pathlib_closed_cnt;
248 node.owner = closedlist;
250 if(vlen(node.origin - goal) <= pathlib_gridsize)
254 goalmove = pathlib_walknode(node.origin,goal,1);
255 if(pathlib_movenode_goodnode)
258 pathlib_foundgoal = true;
263 void pathlib_cleanup()
265 best_open_node = world;
271 node = findfloat(world,is_path_node, true);
275 node.owner = openlist;
276 node.pathlib_node_g = 0;
277 node.pathlib_node_h = 0;
278 node.pathlib_node_f = 0;
279 node.path_prev = world;
283 node = findfloat(node,is_path_node, true);
297 float Cosine_Interpolate(float a, float b, float x)
302 f = (1 - cos(ft)) * 0.5;
304 return a*(1-f) + b*f;
307 float buildpath_nodefilter_directional(vector n,vector c,vector p)
311 d2 = normalize(p - c);
312 d1 = normalize(c - n);
314 if(vlen(d1-d2) < 0.25)
323 float buildpath_nodefilter_moveskip(vector n,vector c,vector p)
325 pathlib_walknode(p,n,1);
326 if(pathlib_movenode_goodnode)
332 float buildpath_nodefilter_none(vector n,vector c,vector p)
337 entity path_build(entity next, vector where, entity prev, entity start)
342 if(buildpath_nodefilter)
343 if(buildpath_nodefilter(next.origin,where,prev.origin))
349 path.path_next = next;
351 setorigin(path,where);
354 path.classname = "path_end";
358 path.classname = "path_start";
360 path.classname = "path_node";
366 entity pathlib_astar(vector from,vector to)
368 entity path, start, end, open, n, ln;
369 float ptime, ftime, ctime;
371 ptime = gettime(GETTIME_REALTIME);
372 pathlib_starttime = ptime;
376 // Select water<->land capable node make/link
377 pathlib_makenode = pathlib_makenode_adaptive;
379 // Select XYZ cost estimate
380 //pathlib_heuristic = pathlib_h_diagonal3;
381 pathlib_heuristic = pathlib_h_diagonal;
383 // Select distance + waterfactor cost
384 pathlib_cost = pathlib_g_euclidean_water;
386 // Select star expander
387 pathlib_expandnode = pathlib_expandnode_star;
389 // Select walk simulation movement test
390 pathlib_movenode = pathlib_walknode;
392 // Filter final nodes by direction
393 buildpath_nodefilter = buildpath_nodefilter_directional;
395 // Filter tiles with cross pattern
396 tile_check = tile_check_cross;
398 // If the start is in water we need diffrent settings
401 // Select volumetric node expaner
402 pathlib_expandnode = pathlib_expandnode_box;
404 // Water movement test
405 pathlib_movenode = pathlib_swimnode;
412 closedlist = spawn();
414 pathlib_closed_cnt = 0;
415 pathlib_open_cnt = 0;
416 pathlib_made_cnt = 0;
417 pathlib_merge_cnt = 0;
418 pathlib_searched_cnt = 0;
419 pathlib_bestopen_seached = 0;
420 pathlib_bestcash_hits = 0;
421 pathlib_bestcash_saved = 0;
423 pathlib_gridsize = 128;
424 pathlib_movecost = pathlib_gridsize;
425 pathlib_movecost_diag = vlen(('1 1 0' * pathlib_gridsize));
426 pathlib_movecost_waterfactor = 25000000;
427 pathlib_foundgoal = 0;
429 movenode_boxmax = self.maxs * 1.1;
430 movenode_boxmin = self.mins * 1.1;
432 movenode_stepsize = pathlib_gridsize * 0.25;
434 tile_check_size = pathlib_gridsize * 0.5;
435 tile_check_up = '0 0 2' * pathlib_gridsize;
436 tile_check_up = '0 0 128';
437 tile_check_down = '0 0 3' * pathlib_gridsize;
438 tile_check_down = '0 0 256';
440 //movenode_stepup = '0 0 128';
441 movenode_stepup = '0 0 36';
442 movenode_maxdrop = '0 0 512';
443 //movenode_maxdrop = '0 0 512';
444 movenode_boxup = '0 0 72';
446 from.x = fsnap(from.x, pathlib_gridsize);
447 from.y = fsnap(from.y, pathlib_gridsize);
450 to.x = fsnap(to.x, pathlib_gridsize);
451 to.y = fsnap(to.y, pathlib_gridsize);
454 dprint("AStar init\n");
455 path = pathlib_mknode(from, world);
456 pathlib_close_node(path, to);
457 if(pathlib_foundgoal)
459 dprint("AStar: Goal found on first node!\n");
463 open.classname = "path_end";
464 setorigin(open,path.origin);
471 if(pathlib_expandnode(path, from, to) <= 0)
473 dprint("AStar path fail.\n");
479 best_open_node = pathlib_getbestopen();
481 pathlib_close_node(best_open_node, to);
482 if(inwater(n.origin))
483 pathlib_expandnode_box(n, from, to);
485 pathlib_expandnode_star(n, from, to);
487 while(pathlib_open_cnt)
489 if((gettime(GETTIME_REALTIME) - pathlib_starttime) > pathlib_maxtime)
491 dprint("Path took to long to compute!\n");
492 dprint("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
493 dprint("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
494 dprint("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
495 dprint("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
501 best_open_node = pathlib_getbestopen();
503 pathlib_close_node(best_open_node,to);
505 if(inwater(n.origin))
506 pathlib_expandnode_box(n,from,to);
508 pathlib_expandnode(n,from,to);
510 if(pathlib_foundgoal)
512 dprint("Target found. Rebuilding and filtering path...\n");
513 ftime = gettime(GETTIME_REALTIME);
514 ptime = ftime - ptime;
516 start = path_build(world,path.origin,world,world);
517 end = path_build(world,goal_node.origin,world,start);
521 for(open = goal_node; open.path_prev != path; open = open.path_prev)
523 n = path_build(ln,open.origin,open.path_prev,start);
529 ftime = gettime(GETTIME_REALTIME) - ftime;
531 ctime = gettime(GETTIME_REALTIME);
533 ctime = gettime(GETTIME_REALTIME) - ctime;
537 pathlib_showpath2(start);
539 dprint("Time used - pathfinding: ", ftos(ptime),"\n");
540 dprint("Time used - rebuild & filter: ", ftos(ftime),"\n");
541 dprint("Time used - cleanup: ", ftos(ctime),"\n");
542 dprint("Time used - total: ", ftos(ptime + ftime + ctime),"\n");
543 dprint("Time used - # frames: ", ftos(ceil((ptime + ftime + ctime) / sys_frametime)),"\n\n");
544 dprint("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
545 dprint("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
546 dprint("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
547 dprint("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
548 dprint("Nodes - searched: ", ftos(pathlib_searched_cnt),"\n");
549 dprint("Nodes bestopen searched: ", ftos(pathlib_bestopen_seached),"\n");
550 dprint("Nodes bestcash - hits: ", ftos(pathlib_bestcash_hits),"\n");
551 dprint("Nodes bestcash - save: ", ftos(pathlib_bestcash_saved),"\n");
552 dprint("AStar done.\n");
558 dprint("A* Faild to find a path! Try a smaller gridsize.\n");