Bot AI: improve ladder usage
[xonotic/xonotic-data.pk3dir.git] / qcsrc / server / bot / default / navigation.qc
1 #include "navigation.qh"
2
3 #include "cvars.qh"
4
5 #include "bot.qh"
6 #include "waypoints.qh"
7
8 #include <common/t_items.qh>
9
10 #include <common/items/_mod.qh>
11
12 #include <common/constants.qh>
13 #include <common/net_linked.qh>
14 #include <common/triggers/trigger/jumppads.qh>
15
16 .float speed;
17
18 void navigation_dynamicgoal_init(entity this, bool initially_static)
19 {
20         this.navigation_dynamicgoal = true;
21         this.bot_basewaypoint = this.nearestwaypoint;
22         if(initially_static)
23                 this.nearestwaypointtimeout = -1;
24         else
25                 this.nearestwaypointtimeout = time;
26 }
27
28 void navigation_dynamicgoal_set(entity this)
29 {
30         this.nearestwaypointtimeout = time;
31 }
32
33 void navigation_dynamicgoal_unset(entity this)
34 {
35         if(this.bot_basewaypoint)
36                 this.nearestwaypoint = this.bot_basewaypoint;
37         this.nearestwaypointtimeout = -1;
38 }
39
40 // rough simulation of walking from one point to another to test if a path
41 // can be traveled, used for waypoint linking and havocbot
42
43 bool tracewalk(entity e, vector start, vector m1, vector m2, vector end, float movemode)
44 {
45         vector org;
46         vector move;
47         vector dir;
48         float dist;
49         float totaldist;
50         float stepdist;
51         float ignorehazards;
52         float swimming;
53         entity tw_ladder = NULL;
54
55         if(autocvar_bot_debug_tracewalk)
56         {
57                 debugresetnodes();
58                 debugnode(e, start);
59         }
60
61         move = end - start;
62         move.z = 0;
63         org = start;
64         dist = totaldist = vlen(move);
65         dir = normalize(move);
66         stepdist = 32;
67         ignorehazards = false;
68         swimming = false;
69
70         // Analyze starting point
71         traceline(start, start, MOVE_NORMAL, e);
72         if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
73                 ignorehazards = true;
74         else
75         {
76                 traceline( start, start + '0 0 -65536', MOVE_NORMAL, e);
77                 if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
78                 {
79                         ignorehazards = true;
80                         swimming = true;
81                 }
82         }
83         tracebox(start, m1, m2, start, MOVE_NOMONSTERS, e);
84         if (trace_startsolid)
85         {
86                 // Bad start
87                 if(autocvar_bot_debug_tracewalk)
88                         debugnodestatus(start, DEBUG_NODE_FAIL);
89
90                 //print("tracewalk: ", vtos(start), " is a bad start\n");
91                 return false;
92         }
93
94         // Movement loop
95         move = end - org;
96         for (;;)
97         {
98                 if (boxesoverlap(end, end, org + m1 + '-1 -1 -1', org + m2 + '1 1 1'))
99                 {
100                         // Succeeded
101                         if(autocvar_bot_debug_tracewalk)
102                                 debugnodestatus(org, DEBUG_NODE_SUCCESS);
103
104                         //print("tracewalk: ", vtos(start), " can reach ", vtos(end), "\n");
105                         return true;
106                 }
107                 if(autocvar_bot_debug_tracewalk)
108                         debugnode(e, org);
109
110                 if (dist <= 0)
111                         break;
112                 if (stepdist > dist)
113                         stepdist = dist;
114                 dist = dist - stepdist;
115                 traceline(org, org, MOVE_NORMAL, e);
116                 if (!ignorehazards)
117                 {
118                         if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
119                         {
120                                 // hazards blocking path
121                                 if(autocvar_bot_debug_tracewalk)
122                                         debugnodestatus(org, DEBUG_NODE_FAIL);
123
124                                 //print("tracewalk: ", vtos(start), " hits a hazard when trying to reach ", vtos(end), "\n");
125                                 return false;
126                         }
127                 }
128                 if (trace_dpstartcontents & DPCONTENTS_LIQUIDSMASK)
129                 {
130                         move = normalize(end - org);
131                         tracebox(org, m1, m2, org + move * stepdist, movemode, e);
132
133                         if(autocvar_bot_debug_tracewalk)
134                                 debugnode(e, trace_endpos);
135
136                         if (trace_fraction < 1)
137                         {
138                                 swimming = true;
139                                 org = trace_endpos - normalize(org - trace_endpos) * stepdist;
140                                 for (; org.z < end.z + e.maxs.z; org.z += stepdist)
141                                 {
142                                         if(autocvar_bot_debug_tracewalk)
143                                                 debugnode(e, org);
144
145                                         if(pointcontents(org) == CONTENT_EMPTY)
146                                                 break;
147                                 }
148
149                                 if(pointcontents(org + '0 0 1') != CONTENT_EMPTY)
150                                 {
151                                         if(autocvar_bot_debug_tracewalk)
152                                                 debugnodestatus(org, DEBUG_NODE_FAIL);
153
154                                         return false;
155                                         //print("tracewalk: ", vtos(start), " failed under water\n");
156                                 }
157                                 continue;
158
159                         }
160                         else
161                                 org = trace_endpos;
162                 }
163                 else
164                 {
165                         move = dir * stepdist + org;
166                         tracebox(org, m1, m2, move, movemode, e);
167
168                         if(autocvar_bot_debug_tracewalk)
169                                 debugnode(e, trace_endpos);
170
171                         // hit something
172                         if (trace_fraction < 1)
173                         {
174                                 // check if we can walk over this obstacle, possibly by jumpstepping
175                                 tracebox(org + stepheightvec, m1, m2, move + stepheightvec, movemode, e);
176                                 if (trace_fraction < 1 || trace_startsolid)
177                                 {
178                                         tracebox(org + jumpstepheightvec, m1, m2, move + jumpstepheightvec, movemode, e);
179                                         if (trace_fraction < 1 || trace_startsolid)
180                                         {
181                                                 if(autocvar_bot_debug_tracewalk)
182                                                         debugnodestatus(trace_endpos, DEBUG_NODE_WARNING);
183
184                                                 FOREACH_ENTITY_CLASS("func_ladder", true,
185                                                         { it.solid = SOLID_BSP; });
186
187                                                 traceline( org, move, movemode, e);
188
189                                                 FOREACH_ENTITY_CLASS("func_ladder", true,
190                                                         { it.solid = SOLID_TRIGGER; });
191
192                                                 if ( trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
193                                                 {
194                                                         vector nextmove;
195                                                         move = trace_endpos;
196                                                         while(trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
197                                                         {
198                                                                 nextmove = move + (dir * stepdist);
199                                                                 traceline( move, nextmove, movemode, e);
200                                                                 move = nextmove;
201                                                         }
202                                                 }
203                                                 else if (trace_ent.classname == "func_ladder")
204                                                 {
205                                                         tw_ladder = trace_ent;
206                                                         vector ladder_bottom = trace_endpos - dir * m2.x;
207                                                         vector ladder_top = ladder_bottom;
208                                                         ladder_top.z = trace_ent.absmax.z + (-m1.z + 1);
209                                                         tracebox(ladder_bottom, m1, m2, ladder_top, movemode, e);
210                                                         if (trace_fraction < 1 || trace_startsolid)
211                                                         {
212                                                                 if(autocvar_bot_debug_tracewalk)
213                                                                         debugnodestatus(trace_endpos, DEBUG_NODE_FAIL);
214
215                                                                 return false; // failed
216                                                         }
217                                                         org = ladder_top + dir * m2.x;
218                                                         move = org + dir * stepdist;
219                                                         continue;
220                                                 }
221                                                 else
222                                                 {
223                                                         if(autocvar_bot_debug_tracewalk)
224                                                                 debugnodestatus(trace_endpos, DEBUG_NODE_FAIL);
225
226                                                         //print("tracewalk: ", vtos(start), " hit something when trying to reach ", vtos(end), "\n");
227                                                         //te_explosion(trace_endpos);
228                                                         //print(ftos(e.dphitcontentsmask), "\n");
229                                                         return false; // failed
230                                                 }
231                                         }
232                                         else
233                                                 move = trace_endpos;
234                                 }
235                                 else
236                                         move = trace_endpos;
237                         }
238                         else
239                                 move = trace_endpos;
240
241                         // trace down from stepheight as far as possible and move there,
242                         // if this starts in solid we try again without the stepup, and
243                         // if that also fails we assume it is a wall
244                         // (this is the same logic as the Quake walkmove function used)
245                         tracebox(move, m1, m2, move + '0 0 -65536', movemode, e);
246
247                         // moved successfully
248                         if(swimming)
249                         {
250                                 float c;
251                                 c = pointcontents(org + '0 0 1');
252                                 if (!(c == CONTENT_WATER || c == CONTENT_LAVA || c == CONTENT_SLIME))
253                                         swimming = false;
254                                 else
255                                         continue;
256                         }
257
258                         org = trace_endpos;
259                 }
260
261                 if(tw_ladder && org.z < tw_ladder.absmax.z)
262                 {
263                         // stop tracewalk if destination height is lower than the top of the ladder
264                         // otherwise bot can't easily figure out climbing direction
265                         if(autocvar_bot_debug_tracewalk)
266                                 debugnodestatus(org, DEBUG_NODE_FAIL);
267
268                         return false;
269                 }
270         }
271
272         //print("tracewalk: ", vtos(start), " did not arrive at ", vtos(end), " but at ", vtos(org), "\n");
273
274         // moved but didn't arrive at the intended destination
275         if(autocvar_bot_debug_tracewalk)
276                 debugnodestatus(org, DEBUG_NODE_FAIL);
277
278         return false;
279 }
280
281 /////////////////////////////////////////////////////////////////////////////
282 // goal stack
283 /////////////////////////////////////////////////////////////////////////////
284
285 // completely empty the goal stack, used when deciding where to go
286 void navigation_clearroute(entity this)
287 {
288         //print("bot ", etos(this), " clear\n");
289         this.goalentity = NULL;
290         this.goalcurrent = NULL;
291         this.goalstack01 = NULL;
292         this.goalstack02 = NULL;
293         this.goalstack03 = NULL;
294         this.goalstack04 = NULL;
295         this.goalstack05 = NULL;
296         this.goalstack06 = NULL;
297         this.goalstack07 = NULL;
298         this.goalstack08 = NULL;
299         this.goalstack09 = NULL;
300         this.goalstack10 = NULL;
301         this.goalstack11 = NULL;
302         this.goalstack12 = NULL;
303         this.goalstack13 = NULL;
304         this.goalstack14 = NULL;
305         this.goalstack15 = NULL;
306         this.goalstack16 = NULL;
307         this.goalstack17 = NULL;
308         this.goalstack18 = NULL;
309         this.goalstack19 = NULL;
310         this.goalstack20 = NULL;
311         this.goalstack21 = NULL;
312         this.goalstack22 = NULL;
313         this.goalstack23 = NULL;
314         this.goalstack24 = NULL;
315         this.goalstack25 = NULL;
316         this.goalstack26 = NULL;
317         this.goalstack27 = NULL;
318         this.goalstack28 = NULL;
319         this.goalstack29 = NULL;
320         this.goalstack30 = NULL;
321         this.goalstack31 = NULL;
322 }
323
324 // add a new goal at the beginning of the stack
325 // (in other words: add a new prerequisite before going to the later goals)
326 // NOTE: when a waypoint is added, the WP gets pushed first, then the
327 // next-closest WP on the shortest path to the WP
328 // That means, if the stack overflows, the bot will know how to do the FIRST 32
329 // steps to the goal, and then recalculate the path.
330 void navigation_pushroute(entity this, entity e)
331 {
332         //print("bot ", etos(this), " push ", etos(e), "\n");
333         if(this.goalstack31 == this.goalentity)
334                 this.goalentity = NULL;
335         this.goalstack31 = this.goalstack30;
336         this.goalstack30 = this.goalstack29;
337         this.goalstack29 = this.goalstack28;
338         this.goalstack28 = this.goalstack27;
339         this.goalstack27 = this.goalstack26;
340         this.goalstack26 = this.goalstack25;
341         this.goalstack25 = this.goalstack24;
342         this.goalstack24 = this.goalstack23;
343         this.goalstack23 = this.goalstack22;
344         this.goalstack22 = this.goalstack21;
345         this.goalstack21 = this.goalstack20;
346         this.goalstack20 = this.goalstack19;
347         this.goalstack19 = this.goalstack18;
348         this.goalstack18 = this.goalstack17;
349         this.goalstack17 = this.goalstack16;
350         this.goalstack16 = this.goalstack15;
351         this.goalstack15 = this.goalstack14;
352         this.goalstack14 = this.goalstack13;
353         this.goalstack13 = this.goalstack12;
354         this.goalstack12 = this.goalstack11;
355         this.goalstack11 = this.goalstack10;
356         this.goalstack10 = this.goalstack09;
357         this.goalstack09 = this.goalstack08;
358         this.goalstack08 = this.goalstack07;
359         this.goalstack07 = this.goalstack06;
360         this.goalstack06 = this.goalstack05;
361         this.goalstack05 = this.goalstack04;
362         this.goalstack04 = this.goalstack03;
363         this.goalstack03 = this.goalstack02;
364         this.goalstack02 = this.goalstack01;
365         this.goalstack01 = this.goalcurrent;
366         this.goalcurrent = e;
367 }
368
369 // remove first goal from stack
370 // (in other words: remove a prerequisite for reaching the later goals)
371 // (used when a spawnfunc_waypoint is reached)
372 void navigation_poproute(entity this)
373 {
374         //print("bot ", etos(this), " pop\n");
375         if(this.goalcurrent == this.goalentity)
376                 this.goalentity = NULL;
377         this.goalcurrent = this.goalstack01;
378         this.goalstack01 = this.goalstack02;
379         this.goalstack02 = this.goalstack03;
380         this.goalstack03 = this.goalstack04;
381         this.goalstack04 = this.goalstack05;
382         this.goalstack05 = this.goalstack06;
383         this.goalstack06 = this.goalstack07;
384         this.goalstack07 = this.goalstack08;
385         this.goalstack08 = this.goalstack09;
386         this.goalstack09 = this.goalstack10;
387         this.goalstack10 = this.goalstack11;
388         this.goalstack11 = this.goalstack12;
389         this.goalstack12 = this.goalstack13;
390         this.goalstack13 = this.goalstack14;
391         this.goalstack14 = this.goalstack15;
392         this.goalstack15 = this.goalstack16;
393         this.goalstack16 = this.goalstack17;
394         this.goalstack17 = this.goalstack18;
395         this.goalstack18 = this.goalstack19;
396         this.goalstack19 = this.goalstack20;
397         this.goalstack20 = this.goalstack21;
398         this.goalstack21 = this.goalstack22;
399         this.goalstack22 = this.goalstack23;
400         this.goalstack23 = this.goalstack24;
401         this.goalstack24 = this.goalstack25;
402         this.goalstack25 = this.goalstack26;
403         this.goalstack26 = this.goalstack27;
404         this.goalstack27 = this.goalstack28;
405         this.goalstack28 = this.goalstack29;
406         this.goalstack29 = this.goalstack30;
407         this.goalstack30 = this.goalstack31;
408         this.goalstack31 = NULL;
409 }
410
411 float navigation_waypoint_will_link(vector v, vector org, entity ent, float walkfromwp, float bestdist)
412 {
413         float dist;
414         dist = vlen(v - org);
415         if (bestdist > dist)
416         {
417                 traceline(v, org, true, ent);
418                 if (trace_fraction == 1)
419                 {
420                         if (walkfromwp)
421                         {
422                                 if (tracewalk(ent, v, PL_MIN_CONST, PL_MAX_CONST, org, bot_navigation_movemode))
423                                         return true;
424                         }
425                         else
426                         {
427                                 if (tracewalk(ent, org, PL_MIN_CONST, PL_MAX_CONST, v, bot_navigation_movemode))
428                                         return true;
429                         }
430                 }
431         }
432         return false;
433 }
434
435 // find the spawnfunc_waypoint near a dynamic goal such as a dropped weapon
436 entity navigation_findnearestwaypoint_withdist_except(entity ent, float walkfromwp, float bestdist, entity except)
437 {
438         vector pm1 = ent.origin + ent.mins;
439         vector pm2 = ent.origin + ent.maxs;
440
441         // do two scans, because box test is cheaper
442         IL_EACH(g_waypoints, it != ent && it != except,
443         {
444                 if(boxesoverlap(pm1, pm2, it.absmin, it.absmax))
445                         return it;
446         });
447
448         vector org = ent.origin + 0.5 * (ent.mins + ent.maxs);
449         org.z = ent.origin.z + ent.mins.z - PL_MIN_CONST.z; // player height
450         // TODO possibly make other code have the same support for bboxes
451         if(ent.tag_entity)
452                 org = org + ent.tag_entity.origin;
453         if (navigation_testtracewalk)
454                 te_plasmaburn(org);
455
456         entity best = NULL;
457         vector v;
458
459         // box check failed, try walk
460         IL_EACH(g_waypoints, it != ent,
461         {
462                 if(it.wpisbox)
463                 {
464                         vector wm1 = it.origin + it.mins;
465                         vector wm2 = it.origin + it.maxs;
466                         v.x = bound(wm1_x, org.x, wm2_x);
467                         v.y = bound(wm1_y, org.y, wm2_y);
468                         v.z = bound(wm1_z, org.z, wm2_z);
469                 }
470                 else
471                         v = it.origin;
472                 if(navigation_waypoint_will_link(v, org, ent, walkfromwp, bestdist))
473                 {
474                         bestdist = vlen(v - org);
475                         best = it;
476                 }
477         });
478         return best;
479 }
480 entity navigation_findnearestwaypoint(entity ent, float walkfromwp)
481 {
482         entity wp = navigation_findnearestwaypoint_withdist_except(ent, walkfromwp, 1050, NULL);
483         if (autocvar_g_waypointeditor_auto)
484         {
485                 entity wp2 = navigation_findnearestwaypoint_withdist_except(ent, walkfromwp, 1050, wp);
486                 if (wp && !wp2)
487                         wp.wpflags |= WAYPOINTFLAG_PROTECTED;
488         }
489         return wp;
490 }
491
492 // finds the waypoints near the bot initiating a navigation query
493 float navigation_markroutes_nearestwaypoints(entity this, float maxdist)
494 {
495         vector v, m1, m2;
496 //      navigation_testtracewalk = true;
497         int c = 0;
498         IL_EACH(g_waypoints, !it.wpconsidered,
499         {
500                 if (it.wpisbox)
501                 {
502                         m1 = it.origin + it.mins;
503                         m2 = it.origin + it.maxs;
504                         v = this.origin;
505                         v.x = bound(m1_x, v.x, m2_x);
506                         v.y = bound(m1_y, v.y, m2_y);
507                         v.z = bound(m1_z, v.z, m2_z);
508                 }
509                 else
510                         v = it.origin;
511                 vector diff = v - this.origin;
512                 diff.z = max(0, diff.z);
513                 if(vdist(diff, <, maxdist))
514                 {
515                         it.wpconsidered = true;
516                         if (tracewalk(this, this.origin, this.mins, this.maxs, v, bot_navigation_movemode))
517                         {
518                                 it.wpnearestpoint = v;
519                                 it.wpcost = vlen(v - this.origin) + it.dmg;
520                                 it.wpfire = 1;
521                                 it.enemy = NULL;
522                                 c = c + 1;
523                         }
524                 }
525         });
526         //navigation_testtracewalk = false;
527         return c;
528 }
529
530 // updates a path link if a spawnfunc_waypoint link is better than the current one
531 void navigation_markroutes_checkwaypoint(entity w, entity wp, float cost2, vector p)
532 {
533         vector m1;
534         vector m2;
535         vector v;
536         if (wp.wpisbox)
537         {
538                 m1 = wp.absmin;
539                 m2 = wp.absmax;
540                 v.x = bound(m1_x, p.x, m2_x);
541                 v.y = bound(m1_y, p.y, m2_y);
542                 v.z = bound(m1_z, p.z, m2_z);
543         }
544         else
545                 v = wp.origin;
546         cost2 = cost2 + vlen(v - p);
547         if (wp.wpcost > cost2)
548         {
549                 wp.wpcost = cost2;
550                 wp.enemy = w;
551                 wp.wpfire = 1;
552                 wp.wpnearestpoint = v;
553         }
554 }
555
556 // queries the entire spawnfunc_waypoint network for pathes leading away from the bot
557 void navigation_markroutes(entity this, entity fixed_source_waypoint)
558 {
559         float cost, cost2;
560         vector p;
561
562         IL_EACH(g_waypoints, true,
563         {
564                 it.wpconsidered = false;
565                 it.wpnearestpoint = '0 0 0';
566                 it.wpcost = 10000000;
567                 it.wpfire = 0;
568                 it.enemy = NULL;
569         });
570
571         if(fixed_source_waypoint)
572         {
573                 fixed_source_waypoint.wpconsidered = true;
574                 fixed_source_waypoint.wpnearestpoint = fixed_source_waypoint.origin + 0.5 * (fixed_source_waypoint.mins + fixed_source_waypoint.maxs);
575                 fixed_source_waypoint.wpcost = fixed_source_waypoint.dmg;
576                 fixed_source_waypoint.wpfire = 1;
577                 fixed_source_waypoint.enemy = NULL;
578         }
579         else
580         {
581                 // try a short range search for the nearest waypoints, and expand the search repeatedly if none are found
582                 // as this search is expensive we will use lower values if the bot is on the air
583                 float increment, maxdistance;
584                 if(IS_ONGROUND(this))
585                 {
586                         increment = 750;
587                         maxdistance = 50000;
588                 }
589                 else
590                 {
591                         increment = 500;
592                         maxdistance = 1500;
593                 }
594
595                 for(int j = increment; !navigation_markroutes_nearestwaypoints(this, j) && j < maxdistance; j += increment);
596         }
597
598         bool searching = true;
599         while (searching)
600         {
601                 searching = false;
602                 IL_EACH(g_waypoints, it.wpfire,
603                 {
604                         searching = true;
605                         it.wpfire = 0;
606                         cost = it.wpcost;
607                         p = it.wpnearestpoint;
608                         entity wp;
609                         wp = it.wp00;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp00mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
610                         wp = it.wp01;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp01mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
611                         wp = it.wp02;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp02mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
612                         wp = it.wp03;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp03mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
613                         wp = it.wp04;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp04mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
614                         wp = it.wp05;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp05mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
615                         wp = it.wp06;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp06mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
616                         wp = it.wp07;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp07mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
617                         wp = it.wp08;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp08mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
618                         wp = it.wp09;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp09mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
619                         wp = it.wp10;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp10mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
620                         wp = it.wp11;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp11mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
621                         wp = it.wp12;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp12mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
622                         wp = it.wp13;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp13mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
623                         wp = it.wp14;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp14mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
624                         wp = it.wp15;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp15mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
625                         wp = it.wp16;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp16mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
626                         wp = it.wp17;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp17mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
627                         wp = it.wp18;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp18mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
628                         wp = it.wp19;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp19mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
629                         wp = it.wp20;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp20mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
630                         wp = it.wp21;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp21mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
631                         wp = it.wp22;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp22mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
632                         wp = it.wp23;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp23mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
633                         wp = it.wp24;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp24mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
634                         wp = it.wp25;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp25mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
635                         wp = it.wp26;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp26mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
636                         wp = it.wp27;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp27mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
637                         wp = it.wp28;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp28mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
638                         wp = it.wp29;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp29mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
639                         wp = it.wp30;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp30mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
640                         wp = it.wp31;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + it.wp31mincost) navigation_markroutes_checkwaypoint(it, wp, cost2, p);
641                         }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
642                 });
643         }
644 }
645
646 // queries the entire spawnfunc_waypoint network for pathes leading to the bot
647 void navigation_markroutes_inverted(entity fixed_source_waypoint)
648 {
649         float cost, cost2;
650         vector p;
651         IL_EACH(g_waypoints, true,
652         {
653                 it.wpconsidered = false;
654                 it.wpnearestpoint = '0 0 0';
655                 it.wpcost = 10000000;
656                 it.wpfire = 0;
657                 it.enemy = NULL;
658         });
659
660         if(fixed_source_waypoint)
661         {
662                 fixed_source_waypoint.wpconsidered = true;
663                 fixed_source_waypoint.wpnearestpoint = fixed_source_waypoint.origin + 0.5 * (fixed_source_waypoint.mins + fixed_source_waypoint.maxs);
664                 fixed_source_waypoint.wpcost = fixed_source_waypoint.dmg; // the cost to get from X to fixed_source_waypoint
665                 fixed_source_waypoint.wpfire = 1;
666                 fixed_source_waypoint.enemy = NULL;
667         }
668         else
669         {
670                 error("need to start with a waypoint\n");
671         }
672
673         bool searching = true;
674         while (searching)
675         {
676                 searching = false;
677                 IL_EACH(g_waypoints, it.wpfire,
678                 {
679                         searching = true;
680                         it.wpfire = 0;
681                         cost = it.wpcost; // cost to walk from it to home
682                         p = it.wpnearestpoint;
683                         entity wp = it;
684                         IL_EACH(g_waypoints, true,
685                         {
686                                 if(wp != it.wp00) if(wp != it.wp01) if(wp != it.wp02) if(wp != it.wp03)
687                                 if(wp != it.wp04) if(wp != it.wp05) if(wp != it.wp06) if(wp != it.wp07)
688                                 if(wp != it.wp08) if(wp != it.wp09) if(wp != it.wp10) if(wp != it.wp11)
689                                 if(wp != it.wp12) if(wp != it.wp13) if(wp != it.wp14) if(wp != it.wp15)
690                                 if(wp != it.wp16) if(wp != it.wp17) if(wp != it.wp18) if(wp != it.wp19)
691                                 if(wp != it.wp20) if(wp != it.wp21) if(wp != it.wp22) if(wp != it.wp23)
692                                 if(wp != it.wp24) if(wp != it.wp25) if(wp != it.wp26) if(wp != it.wp27)
693                                 if(wp != it.wp28) if(wp != it.wp29) if(wp != it.wp30) if(wp != it.wp31)
694                                         continue;
695                                 cost2 = cost + it.dmg;
696                                 navigation_markroutes_checkwaypoint(wp, it, cost2, p);
697                         });
698                 });
699         }
700 }
701
702 // updates the best goal according to a weighted calculation of travel cost and item value of a new proposed item
703 void navigation_routerating(entity this, entity e, float f, float rangebias)
704 {
705         if (!e)
706                 return;
707
708         if(e.blacklisted)
709                 return;
710
711         if (IS_PLAYER(e))
712         {
713                 bool rate_wps = false;
714                 if((e.flags & FL_INWATER) || (e.flags & FL_PARTIALGROUND))
715                         rate_wps = true;
716
717                 if(!IS_ONGROUND(e))
718                 {
719                         traceline(e.origin, e.origin + '0 0 -1500', true, NULL);
720                         int t = pointcontents(trace_endpos + '0 0 1');
721                         if(t != CONTENT_SOLID )
722                         {
723                                 if(t == CONTENT_WATER || t == CONTENT_SLIME || t == CONTENT_LAVA)
724                                         rate_wps = true;
725                                 else if(tracebox_hits_trigger_hurt(e.origin, e.mins, e.maxs, trace_endpos))
726                                         return;
727                         }
728                 }
729
730                 if(rate_wps)
731                 {
732                         entity theEnemy = e;
733                         entity best_wp = NULL;
734                         float best_dist = 10000;
735                         IL_EACH(g_waypoints, vdist(it.origin - theEnemy.origin, <, 500)
736                                 && vdist(it.origin - this.origin, >, 100)
737                                 && !(it.wpflags & WAYPOINTFLAG_TELEPORT),
738                         {
739                                 float dist = vlen(it.origin - theEnemy.origin);
740                                 if (dist < best_dist)
741                                 {
742                                         best_wp = it;
743                                         best_dist = dist;
744                                 }
745                         });
746                         if (!best_wp)
747                                 return;
748                         e = best_wp;
749                 }
750         }
751
752         vector o = (e.absmin + e.absmax) * 0.5;
753
754         //print("routerating ", etos(e), " = ", ftos(f), " - ", ftos(rangebias), "\n");
755
756         // Evaluate path using jetpack
757         if(g_jetpack)
758         if(this.items & IT_JETPACK)
759         if(autocvar_bot_ai_navigation_jetpack)
760         if(vdist(this.origin - o, >, autocvar_bot_ai_navigation_jetpack_mindistance))
761         {
762                 vector pointa, pointb;
763
764                 LOG_DEBUG("jetpack ai: evaluating path for ", e.classname);
765
766                 // Point A
767                 traceline(this.origin, this.origin + '0 0 65535', MOVE_NORMAL, this);
768                 pointa = trace_endpos - '0 0 1';
769
770                 // Point B
771                 traceline(o, o + '0 0 65535', MOVE_NORMAL, e);
772                 pointb = trace_endpos - '0 0 1';
773
774                 // Can I see these two points from the sky?
775                 traceline(pointa, pointb, MOVE_NORMAL, this);
776
777                 if(trace_fraction==1)
778                 {
779                         LOG_DEBUG("jetpack ai: can bridge these two points");
780
781                         // Lower the altitude of these points as much as possible
782                         float zdistance, xydistance, cost, t, fuel;
783                         vector down, npa, npb;
784
785                         down = '0 0 -1' * (STAT(PL_MAX, this).z - STAT(PL_MIN, this).z) * 10;
786
787                         do{
788                                 npa = pointa + down;
789                                 npb = pointb + down;
790
791                                 if(npa.z<=this.absmax.z)
792                                         break;
793
794                                 if(npb.z<=e.absmax.z)
795                                         break;
796
797                                 traceline(npa, npb, MOVE_NORMAL, this);
798                                 if(trace_fraction==1)
799                                 {
800                                         pointa = npa;
801                                         pointb = npb;
802                                 }
803                         }
804                         while(trace_fraction == 1);
805
806
807                         // Rough estimation of fuel consumption
808                         // (ignores acceleration and current xyz velocity)
809                         xydistance = vlen(pointa - pointb);
810                         zdistance = fabs(pointa.z - this.origin.z);
811
812                         t = zdistance / autocvar_g_jetpack_maxspeed_up;
813                         t += xydistance / autocvar_g_jetpack_maxspeed_side;
814                         fuel = t * autocvar_g_jetpack_fuel * 0.8;
815
816                         LOG_DEBUG("jetpack ai: required fuel ", ftos(fuel), " this.ammo_fuel ", ftos(this.ammo_fuel));
817
818                         // enough fuel ?
819                         if(this.ammo_fuel>fuel)
820                         {
821                                 // Estimate cost
822                                 // (as onground costs calculation is mostly based on distances, here we do the same establishing some relationship
823                                 //  - between air and ground speeds)
824
825                                 cost = xydistance / (autocvar_g_jetpack_maxspeed_side/autocvar_sv_maxspeed);
826                                 cost += zdistance / (autocvar_g_jetpack_maxspeed_up/autocvar_sv_maxspeed);
827                                 cost *= 1.5;
828
829                                 // Compare against other goals
830                                 f = f * rangebias / (rangebias + cost);
831
832                                 if (navigation_bestrating < f)
833                                 {
834                                         LOG_DEBUG("jetpack path: added goal ", e.classname, " (with rating ", ftos(f), ")");
835                                         navigation_bestrating = f;
836                                         navigation_bestgoal = e;
837                                         this.navigation_jetpack_goal = e;
838                                         this.navigation_jetpack_point = pointb;
839                                 }
840                                 return;
841                         }
842                 }
843         }
844
845         entity nwp;
846         //te_wizspike(e.origin);
847         //bprint(etos(e));
848         //bprint("\n");
849         // update the cached spawnfunc_waypoint link on a dynamic item entity
850         if(e.classname == "waypoint" && !(e.wpflags & WAYPOINTFLAG_PERSONAL))
851         {
852                 nwp = e;
853         }
854         else
855         {
856                 if ((!e.nearestwaypoint || e.navigation_dynamicgoal)
857                         && e.nearestwaypointtimeout >= 0 && time > e.nearestwaypointtimeout)
858                 {
859                         nwp = navigation_findnearestwaypoint(e, true);
860                         if(nwp)
861                                 e.nearestwaypoint = nwp;
862                         else
863                         {
864                                 LOG_DEBUG("FAILED to find a nearest waypoint to '", e.classname, "' #", etos(e));
865
866                                 if(!e.navigation_dynamicgoal)
867                                         e.blacklisted = true;
868
869                                 if(e.blacklisted)
870                                 {
871                                         LOG_DEBUG("The entity '", e.classname, "' is going to be excluded from path finding during this match");
872                                         return;
873                                 }
874                         }
875
876                         if(e.navigation_dynamicgoal)
877                                 e.nearestwaypointtimeout = time + 2;
878                 }
879                 nwp = e.nearestwaypoint;
880         }
881
882         LOG_DEBUG("-- checking ", e.classname, " (with cost ", ftos(nwp.wpcost), ")");
883         if (nwp)
884         if (nwp.wpcost < 10000000)
885         {
886                 //te_wizspike(nwp.wpnearestpoint);
887                 LOG_DEBUG(e.classname, " ", ftos(f), "/(1+", ftos((nwp.wpcost + vlen(e.origin - nwp.wpnearestpoint))), "/", ftos(rangebias), ") = ");
888                 f = f * rangebias / (rangebias + (nwp.wpcost + vlen(o - nwp.wpnearestpoint)));
889                 LOG_DEBUG("considering ", e.classname, " (with rating ", ftos(f), ")");
890                 if (navigation_bestrating < f)
891                 {
892                         LOG_DEBUG("ground path: added goal ", e.classname, " (with rating ", ftos(f), ")");
893                         navigation_bestrating = f;
894                         navigation_bestgoal = e;
895                 }
896         }
897 }
898
899 // adds an item to the the goal stack with the path to a given item
900 bool navigation_routetogoal(entity this, entity e, vector startposition)
901 {
902         // if there is no goal, just exit
903         if (!e)
904                 return false;
905
906         this.goalentity = e;
907
908         // put the entity on the goal stack
909         //print("routetogoal ", etos(e), "\n");
910         navigation_pushroute(this, e);
911
912         if(e.classname == "waypoint" && !(e.wpflags & WAYPOINTFLAG_PERSONAL))
913         {
914                 this.wp_goal_prev1 = this.wp_goal_prev0;
915                 this.wp_goal_prev0 = e;
916         }
917
918         if(g_jetpack)
919         if(e==this.navigation_jetpack_goal)
920                 return true;
921
922         // if it can reach the goal there is nothing more to do
923         if (tracewalk(this, startposition, STAT(PL_MIN, this), STAT(PL_MAX, this), (e.absmin + e.absmax) * 0.5, bot_navigation_movemode))
924                 return true;
925
926         entity nearest_wp = NULL;
927         // see if there are waypoints describing a path to the item
928         if(e.classname != "waypoint" || (e.wpflags & WAYPOINTFLAG_PERSONAL))
929         {
930                 e = e.nearestwaypoint;
931                 nearest_wp = e;
932         }
933         else
934                 e = e.enemy; // we already have added it, so...
935
936         if(e == NULL)
937                 return false;
938
939         if(nearest_wp && nearest_wp.enemy)
940         {
941                 // often path can be optimized by not adding the nearest waypoint
942                 if(tracewalk(this, nearest_wp.enemy.origin, STAT(PL_MIN, this), STAT(PL_MAX, this), (this.goalentity.absmin + this.goalentity.absmax) * 0.5, bot_navigation_movemode))
943                         e = nearest_wp.enemy;
944         }
945
946         for (;;)
947         {
948                 // add the spawnfunc_waypoint to the path
949                 navigation_pushroute(this, e);
950                 e = e.enemy;
951
952                 if(e==NULL)
953                         break;
954         }
955
956         return false;
957 }
958
959 // removes any currently touching waypoints from the goal stack
960 // (this is how bots detect if they reached a goal)
961 void navigation_poptouchedgoals(entity this)
962 {
963         vector org, m1, m2;
964         org = this.origin;
965         m1 = org + this.mins;
966         m2 = org + this.maxs;
967
968         if(this.goalcurrent.wpflags & WAYPOINTFLAG_TELEPORT)
969         {
970                 // make sure jumppad is really hit, don't rely on distance based checks
971                 // as they may report a touch even if it didn't really happen
972                 if(this.lastteleporttime>0)
973                 if(time - this.lastteleporttime < ((this.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL) ? 2 : 0.15))
974                 {
975                         if(this.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
976                         if(this.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && this.goalcurrent.owner==this)
977                         {
978                                 this.aistatus &= ~AI_STATUS_WAYPOINT_PERSONAL_GOING;
979                                 this.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
980                         }
981                         navigation_poproute(this);
982                         return;
983                 }
984         }
985
986         // If for some reason the bot is closer to the next goal, pop the current one
987         if(this.goalstack01 && !wasfreed(this.goalstack01))
988         if(vlen2(this.goalcurrent.origin - this.origin) > vlen2(this.goalstack01.origin - this.origin))
989         if(checkpvs(this.origin + this.view_ofs, this.goalstack01))
990         if(tracewalk(this, this.origin, this.mins, this.maxs, (this.goalstack01.absmin + this.goalstack01.absmax) * 0.5, bot_navigation_movemode))
991         {
992                 LOG_DEBUG("path optimized for ", this.netname, ", removed a goal from the queue");
993                 navigation_poproute(this);
994                 // TODO this may also be a nice idea to do "early" (e.g. by
995                 // manipulating the vlen() comparisons) to shorten paths in
996                 // general - this would make bots walk more "on rails" than
997                 // "zigzagging" which they currently do with sufficiently
998                 // random-like waypoints, and thus can make a nice bot
999                 // personality property
1000         }
1001
1002         // Loose goal touching check when running
1003         if(this.aistatus & AI_STATUS_RUNNING)
1004         if(this.goalcurrent.classname=="waypoint")
1005         if(!(this.goalcurrent.wpflags & WAYPOINTFLAG_TELEPORT))
1006         if(vlen(this.velocity - eZ * this.velocity.z) >= autocvar_sv_maxspeed) // if -really- running
1007         {
1008                 if(vdist(this.origin - this.goalcurrent.origin, <, 150))
1009                 {
1010                         traceline(this.origin + this.view_ofs , this.goalcurrent.origin, true, NULL);
1011                         if(trace_fraction==1)
1012                         {
1013                                 // Detect personal waypoints
1014                                 if(this.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
1015                                 if(this.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && this.goalcurrent.owner==this)
1016                                 {
1017                                         this.aistatus &= ~AI_STATUS_WAYPOINT_PERSONAL_GOING;
1018                                         this.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
1019                                 }
1020
1021                                 navigation_poproute(this);
1022                         }
1023                 }
1024         }
1025
1026         while (this.goalcurrent && !IS_PLAYER(this.goalcurrent))
1027         {
1028                 vector gc_min = this.goalcurrent.absmin;
1029                 vector gc_max = this.goalcurrent.absmax;
1030                 if(this.goalcurrent.classname == "waypoint" && !this.goalcurrent.wpisbox)
1031                 {
1032                         gc_min = this.goalcurrent.origin - '1 1 1' * 12;
1033                         gc_max = this.goalcurrent.origin + '1 1 1' * 12;
1034                 }
1035                 if(!boxesoverlap(m1, m2, gc_min, gc_max))
1036                         break;
1037
1038                 if((this.goalcurrent.wpflags & WAYPOINTFLAG_TELEPORT))
1039                         break;
1040
1041                 // Detect personal waypoints
1042                 if(this.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
1043                 if(this.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && this.goalcurrent.owner==this)
1044                 {
1045                         this.aistatus &= ~AI_STATUS_WAYPOINT_PERSONAL_GOING;
1046                         this.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
1047                 }
1048
1049                 navigation_poproute(this);
1050         }
1051 }
1052
1053 // begin a goal selection session (queries spawnfunc_waypoint network)
1054 void navigation_goalrating_start(entity this)
1055 {
1056         if(this.aistatus & AI_STATUS_STUCK)
1057                 return;
1058
1059         this.navigation_jetpack_goal = NULL;
1060         navigation_bestrating = -1;
1061         navigation_clearroute(this);
1062         navigation_bestgoal = NULL;
1063         navigation_markroutes(this, NULL);
1064 }
1065
1066 // ends a goal selection session (updates goal stack to the best goal)
1067 void navigation_goalrating_end(entity this)
1068 {
1069         if(this.aistatus & AI_STATUS_STUCK)
1070                 return;
1071
1072         navigation_routetogoal(this, navigation_bestgoal, this.origin);
1073         LOG_DEBUG("best goal ", this.goalcurrent.classname);
1074
1075         // If the bot got stuck then try to reach the farthest waypoint
1076         if (!this.goalentity && autocvar_bot_wander_enable)
1077         {
1078                 if (!(this.aistatus & AI_STATUS_STUCK))
1079                 {
1080                         LOG_DEBUG(this.netname, " cannot walk to any goal");
1081                         this.aistatus |= AI_STATUS_STUCK;
1082                 }
1083         }
1084 }
1085
1086 void botframe_updatedangerousobjects(float maxupdate)
1087 {
1088         vector m1, m2, v, o;
1089         float c, d, danger;
1090         c = 0;
1091         IL_EACH(g_waypoints, true,
1092         {
1093                 danger = 0;
1094                 m1 = it.mins;
1095                 m2 = it.maxs;
1096                 IL_EACH(g_bot_dodge, it.bot_dodge,
1097                 {
1098                         v = it.origin;
1099                         v.x = bound(m1_x, v.x, m2_x);
1100                         v.y = bound(m1_y, v.y, m2_y);
1101                         v.z = bound(m1_z, v.z, m2_z);
1102                         o = (it.absmin + it.absmax) * 0.5;
1103                         d = it.bot_dodgerating - vlen(o - v);
1104                         if (d > 0)
1105                         {
1106                                 traceline(o, v, true, NULL);
1107                                 if (trace_fraction == 1)
1108                                         danger = danger + d;
1109                         }
1110                 });
1111                 it.dmg = danger;
1112                 c = c + 1;
1113                 if (c >= maxupdate)
1114                         break;
1115         });
1116 }
1117
1118 void navigation_unstuck(entity this)
1119 {
1120         float search_radius = 1000;
1121
1122         if (!autocvar_bot_wander_enable)
1123                 return;
1124
1125         if (!bot_waypoint_queue_owner)
1126         {
1127                 LOG_DEBUG(this.netname, " stuck, taking over the waypoints queue");
1128                 bot_waypoint_queue_owner = this;
1129                 bot_waypoint_queue_bestgoal = NULL;
1130                 bot_waypoint_queue_bestgoalrating = 0;
1131         }
1132
1133         if(bot_waypoint_queue_owner!=this)
1134                 return;
1135
1136         if (bot_waypoint_queue_goal)
1137         {
1138                 // evaluate the next goal on the queue
1139                 float d = vlen2(this.origin - bot_waypoint_queue_goal.origin);
1140                 LOG_DEBUG(this.netname, " evaluating ", bot_waypoint_queue_goal.classname, " with distance ", ftos(d));
1141                 if(tracewalk(bot_waypoint_queue_goal, this.origin, STAT(PL_MIN, this), STAT(PL_MAX, this), bot_waypoint_queue_goal.origin, bot_navigation_movemode))
1142                 {
1143                         if( d > bot_waypoint_queue_bestgoalrating)
1144                         {
1145                                 bot_waypoint_queue_bestgoalrating = d;
1146                                 bot_waypoint_queue_bestgoal = bot_waypoint_queue_goal;
1147                         }
1148                 }
1149                 bot_waypoint_queue_goal = bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal;
1150
1151                 if (!bot_waypoint_queue_goal)
1152                 {
1153                         if (bot_waypoint_queue_bestgoal)
1154                         {
1155                                 LOG_DEBUG(this.netname, " stuck, reachable waypoint found, heading to it");
1156                                 navigation_routetogoal(this, bot_waypoint_queue_bestgoal, this.origin);
1157                                 this.bot_strategytime = time + autocvar_bot_ai_strategyinterval;
1158                                 this.aistatus &= ~AI_STATUS_STUCK;
1159                         }
1160                         else
1161                         {
1162                                 LOG_DEBUG(this.netname, " stuck, cannot walk to any waypoint at all");
1163                         }
1164
1165                         bot_waypoint_queue_owner = NULL;
1166                 }
1167         }
1168         else
1169         {
1170                 if(bot_strategytoken!=this)
1171                         return;
1172
1173                 // build a new queue
1174                 LOG_DEBUG(this.netname, " stuck, scanning reachable waypoints within ", ftos(search_radius)," qu");
1175
1176                 entity first = NULL;
1177
1178                 FOREACH_ENTITY_RADIUS(this.origin, search_radius, it.classname == "waypoint" && !(it.wpflags & WAYPOINTFLAG_GENERATED),
1179                 {
1180                         if(bot_waypoint_queue_goal)
1181                                 bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = it;
1182                         else
1183                                 first = it;
1184
1185                         bot_waypoint_queue_goal = it;
1186                         bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = NULL;
1187                 });
1188
1189                 if (first)
1190                         bot_waypoint_queue_goal = first;
1191                 else
1192                 {
1193                         LOG_DEBUG(this.netname, " stuck, cannot walk to any waypoint at all");
1194                         bot_waypoint_queue_owner = NULL;
1195                 }
1196         }
1197 }
1198
1199 // Support for debugging tracewalk visually
1200
1201 void debugresetnodes()
1202 {
1203         debuglastnode = '0 0 0';
1204 }
1205
1206 void debugnode(entity this, vector node)
1207 {
1208         if (!IS_PLAYER(this))
1209                 return;
1210
1211         if(debuglastnode=='0 0 0')
1212         {
1213                 debuglastnode = node;
1214                 return;
1215         }
1216
1217         te_lightning2(NULL, node, debuglastnode);
1218         debuglastnode = node;
1219 }
1220
1221 void debugnodestatus(vector position, float status)
1222 {
1223         vector c;
1224
1225         switch (status)
1226         {
1227                 case DEBUG_NODE_SUCCESS:
1228                         c = '0 15 0';
1229                         break;
1230                 case DEBUG_NODE_WARNING:
1231                         c = '15 15 0';
1232                         break;
1233                 case DEBUG_NODE_FAIL:
1234                         c = '15 0 0';
1235                         break;
1236                 default:
1237                         c = '15 15 15';
1238         }
1239
1240         te_customflash(position, 40,  2, c);
1241 }
1242
1243 // Support for debugging the goal stack visually
1244
1245 .float goalcounter;
1246 .vector lastposition;
1247
1248 // Debug the goal stack visually
1249 void debuggoalstack(entity this)
1250 {
1251         entity goal;
1252         vector org, go;
1253
1254         if(this.goalcounter==0)goal=this.goalcurrent;
1255         else if(this.goalcounter==1)goal=this.goalstack01;
1256         else if(this.goalcounter==2)goal=this.goalstack02;
1257         else if(this.goalcounter==3)goal=this.goalstack03;
1258         else if(this.goalcounter==4)goal=this.goalstack04;
1259         else if(this.goalcounter==5)goal=this.goalstack05;
1260         else if(this.goalcounter==6)goal=this.goalstack06;
1261         else if(this.goalcounter==7)goal=this.goalstack07;
1262         else if(this.goalcounter==8)goal=this.goalstack08;
1263         else if(this.goalcounter==9)goal=this.goalstack09;
1264         else if(this.goalcounter==10)goal=this.goalstack10;
1265         else if(this.goalcounter==11)goal=this.goalstack11;
1266         else if(this.goalcounter==12)goal=this.goalstack12;
1267         else if(this.goalcounter==13)goal=this.goalstack13;
1268         else if(this.goalcounter==14)goal=this.goalstack14;
1269         else if(this.goalcounter==15)goal=this.goalstack15;
1270         else if(this.goalcounter==16)goal=this.goalstack16;
1271         else if(this.goalcounter==17)goal=this.goalstack17;
1272         else if(this.goalcounter==18)goal=this.goalstack18;
1273         else if(this.goalcounter==19)goal=this.goalstack19;
1274         else if(this.goalcounter==20)goal=this.goalstack20;
1275         else if(this.goalcounter==21)goal=this.goalstack21;
1276         else if(this.goalcounter==22)goal=this.goalstack22;
1277         else if(this.goalcounter==23)goal=this.goalstack23;
1278         else if(this.goalcounter==24)goal=this.goalstack24;
1279         else if(this.goalcounter==25)goal=this.goalstack25;
1280         else if(this.goalcounter==26)goal=this.goalstack26;
1281         else if(this.goalcounter==27)goal=this.goalstack27;
1282         else if(this.goalcounter==28)goal=this.goalstack28;
1283         else if(this.goalcounter==29)goal=this.goalstack29;
1284         else if(this.goalcounter==30)goal=this.goalstack30;
1285         else if(this.goalcounter==31)goal=this.goalstack31;
1286         else goal=NULL;
1287
1288         if(goal==NULL)
1289         {
1290                 this.goalcounter = 0;
1291                 this.lastposition='0 0 0';
1292                 return;
1293         }
1294
1295         if(this.lastposition=='0 0 0')
1296                 org = this.origin;
1297         else
1298                 org = this.lastposition;
1299
1300
1301         go = ( goal.absmin + goal.absmax ) * 0.5;
1302         te_lightning2(NULL, org, go);
1303         this.lastposition = go;
1304
1305         this.goalcounter++;
1306 }