1 void pathlib_deletepath(entity start)
5 e = findchainentity(owner, start);
14 //#define PATHLIB_NODEEXPIRE 0.05
15 #define 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);
31 mark_error(where, 60);
37 node.think = SUB_Remove;
38 node.nextthink = time + PATHLIB_NODEEXPIRE;
39 node.is_path_node = TRUE;
40 node.owner = openlist;
41 node.path_prev = parent;
44 setsize(node, '0 0 0', '0 0 0');
46 setorigin(node, where);
47 node.medium = pointcontents(where);
48 pathlib_showsquare(where, 1 ,15);
56 float pathlib_makenode_adaptive(entity parent,vector start, vector to, vector goal,float cost)
62 ++pathlib_searched_cnt;
64 if(inwater(parent.origin))
66 dprint("FromWater\n");
67 pathlib_expandnode = pathlib_expandnode_box;
68 pathlib_movenode = pathlib_swimnode;
75 pathlib_expandnode = pathlib_expandnode_box;
76 pathlib_movenode = pathlib_walknode;
80 dprint("LandToLoand\n");
81 //if(edge_check(parent.origin))
84 pathlib_expandnode = pathlib_expandnode_star;
85 pathlib_movenode = pathlib_walknode;
90 node = pathlib_nodeatpoint(to);
93 dprint("NodeAtPoint\n");
96 if(node.owner == openlist)
98 h = pathlib_heuristic(node.origin,goal);
99 g = pathlib_cost(parent,node.origin,cost);
102 if(node.pathlib_node_g > g)
104 node.pathlib_node_h = h;
105 node.pathlib_node_g = g;
106 node.pathlib_node_f = f;
108 node.path_prev = parent;
111 if not (best_open_node)
112 best_open_node = node;
113 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
114 best_open_node = node;
120 where = pathlib_movenode(parent.origin, to, 0);
122 if not(pathlib_movenode_goodnode)
124 //pathlib_showsquare(where, 0 ,30);
125 //pathlib_showsquare(parent.origin, 1 ,30);
126 dprint("pathlib_movenode_goodnode = 0\n");
130 //pathlib_showsquare(where, 1 ,30);
132 if(pathlib_nodeatpoint(where))
134 dprint("NAP WHERE :",vtos(where),"\n");
135 dprint("not NAP TO:",vtos(to),"\n");
136 dprint("NAP-NNAP:",ftos(vlen(to-where)),"\n\n");
142 if not (tile_check(where))
144 dprint("tile_check fail\n");
145 pathlib_showsquare(where, 0 ,30);
150 h = pathlib_heuristic(where,goal);
151 g = pathlib_cost(parent,where,cost);
155 node = findradius(where,pathlib_gridsize * 0.5);
158 if(node.is_path_node == TRUE)
161 if(node.owner == openlist)
163 if(node.pathlib_node_g > g)
165 //pathlib_movenode(where,node.origin,0);
166 //if(pathlib_movenode_goodnode)
168 //mark_error(node.origin + '0 0 128',30);
169 node.pathlib_node_h = h;
170 node.pathlib_node_g = g;
171 node.pathlib_node_f = f;
172 node.path_prev = parent;
176 if not (best_open_node)
177 best_open_node = node;
178 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
179 best_open_node = node;
188 node = pathlib_mknode(where, parent);
189 node.pathlib_node_h = h;
190 node.pathlib_node_g = g;
191 node.pathlib_node_f = f;
193 if not (best_open_node)
194 best_open_node = node;
195 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
196 best_open_node = node;
201 entity pathlib_getbestopen()
208 ++pathlib_bestcash_hits;
209 pathlib_bestcash_saved += pathlib_open_cnt;
211 return best_open_node;
214 node = findchainentity(owner,openlist);
221 ++pathlib_bestopen_seached;
222 if(node.pathlib_node_f < bestnode.pathlib_node_f)
231 void pathlib_close_node(entity node,vector goal)
234 if(node.owner == closedlist)
236 dprint("Pathlib: Tried to close a closed node!\n");
240 if(node == best_open_node)
241 best_open_node = world;
243 ++pathlib_closed_cnt;
246 node.owner = closedlist;
248 if(vlen(node.origin - goal) <= pathlib_gridsize)
252 goalmove = pathlib_walknode(node.origin,goal,1);
253 if(pathlib_movenode_goodnode)
256 pathlib_foundgoal = TRUE;
261 void pathlib_cleanup()
263 best_open_node = world;
269 node = findfloat(world,is_path_node, TRUE);
273 node.owner = openlist;
274 node.pathlib_node_g = 0;
275 node.pathlib_node_h = 0;
276 node.pathlib_node_f = 0;
277 node.path_prev = world;
281 node = findfloat(node,is_path_node, TRUE);
295 float Cosine_Interpolate(float a, float b, float x)
300 f = (1 - cos(ft)) * 0.5;
302 return a*(1-f) + b*f;
305 float buildpath_nodefilter_directional(vector n,vector c,vector p)
309 d2 = normalize(p - c);
310 d1 = normalize(c - n);
312 if(vlen(d1-d2) < 0.25)
321 float buildpath_nodefilter_moveskip(vector n,vector c,vector p)
323 pathlib_walknode(p,n,1);
324 if(pathlib_movenode_goodnode)
330 entity path_build(entity next, vector where, entity prev, entity start)
335 if(buildpath_nodefilter)
336 if(buildpath_nodefilter(next.origin,where,prev.origin))
342 path.path_next = next;
344 setorigin(path,where);
347 path.classname = "path_end";
351 path.classname = "path_start";
353 path.classname = "path_node";
359 entity pathlib_astar(vector from,vector to)
361 entity path, start, end, open, n, ln;
362 float ptime, ftime, ctime;
364 ptime = gettime(GETTIME_REALTIME);
365 pathlib_starttime = ptime;
369 // Select water<->land capable node make/link
370 pathlib_makenode = pathlib_makenode_adaptive;
372 // Select XYZ cost estimate
373 //pathlib_heuristic = pathlib_h_diagonal3;
374 pathlib_heuristic = pathlib_h_diagonal;
376 // Select distance + waterfactor cost
377 pathlib_cost = pathlib_g_euclidean_water;
379 // Select star expander
380 pathlib_expandnode = pathlib_expandnode_star;
382 // Select walk simulation movement test
383 pathlib_movenode = pathlib_walknode;
385 // Filter final nodes by direction
386 buildpath_nodefilter = buildpath_nodefilter_directional;
388 // Filter tiles with cross pattern
389 tile_check = tile_check_cross;
391 // If the start is in water we need diffrent settings
394 // Select volumetric node expaner
395 pathlib_expandnode = pathlib_expandnode_box;
397 // Water movement test
398 pathlib_movenode = pathlib_swimnode;
405 closedlist = spawn();
407 pathlib_closed_cnt = 0;
408 pathlib_open_cnt = 0;
409 pathlib_made_cnt = 0;
410 pathlib_merge_cnt = 0;
411 pathlib_searched_cnt = 0;
412 pathlib_bestopen_seached = 0;
413 pathlib_bestcash_hits = 0;
414 pathlib_bestcash_saved = 0;
416 pathlib_gridsize = 128;
417 pathlib_movecost = pathlib_gridsize;
418 pathlib_movecost_diag = vlen(('1 1 0' * pathlib_gridsize));
419 pathlib_movecost_waterfactor = 25000000;
420 pathlib_foundgoal = 0;
422 movenode_boxmax = self.maxs * 1.1;
423 movenode_boxmin = self.mins * 1.1;
425 movenode_stepsize = pathlib_gridsize * 0.25;
427 tile_check_size = pathlib_gridsize * 0.5;
428 tile_check_up = '0 0 2' * pathlib_gridsize;
429 tile_check_up = '0 0 128';
430 tile_check_down = '0 0 3' * pathlib_gridsize;
431 tile_check_down = '0 0 256';
433 //movenode_stepup = '0 0 128';
434 movenode_stepup = '0 0 36';
435 movenode_maxdrop = '0 0 512';
436 //movenode_maxdrop = '0 0 512';
437 movenode_boxup = '0 0 72';
439 from_x = fsnap(from_x, pathlib_gridsize);
440 from_y = fsnap(from_y, pathlib_gridsize);
443 to_x = fsnap(to_x, pathlib_gridsize);
444 to_y = fsnap(to_y, pathlib_gridsize);
447 dprint("AStar init\n");
448 path = pathlib_mknode(from, world);
449 pathlib_close_node(path, to);
450 if(pathlib_foundgoal)
452 dprint("AStar: Goal found on first node!\n");
456 open.classname = "path_end";
457 setorigin(open,path.origin);
464 if(pathlib_expandnode(path, from, to) <= 0)
466 dprint("AStar path fail.\n");
472 best_open_node = pathlib_getbestopen();
474 pathlib_close_node(best_open_node, to);
475 if(inwater(n.origin))
476 pathlib_expandnode_box(n, from, to);
478 pathlib_expandnode_star(n, from, to);
480 while(pathlib_open_cnt)
482 if((gettime(GETTIME_REALTIME) - pathlib_starttime) > pathlib_maxtime)
484 dprint("Path took to long to compute!\n");
485 dprint("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
486 dprint("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
487 dprint("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
488 dprint("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
494 best_open_node = pathlib_getbestopen();
496 pathlib_close_node(best_open_node,to);
498 if(inwater(n.origin))
499 pathlib_expandnode_box(n,from,to);
501 pathlib_expandnode(n,from,to);
503 if(pathlib_foundgoal)
505 dprint("Target found. Rebuilding and filtering path...\n");
506 ftime = gettime(GETTIME_REALTIME);
507 ptime = ftime - ptime;
509 start = path_build(world,path.origin,world,world);
510 end = path_build(world,goal_node.origin,world,start);
514 for(open = goal_node; open.path_prev != path; open = open.path_prev)
516 n = path_build(ln,open.origin,open.path_prev,start);
522 ftime = gettime(GETTIME_REALTIME) - ftime;
524 ctime = gettime(GETTIME_REALTIME);
526 ctime = gettime(GETTIME_REALTIME) - ctime;
530 pathlib_showpath2(start);
532 dprint("Time used - pathfinding: ", ftos(ptime),"\n");
533 dprint("Time used - rebuild & filter: ", ftos(ftime),"\n");
534 dprint("Time used - cleanup: ", ftos(ctime),"\n");
535 dprint("Time used - total: ", ftos(ptime + ftime + ctime),"\n");
536 dprint("Time used - # frames: ", ftos(ceil((ptime + ftime + ctime) / sys_frametime)),"\n\n");
537 dprint("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
538 dprint("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
539 dprint("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
540 dprint("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
541 dprint("Nodes - searched: ", ftos(pathlib_searched_cnt),"\n");
542 dprint("Nodes bestopen searched: ", ftos(pathlib_bestopen_seached),"\n");
543 dprint("Nodes bestcash - hits: ", ftos(pathlib_bestcash_hits),"\n");
544 dprint("Nodes bestcash - save: ", ftos(pathlib_bestcash_saved),"\n");
545 dprint("AStar done.\n");
551 dprint("A* Faild to find a path! Try a smaller gridsize.\n");