2 // rough simulation of walking from one point to another to test if a path
3 // can be traveled, used for waypoint linking and havocbot
5 float tracewalk(entity e, vector start, vector m1, vector m2, vector end, float movemode)
11 local float totaldist;
14 local float ignorehazards;
17 if(autocvar_bot_debug_tracewalk)
26 dist = totaldist = vlen(move);
27 dir = normalize(move);
29 ignorehazards = FALSE;
31 // Analyze starting point
32 traceline(start, start, MOVE_NORMAL, e);
33 if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
37 traceline( start, start + '0 0 -65536', MOVE_NORMAL, e);
38 if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
44 tracebox(start, m1, m2, start, MOVE_NOMONSTERS, e);
48 if(autocvar_bot_debug_tracewalk)
49 debugnodestatus(start, DEBUG_NODE_FAIL);
51 //print("tracewalk: ", vtos(start), " is a bad start\n");
60 if (boxesoverlap(end, end, org + m1 + '-1 -1 -1', org + m2 + '1 1 1'))
63 if(autocvar_bot_debug_tracewalk)
64 debugnodestatus(org, DEBUG_NODE_SUCCESS);
66 //print("tracewalk: ", vtos(start), " can reach ", vtos(end), "\n");
69 if(autocvar_bot_debug_tracewalk)
76 dist = dist - stepdist;
77 traceline(org, org, MOVE_NORMAL, e);
80 if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
82 // hazards blocking path
83 if(autocvar_bot_debug_tracewalk)
84 debugnodestatus(org, DEBUG_NODE_FAIL);
86 //print("tracewalk: ", vtos(start), " hits a hazard when trying to reach ", vtos(end), "\n");
90 if (trace_dpstartcontents & DPCONTENTS_LIQUIDSMASK)
92 move = normalize(end - org);
93 tracebox(org, m1, m2, org + move * stepdist, movemode, e);
95 if(autocvar_bot_debug_tracewalk)
96 debugnode(trace_endpos);
98 if (trace_fraction < 1)
101 org = trace_endpos - normalize(org - trace_endpos) * stepdist;
102 for(; org_z < end_z + self.maxs_z; org_z += stepdist)
104 if(autocvar_bot_debug_tracewalk)
107 if(pointcontents(org) == CONTENT_EMPTY)
111 if not (pointcontents(org + '0 0 1') == CONTENT_EMPTY)
113 if(autocvar_bot_debug_tracewalk)
114 debugnodestatus(org, DEBUG_NODE_FAIL);
117 //print("tracewalk: ", vtos(start), " failed under water\n");
127 move = dir * stepdist + org;
128 tracebox(org, m1, m2, move, movemode, e);
130 if(autocvar_bot_debug_tracewalk)
131 debugnode(trace_endpos);
134 if (trace_fraction < 1)
136 // check if we can walk over this obstacle, possibly by jumpstepping
137 tracebox(org + jumpstepheightvec, m1, m2, move + jumpstepheightvec, movemode, e);
138 if (trace_fraction < 1 || trace_startsolid)
140 if(autocvar_bot_debug_tracewalk)
141 debugnodestatus(trace_endpos, DEBUG_NODE_WARNING);
144 traceline( org, move, movemode, e);
145 if ( trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
147 local vector nextmove;
149 while(trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
151 nextmove = move + (dir * stepdist);
152 traceline( move, nextmove, movemode, e);
158 if(autocvar_bot_debug_tracewalk)
159 debugnodestatus(trace_endpos, DEBUG_NODE_FAIL);
161 //print("tracewalk: ", vtos(start), " hit something when trying to reach ", vtos(end), "\n");
162 //te_explosion(trace_endpos);
163 //print(ftos(e.dphitcontentsmask), "\n");
164 return FALSE; // failed
173 // trace down from stepheight as far as possible and move there,
174 // if this starts in solid we try again without the stepup, and
175 // if that also fails we assume it is a wall
176 // (this is the same logic as the Quake walkmove function used)
177 tracebox(move, m1, m2, move + '0 0 -65536', movemode, e);
179 // moved successfully
183 c = pointcontents(org + '0 0 1');
184 if not(c == CONTENT_WATER || c == CONTENT_LAVA || c == CONTENT_SLIME)
194 //print("tracewalk: ", vtos(start), " did not arrive at ", vtos(end), " but at ", vtos(org), "\n");
196 // moved but didn't arrive at the intended destination
197 if(autocvar_bot_debug_tracewalk)
198 debugnodestatus(org, DEBUG_NODE_FAIL);
203 /////////////////////////////////////////////////////////////////////////////
205 /////////////////////////////////////////////////////////////////////////////
207 // completely empty the goal stack, used when deciding where to go
208 void navigation_clearroute()
210 //print("bot ", etos(self), " clear\n");
211 self.navigation_hasgoals = FALSE;
212 self.goalcurrent = world;
213 self.goalstack01 = world;
214 self.goalstack02 = world;
215 self.goalstack03 = world;
216 self.goalstack04 = world;
217 self.goalstack05 = world;
218 self.goalstack06 = world;
219 self.goalstack07 = world;
220 self.goalstack08 = world;
221 self.goalstack09 = world;
222 self.goalstack10 = world;
223 self.goalstack11 = world;
224 self.goalstack12 = world;
225 self.goalstack13 = world;
226 self.goalstack14 = world;
227 self.goalstack15 = world;
228 self.goalstack16 = world;
229 self.goalstack17 = world;
230 self.goalstack18 = world;
231 self.goalstack19 = world;
232 self.goalstack20 = world;
233 self.goalstack21 = world;
234 self.goalstack22 = world;
235 self.goalstack23 = world;
236 self.goalstack24 = world;
237 self.goalstack25 = world;
238 self.goalstack26 = world;
239 self.goalstack27 = world;
240 self.goalstack28 = world;
241 self.goalstack29 = world;
242 self.goalstack30 = world;
243 self.goalstack31 = world;
246 // add a new goal at the beginning of the stack
247 // (in other words: add a new prerequisite before going to the later goals)
248 // NOTE: when a waypoint is added, the WP gets pushed first, then the
249 // next-closest WP on the shortest path to the WP
250 // That means, if the stack overflows, the bot will know how to do the FIRST 32
251 // steps to the goal, and then recalculate the path.
252 void navigation_pushroute(entity e)
254 //print("bot ", etos(self), " push ", etos(e), "\n");
255 self.goalstack31 = self.goalstack30;
256 self.goalstack30 = self.goalstack29;
257 self.goalstack29 = self.goalstack28;
258 self.goalstack28 = self.goalstack27;
259 self.goalstack27 = self.goalstack26;
260 self.goalstack26 = self.goalstack25;
261 self.goalstack25 = self.goalstack24;
262 self.goalstack24 = self.goalstack23;
263 self.goalstack23 = self.goalstack22;
264 self.goalstack22 = self.goalstack21;
265 self.goalstack21 = self.goalstack20;
266 self.goalstack20 = self.goalstack19;
267 self.goalstack19 = self.goalstack18;
268 self.goalstack18 = self.goalstack17;
269 self.goalstack17 = self.goalstack16;
270 self.goalstack16 = self.goalstack15;
271 self.goalstack15 = self.goalstack14;
272 self.goalstack14 = self.goalstack13;
273 self.goalstack13 = self.goalstack12;
274 self.goalstack12 = self.goalstack11;
275 self.goalstack11 = self.goalstack10;
276 self.goalstack10 = self.goalstack09;
277 self.goalstack09 = self.goalstack08;
278 self.goalstack08 = self.goalstack07;
279 self.goalstack07 = self.goalstack06;
280 self.goalstack06 = self.goalstack05;
281 self.goalstack05 = self.goalstack04;
282 self.goalstack04 = self.goalstack03;
283 self.goalstack03 = self.goalstack02;
284 self.goalstack02 = self.goalstack01;
285 self.goalstack01 = self.goalcurrent;
286 self.goalcurrent = e;
289 // remove first goal from stack
290 // (in other words: remove a prerequisite for reaching the later goals)
291 // (used when a spawnfunc_waypoint is reached)
292 void navigation_poproute()
294 //print("bot ", etos(self), " pop\n");
295 self.goalcurrent = self.goalstack01;
296 self.goalstack01 = self.goalstack02;
297 self.goalstack02 = self.goalstack03;
298 self.goalstack03 = self.goalstack04;
299 self.goalstack04 = self.goalstack05;
300 self.goalstack05 = self.goalstack06;
301 self.goalstack06 = self.goalstack07;
302 self.goalstack07 = self.goalstack08;
303 self.goalstack08 = self.goalstack09;
304 self.goalstack09 = self.goalstack10;
305 self.goalstack10 = self.goalstack11;
306 self.goalstack11 = self.goalstack12;
307 self.goalstack12 = self.goalstack13;
308 self.goalstack13 = self.goalstack14;
309 self.goalstack14 = self.goalstack15;
310 self.goalstack15 = self.goalstack16;
311 self.goalstack16 = self.goalstack17;
312 self.goalstack17 = self.goalstack18;
313 self.goalstack18 = self.goalstack19;
314 self.goalstack19 = self.goalstack20;
315 self.goalstack20 = self.goalstack21;
316 self.goalstack21 = self.goalstack22;
317 self.goalstack22 = self.goalstack23;
318 self.goalstack23 = self.goalstack24;
319 self.goalstack24 = self.goalstack25;
320 self.goalstack25 = self.goalstack26;
321 self.goalstack26 = self.goalstack27;
322 self.goalstack27 = self.goalstack28;
323 self.goalstack28 = self.goalstack29;
324 self.goalstack29 = self.goalstack30;
325 self.goalstack30 = self.goalstack31;
326 self.goalstack31 = world;
329 float navigation_waypoint_will_link(vector v, vector org, entity ent, float walkfromwp, float bestdist)
332 dist = vlen(v - org);
335 traceline(v, org, TRUE, ent);
336 if (trace_fraction == 1)
340 if (tracewalk(ent, v, PL_MIN, PL_MAX, org, bot_navigation_movemode))
345 if (tracewalk(ent, org, PL_MIN, PL_MAX, v, bot_navigation_movemode))
353 // find the spawnfunc_waypoint near a dynamic goal such as a dropped weapon
354 entity navigation_findnearestwaypoint_withdist(entity ent, float walkfromwp, float bestdist)
356 local entity waylist, w, best;
357 local vector v, org, pm1, pm2;
358 pm1 = ent.origin + ent.mins;
359 pm2 = ent.origin + ent.maxs;
360 waylist = findchain(classname, "waypoint");
362 // do two scans, because box test is cheaper
366 // if object is touching spawnfunc_waypoint
368 if (boxesoverlap(pm1, pm2, w.absmin, w.absmax))
373 org = ent.origin + 0.5 * (ent.mins + ent.maxs);
374 org_z = ent.origin_z + ent.mins_z - PL_MIN_z; // player height
375 // TODO possibly make other code have the same support for bboxes
377 org = org + ent.tag_entity.origin;
378 if (navigation_testtracewalk)
383 // box check failed, try walk
387 // if object can walk from spawnfunc_waypoint
392 local vector wm1, wm2;
393 wm1 = w.origin + w.mins;
394 wm2 = w.origin + w.maxs;
395 v_x = bound(wm1_x, org_x, wm2_x);
396 v_y = bound(wm1_y, org_y, wm2_y);
397 v_z = bound(wm1_z, org_z, wm2_z);
401 if(navigation_waypoint_will_link(v, org, ent, walkfromwp, bestdist))
403 bestdist = vlen(v - org);
411 entity navigation_findnearestwaypoint(entity ent, float walkfromwp)
413 return navigation_findnearestwaypoint_withdist(ent, walkfromwp, 1050);
416 // finds the waypoints near the bot initiating a navigation query
417 float navigation_markroutes_nearestwaypoints(entity waylist, float maxdist)
420 local vector v, m1, m2, diff;
422 // navigation_testtracewalk = TRUE;
427 if (!head.wpconsidered)
431 m1 = head.origin + head.mins;
432 m2 = head.origin + head.maxs;
434 v_x = bound(m1_x, v_x, m2_x);
435 v_y = bound(m1_y, v_y, m2_y);
436 v_z = bound(m1_z, v_z, m2_z);
440 diff = v - self.origin;
441 diff_z = max(0, diff_z);
442 if (vlen(diff) < maxdist)
444 head.wpconsidered = TRUE;
445 if (tracewalk(self, self.origin, self.mins, self.maxs, v, bot_navigation_movemode))
447 head.wpnearestpoint = v;
448 head.wpcost = vlen(v - self.origin) + head.dmg;
457 //navigation_testtracewalk = FALSE;
461 // updates a path link if a spawnfunc_waypoint link is better than the current one
462 void navigation_markroutes_checkwaypoint(entity w, entity wp, float cost2, vector p)
471 v_x = bound(m1_x, p_x, m2_x);
472 v_y = bound(m1_y, p_y, m2_y);
473 v_z = bound(m1_z, p_z, m2_z);
477 cost2 = cost2 + vlen(v - p);
478 if (wp.wpcost > cost2)
483 wp.wpnearestpoint = v;
487 // queries the entire spawnfunc_waypoint network for pathes leading away from the bot
488 void navigation_markroutes(entity fixed_source_waypoint)
490 local entity w, wp, waylist;
491 local float searching, cost, cost2;
493 w = waylist = findchain(classname, "waypoint");
496 w.wpconsidered = FALSE;
497 w.wpnearestpoint = '0 0 0';
504 if(fixed_source_waypoint)
506 fixed_source_waypoint.wpconsidered = TRUE;
507 fixed_source_waypoint.wpnearestpoint = fixed_source_waypoint.origin + 0.5 * (fixed_source_waypoint.mins + fixed_source_waypoint.maxs);
508 fixed_source_waypoint.wpcost = fixed_source_waypoint.dmg;
509 fixed_source_waypoint.wpfire = 1;
510 fixed_source_waypoint.enemy = world;
514 // try a short range search for the nearest waypoints, and expand the search repeatedly if none are found
515 // as this search is expensive we will use lower values if the bot is on the air
516 local float i, increment, maxdistance;
517 if(self.flags & FL_ONGROUND)
528 for(i=increment;!navigation_markroutes_nearestwaypoints(waylist, i)&&i<maxdistance;i+=increment);
543 p = w.wpnearestpoint;
544 wp = w.wp00;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp00mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
545 wp = w.wp01;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp01mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
546 wp = w.wp02;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp02mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
547 wp = w.wp03;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp03mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
548 wp = w.wp04;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp04mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
549 wp = w.wp05;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp05mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
550 wp = w.wp06;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp06mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
551 wp = w.wp07;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp07mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
552 wp = w.wp08;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp08mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
553 wp = w.wp09;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp09mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
554 wp = w.wp10;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp10mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
555 wp = w.wp11;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp11mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
556 wp = w.wp12;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp12mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
557 wp = w.wp13;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp13mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
558 wp = w.wp14;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp14mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
559 wp = w.wp15;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp15mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
560 wp = w.wp16;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp16mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
561 wp = w.wp17;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp17mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
562 wp = w.wp18;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp18mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
563 wp = w.wp19;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp19mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
564 wp = w.wp20;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp20mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
565 wp = w.wp21;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp21mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
566 wp = w.wp22;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp22mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
567 wp = w.wp23;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp23mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
568 wp = w.wp24;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp24mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
569 wp = w.wp25;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp25mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
570 wp = w.wp26;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp26mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
571 wp = w.wp27;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp27mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
572 wp = w.wp28;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp28mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
573 wp = w.wp29;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp29mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
574 wp = w.wp30;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp30mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
575 wp = w.wp31;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp31mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
576 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
583 // queries the entire spawnfunc_waypoint network for pathes leading to the bot
584 void navigation_markroutes_inverted(entity fixed_source_waypoint)
586 local entity w, wp, waylist;
587 local float searching, cost, cost2;
589 w = waylist = findchain(classname, "waypoint");
592 w.wpconsidered = FALSE;
593 w.wpnearestpoint = '0 0 0';
600 if(fixed_source_waypoint)
602 fixed_source_waypoint.wpconsidered = TRUE;
603 fixed_source_waypoint.wpnearestpoint = fixed_source_waypoint.origin + 0.5 * (fixed_source_waypoint.mins + fixed_source_waypoint.maxs);
604 fixed_source_waypoint.wpcost = fixed_source_waypoint.dmg; // the cost to get from X to fixed_source_waypoint
605 fixed_source_waypoint.wpfire = 1;
606 fixed_source_waypoint.enemy = world;
610 error("need to start with a waypoint\n");
624 cost = w.wpcost; // cost to walk from w to home
625 p = w.wpnearestpoint;
626 for(wp = waylist; wp; wp = wp.chain)
628 if(w != wp.wp00) if(w != wp.wp01) if(w != wp.wp02) if(w != wp.wp03)
629 if(w != wp.wp04) if(w != wp.wp05) if(w != wp.wp06) if(w != wp.wp07)
630 if(w != wp.wp08) if(w != wp.wp09) if(w != wp.wp10) if(w != wp.wp11)
631 if(w != wp.wp12) if(w != wp.wp13) if(w != wp.wp14) if(w != wp.wp15)
632 if(w != wp.wp16) if(w != wp.wp17) if(w != wp.wp18) if(w != wp.wp19)
633 if(w != wp.wp20) if(w != wp.wp21) if(w != wp.wp22) if(w != wp.wp23)
634 if(w != wp.wp24) if(w != wp.wp25) if(w != wp.wp26) if(w != wp.wp27)
635 if(w != wp.wp28) if(w != wp.wp29) if(w != wp.wp30) if(w != wp.wp31)
637 cost2 = cost + wp.dmg;
638 navigation_markroutes_checkwaypoint(w, wp, cost2, p);
646 // updates the best goal according to a weighted calculation of travel cost and item value of a new proposed item
647 void navigation_routerating(entity e, float f, float rangebias)
657 o = (e.absmin + e.absmax) * 0.5;
659 //print("routerating ", etos(e), " = ", ftos(f), " - ", ftos(rangebias), "\n");
661 // Evaluate path using jetpack
663 if(self.items & IT_JETPACK)
664 if(autocvar_bot_ai_navigation_jetpack)
665 if(vlen(self.origin - o) > autocvar_bot_ai_navigation_jetpack_mindistance)
667 vector pointa, pointb;
669 // dprint("jetpack ai: evaluating path for ", e.classname,"\n");
672 traceline(self.origin, self.origin + '0 0 65535', MOVE_NORMAL, self);
673 pointa = trace_endpos - '0 0 1';
676 traceline(o, o + '0 0 65535', MOVE_NORMAL, e);
677 pointb = trace_endpos - '0 0 1';
679 // Can I see these two points from the sky?
680 traceline(pointa, pointb, MOVE_NORMAL, self);
682 if(trace_fraction==1)
684 // dprint("jetpack ai: can bridge these two points\n");
686 // Lower the altitude of these points as much as possible
687 local float zdistance, xydistance, cost, t, fuel;
688 local vector down, npa, npb;
690 down = '0 0 -1' * (PL_MAX_z - PL_MIN_z) * 10;
696 if(npa_z<=self.absmax_z)
699 if(npb_z<=e.absmax_z)
702 traceline(npa, npb, MOVE_NORMAL, self);
703 if(trace_fraction==1)
709 while(trace_fraction == 1);
712 // Rough estimation of fuel consumption
713 // (ignores acceleration and current xyz velocity)
714 xydistance = vlen(pointa - pointb);
715 zdistance = fabs(pointa_z - self.origin_z);
717 t = zdistance / autocvar_g_jetpack_maxspeed_up;
718 t += xydistance / autocvar_g_jetpack_maxspeed_side;
719 fuel = t * autocvar_g_jetpack_fuel * 0.8;
721 // dprint("jetpack ai: required fuel ", ftos(fuel), " self.ammo_fuel ", ftos(self.ammo_fuel),"\n");
724 if(self.ammo_fuel>fuel)
727 // (as onground costs calculation is mostly based on distances, here we do the same establishing some relationship
728 // - between air and ground speeds)
730 cost = xydistance / (autocvar_g_jetpack_maxspeed_side/autocvar_sv_maxspeed);
731 cost += zdistance / (autocvar_g_jetpack_maxspeed_up/autocvar_sv_maxspeed);
734 // Compare against other goals
735 f = f * rangebias / (rangebias + cost);
737 if (navigation_bestrating < f)
739 // dprint("jetpack path: added goal", e.classname, " (with rating ", ftos(f), ")\n");
740 navigation_bestrating = f;
741 navigation_bestgoal = e;
742 self.navigation_jetpack_goal = e;
743 self.navigation_jetpack_point = pointb;
750 //te_wizspike(e.origin);
753 // update the cached spawnfunc_waypoint link on a dynamic item entity
754 if(e.classname == "waypoint" && !(e.wpflags & WAYPOINTFLAG_PERSONAL))
764 if(e.flags & FL_ITEM)
766 if not(e.flags & FL_WEAPON)
767 if(e.nearestwaypoint)
770 else if (e.flags & FL_WEAPON)
772 if(e.classname != "droppedweapon")
773 if(e.nearestwaypoint)
778 if (time > e.nearestwaypointtimeout)
780 nwp = navigation_findnearestwaypoint(e, TRUE);
782 e.nearestwaypoint = nwp;
785 dprint("FAILED to find a nearest waypoint to '", e.classname, "' #", etos(e), "\n");
787 if(e.flags & FL_ITEM)
788 e.blacklisted = TRUE;
789 else if (e.flags & FL_WEAPON)
791 if(e.classname != "droppedweapon")
792 e.blacklisted = TRUE;
797 dprint("The entity '", e.classname, "' is going to be excluded from path finding during this match\n");
802 // TODO: Cleaner solution, probably handling this timeout from ctf.qc
803 if(e.classname=="item_flag_team")
804 e.nearestwaypointtimeout = time + 2;
806 e.nearestwaypointtimeout = time + random() * 3 + 5;
808 nwp = e.nearestwaypoint;
811 //dprint("-- checking ", e.classname, " (with cost ", ftos(nwp.wpcost), ")\n");
813 if (nwp.wpcost < 10000000)
815 //te_wizspike(nwp.wpnearestpoint);
816 // dprint(e.classname, " ", ftos(f), "/(1+", ftos((nwp.wpcost + vlen(e.origin - nwp.wpnearestpoint))), "/", ftos(rangebias), ") = ");
817 f = f * rangebias / (rangebias + (nwp.wpcost + vlen(o - nwp.wpnearestpoint)));
818 //dprint("considering ", e.classname, " (with rating ", ftos(f), ")\n");
820 if (navigation_bestrating < f)
822 // dprint("ground path: added goal ", e.classname, " (with rating ", ftos(f), ")\n");
823 navigation_bestrating = f;
824 navigation_bestgoal = e;
830 // adds an item to the the goal stack with the path to a given item
831 float navigation_routetogoal(entity e, vector startposition)
835 // if there is no goal, just exit
839 self.navigation_hasgoals = TRUE;
841 // put the entity on the goal stack
842 //print("routetogoal ", etos(e), "\n");
843 navigation_pushroute(e);
846 if(e==self.navigation_jetpack_goal)
849 // if it can reach the goal there is nothing more to do
850 if (tracewalk(self, startposition, PL_MIN, PL_MAX, (e.absmin + e.absmax) * 0.5, bot_navigation_movemode))
853 // see if there are waypoints describing a path to the item
854 if(e.classname != "waypoint" || (e.wpflags & WAYPOINTFLAG_PERSONAL))
855 e = e.nearestwaypoint;
857 e = e.enemy; // we already have added it, so...
864 // add the spawnfunc_waypoint to the path
865 navigation_pushroute(e);
875 // removes any currently touching waypoints from the goal stack
876 // (this is how bots detect if they reached a goal)
877 void navigation_poptouchedgoals()
879 local vector org, m1, m2;
881 m1 = org + self.mins;
882 m2 = org + self.maxs;
884 if(self.goalcurrent.wpflags & WAYPOINTFLAG_TELEPORT)
886 if(self.lastteleporttime>0)
887 if(time-self.lastteleporttime<(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL)?2:0.15)
889 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
890 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
892 self.aistatus &~= AI_STATUS_WAYPOINT_PERSONAL_GOING;
893 self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
895 navigation_poproute();
900 // If for some reason the bot is closer to the next goal, pop the current one
902 if(vlen(self.goalcurrent.origin - self.origin) > vlen(self.goalstack01.origin - self.origin))
903 if(checkpvs(self.origin + self.view_ofs, self.goalstack01))
904 if(tracewalk(self, self.origin, self.mins, self.maxs, (self.goalstack01.absmin + self.goalstack01.absmax) * 0.5, bot_navigation_movemode))
906 /// dprint("path optimized, removed a goal from the queue\n");
907 navigation_poproute();
908 // TODO this may also be a nice idea to do "early" (e.g. by
909 // manipulating the vlen() comparisons) to shorten paths in
910 // general - this would make bots walk more "on rails" than
911 // "zigzagging" which they currently do with sufficiently
912 // random-like waypoints, and thus can make a nice bot
913 // personality property
917 // Loose goal touching check when running
918 if(self.aistatus & AI_STATUS_RUNNING)
919 if(self.goalcurrent.classname=="waypoint")
921 if(vlen(self.origin - self.goalcurrent.origin)<150)
923 traceline(self.origin + self.view_ofs , self.goalcurrent.origin, TRUE, world);
924 if(trace_fraction==1)
926 // Detect personal waypoints
927 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
928 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
930 self.aistatus &~= AI_STATUS_WAYPOINT_PERSONAL_GOING;
931 self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
934 navigation_poproute();
939 while (self.goalcurrent && boxesoverlap(m1, m2, self.goalcurrent.absmin, self.goalcurrent.absmax))
941 // Detect personal waypoints
942 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
943 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
945 self.aistatus &~= AI_STATUS_WAYPOINT_PERSONAL_GOING;
946 self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
949 navigation_poproute();
953 // begin a goal selection session (queries spawnfunc_waypoint network)
954 void navigation_goalrating_start()
956 if(self.aistatus & AI_STATUS_STUCK)
959 self.navigation_jetpack_goal = world;
960 navigation_bestrating = -1;
961 self.navigation_hasgoals = FALSE;
962 navigation_clearroute();
963 navigation_bestgoal = world;
964 navigation_markroutes(world);
967 // ends a goal selection session (updates goal stack to the best goal)
968 void navigation_goalrating_end()
970 if(self.aistatus & AI_STATUS_STUCK)
973 navigation_routetogoal(navigation_bestgoal, self.origin);
974 // dprint("best goal ", self.goalcurrent.classname , "\n");
976 // If the bot got stuck then try to reach the farthest waypoint
977 if not (self.navigation_hasgoals)
978 if (autocvar_bot_wander_enable)
980 if not(self.aistatus & AI_STATUS_STUCK)
982 dprint(self.netname, " cannot walk to any goal\n");
983 self.aistatus |= AI_STATUS_STUCK;
986 self.navigation_hasgoals = FALSE; // Reset this value
990 void botframe_updatedangerousobjects(float maxupdate)
992 local entity head, bot_dodgelist;
993 local vector m1, m2, v, o;
994 local float c, d, danger;
996 bot_dodgelist = findchainfloat(bot_dodge, TRUE);
997 botframe_dangerwaypoint = find(botframe_dangerwaypoint, classname, "waypoint");
998 while (botframe_dangerwaypoint != world)
1001 m1 = botframe_dangerwaypoint.mins;
1002 m2 = botframe_dangerwaypoint.maxs;
1003 head = bot_dodgelist;
1007 v_x = bound(m1_x, v_x, m2_x);
1008 v_y = bound(m1_y, v_y, m2_y);
1009 v_z = bound(m1_z, v_z, m2_z);
1010 o = (head.absmin + head.absmax) * 0.5;
1011 d = head.bot_dodgerating - vlen(o - v);
1014 traceline(o, v, TRUE, world);
1015 if (trace_fraction == 1)
1016 danger = danger + d;
1020 botframe_dangerwaypoint.dmg = danger;
1024 botframe_dangerwaypoint = find(botframe_dangerwaypoint, classname, "waypoint");
1028 void navigation_unstuck()
1030 float search_radius = 1000;
1032 if not(autocvar_bot_wander_enable)
1035 if not(bot_waypoint_queue_owner)
1037 // dprint(self.netname, " sutck, taking over the waypoints queue\n");
1038 bot_waypoint_queue_owner = self;
1039 bot_waypoint_queue_bestgoal = world;
1040 bot_waypoint_queue_bestgoalrating = 0;
1043 if(bot_waypoint_queue_owner!=self)
1046 if (bot_waypoint_queue_goal)
1048 // evaluate the next goal on the queue
1049 float d = vlen(self.origin - bot_waypoint_queue_goal.origin);
1050 // dprint(self.netname, " evaluating ", bot_waypoint_queue_goal.classname, " with distance ", ftos(d), "\n");
1051 if(tracewalk(bot_waypoint_queue_goal, self.origin, PL_MIN, PL_MAX, bot_waypoint_queue_goal.origin, bot_navigation_movemode))
1053 if( d > bot_waypoint_queue_bestgoalrating)
1055 bot_waypoint_queue_bestgoalrating = d;
1056 bot_waypoint_queue_bestgoal = bot_waypoint_queue_goal;
1059 bot_waypoint_queue_goal = bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal;
1061 if not(bot_waypoint_queue_goal)
1063 if (bot_waypoint_queue_bestgoal)
1065 dprint(self.netname, " stuck, reachable waypoint found, heading to it\n");
1066 navigation_routetogoal(bot_waypoint_queue_bestgoal, self.origin);
1067 self.bot_strategytime = time + autocvar_bot_ai_strategyinterval;
1068 self.aistatus &~= AI_STATUS_STUCK;
1072 dprint(self.netname, " stuck, cannot walk to any waypoint at all\n");
1075 bot_waypoint_queue_owner = world;
1080 if(bot_strategytoken!=self)
1083 // build a new queue
1084 dprint(self.netname, " stuck, scanning reachable waypoints within ", ftos(search_radius)," qu\n");
1089 head = findradius(self.origin, search_radius);
1093 if(head.classname=="waypoint")
1094 // if(!(head.wpflags & WAYPOINTFLAG_GENERATED))
1096 if(bot_waypoint_queue_goal)
1097 bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = head;
1101 bot_waypoint_queue_goal = head;
1102 bot_waypoint_queue_goal.bot_waypoint_queue_nextgoal = world;
1109 bot_waypoint_queue_goal = first;
1112 dprint(self.netname, " stuck, cannot walk to any waypoint at all\n");
1113 bot_waypoint_queue_owner = world;
1118 // Support for debugging tracewalk visually
1120 void debugresetnodes()
1122 debuglastnode = '0 0 0';
1125 void debugnode(vector node)
1127 if not(self.classname=="player")
1130 if(debuglastnode=='0 0 0')
1132 debuglastnode = node;
1136 te_lightning2(world, node, debuglastnode);
1137 debuglastnode = node;
1140 void debugnodestatus(vector position, float status)
1146 case DEBUG_NODE_SUCCESS:
1149 case DEBUG_NODE_WARNING:
1152 case DEBUG_NODE_FAIL:
1159 te_customflash(position, 40, 2, c);
1162 // Support for debugging the goal stack visually
1165 .vector lastposition;
1167 // Debug the goal stack visually
1168 void debuggoalstack()
1171 local vector org, go;
1173 if(self.goalcounter==0)goal=self.goalcurrent;
1174 else if(self.goalcounter==1)goal=self.goalstack01;
1175 else if(self.goalcounter==2)goal=self.goalstack02;
1176 else if(self.goalcounter==3)goal=self.goalstack03;
1177 else if(self.goalcounter==4)goal=self.goalstack04;
1178 else if(self.goalcounter==5)goal=self.goalstack05;
1179 else if(self.goalcounter==6)goal=self.goalstack06;
1180 else if(self.goalcounter==7)goal=self.goalstack07;
1181 else if(self.goalcounter==8)goal=self.goalstack08;
1182 else if(self.goalcounter==9)goal=self.goalstack09;
1183 else if(self.goalcounter==10)goal=self.goalstack10;
1184 else if(self.goalcounter==11)goal=self.goalstack11;
1185 else if(self.goalcounter==12)goal=self.goalstack12;
1186 else if(self.goalcounter==13)goal=self.goalstack13;
1187 else if(self.goalcounter==14)goal=self.goalstack14;
1188 else if(self.goalcounter==15)goal=self.goalstack15;
1189 else if(self.goalcounter==16)goal=self.goalstack16;
1190 else if(self.goalcounter==17)goal=self.goalstack17;
1191 else if(self.goalcounter==18)goal=self.goalstack18;
1192 else if(self.goalcounter==19)goal=self.goalstack19;
1193 else if(self.goalcounter==20)goal=self.goalstack20;
1194 else if(self.goalcounter==21)goal=self.goalstack21;
1195 else if(self.goalcounter==22)goal=self.goalstack22;
1196 else if(self.goalcounter==23)goal=self.goalstack23;
1197 else if(self.goalcounter==24)goal=self.goalstack24;
1198 else if(self.goalcounter==25)goal=self.goalstack25;
1199 else if(self.goalcounter==26)goal=self.goalstack26;
1200 else if(self.goalcounter==27)goal=self.goalstack27;
1201 else if(self.goalcounter==28)goal=self.goalstack28;
1202 else if(self.goalcounter==29)goal=self.goalstack29;
1203 else if(self.goalcounter==30)goal=self.goalstack30;
1204 else if(self.goalcounter==31)goal=self.goalstack31;
1208 self.goalcounter = 0;
1209 self.lastposition='0 0 0';
1213 if(self.lastposition=='0 0 0')
1216 org = self.lastposition;
1219 go = ( goal.absmin + goal.absmax ) * 0.5;
1220 te_lightning2(world, org, go);
1221 self.lastposition = go;