1 #include "navigation.qh"
4 #include "waypoints.qh"
6 #include <common/t_items.qh>
8 #include <common/items/all.qh>
10 #include <common/constants.qh>
11 #include <common/triggers/trigger/jumppads.qh>
15 // rough simulation of walking from one point to another to test if a path
16 // can be traveled, used for waypoint linking and havocbot
18 float tracewalk(entity e, vector start, vector m1, vector m2, vector end, float movemode)
30 if(autocvar_bot_debug_tracewalk)
39 dist = totaldist = vlen(move);
40 dir = normalize(move);
42 ignorehazards = false;
45 // Analyze starting point
46 traceline(start, start, MOVE_NORMAL, e);
47 if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
51 traceline( start, start + '0 0 -65536', MOVE_NORMAL, e);
52 if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
58 tracebox(start, m1, m2, start, MOVE_NOMONSTERS, e);
62 if(autocvar_bot_debug_tracewalk)
63 debugnodestatus(start, DEBUG_NODE_FAIL);
65 //print("tracewalk: ", vtos(start), " is a bad start\n");
74 if (boxesoverlap(end, end, org + m1 + '-1 -1 -1', org + m2 + '1 1 1'))
77 if(autocvar_bot_debug_tracewalk)
78 debugnodestatus(org, DEBUG_NODE_SUCCESS);
80 //print("tracewalk: ", vtos(start), " can reach ", vtos(end), "\n");
83 if(autocvar_bot_debug_tracewalk)
90 dist = dist - stepdist;
91 traceline(org, org, MOVE_NORMAL, e);
94 if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
96 // hazards blocking path
97 if(autocvar_bot_debug_tracewalk)
98 debugnodestatus(org, DEBUG_NODE_FAIL);
100 //print("tracewalk: ", vtos(start), " hits a hazard when trying to reach ", vtos(end), "\n");
104 if (trace_dpstartcontents & DPCONTENTS_LIQUIDSMASK)
106 move = normalize(end - org);
107 tracebox(org, m1, m2, org + move * stepdist, movemode, e);
109 if(autocvar_bot_debug_tracewalk)
110 debugnode(trace_endpos);
112 if (trace_fraction < 1)
115 org = trace_endpos - normalize(org - trace_endpos) * stepdist;
116 for (; org.z < end.z + self.maxs.z; org.z += stepdist)
118 if(autocvar_bot_debug_tracewalk)
121 if(pointcontents(org) == CONTENT_EMPTY)
125 if(pointcontents(org + '0 0 1') != CONTENT_EMPTY)
127 if(autocvar_bot_debug_tracewalk)
128 debugnodestatus(org, DEBUG_NODE_FAIL);
131 //print("tracewalk: ", vtos(start), " failed under water\n");
141 move = dir * stepdist + org;
142 tracebox(org, m1, m2, move, movemode, e);
144 if(autocvar_bot_debug_tracewalk)
145 debugnode(trace_endpos);
148 if (trace_fraction < 1)
150 // check if we can walk over this obstacle, possibly by jumpstepping
151 tracebox(org + stepheightvec, m1, m2, move + stepheightvec, movemode, e);
152 if (trace_fraction < 1 || trace_startsolid)
154 tracebox(org + jumpstepheightvec, m1, m2, move + jumpstepheightvec, movemode, e);
155 if (trace_fraction < 1 || trace_startsolid)
157 if(autocvar_bot_debug_tracewalk)
158 debugnodestatus(trace_endpos, DEBUG_NODE_WARNING);
161 traceline( org, move, movemode, e);
162 if ( trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
166 while(trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
168 nextmove = move + (dir * stepdist);
169 traceline( move, nextmove, movemode, e);
175 if(autocvar_bot_debug_tracewalk)
176 debugnodestatus(trace_endpos, DEBUG_NODE_FAIL);
178 //print("tracewalk: ", vtos(start), " hit something when trying to reach ", vtos(end), "\n");
179 //te_explosion(trace_endpos);
180 //print(ftos(e.dphitcontentsmask), "\n");
181 return false; // failed
193 // trace down from stepheight as far as possible and move there,
194 // if this starts in solid we try again without the stepup, and
195 // if that also fails we assume it is a wall
196 // (this is the same logic as the Quake walkmove function used)
197 tracebox(move, m1, m2, move + '0 0 -65536', movemode, e);
199 // moved successfully
203 c = pointcontents(org + '0 0 1');
204 if (!(c == CONTENT_WATER || c == CONTENT_LAVA || c == CONTENT_SLIME))
214 //print("tracewalk: ", vtos(start), " did not arrive at ", vtos(end), " but at ", vtos(org), "\n");
216 // moved but didn't arrive at the intended destination
217 if(autocvar_bot_debug_tracewalk)
218 debugnodestatus(org, DEBUG_NODE_FAIL);
223 /////////////////////////////////////////////////////////////////////////////
225 /////////////////////////////////////////////////////////////////////////////
227 // completely empty the goal stack, used when deciding where to go
228 void navigation_clearroute(entity this)
230 //print("bot ", etos(this), " clear\n");
231 this.navigation_hasgoals = false;
232 this.goalcurrent = world;
233 this.goalstack01 = world;
234 this.goalstack02 = world;
235 this.goalstack03 = world;
236 this.goalstack04 = world;
237 this.goalstack05 = world;
238 this.goalstack06 = world;
239 this.goalstack07 = world;
240 this.goalstack08 = world;
241 this.goalstack09 = world;
242 this.goalstack10 = world;
243 this.goalstack11 = world;
244 this.goalstack12 = world;
245 this.goalstack13 = world;
246 this.goalstack14 = world;
247 this.goalstack15 = world;
248 this.goalstack16 = world;
249 this.goalstack17 = world;
250 this.goalstack18 = world;
251 this.goalstack19 = world;
252 this.goalstack20 = world;
253 this.goalstack21 = world;
254 this.goalstack22 = world;
255 this.goalstack23 = world;
256 this.goalstack24 = world;
257 this.goalstack25 = world;
258 this.goalstack26 = world;
259 this.goalstack27 = world;
260 this.goalstack28 = world;
261 this.goalstack29 = world;
262 this.goalstack30 = world;
263 this.goalstack31 = world;
266 // add a new goal at the beginning of the stack
267 // (in other words: add a new prerequisite before going to the later goals)
268 // NOTE: when a waypoint is added, the WP gets pushed first, then the
269 // next-closest WP on the shortest path to the WP
270 // That means, if the stack overflows, the bot will know how to do the FIRST 32
271 // steps to the goal, and then recalculate the path.
272 void navigation_pushroute(entity this, entity e)
274 //print("bot ", etos(this), " push ", etos(e), "\n");
275 this.goalstack31 = this.goalstack30;
276 this.goalstack30 = this.goalstack29;
277 this.goalstack29 = this.goalstack28;
278 this.goalstack28 = this.goalstack27;
279 this.goalstack27 = this.goalstack26;
280 this.goalstack26 = this.goalstack25;
281 this.goalstack25 = this.goalstack24;
282 this.goalstack24 = this.goalstack23;
283 this.goalstack23 = this.goalstack22;
284 this.goalstack22 = this.goalstack21;
285 this.goalstack21 = this.goalstack20;
286 this.goalstack20 = this.goalstack19;
287 this.goalstack19 = this.goalstack18;
288 this.goalstack18 = this.goalstack17;
289 this.goalstack17 = this.goalstack16;
290 this.goalstack16 = this.goalstack15;
291 this.goalstack15 = this.goalstack14;
292 this.goalstack14 = this.goalstack13;
293 this.goalstack13 = this.goalstack12;
294 this.goalstack12 = this.goalstack11;
295 this.goalstack11 = this.goalstack10;
296 this.goalstack10 = this.goalstack09;
297 this.goalstack09 = this.goalstack08;
298 this.goalstack08 = this.goalstack07;
299 this.goalstack07 = this.goalstack06;
300 this.goalstack06 = this.goalstack05;
301 this.goalstack05 = this.goalstack04;
302 this.goalstack04 = this.goalstack03;
303 this.goalstack03 = this.goalstack02;
304 this.goalstack02 = this.goalstack01;
305 this.goalstack01 = this.goalcurrent;
306 this.goalcurrent = e;
309 // remove first goal from stack
310 // (in other words: remove a prerequisite for reaching the later goals)
311 // (used when a spawnfunc_waypoint is reached)
312 void navigation_poproute()
314 //print("bot ", etos(self), " pop\n");
315 self.goalcurrent = self.goalstack01;
316 self.goalstack01 = self.goalstack02;
317 self.goalstack02 = self.goalstack03;
318 self.goalstack03 = self.goalstack04;
319 self.goalstack04 = self.goalstack05;
320 self.goalstack05 = self.goalstack06;
321 self.goalstack06 = self.goalstack07;
322 self.goalstack07 = self.goalstack08;
323 self.goalstack08 = self.goalstack09;
324 self.goalstack09 = self.goalstack10;
325 self.goalstack10 = self.goalstack11;
326 self.goalstack11 = self.goalstack12;
327 self.goalstack12 = self.goalstack13;
328 self.goalstack13 = self.goalstack14;
329 self.goalstack14 = self.goalstack15;
330 self.goalstack15 = self.goalstack16;
331 self.goalstack16 = self.goalstack17;
332 self.goalstack17 = self.goalstack18;
333 self.goalstack18 = self.goalstack19;
334 self.goalstack19 = self.goalstack20;
335 self.goalstack20 = self.goalstack21;
336 self.goalstack21 = self.goalstack22;
337 self.goalstack22 = self.goalstack23;
338 self.goalstack23 = self.goalstack24;
339 self.goalstack24 = self.goalstack25;
340 self.goalstack25 = self.goalstack26;
341 self.goalstack26 = self.goalstack27;
342 self.goalstack27 = self.goalstack28;
343 self.goalstack28 = self.goalstack29;
344 self.goalstack29 = self.goalstack30;
345 self.goalstack30 = self.goalstack31;
346 self.goalstack31 = world;
349 float navigation_waypoint_will_link(vector v, vector org, entity ent, float walkfromwp, float bestdist)
352 dist = vlen(v - org);
355 traceline(v, org, true, ent);
356 if (trace_fraction == 1)
360 if (tracewalk(ent, v, STAT(PL_MIN, NULL), STAT(PL_MAX, NULL), org, bot_navigation_movemode))
365 if (tracewalk(ent, org, STAT(PL_MIN, NULL), STAT(PL_MAX, NULL), v, bot_navigation_movemode))
373 // find the spawnfunc_waypoint near a dynamic goal such as a dropped weapon
374 entity navigation_findnearestwaypoint_withdist_except(entity ent, float walkfromwp, float bestdist, entity except)
376 entity waylist, w, best;
377 vector v, org, pm1, pm2;
379 pm1 = ent.origin + ent.mins;
380 pm2 = ent.origin + ent.maxs;
381 waylist = findchain(classname, "waypoint");
383 // do two scans, because box test is cheaper
387 // if object is touching spawnfunc_waypoint
388 if(w != ent && w != except)
389 if (boxesoverlap(pm1, pm2, w.absmin, w.absmax))
394 org = ent.origin + 0.5 * (ent.mins + ent.maxs);
395 org.z = ent.origin.z + ent.mins.z - STAT(PL_MIN, NULL).z; // player height
396 // TODO possibly make other code have the same support for bboxes
398 org = org + ent.tag_entity.origin;
399 if (navigation_testtracewalk)
404 // box check failed, try walk
408 // if object can walk from spawnfunc_waypoint
414 wm1 = w.origin + w.mins;
415 wm2 = w.origin + w.maxs;
416 v.x = bound(wm1_x, org.x, wm2_x);
417 v.y = bound(wm1_y, org.y, wm2_y);
418 v.z = bound(wm1_z, org.z, wm2_z);
422 if(navigation_waypoint_will_link(v, org, ent, walkfromwp, bestdist))
424 bestdist = vlen(v - org);
432 entity navigation_findnearestwaypoint(entity ent, float walkfromwp)
434 entity wp = navigation_findnearestwaypoint_withdist_except(ent, walkfromwp, 1050, world);
435 if (autocvar_g_waypointeditor_auto)
437 entity wp2 = navigation_findnearestwaypoint_withdist_except(ent, walkfromwp, 1050, wp);
439 wp.wpflags |= WAYPOINTFLAG_PROTECTED;
444 // finds the waypoints near the bot initiating a navigation query
445 float navigation_markroutes_nearestwaypoints(entity waylist, float maxdist)
448 vector v, m1, m2, diff;
450 // navigation_testtracewalk = true;
455 if (!head.wpconsidered)
459 m1 = head.origin + head.mins;
460 m2 = head.origin + head.maxs;
462 v.x = bound(m1_x, v.x, m2_x);
463 v.y = bound(m1_y, v.y, m2_y);
464 v.z = bound(m1_z, v.z, m2_z);
468 diff = v - self.origin;
469 diff.z = max(0, diff.z);
470 if (vlen(diff) < maxdist)
472 head.wpconsidered = true;
473 if (tracewalk(self, self.origin, self.mins, self.maxs, v, bot_navigation_movemode))
475 head.wpnearestpoint = v;
476 head.wpcost = vlen(v - self.origin) + head.dmg;
485 //navigation_testtracewalk = false;
489 // updates a path link if a spawnfunc_waypoint link is better than the current one
490 void navigation_markroutes_checkwaypoint(entity w, entity wp, float cost2, vector p)
499 v.x = bound(m1_x, p.x, m2_x);
500 v.y = bound(m1_y, p.y, m2_y);
501 v.z = bound(m1_z, p.z, m2_z);
505 cost2 = cost2 + vlen(v - p);
506 if (wp.wpcost > cost2)
511 wp.wpnearestpoint = v;
515 // queries the entire spawnfunc_waypoint network for pathes leading away from the bot
516 void navigation_markroutes(entity fixed_source_waypoint)
518 entity w, wp, waylist;
519 float searching, cost, cost2;
521 w = waylist = findchain(classname, "waypoint");
524 w.wpconsidered = false;
525 w.wpnearestpoint = '0 0 0';
532 if(fixed_source_waypoint)
534 fixed_source_waypoint.wpconsidered = true;
535 fixed_source_waypoint.wpnearestpoint = fixed_source_waypoint.origin + 0.5 * (fixed_source_waypoint.mins + fixed_source_waypoint.maxs);
536 fixed_source_waypoint.wpcost = fixed_source_waypoint.dmg;
537 fixed_source_waypoint.wpfire = 1;
538 fixed_source_waypoint.enemy = world;
542 // try a short range search for the nearest waypoints, and expand the search repeatedly if none are found
543 // as this search is expensive we will use lower values if the bot is on the air
544 float i, increment, maxdistance;
545 if(IS_ONGROUND(self))
556 for(i=increment;!navigation_markroutes_nearestwaypoints(waylist, i)&&i<maxdistance;i+=increment);
571 p = w.wpnearestpoint;
572 wp = w.wp00;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp00mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
573 wp = w.wp01;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp01mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
574 wp = w.wp02;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp02mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
575 wp = w.wp03;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp03mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
576 wp = w.wp04;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp04mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
577 wp = w.wp05;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp05mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
578 wp = w.wp06;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp06mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
579 wp = w.wp07;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp07mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
580 wp = w.wp08;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp08mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
581 wp = w.wp09;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp09mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
582 wp = w.wp10;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp10mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
583 wp = w.wp11;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp11mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
584 wp = w.wp12;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp12mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
585 wp = w.wp13;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp13mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
586 wp = w.wp14;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp14mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
587 wp = w.wp15;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp15mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
588 wp = w.wp16;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp16mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
589 wp = w.wp17;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp17mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
590 wp = w.wp18;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp18mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
591 wp = w.wp19;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp19mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
592 wp = w.wp20;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp20mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
593 wp = w.wp21;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp21mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
594 wp = w.wp22;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp22mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
595 wp = w.wp23;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp23mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
596 wp = w.wp24;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp24mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
597 wp = w.wp25;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp25mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
598 wp = w.wp26;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp26mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
599 wp = w.wp27;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp27mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
600 wp = w.wp28;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp28mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
601 wp = w.wp29;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp29mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
602 wp = w.wp30;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp30mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
603 wp = w.wp31;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp31mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
604 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
611 // queries the entire spawnfunc_waypoint network for pathes leading to the bot
612 void navigation_markroutes_inverted(entity fixed_source_waypoint)
614 entity w, wp, waylist;
615 float searching, cost, cost2;
617 w = waylist = findchain(classname, "waypoint");
620 w.wpconsidered = false;
621 w.wpnearestpoint = '0 0 0';
628 if(fixed_source_waypoint)
630 fixed_source_waypoint.wpconsidered = true;
631 fixed_source_waypoint.wpnearestpoint = fixed_source_waypoint.origin + 0.5 * (fixed_source_waypoint.mins + fixed_source_waypoint.maxs);
632 fixed_source_waypoint.wpcost = fixed_source_waypoint.dmg; // the cost to get from X to fixed_source_waypoint
633 fixed_source_waypoint.wpfire = 1;
634 fixed_source_waypoint.enemy = world;
638 error("need to start with a waypoint\n");
652 cost = w.wpcost; // cost to walk from w to home
653 p = w.wpnearestpoint;
654 for(wp = waylist; wp; wp = wp.chain)
656 if(w != wp.wp00) if(w != wp.wp01) if(w != wp.wp02) if(w != wp.wp03)
657 if(w != wp.wp04) if(w != wp.wp05) if(w != wp.wp06) if(w != wp.wp07)
658 if(w != wp.wp08) if(w != wp.wp09) if(w != wp.wp10) if(w != wp.wp11)
659 if(w != wp.wp12) if(w != wp.wp13) if(w != wp.wp14) if(w != wp.wp15)
660 if(w != wp.wp16) if(w != wp.wp17) if(w != wp.wp18) if(w != wp.wp19)
661 if(w != wp.wp20) if(w != wp.wp21) if(w != wp.wp22) if(w != wp.wp23)
662 if(w != wp.wp24) if(w != wp.wp25) if(w != wp.wp26) if(w != wp.wp27)
663 if(w != wp.wp28) if(w != wp.wp29) if(w != wp.wp30) if(w != wp.wp31)
665 cost2 = cost + wp.dmg;
666 navigation_markroutes_checkwaypoint(w, wp, cost2, p);
674 // updates the best goal according to a weighted calculation of travel cost and item value of a new proposed item
675 void navigation_routerating(entity e, float f, float rangebias)
685 o = (e.absmin + e.absmax) * 0.5;
687 //print("routerating ", etos(e), " = ", ftos(f), " - ", ftos(rangebias), "\n");
689 // Evaluate path using jetpack
691 if(self.items & IT_JETPACK)
692 if(autocvar_bot_ai_navigation_jetpack)
693 if(vlen(self.origin - o) > autocvar_bot_ai_navigation_jetpack_mindistance)
695 vector pointa, pointb;
697 LOG_DEBUG("jetpack ai: evaluating path for ", e.classname, "\n");
700 traceline(self.origin, self.origin + '0 0 65535', MOVE_NORMAL, self);
701 pointa = trace_endpos - '0 0 1';
704 traceline(o, o + '0 0 65535', MOVE_NORMAL, e);
705 pointb = trace_endpos - '0 0 1';
707 // Can I see these two points from the sky?
708 traceline(pointa, pointb, MOVE_NORMAL, self);
710 if(trace_fraction==1)
712 LOG_DEBUG("jetpack ai: can bridge these two points\n");
714 // Lower the altitude of these points as much as possible
715 float zdistance, xydistance, cost, t, fuel;
716 vector down, npa, npb;
718 down = '0 0 -1' * (STAT(PL_MAX, NULL).z - STAT(PL_MIN, NULL).z) * 10;
724 if(npa.z<=self.absmax.z)
727 if(npb.z<=e.absmax.z)
730 traceline(npa, npb, MOVE_NORMAL, self);
731 if(trace_fraction==1)
737 while(trace_fraction == 1);
740 // Rough estimation of fuel consumption
741 // (ignores acceleration and current xyz velocity)
742 xydistance = vlen(pointa - pointb);
743 zdistance = fabs(pointa.z - self.origin.z);
745 t = zdistance / autocvar_g_jetpack_maxspeed_up;
746 t += xydistance / autocvar_g_jetpack_maxspeed_side;
747 fuel = t * autocvar_g_jetpack_fuel * 0.8;
749 LOG_DEBUG(strcat("jetpack ai: required fuel ", ftos(fuel), " self.ammo_fuel ", ftos(self.ammo_fuel), "\n"));
752 if(self.ammo_fuel>fuel)
755 // (as onground costs calculation is mostly based on distances, here we do the same establishing some relationship
756 // - between air and ground speeds)
758 cost = xydistance / (autocvar_g_jetpack_maxspeed_side/autocvar_sv_maxspeed);
759 cost += zdistance / (autocvar_g_jetpack_maxspeed_up/autocvar_sv_maxspeed);
762 // Compare against other goals
763 f = f * rangebias / (rangebias + cost);
765 if (navigation_bestrating < f)
767 LOG_DEBUG(strcat("jetpack path: added goal ", e.classname, " (with rating ", ftos(f), ")\n"));
768 navigation_bestrating = f;
769 navigation_bestgoal = e;
770 self.navigation_jetpack_goal = e;
771 self.navigation_jetpack_point = pointb;
778 //te_wizspike(e.origin);
781 // update the cached spawnfunc_waypoint link on a dynamic item entity
782 if(e.classname == "waypoint" && !(e.wpflags & WAYPOINTFLAG_PERSONAL))
792 if(e.flags & FL_ITEM)
794 if (!(e.flags & FL_WEAPON))
795 if(e.nearestwaypoint)
798 else if (e.flags & FL_WEAPON)
800 if(e.classname != "droppedweapon")
801 if(e.nearestwaypoint)
806 if (time > e.nearestwaypointtimeout)
808 nwp = navigation_findnearestwaypoint(e, true);
810 e.nearestwaypoint = nwp;
813 LOG_DEBUG(strcat("FAILED to find a nearest waypoint to '", e.classname, "' #", etos(e), "\n"));
815 if(e.flags & FL_ITEM)
816 e.blacklisted = true;
817 else if (e.flags & FL_WEAPON)
819 if(e.classname != "droppedweapon")
820 e.blacklisted = true;
825 LOG_DEBUG(strcat("The entity '", e.classname, "' is going to be excluded from path finding during this match\n"));
830 // TODO: Cleaner solution, probably handling this timeout from ctf.qc
831 if(e.classname=="item_flag_team")
832 e.nearestwaypointtimeout = time + 2;
834 e.nearestwaypointtimeout = time + random() * 3 + 5;
836 nwp = e.nearestwaypoint;
839 LOG_DEBUG(strcat("-- checking ", e.classname, " (with cost ", ftos(nwp.wpcost), ")\n"));
841 if (nwp.wpcost < 10000000)
843 //te_wizspike(nwp.wpnearestpoint);
844 LOG_DEBUG(strcat(e.classname, " ", ftos(f), "/(1+", ftos((nwp.wpcost + vlen(e.origin - nwp.wpnearestpoint))), "/", ftos(rangebias), ") = "));
845 f = f * rangebias / (rangebias + (nwp.wpcost + vlen(o - nwp.wpnearestpoint)));
846 LOG_DEBUG(strcat("considering ", e.classname, " (with rating ", ftos(f), ")\n"));
847 if (navigation_bestrating < f)
849 LOG_DEBUG(strcat("ground path: added goal ", e.classname, " (with rating ", ftos(f), ")\n"));
850 navigation_bestrating = f;
851 navigation_bestgoal = e;
856 // adds an item to the the goal stack with the path to a given item
857 bool navigation_routetogoal(entity this, entity e, vector startposition)
861 // if there is no goal, just exit
865 this.navigation_hasgoals = true;
867 // put the entity on the goal stack
868 //print("routetogoal ", etos(e), "\n");
869 navigation_pushroute(this, e);
872 if(e==this.navigation_jetpack_goal)
875 // if it can reach the goal there is nothing more to do
876 if (tracewalk(this, startposition, STAT(PL_MIN, NULL), STAT(PL_MAX, NULL), (e.absmin + e.absmax) * 0.5, bot_navigation_movemode))
879 // see if there are waypoints describing a path to the item
880 if(e.classname != "waypoint" || (e.wpflags & WAYPOINTFLAG_PERSONAL))
881 e = e.nearestwaypoint;
883 e = e.enemy; // we already have added it, so...
890 // add the spawnfunc_waypoint to the path
891 navigation_pushroute(this, e);
901 // removes any currently touching waypoints from the goal stack
902 // (this is how bots detect if they reached a goal)
903 void navigation_poptouchedgoals()
907 m1 = org + self.mins;
908 m2 = org + self.maxs;
910 if(self.goalcurrent.wpflags & WAYPOINTFLAG_TELEPORT)
912 if(self.lastteleporttime>0)
913 if(time-self.lastteleporttime<(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL)?2:0.15)
915 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
916 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
918 self.aistatus &= ~AI_STATUS_WAYPOINT_PERSONAL_GOING;
919 self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
921 navigation_poproute();
926 // If for some reason the bot is closer to the next goal, pop the current one
928 if(vlen(self.goalcurrent.origin - self.origin) > vlen(self.goalstack01.origin - self.origin))
929 if(checkpvs(self.origin + self.view_ofs, self.goalstack01))
930 if(tracewalk(self, self.origin, self.mins, self.maxs, (self.goalstack01.absmin + self.goalstack01.absmax) * 0.5, bot_navigation_movemode))
932 LOG_DEBUG(strcat("path optimized for ", self.netname, ", removed a goal from the queue\n"));
933 navigation_poproute();
934 // TODO this may also be a nice idea to do "early" (e.g. by
935 // manipulating the vlen() comparisons) to shorten paths in
936 // general - this would make bots walk more "on rails" than
937 // "zigzagging" which they currently do with sufficiently
938 // random-like waypoints, and thus can make a nice bot
939 // personality property
942 // HACK: remove players/bots as goals, they can lead a bot to unexpected places (cliffs, lava, etc)
943 // TODO: rate waypoints near the targetted player at that moment, instead of the player itself
944 if(IS_PLAYER(self.goalcurrent))
945 navigation_poproute();
947 // aid for detecting jump pads better (distance based check fails sometimes)
948 if(self.goalcurrent.wpflags & WAYPOINTFLAG_TELEPORT && self.jumppadcount > 0 )
949 navigation_poproute();
951 // Loose goal touching check when running
952 if(self.aistatus & AI_STATUS_RUNNING)
953 if(self.speed >= autocvar_sv_maxspeed) // if -really- running
954 if(self.goalcurrent.classname=="waypoint")
956 if(vlen(self.origin - self.goalcurrent.origin)<150)
958 traceline(self.origin + self.view_ofs , self.goalcurrent.origin, true, world);
959 if(trace_fraction==1)
961 // Detect personal waypoints
962 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
963 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
965 self.aistatus &= ~AI_STATUS_WAYPOINT_PERSONAL_GOING;
966 self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
969 navigation_poproute();
974 while (self.goalcurrent && boxesoverlap(m1, m2, self.goalcurrent.absmin, self.goalcurrent.absmax))
976 // Detect personal waypoints
977 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
978 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
980 self.aistatus &= ~AI_STATUS_WAYPOINT_PERSONAL_GOING;
981 self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
984 navigation_poproute();
988 // begin a goal selection session (queries spawnfunc_waypoint network)
989 void navigation_goalrating_start()
991 if(self.aistatus & AI_STATUS_STUCK)
994 self.navigation_jetpack_goal = world;
995 navigation_bestrating = -1;
996 self.navigation_hasgoals = false;
997 navigation_clearroute(self);
998 navigation_bestgoal = world;
999 navigation_markroutes(world);
1002 // ends a goal selection session (updates goal stack to the best goal)
1003 void navigation_goalrating_end()
1005 if(self.aistatus & AI_STATUS_STUCK)
1008 navigation_routetogoal(self, navigation_bestgoal, self.origin);
1009 LOG_DEBUG(strcat("best goal ", self.goalcurrent.classname , "\n"));
1011 // If the bot got stuck then try to reach the farthest waypoint
1012 if (!self.navigation_hasgoals)
1013 if (autocvar_bot_wander_enable)
1015 if (!(self.aistatus & AI_STATUS_STUCK))
1017 LOG_DEBUG(strcat(self.netname, " cannot walk to any goal\n"));
1018 self.aistatus |= AI_STATUS_STUCK;
1021 self.navigation_hasgoals = false; // Reset this value
1025 void botframe_updatedangerousobjects(float maxupdate)
1027 entity head, bot_dodgelist;
1028 vector m1, m2, v, o;
1031 bot_dodgelist = findchainfloat(bot_dodge, true);
1032 botframe_dangerwaypoint = find(botframe_dangerwaypoint, classname, "waypoint");
1033 while (botframe_dangerwaypoint != world)
1036 m1 = botframe_dangerwaypoint.mins;
1037 m2 = botframe_dangerwaypoint.maxs;
1038 head = bot_dodgelist;
1042 v.x = bound(m1_x, v.x, m2_x);
1043 v.y = bound(m1_y, v.y, m2_y);
1044 v.z = bound(m1_z, v.z, m2_z);
1045 o = (head.absmin + head.absmax) * 0.5;
1046 d = head.bot_dodgerating - vlen(o - v);
1049 traceline(o, v, true, world);
1050 if (trace_fraction == 1)
1051 danger = danger + d;
1055 botframe_dangerwaypoint.dmg = danger;
1059 botframe_dangerwaypoint = find(botframe_dangerwaypoint, classname, "waypoint");
1063 void navigation_unstuck()
1065 float search_radius = 1000;
1067 if (!autocvar_bot_wander_enable)
1070 if (!bot_waypoint_queue_owner)
1072 LOG_DEBUG(strcat(self.netname, " sutck, taking over the waypoints queue\n"));
1073 bot_waypoint_queue_owner = self;
1074 bot_waypoint_queue_bestgoal = world;
1075 bot_waypoint_queue_bestgoalrating = 0;
1078 if(bot_waypoint_queue_owner!=self)
1081 if (bot_waypoint_queue_goal)
1083 // evaluate the next goal on the queue
1084 float d = vlen(self.origin - bot_waypoint_queue_goal.origin);
1085 LOG_DEBUG(strcat(self.netname, " evaluating ", bot_waypoint_queue_goal.classname, " with distance ", ftos(d), "\n"));
1086 if(tracewalk(bot_waypoint_queue_goal, self.origin, STAT(PL_MIN, NULL), STAT(PL_MAX, NULL), bot_waypoint_queue_goal.origin, bot_navigation_movemode))
1088 if( d > bot_waypoint_queue_bestgoalrating)
1090 bot_waypoint_queue_bestgoalrating = d;
1091 bot_waypoint_queue_bestgoal = bot_waypoint_queue_goal;
1094 bot_waypoint_queue_goal = bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal;
1096 if (!bot_waypoint_queue_goal)
1098 if (bot_waypoint_queue_bestgoal)
1100 LOG_DEBUG(strcat(self.netname, " stuck, reachable waypoint found, heading to it\n"));
1101 navigation_routetogoal(self, bot_waypoint_queue_bestgoal, self.origin);
1102 self.bot_strategytime = time + autocvar_bot_ai_strategyinterval;
1103 self.aistatus &= ~AI_STATUS_STUCK;
1107 LOG_DEBUG(strcat(self.netname, " stuck, cannot walk to any waypoint at all\n"));
1110 bot_waypoint_queue_owner = world;
1115 if(bot_strategytoken!=self)
1118 // build a new queue
1119 LOG_DEBUG(strcat(self.netname, " stuck, scanning reachable waypoints within ", ftos(search_radius)," qu\n"));
1124 head = findradius(self.origin, search_radius);
1128 if(head.classname=="waypoint")
1129 // if(!(head.wpflags & WAYPOINTFLAG_GENERATED))
1131 if(bot_waypoint_queue_goal)
1132 bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = head;
1136 bot_waypoint_queue_goal = head;
1137 bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = world;
1144 bot_waypoint_queue_goal = first;
1147 LOG_DEBUG(strcat(self.netname, " stuck, cannot walk to any waypoint at all\n"));
1148 bot_waypoint_queue_owner = world;
1153 // Support for debugging tracewalk visually
1155 void debugresetnodes()
1157 debuglastnode = '0 0 0';
1160 void debugnode(vector node)
1162 if (!IS_PLAYER(self))
1165 if(debuglastnode=='0 0 0')
1167 debuglastnode = node;
1171 te_lightning2(world, node, debuglastnode);
1172 debuglastnode = node;
1175 void debugnodestatus(vector position, float status)
1181 case DEBUG_NODE_SUCCESS:
1184 case DEBUG_NODE_WARNING:
1187 case DEBUG_NODE_FAIL:
1194 te_customflash(position, 40, 2, c);
1197 // Support for debugging the goal stack visually
1200 .vector lastposition;
1202 // Debug the goal stack visually
1203 void debuggoalstack(entity this)
1208 if(this.goalcounter==0)goal=this.goalcurrent;
1209 else if(this.goalcounter==1)goal=this.goalstack01;
1210 else if(this.goalcounter==2)goal=this.goalstack02;
1211 else if(this.goalcounter==3)goal=this.goalstack03;
1212 else if(this.goalcounter==4)goal=this.goalstack04;
1213 else if(this.goalcounter==5)goal=this.goalstack05;
1214 else if(this.goalcounter==6)goal=this.goalstack06;
1215 else if(this.goalcounter==7)goal=this.goalstack07;
1216 else if(this.goalcounter==8)goal=this.goalstack08;
1217 else if(this.goalcounter==9)goal=this.goalstack09;
1218 else if(this.goalcounter==10)goal=this.goalstack10;
1219 else if(this.goalcounter==11)goal=this.goalstack11;
1220 else if(this.goalcounter==12)goal=this.goalstack12;
1221 else if(this.goalcounter==13)goal=this.goalstack13;
1222 else if(this.goalcounter==14)goal=this.goalstack14;
1223 else if(this.goalcounter==15)goal=this.goalstack15;
1224 else if(this.goalcounter==16)goal=this.goalstack16;
1225 else if(this.goalcounter==17)goal=this.goalstack17;
1226 else if(this.goalcounter==18)goal=this.goalstack18;
1227 else if(this.goalcounter==19)goal=this.goalstack19;
1228 else if(this.goalcounter==20)goal=this.goalstack20;
1229 else if(this.goalcounter==21)goal=this.goalstack21;
1230 else if(this.goalcounter==22)goal=this.goalstack22;
1231 else if(this.goalcounter==23)goal=this.goalstack23;
1232 else if(this.goalcounter==24)goal=this.goalstack24;
1233 else if(this.goalcounter==25)goal=this.goalstack25;
1234 else if(this.goalcounter==26)goal=this.goalstack26;
1235 else if(this.goalcounter==27)goal=this.goalstack27;
1236 else if(this.goalcounter==28)goal=this.goalstack28;
1237 else if(this.goalcounter==29)goal=this.goalstack29;
1238 else if(this.goalcounter==30)goal=this.goalstack30;
1239 else if(this.goalcounter==31)goal=this.goalstack31;
1244 this.goalcounter = 0;
1245 this.lastposition='0 0 0';
1249 if(this.lastposition=='0 0 0')
1252 org = this.lastposition;
1255 go = ( goal.absmin + goal.absmax ) * 0.5;
1256 te_lightning2(world, org, go);
1257 this.lastposition = go;