1 void pathlib_deletepath(entity start)
\r
5 e = findchainentity(owner, start);
\r
8 e.think = SUB_Remove;
\r
14 //#define PATHLIB_NODEEXPIRE 0.05
\r
15 #define PATHLIB_NODEEXPIRE 20
\r
17 void dumpnode(entity n)
\r
19 n.is_path_node = FALSE;
\r
20 n.think = SUB_Remove;
\r
24 entity pathlib_mknode(vector where,entity parent)
\r
28 node = pathlib_nodeatpoint(where);
\r
31 mark_error(where,60);
\r
37 node.think = SUB_Remove;
\r
38 node.nextthink = time + PATHLIB_NODEEXPIRE;
\r
39 node.is_path_node = TRUE;
\r
40 node.owner = openlist;
\r
41 node.path_prev = parent;
\r
43 setmodel(node,"models/pathlib/square.md3");
\r
44 setsize(node,'0 0 0','0 0 0');
\r
45 node.colormod = randomvec() * 2;
\r
47 node.scale = pathlib_gridsize / 512.001;
\r
49 //pathlib_showsquare2(node,'1 1 1',0);//(node.medium & CONTENT_EMPTY));
\r
50 setorigin(node, where);
\r
51 node.medium = pointcontents(where);
\r
53 mark_info(where,60);
\r
54 //pathlib_showsquare(where,1,30);
\r
63 float pathlib_makenode_adaptive(entity parent,vector start, vector to, vector goal,float cost)
\r
69 ++pathlib_searched_cnt;
\r
71 if(inwater(parent.origin))
\r
73 pathlib_expandnode = pathlib_expandnode_box;
\r
74 pathlib_movenode = pathlib_swimnode;
\r
80 pathlib_expandnode = pathlib_expandnode_box;
\r
81 pathlib_movenode = pathlib_walknode;
\r
85 //if(edge_check(parent.origin))
\r
88 pathlib_expandnode = pathlib_expandnode_star;
\r
89 pathlib_movenode = pathlib_walknode;
\r
94 node = pathlib_nodeatpoint(to);
\r
97 ++pathlib_merge_cnt;
\r
99 if(node.owner == openlist)
\r
101 h = pathlib_heuristic(node.origin,goal);
\r
102 g = pathlib_cost(parent,node.origin,cost);
\r
105 if(node.pathlib_node_g > g)
\r
107 node.pathlib_node_h = h;
\r
108 node.pathlib_node_g = g;
\r
109 node.pathlib_node_f = f;
\r
111 node.path_prev = parent;
\r
114 if not (best_open_node)
\r
115 best_open_node = node;
\r
116 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
\r
117 best_open_node = node;
\r
123 where = pathlib_movenode(parent.origin,to,0);
\r
124 if not(pathlib_movenode_goodnode)
\r
127 if(pathlib_nodeatpoint(where))
\r
129 dprint("NAP WHERE :",vtos(where),"\n");
\r
130 dprint("not NAP TO:",vtos(to),"\n");
\r
131 dprint("NAP-NNAP:",ftos(vlen(to-where)),"\n\n");
\r
136 if not (tile_check(where))
\r
139 h = pathlib_heuristic(where,goal);
\r
140 g = pathlib_cost(parent,where,cost);
\r
145 node = findradius(where,pathlib_gridsize * 0.5);
\r
148 if(node.is_path_node == TRUE)
\r
150 ++pathlib_merge_cnt;
\r
151 if(node.owner == openlist)
\r
153 if(node.pathlib_node_g > g)
\r
155 //pathlib_movenode(where,node.origin,0);
\r
156 //if(pathlib_movenode_goodnode)
\r
158 //mark_error(node.origin + '0 0 128',30);
\r
159 node.pathlib_node_h = h;
\r
160 node.pathlib_node_g = g;
\r
161 node.pathlib_node_f = f;
\r
162 node.path_prev = parent;
\r
166 if not (best_open_node)
\r
167 best_open_node = node;
\r
168 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
\r
169 best_open_node = node;
\r
178 node = pathlib_mknode(where,parent);
\r
179 node.pathlib_node_h = h;
\r
180 node.pathlib_node_g = g;
\r
181 node.pathlib_node_f = f;
\r
183 if not (best_open_node)
\r
184 best_open_node = node;
\r
185 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
\r
186 best_open_node = node;
\r
191 entity pathlib_getbestopen()
\r
198 ++pathlib_bestcash_hits;
\r
199 pathlib_bestcash_saved += pathlib_open_cnt;
\r
201 return best_open_node;
\r
204 node = findchainentity(owner,openlist);
\r
211 ++pathlib_bestopen_seached;
\r
212 if(node.pathlib_node_f < bestnode.pathlib_node_f)
\r
221 void pathlib_close_node(entity node,vector goal)
\r
224 if(node.owner == closedlist)
\r
226 dprint("Pathlib: Tried to close a closed node!\n");
\r
230 if(node == best_open_node)
\r
231 best_open_node = world;
\r
233 ++pathlib_closed_cnt;
\r
234 --pathlib_open_cnt;
\r
236 node.owner = closedlist;
\r
238 if(vlen(node.origin - goal) <= pathlib_gridsize)
\r
242 goalmove = pathlib_walknode(node.origin,goal,1);
\r
243 if(pathlib_movenode_goodnode)
\r
246 pathlib_foundgoal = TRUE;
\r
251 void pathlib_cleanup()
\r
253 best_open_node = world;
\r
259 node = findfloat(world,is_path_node, TRUE);
\r
263 node.owner = openlist;
\r
264 node.pathlib_node_g = 0;
\r
265 node.pathlib_node_h = 0;
\r
266 node.pathlib_node_f = 0;
\r
267 node.path_prev = world;
\r
271 node = findfloat(node,is_path_node, TRUE);
\r
278 remove(closedlist);
\r
281 closedlist = world;
\r
285 float Cosine_Interpolate(float a, float b, float x)
\r
289 ft = x * 3.1415927;
\r
290 f = (1 - cos(ft)) * 0.5;
\r
292 return a*(1-f) + b*f;
\r
295 float buildpath_nodefilter_directional(vector n,vector c,vector p)
\r
299 d2 = normalize(p - c);
\r
300 d1 = normalize(c - n);
\r
302 if(vlen(d1-d2) < 0.25)
\r
304 //mark_error(c,30);
\r
311 float buildpath_nodefilter_moveskip(vector n,vector c,vector p)
\r
313 pathlib_walknode(p,n,1);
\r
314 if(pathlib_movenode_goodnode)
\r
320 entity path_build(entity next, vector where, entity prev, entity start)
\r
325 if(buildpath_nodefilter)
\r
326 if(buildpath_nodefilter(next.origin,where,prev.origin))
\r
331 path.owner = start;
\r
332 path.path_next = next;
\r
334 setorigin(path,where);
\r
337 path.classname = "path_end";
\r
341 path.classname = "path_start";
\r
343 path.classname = "path_node";
\r
349 entity pathlib_astar(vector from,vector to)
\r
351 entity path, start, end, open, n, ln;
\r
352 float ptime, ftime, ctime;
\r
354 ptime = gettime(GETTIME_REALTIME);
\r
355 pathlib_starttime = ptime;
\r
359 // Select water<->land capable node make/link
\r
360 pathlib_makenode = pathlib_makenode_adaptive;
\r
361 // Select XYZ cost estimate
\r
362 //pathlib_heuristic = pathlib_h_diagonal3;
\r
363 pathlib_heuristic = pathlib_h_diagonal;
\r
364 // Select distance + waterfactor cost
\r
365 pathlib_cost = pathlib_g_euclidean_water;
\r
366 // Select star expander
\r
367 pathlib_expandnode = pathlib_expandnode_star;
\r
368 // Select walk simulation movement test
\r
369 pathlib_movenode = pathlib_walknode;
\r
370 // Filter final nodes by direction
\r
371 buildpath_nodefilter = buildpath_nodefilter_directional;
\r
372 // Filter tiles with cross pattern
\r
373 tile_check = tile_check_cross;
\r
375 // If the start is in water we need diffrent settings
\r
378 // Select volumetric node expaner
\r
379 pathlib_expandnode = pathlib_expandnode_box;
\r
381 // Water movement test
\r
382 pathlib_movenode = pathlib_swimnode;
\r
386 openlist = spawn();
\r
389 closedlist = spawn();
\r
391 pathlib_closed_cnt = 0;
\r
392 pathlib_open_cnt = 0;
\r
393 pathlib_made_cnt = 0;
\r
394 pathlib_merge_cnt = 0;
\r
395 pathlib_searched_cnt = 0;
\r
396 pathlib_bestopen_seached = 0;
\r
397 pathlib_bestcash_hits = 0;
\r
398 pathlib_bestcash_saved = 0;
\r
400 pathlib_gridsize = 128;
\r
401 pathlib_movecost = pathlib_gridsize;
\r
402 pathlib_movecost_diag = vlen(('1 1 0' * pathlib_gridsize));
\r
403 pathlib_movecost_waterfactor = 1;
\r
404 pathlib_foundgoal = 0;
\r
406 movenode_boxmax = self.maxs * 1.25;
\r
407 movenode_boxmin = self.mins * 1.25;
\r
409 movenode_stepsize = 32;
\r
411 tile_check_size = 65;
\r
412 tile_check_up = '0 0 128';
\r
413 tile_check_down = '0 0 128';
\r
415 movenode_stepup = '0 0 36';
\r
416 movenode_maxdrop = '0 0 128';
\r
417 movenode_boxup = '0 0 72';
\r
419 from_x = fsnap(from_x,pathlib_gridsize);
\r
420 from_y = fsnap(from_y,pathlib_gridsize);
\r
422 to_x = fsnap(to_x,pathlib_gridsize);
\r
423 to_y = fsnap(to_y,pathlib_gridsize);
\r
425 dprint("AStar init\n");
\r
426 path = pathlib_mknode(from,world);
\r
427 pathlib_close_node(path,to);
\r
428 if(pathlib_foundgoal)
\r
430 dprint("AStar: Goal found on first node!\n");
\r
434 open.classname = "path_end";
\r
435 setorigin(open,path.origin);
\r
442 if(pathlib_expandnode(path,from,to) <= 0)
\r
444 dprint("AStar path fail.\n");
\r
450 best_open_node = pathlib_getbestopen();
\r
451 n = best_open_node;
\r
452 pathlib_close_node(best_open_node,to);
\r
453 if(inwater(n.origin))
\r
454 pathlib_expandnode_box(n,from,to);
\r
456 pathlib_expandnode_star(n,from,to);
\r
458 while(pathlib_open_cnt)
\r
460 if((gettime(GETTIME_REALTIME) - pathlib_starttime) > pathlib_maxtime)
\r
462 dprint("Path took to long to compute!\n");
\r
463 dprint("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
\r
464 dprint("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
\r
465 dprint("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
\r
466 dprint("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
\r
472 best_open_node = pathlib_getbestopen();
\r
473 n = best_open_node;
\r
474 pathlib_close_node(best_open_node,to);
\r
476 if(inwater(n.origin))
\r
477 pathlib_expandnode_box(n,from,to);
\r
479 pathlib_expandnode(n,from,to);
\r
481 if(pathlib_foundgoal)
\r
483 dprint("Target found. Rebuilding and filtering path...\n");
\r
484 ftime = gettime(GETTIME_REALTIME);
\r
485 ptime = ftime - ptime;
\r
487 start = path_build(world,path.origin,world,world);
\r
488 end = path_build(world,goal_node.origin,world,start);
\r
492 for(open = goal_node; open.path_prev != path; open = open.path_prev)
\r
494 n = path_build(ln,open.origin,open.path_prev,start);
\r
498 start.path_next = n;
\r
499 n.path_prev = start;
\r
500 ftime = gettime(GETTIME_REALTIME) - ftime;
\r
502 ctime = gettime(GETTIME_REALTIME);
\r
504 ctime = gettime(GETTIME_REALTIME) - ctime;
\r
507 #ifdef DEBUGPATHING
\r
508 pathlib_showpath2(start);
\r
510 dprint("Time used - pathfinding: ", ftos(ptime),"\n");
\r
511 dprint("Time used - rebuild & filter: ", ftos(ftime),"\n");
\r
512 dprint("Time used - cleanup: ", ftos(ctime),"\n");
\r
513 dprint("Time used - total: ", ftos(ptime + ftime + ctime),"\n");
\r
514 dprint("Time used - # frames: ", ftos(ceil((ptime + ftime + ctime) / sys_frametime)),"\n\n");
\r
515 dprint("Nodes - created: ", ftos(pathlib_made_cnt),"\n");
\r
516 dprint("Nodes - open: ", ftos(pathlib_open_cnt),"\n");
\r
517 dprint("Nodes - merged: ", ftos(pathlib_merge_cnt),"\n");
\r
518 dprint("Nodes - closed: ", ftos(pathlib_closed_cnt),"\n");
\r
519 dprint("Nodes - searched: ", ftos(pathlib_searched_cnt),"\n");
\r
520 dprint("Nodes bestopen searched: ", ftos(pathlib_bestopen_seached),"\n");
\r
521 dprint("Nodes bestcash - hits: ", ftos(pathlib_bestcash_hits),"\n");
\r
522 dprint("Nodes bestcash - save: ", ftos(pathlib_bestcash_saved),"\n");
\r
523 dprint("AStar done.\n");
\r
529 dprint("A* Faild to find a path! Try a smaller gridsize.\n");
\r