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 float buildpath_nodefilter_none(vector n,vector c,vector p)
335 entity path_build(entity next, vector where, entity prev, entity start)
340 if(buildpath_nodefilter)
341 if(buildpath_nodefilter(next.origin,where,prev.origin))
347 path.path_next = next;
349 setorigin(path,where);
352 path.classname = "path_end";
356 path.classname = "path_start";
358 path.classname = "path_node";
364 entity pathlib_astar(vector from,vector to)
366 entity path, start, end, open, n, ln;
367 float ptime, ftime, ctime;
369 ptime = gettime(GETTIME_REALTIME);
370 pathlib_starttime = ptime;
374 // Select water<->land capable node make/link
375 pathlib_makenode = pathlib_makenode_adaptive;
377 // Select XYZ cost estimate
378 //pathlib_heuristic = pathlib_h_diagonal3;
379 pathlib_heuristic = pathlib_h_diagonal;
381 // Select distance + waterfactor cost
382 pathlib_cost = pathlib_g_euclidean_water;
384 // Select star expander
385 pathlib_expandnode = pathlib_expandnode_star;
387 // Select walk simulation movement test
388 pathlib_movenode = pathlib_walknode;
390 // Filter final nodes by direction
391 buildpath_nodefilter = buildpath_nodefilter_directional;
393 // Filter tiles with cross pattern
394 tile_check = tile_check_cross;
396 // If the start is in water we need diffrent settings
399 // Select volumetric node expaner
400 pathlib_expandnode = pathlib_expandnode_box;
402 // Water movement test
403 pathlib_movenode = pathlib_swimnode;
410 closedlist = spawn();
412 pathlib_closed_cnt = 0;
413 pathlib_open_cnt = 0;
414 pathlib_made_cnt = 0;
415 pathlib_merge_cnt = 0;
416 pathlib_searched_cnt = 0;
417 pathlib_bestopen_seached = 0;
418 pathlib_bestcash_hits = 0;
419 pathlib_bestcash_saved = 0;
421 pathlib_gridsize = 128;
422 pathlib_movecost = pathlib_gridsize;
423 pathlib_movecost_diag = vlen(('1 1 0' * pathlib_gridsize));
424 pathlib_movecost_waterfactor = 25000000;
425 pathlib_foundgoal = 0;
427 movenode_boxmax = self.maxs * 1.1;
428 movenode_boxmin = self.mins * 1.1;
430 movenode_stepsize = pathlib_gridsize * 0.25;
432 tile_check_size = pathlib_gridsize * 0.5;
433 tile_check_up = '0 0 2' * pathlib_gridsize;
434 tile_check_up = '0 0 128';
435 tile_check_down = '0 0 3' * pathlib_gridsize;
436 tile_check_down = '0 0 256';
438 //movenode_stepup = '0 0 128';
439 movenode_stepup = '0 0 36';
440 movenode_maxdrop = '0 0 512';
441 //movenode_maxdrop = '0 0 512';
442 movenode_boxup = '0 0 72';
444 from_x = fsnap(from_x, pathlib_gridsize);
445 from_y = fsnap(from_y, pathlib_gridsize);
448 to_x = fsnap(to_x, pathlib_gridsize);
449 to_y = fsnap(to_y, pathlib_gridsize);
452 dprint("AStar init\n");
453 path = pathlib_mknode(from, world);
454 pathlib_close_node(path, to);
455 if(pathlib_foundgoal)
457 dprint("AStar: Goal found on first node!\n");
461 open.classname = "path_end";
462 setorigin(open,path.origin);
469 if(pathlib_expandnode(path, from, to) <= 0)
471 dprint("AStar path fail.\n");
477 best_open_node = pathlib_getbestopen();
479 pathlib_close_node(best_open_node, to);
480 if(inwater(n.origin))
481 pathlib_expandnode_box(n, from, to);
483 pathlib_expandnode_star(n, from, to);
485 while(pathlib_open_cnt)
487 if((gettime(GETTIME_REALTIME) - pathlib_starttime) > pathlib_maxtime)
489 dprint("Path took to long to compute!\n");
490 dprint("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
491 dprint("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
492 dprint("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
493 dprint("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
499 best_open_node = pathlib_getbestopen();
501 pathlib_close_node(best_open_node,to);
503 if(inwater(n.origin))
504 pathlib_expandnode_box(n,from,to);
506 pathlib_expandnode(n,from,to);
508 if(pathlib_foundgoal)
510 dprint("Target found. Rebuilding and filtering path...\n");
511 ftime = gettime(GETTIME_REALTIME);
512 ptime = ftime - ptime;
514 start = path_build(world,path.origin,world,world);
515 end = path_build(world,goal_node.origin,world,start);
519 for(open = goal_node; open.path_prev != path; open = open.path_prev)
521 n = path_build(ln,open.origin,open.path_prev,start);
527 ftime = gettime(GETTIME_REALTIME) - ftime;
529 ctime = gettime(GETTIME_REALTIME);
531 ctime = gettime(GETTIME_REALTIME) - ctime;
535 pathlib_showpath2(start);
537 dprint("Time used - pathfinding: ", ftos(ptime),"\n");
538 dprint("Time used - rebuild & filter: ", ftos(ftime),"\n");
539 dprint("Time used - cleanup: ", ftos(ctime),"\n");
540 dprint("Time used - total: ", ftos(ptime + ftime + ctime),"\n");
541 dprint("Time used - # frames: ", ftos(ceil((ptime + ftime + ctime) / sys_frametime)),"\n\n");
542 dprint("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
543 dprint("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
544 dprint("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
545 dprint("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
546 dprint("Nodes - searched: ", ftos(pathlib_searched_cnt),"\n");
547 dprint("Nodes bestopen searched: ", ftos(pathlib_bestopen_seached),"\n");
548 dprint("Nodes bestcash - hits: ", ftos(pathlib_bestcash_hits),"\n");
549 dprint("Nodes bestcash - save: ", ftos(pathlib_bestcash_saved),"\n");
550 dprint("AStar done.\n");
556 dprint("A* Faild to find a path! Try a smaller gridsize.\n");