]> git.xonotic.org Git - xonotic/xonotic-data.pk3dir.git/blob - qcsrc/server/pathlib/main.qc
Phase out miscfunctions.qc from the server codebase, preferring more fitting location...
[xonotic/xonotic-data.pk3dir.git] / qcsrc / server / pathlib / main.qc
1 #include "main.qh"
2
3 #include <common/weapons/_all.qh>
4 #include <common/stats.qh>
5 #include "pathlib.qh"
6 #include "utility.qh"
7 #include <common/turrets/util.qh>
8 #include "../command/common.qh"
9
10 void pathlib_deletepath(entity start)
11 {
12     if(!start)
13         return;
14
15     FOREACH_ENTITY_ENT(owner, start,
16     {
17         setthink(it, SUB_Remove);
18         it.nextthink = time;
19     });
20 }
21
22 const float PATHLIB_NODEEXPIRE = 20; // 0.05
23
24 void dumpnode(entity n)
25 {
26     if(n.is_path_node)
27         IL_REMOVE(g_pathlib_nodes, n);
28     n.is_path_node = false;
29     setthink(n, SUB_Remove);
30     n.nextthink    = time;
31 }
32
33 #if DEBUGPATHING
34 #include "debug.qh"
35 #endif
36
37
38 entity pathlib_mknode(vector where,entity parent)
39 {
40     entity node = pathlib_nodeatpoint(where);
41     if(node)
42     {
43         #ifdef TURRET_DEBUG
44         mark_error(where, 60);
45         #endif
46         return node;
47     }
48
49     node = spawn();
50
51     setthink(node, SUB_Remove);
52     node.nextthink    = time + PATHLIB_NODEEXPIRE;
53     IL_PUSH(g_pathlib_nodes, node);
54     node.is_path_node = true;
55     node.owner        = openlist;
56     node.path_prev    = parent;
57
58     setsize(node, '0 0 0', '0 0 0');
59
60     setorigin(node, where);
61 #if DEBUGPATHING
62     pathlib_showsquare(where, 1 ,15);
63 #endif
64     ++pathlib_made_cnt;
65     ++pathlib_open_cnt;
66
67     return node;
68 }
69
70 bool pathlib_makenode_adaptive(entity parent,vector start, vector to, vector goal,float cost)
71 {
72     bool dodge = false;
73     float f, h, g;
74
75     ++pathlib_searched_cnt;
76
77     if(inwater(parent.origin))
78     {
79         LOG_DEBUG("FromWater");
80         pathlib_expandnode = pathlib_expandnode_box;
81         pathlib_movenode   = pathlib_swimnode;
82     }
83     else
84     {
85         if(inwater(to))
86         {
87             LOG_DEBUG("ToWater");
88             pathlib_expandnode = pathlib_expandnode_box;
89             pathlib_movenode   = pathlib_walknode;
90         }
91         else
92         {
93             LOG_DEBUG("LandToLoand");
94             //if(edge_check(parent.origin))
95             //    return 0;
96
97             pathlib_expandnode = pathlib_expandnode_star;
98             pathlib_movenode   = pathlib_walknode;
99             dodge = true;
100         }
101     }
102
103     entity node = pathlib_nodeatpoint(to);
104     if(node)
105     {
106         LOG_DEBUG("NodeAtPoint");
107         ++pathlib_merge_cnt;
108
109         if(node.owner == openlist)
110         {
111             h = pathlib_heuristic(node.origin,goal);
112             float g = pathlib_cost(parent,node.origin,cost);
113             f = g + h;
114
115             if(node.pathlib_node_g > g)
116             {
117                 node.pathlib_node_h = h;
118                 node.pathlib_node_g = g;
119                 node.pathlib_node_f = f;
120
121                 node.path_prev = parent;
122             }
123
124             if (!best_open_node)
125                 best_open_node = node;
126             else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
127                 best_open_node = node;
128         }
129
130         return true;
131     }
132
133     vector where = pathlib_movenode(parent, parent.origin, to, 0);
134
135     if (!pathlib_movenode_goodnode)
136     {
137         //pathlib_showsquare(where, 0 ,30);
138         //pathlib_showsquare(parent.origin, 1 ,30);
139         LOG_DEBUG("pathlib_movenode_goodnode = 0");
140         return false;
141     }
142
143     //pathlib_showsquare(where, 1 ,30);
144
145     if(pathlib_nodeatpoint(where))
146     {
147         LOG_DEBUG("NAP WHERE :",vtos(where));
148         LOG_DEBUG("not NAP TO:",vtos(to));
149         LOG_DEBUG("NAP-NNAP:",ftos(vlen(to-where)));
150         return false;
151     }
152
153
154     if(dodge)
155         if (!tile_check(parent, where))
156         {
157             LOG_DEBUG("tile_check fail");
158 #if DEBUGPATHING
159             pathlib_showsquare(where, 0 ,30);
160 #endif
161             return false;
162         }
163
164
165     h = pathlib_heuristic(where,goal);
166     g = pathlib_cost(parent,where,cost);
167     f = g + h;
168
169     /*
170     node = findradius(where,pathlib_gridsize * 0.5);
171     while(node)
172     {
173         if(node.is_path_node == true)
174         {
175             ++pathlib_merge_cnt;
176             if(node.owner == openlist)
177             {
178                 if(node.pathlib_node_g > g)
179                 {
180                     //pathlib_movenode(node, where,node.origin,0);
181                     //if(pathlib_movenode_goodnode)
182                     //{
183                         //mark_error(node.origin + '0 0 128',30);
184                         node.pathlib_node_h = h;
185                         node.pathlib_node_g = g;
186                         node.pathlib_node_f = f;
187                         node.path_prev = parent;
188                     //}
189                 }
190
191                 if (!best_open_node)
192                     best_open_node = node;
193                 else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
194                     best_open_node = node;
195             }
196
197             return 1;
198         }
199         node = node.chain;
200     }
201     */
202
203     node = pathlib_mknode(where, parent);
204     node.pathlib_node_h = h;
205     node.pathlib_node_g = g;
206     node.pathlib_node_f = f;
207
208     if (!best_open_node)
209         best_open_node = node;
210     else if(best_open_node.pathlib_node_f > node.pathlib_node_f)
211         best_open_node = node;
212
213     return true;
214 }
215
216 entity pathlib_getbestopen()
217 {
218     if(best_open_node)
219     {
220         ++pathlib_bestcash_hits;
221         pathlib_bestcash_saved += pathlib_open_cnt;
222
223         return best_open_node;
224     }
225
226     entity bestnode = NULL;
227     FOREACH_ENTITY_ENT(owner, openlist,
228     {
229         ++pathlib_bestopen_searched;
230
231         if(!bestnode || it.pathlib_node_f < bestnode.pathlib_node_f)
232             bestnode = it;
233     });
234
235     return bestnode;
236 }
237
238 void pathlib_close_node(entity node,vector goal)
239 {
240     if(node.owner == closedlist)
241     {
242         LOG_TRACE("Pathlib: Tried to close a closed node!");
243         return;
244     }
245
246     if(node == best_open_node)
247         best_open_node = NULL;
248
249     ++pathlib_closed_cnt;
250     --pathlib_open_cnt;
251
252     node.owner = closedlist;
253
254     if(vdist(node.origin - goal, <=, pathlib_gridsize))
255     {
256         vector goalmove;
257
258         goalmove = pathlib_walknode(node, node.origin, goal, 1);
259         if(pathlib_movenode_goodnode)
260         {
261             goal_node         = node;
262             pathlib_foundgoal = true;
263         }
264     }
265 }
266
267 void pathlib_cleanup()
268 {
269     best_open_node = NULL;
270
271     //return;
272
273     IL_EACH(g_pathlib_nodes, it.is_path_node,
274     {
275         dumpnode(it);
276     });
277
278     IL_CLEAR(g_pathlib_nodes);
279
280     if(openlist)
281         delete(openlist);
282
283     if(closedlist)
284         delete(closedlist);
285
286     openlist = NULL;
287     closedlist = NULL;
288 }
289
290 float Cosine_Interpolate(float a, float b, float c)
291 {
292         float ft = c * M_PI;
293         float f = (1 - cos(ft)) * 0.5;
294
295         return a*(1-f) + b*f;
296 }
297
298 bool buildpath_nodefilter_directional(vector n,vector c,vector p)
299 {
300     vector d2 = normalize(p - c);
301     vector d1 = normalize(c - n);
302
303     if(vdist(d1 - d2, <, 0.25))
304     {
305         //mark_error(c,30);
306         return true;
307     }
308     //mark_info(c,30);
309     return false;
310 }
311
312 bool buildpath_nodefilter_moveskip(entity this, vector n,vector c,vector p)
313 {
314     pathlib_walknode(this, p, n, 1);
315     if(pathlib_movenode_goodnode)
316         return true;
317
318     return false;
319 }
320
321 bool buildpath_nodefilter_none(vector n,vector c,vector p)
322 {
323     return false;
324 }
325
326 entity path_build(entity next, vector where, entity prev, entity start)
327 {
328     if(prev && next)
329         if(buildpath_nodefilter)
330             if(buildpath_nodefilter(next.origin,where,prev.origin))
331                 return next;
332
333
334     entity path    = spawn();
335     path.owner     = start;
336     path.path_next = next;
337
338     setorigin(path, where);
339
340     if(!next)
341         path.classname = "path_end";
342     else
343     {
344         if(!prev)
345             path.classname = "path_start";
346         else
347             path.classname = "path_node";
348     }
349
350     return path;
351 }
352
353 entity pathlib_astar(entity this, vector from, vector to)
354 {
355         entity open;
356     float ptime = gettime(GETTIME_REALTIME);
357     pathlib_starttime = ptime;
358
359     pathlib_cleanup();
360
361     // Select water<->land capable node make/link
362     pathlib_makenode     = pathlib_makenode_adaptive;
363
364     // Select XYZ cost estimate
365     //pathlib_heuristic    = pathlib_h_diagonal3;
366     pathlib_heuristic    = pathlib_h_diagonal;
367
368     // Select distance + waterfactor cost
369     pathlib_cost         = pathlib_g_euclidean_water;
370
371     // Select star expander
372     pathlib_expandnode   = pathlib_expandnode_star;
373
374     // Select walk simulation movement test
375     pathlib_movenode     = pathlib_walknode;
376
377     // Filter final nodes by direction
378     buildpath_nodefilter = buildpath_nodefilter_directional;
379
380     // Filter tiles with cross pattern
381     tile_check = tile_check_cross;
382
383     // If the start is in water we need diffrent settings
384     if(inwater(from))
385     {
386         // Select volumetric node expaner
387         pathlib_expandnode = pathlib_expandnode_box;
388
389         // Water movement test
390         pathlib_movenode   = pathlib_swimnode;
391     }
392
393     if (!openlist)
394         openlist       = spawn();
395
396     if (!closedlist)
397         closedlist     = spawn();
398
399     pathlib_closed_cnt       = 0;
400     pathlib_open_cnt         = 0;
401     pathlib_made_cnt         = 0;
402     pathlib_merge_cnt        = 0;
403     pathlib_searched_cnt     = 0;
404     pathlib_bestopen_searched = 0;
405     pathlib_bestcash_hits    = 0;
406     pathlib_bestcash_saved   = 0;
407
408     pathlib_gridsize       = 128;
409     pathlib_movecost       = pathlib_gridsize;
410     pathlib_movecost_diag  = vlen(('1 1 0' * pathlib_gridsize));
411     pathlib_movecost_waterfactor = 25000000;
412     pathlib_foundgoal      = 0;
413
414     movenode_boxmax   = this.maxs * 1.1;
415     movenode_boxmin   = this.mins * 1.1;
416
417     movenode_stepsize = pathlib_gridsize * 0.25;
418
419     tile_check_size = pathlib_gridsize * 0.5;
420     tile_check_up   = '0 0 2' * pathlib_gridsize;
421     tile_check_up   = '0 0 128';
422     tile_check_down = '0 0 3' * pathlib_gridsize;
423     tile_check_down = '0 0 256';
424
425     //movenode_stepup   = '0 0 128';
426     movenode_stepup   = '0 0 36';
427     movenode_maxdrop  = '0 0 512';
428     //movenode_maxdrop  = '0 0 512';
429     movenode_boxup    = '0 0 72';
430
431     from.x = fsnap(from.x, pathlib_gridsize);
432     from.y = fsnap(from.y, pathlib_gridsize);
433     //from.z += 32;
434
435     to.x = fsnap(to.x, pathlib_gridsize);
436     to.y = fsnap(to.y, pathlib_gridsize);
437     //to.z += 32;
438
439     LOG_DEBUG("AStar init");
440     entity path = pathlib_mknode(from, NULL);
441     pathlib_close_node(path, to);
442     if(pathlib_foundgoal)
443     {
444         LOG_DEBUG("AStar: Goal found on first node!");
445
446         open           = new(path_end);
447         open.owner     = open;
448         setorigin(open, path.origin);
449
450         pathlib_cleanup();
451
452         return open;
453     }
454
455     if(pathlib_expandnode(path, from, to) <= 0)
456     {
457         LOG_TRACE("AStar path fail.");
458         pathlib_cleanup();
459
460         return NULL;
461     }
462
463     best_open_node = pathlib_getbestopen();
464     entity n = best_open_node;
465     pathlib_close_node(best_open_node, to);
466     if(inwater(n.origin))
467         pathlib_expandnode_box(n, from, to);
468     else
469         pathlib_expandnode_star(n, from, to);
470
471     while(pathlib_open_cnt)
472     {
473         if((gettime(GETTIME_REALTIME) - pathlib_starttime) > pathlib_maxtime)
474         {
475             LOG_TRACE("Path took too long to compute!");
476             LOG_TRACE("Nodes - created: ", ftos(pathlib_made_cnt));
477             LOG_TRACE("Nodes -    open: ", ftos(pathlib_open_cnt));
478             LOG_TRACE("Nodes -  merged: ", ftos(pathlib_merge_cnt));
479             LOG_TRACE("Nodes -  closed: ", ftos(pathlib_closed_cnt));
480
481             pathlib_cleanup();
482             return NULL;
483         }
484
485         best_open_node = pathlib_getbestopen();
486         n = best_open_node;
487         pathlib_close_node(best_open_node,to);
488
489         if(inwater(n.origin))
490             pathlib_expandnode_box(n,from,to);
491         else
492             pathlib_expandnode(n,from,to);
493
494         if(pathlib_foundgoal)
495         {
496             LOG_DEBUG("Target found. Rebuilding and filtering path...");
497             float ftime = gettime(GETTIME_REALTIME);
498             ptime = ftime - ptime;
499
500             entity start = path_build(NULL,path.origin,NULL,NULL);
501             entity end   = path_build(NULL,goal_node.origin,NULL,start);
502             entity ln    = end;
503
504             open = goal_node;
505             for(open = goal_node; open.path_prev != path; open = open.path_prev)
506             {
507                 n    = path_build(ln,open.origin,open.path_prev,start);
508                 ln.path_prev = n;
509                 ln = n;
510             }
511             start.path_next = n;
512             n.path_prev = start;
513             ftime = gettime(GETTIME_REALTIME) - ftime;
514
515             float ctime = gettime(GETTIME_REALTIME);
516             pathlib_cleanup();
517             ctime = gettime(GETTIME_REALTIME) - ctime;
518
519
520 #if DEBUGPATHING
521             pathlib_showpath2(start);
522
523             LOG_TRACE("Time used -      pathfinding: ", ftos(ptime));
524             LOG_TRACE("Time used - rebuild & filter: ", ftos(ftime));
525             LOG_TRACE("Time used -          cleanup: ", ftos(ctime));
526             LOG_TRACE("Time used -            total: ", ftos(ptime + ftime + ctime));
527             LOG_TRACE("Time used -         # frames: ", ftos(ceil((ptime + ftime + ctime) / sys_frametime)));
528             LOG_TRACE("Nodes -         created: ", ftos(pathlib_made_cnt));
529             LOG_TRACE("Nodes -            open: ", ftos(pathlib_open_cnt));
530             LOG_TRACE("Nodes -          merged: ", ftos(pathlib_merge_cnt));
531             LOG_TRACE("Nodes -          closed: ", ftos(pathlib_closed_cnt));
532             LOG_TRACE("Nodes -        searched: ", ftos(pathlib_searched_cnt));
533             LOG_TRACE("Nodes bestopen searched: ", ftos(pathlib_bestopen_searched));
534             LOG_TRACE("Nodes bestcash -   hits: ", ftos(pathlib_bestcash_hits));
535             LOG_TRACE("Nodes bestcash -   save: ", ftos(pathlib_bestcash_saved));
536             LOG_TRACE("AStar done.");
537 #endif
538             return start;
539         }
540     }
541
542     LOG_TRACE("A* Faild to find a path! Try a smaller gridsize.");
543
544     pathlib_cleanup();
545
546     return NULL;
547 }