Removed support for multi goal routes. Extra overhead, also will become obsolete...
[divverent/nexuiz.git] / data / qcsrc / server / bot / navigation.qc
1
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
4
5 float tracewalk(entity e, vector start, vector m1, vector m2, vector end, float movemode)
6 {
7         local vector org;
8         local vector move;
9         local vector dir;
10         local float dist;
11         local float totaldist;
12         local float stepdist;
13         local float yaw;
14         local float ignorehazards;
15         local float swimming;
16
17         #ifdef DEBUG_TRACEWALK
18                 debugresetnodes();
19                 debugnode(start);
20         #endif
21
22         move = end - start;
23         move_z = 0;
24         org = start;
25         dist = totaldist = vlen(move);
26         dir = normalize(move);
27         stepdist = 32;
28         ignorehazards = FALSE;
29
30         // Analyze starting point
31         traceline(start, start, MOVE_NORMAL, e);
32         if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
33                 ignorehazards = TRUE;
34         else
35         {
36                 traceline( start, start + '0 0 -65536', MOVE_NORMAL, e);
37                 if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
38                 {
39                         ignorehazards = TRUE;
40                         swimming = TRUE;
41                 }
42         }
43         tracebox(start, m1, m2, start, MOVE_NOMONSTERS, e);
44         if (trace_startsolid)
45         {
46                 // Bad start
47                 #ifdef DEBUG_TRACEWALK
48                         debugnodestatus(start, DEBUG_NODE_FAIL);
49                 #endif
50                 //print("tracewalk: ", vtos(start), " is a bad start\n");
51                 return FALSE;
52         }
53
54         // Movement loop
55         yaw = vectoyaw(move);
56         move = end - org;
57         for (;;)
58         {
59                 if (boxesoverlap(end, end, org + m1 + '-1 -1 -1', org + m2 + '1 1 1'))
60                 {
61                         // Succeeded
62                         #ifdef DEBUG_TRACEWALK
63                                 debugnodestatus(org, DEBUG_NODE_SUCCESS);
64                         #endif
65                         //print("tracewalk: ", vtos(start), " can reach ", vtos(end), "\n");
66                         return TRUE;
67                 }
68                 #ifdef DEBUG_TRACEWALK
69                         debugnode(org);
70                 #endif
71
72                 if (dist <= 0)
73                         break;
74                 if (stepdist > dist)
75                         stepdist = dist;
76                 dist = dist - stepdist;
77                 traceline(org, org, MOVE_NORMAL, e);
78                 if (!ignorehazards)
79                 {
80                         if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
81                         {
82                                 // hazards blocking path
83                                 #ifdef DEBUG_TRACEWALK
84                                         debugnodestatus(org, DEBUG_NODE_FAIL);
85                                 #endif
86                                 //print("tracewalk: ", vtos(start), " hits a hazard when trying to reach ", vtos(end), "\n");
87                                 return FALSE;
88                         }
89                 }
90                 if (trace_dpstartcontents & DPCONTENTS_LIQUIDSMASK)
91                 {
92                         move = normalize(end - org);
93                         tracebox(org, m1, m2, org + move * stepdist, movemode, e);
94
95                         #ifdef DEBUG_TRACEWALK
96                                 debugnode(trace_endpos);
97                         #endif
98
99                         if (trace_fraction < 1)
100                         {
101                                 swimming = TRUE;
102                                 org = trace_endpos - normalize(org - trace_endpos) * stepdist;
103                                 for(; org_z < end_z + self.maxs_z; org_z += stepdist)
104                                 {
105                                                 #ifdef DEBUG_TRACEWALK
106                                                         debugnode(org);
107                                                 #endif
108                                         if(pointcontents(org) == CONTENT_EMPTY)
109                                                         break;
110                                 }
111
112                                 if not (pointcontents(org + '0 0 1') == CONTENT_EMPTY)
113                                 {
114                                         #ifdef DEBUG_TRACEWALK
115                                                 debugnodestatus(org, DEBUG_NODE_FAIL);
116                                         #endif
117                                         return FALSE;
118                                         //print("tracewalk: ", vtos(start), " failed under water\n");
119                                 }
120                                 continue;
121
122                         }
123                         else
124                                 org = trace_endpos;
125                 }
126                 else
127                 {
128                         move = dir * stepdist + org;
129                         tracebox(org, m1, m2, move, movemode, e);
130
131                         #ifdef DEBUG_TRACEWALK
132                                 debugnode(trace_endpos);
133                         #endif
134
135                         // hit something
136                         if (trace_fraction < 1)
137                         {
138                                 // check if we can walk over this obstacle
139                                 tracebox(org + stepheightvec, m1, m2, move + stepheightvec, movemode, e);
140                                 if (trace_fraction < 1 || trace_startsolid)
141                                 {
142                                         #ifdef DEBUG_TRACEWALK
143                                                 debugnodestatus(trace_endpos, DEBUG_NODE_WARNING);
144                                         #endif
145
146                                         // check for doors
147                                         traceline( org, move, movemode, e);
148                                         if ( trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
149                                         {
150                                                 local vector nextmove;
151                                                 move = trace_endpos;
152                                                 while(trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
153                                                 {
154                                                         nextmove = move + (dir * stepdist);
155                                                         traceline( move, nextmove, movemode, e);
156                                                         move = nextmove;
157                                                 }
158                                         }
159                                         else
160                                         {
161                                                 #ifdef DEBUG_TRACEWALK
162                                                         debugnodestatus(trace_endpos, DEBUG_NODE_FAIL);
163                                                 #endif
164                                                 //print("tracewalk: ", vtos(start), " hit something when trying to reach ", vtos(end), "\n");
165                                                 //te_explosion(trace_endpos);
166                                                 //print(ftos(e.dphitcontentsmask), "\n");
167                                                 return FALSE; // failed
168                                         }
169                                 }
170                                 else
171                                         move = trace_endpos;
172                         }
173                         else
174                                 move = trace_endpos;
175
176                         // trace down from stepheight as far as possible and move there,
177                         // if this starts in solid we try again without the stepup, and
178                         // if that also fails we assume it is a wall
179                         // (this is the same logic as the Quake walkmove function used)
180                         tracebox(move, m1, m2, move + '0 0 -65536', movemode, e);
181
182                         // moved successfully
183                         if(swimming)
184                         {
185                                 local float c;
186                                 c = pointcontents(org + '0 0 1');
187                                 if not(c == CONTENT_WATER || c == CONTENT_LAVA || c == CONTENT_SLIME)
188                                         swimming = FALSE;
189                                 else
190                                         continue;
191                         }
192
193                         org = trace_endpos;
194                 }
195         }
196
197         //print("tracewalk: ", vtos(start), " did not arrive at ", vtos(end), " but at ", vtos(org), "\n");
198
199         // moved but didn't arrive at the intended destination
200         #ifdef DEBUG_TRACEWALK
201                 debugnodestatus(org, DEBUG_NODE_FAIL);
202         #endif
203
204         return FALSE;
205 };
206
207 /////////////////////////////////////////////////////////////////////////////
208 // goal stack
209 /////////////////////////////////////////////////////////////////////////////
210
211 // completely empty the goal stack, used when deciding where to go
212 void navigation_clearroute()
213 {
214         //print("bot ", etos(self), " clear\n");
215         self.navigation_hasgoals = FALSE;
216         self.goalcurrent = world;
217         self.goalstack01 = world;
218         self.goalstack02 = world;
219         self.goalstack03 = world;
220         self.goalstack04 = world;
221         self.goalstack05 = world;
222         self.goalstack06 = world;
223         self.goalstack07 = world;
224         self.goalstack08 = world;
225         self.goalstack09 = world;
226         self.goalstack10 = world;
227         self.goalstack11 = world;
228         self.goalstack12 = world;
229         self.goalstack13 = world;
230         self.goalstack14 = world;
231         self.goalstack15 = world;
232         self.goalstack16 = world;
233         self.goalstack17 = world;
234         self.goalstack18 = world;
235         self.goalstack19 = world;
236         self.goalstack20 = world;
237         self.goalstack21 = world;
238         self.goalstack22 = world;
239         self.goalstack23 = world;
240         self.goalstack24 = world;
241         self.goalstack25 = world;
242         self.goalstack26 = world;
243         self.goalstack27 = world;
244         self.goalstack28 = world;
245         self.goalstack29 = world;
246         self.goalstack30 = world;
247         self.goalstack31 = world;
248 };
249
250 // add a new goal at the beginning of the stack
251 // (in other words: add a new prerequisite before going to the later goals)
252 // NOTE: when a waypoint is added, the WP gets pushed first, then the
253 // next-closest WP on the shortest path to the WP
254 // That means, if the stack overflows, the bot will know how to do the FIRST 32
255 // steps to the goal, and then recalculate the path.
256 void navigation_pushroute(entity e)
257 {
258         //print("bot ", etos(self), " push ", etos(e), "\n");
259         self.goalstack31 = self.goalstack30;
260         self.goalstack30 = self.goalstack29;
261         self.goalstack29 = self.goalstack28;
262         self.goalstack28 = self.goalstack27;
263         self.goalstack27 = self.goalstack26;
264         self.goalstack26 = self.goalstack25;
265         self.goalstack25 = self.goalstack24;
266         self.goalstack24 = self.goalstack23;
267         self.goalstack23 = self.goalstack22;
268         self.goalstack22 = self.goalstack21;
269         self.goalstack21 = self.goalstack20;
270         self.goalstack20 = self.goalstack19;
271         self.goalstack19 = self.goalstack18;
272         self.goalstack18 = self.goalstack17;
273         self.goalstack17 = self.goalstack16;
274         self.goalstack16 = self.goalstack15;
275         self.goalstack15 = self.goalstack14;
276         self.goalstack14 = self.goalstack13;
277         self.goalstack13 = self.goalstack12;
278         self.goalstack12 = self.goalstack11;
279         self.goalstack11 = self.goalstack10;
280         self.goalstack10 = self.goalstack09;
281         self.goalstack09 = self.goalstack08;
282         self.goalstack08 = self.goalstack07;
283         self.goalstack07 = self.goalstack06;
284         self.goalstack06 = self.goalstack05;
285         self.goalstack05 = self.goalstack04;
286         self.goalstack04 = self.goalstack03;
287         self.goalstack03 = self.goalstack02;
288         self.goalstack02 = self.goalstack01;
289         self.goalstack01 = self.goalcurrent;
290         self.goalcurrent = e;
291 };
292
293 // remove first goal from stack
294 // (in other words: remove a prerequisite for reaching the later goals)
295 // (used when a spawnfunc_waypoint is reached)
296 void navigation_poproute()
297 {
298         //print("bot ", etos(self), " pop\n");
299         self.goalcurrent = self.goalstack01;
300         self.goalstack01 = self.goalstack02;
301         self.goalstack02 = self.goalstack03;
302         self.goalstack03 = self.goalstack04;
303         self.goalstack04 = self.goalstack05;
304         self.goalstack05 = self.goalstack06;
305         self.goalstack06 = self.goalstack07;
306         self.goalstack07 = self.goalstack08;
307         self.goalstack08 = self.goalstack09;
308         self.goalstack09 = self.goalstack10;
309         self.goalstack10 = self.goalstack11;
310         self.goalstack11 = self.goalstack12;
311         self.goalstack12 = self.goalstack13;
312         self.goalstack13 = self.goalstack14;
313         self.goalstack14 = self.goalstack15;
314         self.goalstack15 = self.goalstack16;
315         self.goalstack16 = self.goalstack17;
316         self.goalstack17 = self.goalstack18;
317         self.goalstack18 = self.goalstack19;
318         self.goalstack19 = self.goalstack20;
319         self.goalstack20 = self.goalstack21;
320         self.goalstack21 = self.goalstack22;
321         self.goalstack22 = self.goalstack23;
322         self.goalstack23 = self.goalstack24;
323         self.goalstack24 = self.goalstack25;
324         self.goalstack25 = self.goalstack26;
325         self.goalstack26 = self.goalstack27;
326         self.goalstack27 = self.goalstack28;
327         self.goalstack28 = self.goalstack29;
328         self.goalstack29 = self.goalstack30;
329         self.goalstack30 = self.goalstack31;
330         self.goalstack31 = world;
331 };
332
333 // find the spawnfunc_waypoint near a dynamic goal such as a dropped weapon
334 entity navigation_findnearestwaypoint(entity ent, float walkfromwp)
335 {
336         local entity waylist, w, best;
337         local float dist, bestdist;
338         local vector v, org, pm1, pm2;
339         pm1 = ent.origin + ent.mins;
340         pm2 = ent.origin + ent.maxs;
341         waylist = findchain(classname, "waypoint");
342
343         // do two scans, because box test is cheaper
344         w = waylist;
345         while (w)
346         {
347                 // if object is touching spawnfunc_waypoint
348                 if(w != ent)
349                         if (boxesoverlap(pm1, pm2, w.absmin, w.absmax))
350                                 return w;
351                 w = w.chain;
352         }
353
354         org = ent.origin + 0.5 * (ent.mins + ent.maxs);
355         org_z = ent.origin_z + ent.mins_z - PL_MIN_z; // player height
356         // TODO possibly make other code have the same support for bboxes
357         if(ent.tag_entity)
358                 org = org + ent.tag_entity.origin;
359         if (navigation_testtracewalk)
360                 te_plasmaburn(org);
361
362         best = world;
363         bestdist = 1050;
364
365         // box check failed, try walk
366         w = waylist;
367         while (w)
368         {
369                 // if object can walk from spawnfunc_waypoint
370                 if(w != ent)
371                 {
372                         if (w.wpisbox)
373                         {
374                                 local vector wm1, wm2;
375                                 wm1 = w.origin + w.mins;
376                                 wm2 = w.origin + w.maxs;
377                                 v_x = bound(wm1_x, org_x, wm2_x);
378                                 v_y = bound(wm1_y, org_y, wm2_y);
379                                 v_z = bound(wm1_z, org_z, wm2_z);
380                         }
381                         else
382                                 v = w.origin;
383                         dist = vlen(v - org);
384                         if (bestdist > dist)
385                         {
386                                 traceline(v, org, TRUE, ent);
387                                 if (trace_fraction == 1)
388                                 {
389                                         if (walkfromwp)
390                                         {
391                                                 //print("^1can I reach ", vtos(org), " from ", vtos(v), "?\n");
392                                                 if (tracewalk(ent, v, PL_MIN, PL_MAX, org, bot_navigation_movemode))
393                                                 {
394                                                         bestdist = dist;
395                                                         best = w;
396                                                 }
397                                         }
398                                         else
399                                         {
400                                                 if (tracewalk(ent, org, PL_MIN, PL_MAX, v, bot_navigation_movemode))
401                                                 {
402                                                         bestdist = dist;
403                                                         best = w;
404                                                 }
405                                         }
406                                 }
407                         }
408                 }
409                 w = w.chain;
410         }
411         return best;
412 }
413
414 // finds the waypoints near the bot initiating a navigation query
415 float navigation_markroutes_nearestwaypoints(entity waylist, float maxdist)
416 {
417         local entity head;
418         local vector v, m1, m2, diff;
419         local float c;
420 //      navigation_testtracewalk = TRUE;
421         c = 0;
422         head = waylist;
423         while (head)
424         {
425                 if (!head.wpconsidered)
426                 {
427                         if (head.wpisbox)
428                         {
429                                 m1 = head.origin + head.mins;
430                                 m2 = head.origin + head.maxs;
431                                 v = self.origin;
432                                 v_x = bound(m1_x, v_x, m2_x);
433                                 v_y = bound(m1_y, v_y, m2_y);
434                                 v_z = bound(m1_z, v_z, m2_z);
435                         }
436                         else
437                                 v = head.origin;
438                         diff = v - self.origin;
439                         diff_z = max(0, diff_z);
440                         if (vlen(diff) < maxdist)
441                         {
442                                 head.wpconsidered = TRUE;
443                                 if (tracewalk(self, self.origin, self.mins, self.maxs, v, bot_navigation_movemode))
444                                 {
445                                         head.wpnearestpoint = v;
446                                         head.wpcost = vlen(v - self.origin) + head.dmg;
447                                         head.wpfire = 1;
448                                         head.enemy = world;
449                                         c = c + 1;
450                                 }
451                         }
452                 }
453                 head = head.chain;
454         }
455         //navigation_testtracewalk = FALSE;
456         return c;
457 }
458
459 // updates a path link if a spawnfunc_waypoint link is better than the current one
460 void navigation_markroutes_checkwaypoint(entity w, entity wp, float cost2, vector p)
461 {
462         local vector m1;
463         local vector m2;
464         local vector v;
465         if (wp.wpisbox)
466         {
467                 m1 = wp.absmin;
468                 m2 = wp.absmax;
469                 v_x = bound(m1_x, p_x, m2_x);
470                 v_y = bound(m1_y, p_y, m2_y);
471                 v_z = bound(m1_z, p_z, m2_z);
472         }
473         else
474                 v = wp.origin;
475         cost2 = cost2 + vlen(v - p);
476         if (wp.wpcost > cost2)
477         {
478                 wp.wpcost = cost2;
479                 wp.enemy = w;
480                 wp.wpfire = 1;
481                 wp.wpnearestpoint = v;
482         }
483 };
484
485 // queries the entire spawnfunc_waypoint network for pathes leading away from the bot
486 void navigation_markroutes(entity fixed_source_waypoint)
487 {
488         local entity w, wp, waylist;
489         local float searching, cost, cost2;
490         local vector p;
491         w = waylist = findchain(classname, "waypoint");
492         while (w)
493         {
494                 w.wpconsidered = FALSE;
495                 w.wpnearestpoint = '0 0 0';
496                 w.wpcost = 10000000;
497                 w.wpfire = 0;
498                 w.enemy = world;
499                 w = w.chain;
500         }
501
502         if(fixed_source_waypoint)
503         {
504                 fixed_source_waypoint.wpconsidered = TRUE;
505                 fixed_source_waypoint.wpnearestpoint = fixed_source_waypoint.origin + 0.5 * (fixed_source_waypoint.mins + fixed_source_waypoint.maxs);
506                 fixed_source_waypoint.wpcost = fixed_source_waypoint.dmg;
507                 fixed_source_waypoint.wpfire = 1;
508                 fixed_source_waypoint.enemy = world;
509         }
510         else
511         {
512                 // try a short range search for the nearest waypoints, and expand the search repeatedly if none are found
513                 // as this search is expensive we will use lower values if the bot is on the air
514                 local float i, increment, maxdistance;
515                 if(self.flags & FL_ONGROUND)
516                 {
517                         increment = 750;
518                         maxdistance = 50000;
519                 }
520                 else
521                 {
522                         increment = 500;
523                         maxdistance = 1500;
524                 }
525
526                 for(i=increment;!navigation_markroutes_nearestwaypoints(waylist, i)&&i<maxdistance;i+=increment);
527         }
528
529         searching = TRUE;
530         while (searching)
531         {
532                 searching = FALSE;
533                 w = waylist;
534                 while (w)
535                 {
536                         if (w.wpfire)
537                         {
538                                 searching = TRUE;
539                                 w.wpfire = 0;
540                                 cost = w.wpcost;
541                                 p = w.wpnearestpoint;
542                                 wp = w.wp00;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp00mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
543                                 wp = w.wp01;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp01mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
544                                 wp = w.wp02;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp02mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
545                                 wp = w.wp03;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp03mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
546                                 wp = w.wp04;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp04mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
547                                 wp = w.wp05;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp05mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
548                                 wp = w.wp06;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp06mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
549                                 wp = w.wp07;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp07mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
550                                 wp = w.wp08;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp08mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
551                                 wp = w.wp09;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp09mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
552                                 wp = w.wp10;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp10mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
553                                 wp = w.wp11;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp11mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
554                                 wp = w.wp12;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp12mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
555                                 wp = w.wp13;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp13mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
556                                 wp = w.wp14;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp14mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
557                                 wp = w.wp15;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp15mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
558                                 wp = w.wp16;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp16mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
559                                 wp = w.wp17;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp17mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
560                                 wp = w.wp18;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp18mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
561                                 wp = w.wp19;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp19mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
562                                 wp = w.wp20;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp20mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
563                                 wp = w.wp21;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp21mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
564                                 wp = w.wp22;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp22mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
565                                 wp = w.wp23;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp23mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
566                                 wp = w.wp24;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp24mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
567                                 wp = w.wp25;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp25mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
568                                 wp = w.wp26;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp26mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
569                                 wp = w.wp27;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp27mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
570                                 wp = w.wp28;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp28mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
571                                 wp = w.wp29;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp29mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
572                                 wp = w.wp30;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp30mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
573                                 wp = w.wp31;if (wp){cost2 = cost + wp.dmg;if (wp.wpcost > cost2 + w.wp31mincost) navigation_markroutes_checkwaypoint(w, wp, cost2, p);
574                                 }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
575                         }
576                         w = w.chain;
577                 }
578         }
579 };
580
581 // queries the entire spawnfunc_waypoint network for pathes leading to the bot
582 void navigation_markroutes_inverted(entity fixed_source_waypoint)
583 {
584         local entity w, wp, waylist;
585         local float searching, cost, cost2;
586         local vector p;
587         w = waylist = findchain(classname, "waypoint");
588         while (w)
589         {
590                 w.wpconsidered = FALSE;
591                 w.wpnearestpoint = '0 0 0';
592                 w.wpcost = 10000000;
593                 w.wpfire = 0;
594                 w.enemy = world;
595                 w = w.chain;
596         }
597
598         if(fixed_source_waypoint)
599         {
600                 fixed_source_waypoint.wpconsidered = TRUE;
601                 fixed_source_waypoint.wpnearestpoint = fixed_source_waypoint.origin + 0.5 * (fixed_source_waypoint.mins + fixed_source_waypoint.maxs);
602                 fixed_source_waypoint.wpcost = fixed_source_waypoint.dmg; // the cost to get from X to fixed_source_waypoint
603                 fixed_source_waypoint.wpfire = 1;
604                 fixed_source_waypoint.enemy = world;
605         }
606         else
607         {
608                 error("need to start with a waypoint\n");
609         }
610
611         searching = TRUE;
612         while (searching)
613         {
614                 searching = FALSE;
615                 w = waylist;
616                 while (w)
617                 {
618                         if (w.wpfire)
619                         {
620                                 searching = TRUE;
621                                 w.wpfire = 0;
622                                 cost = w.wpcost; // cost to walk from w to home
623                                 p = w.wpnearestpoint;
624                                 for(wp = waylist; wp; wp = wp.chain)
625                                 {
626                                         if(w != wp.wp00) if(w != wp.wp01) if(w != wp.wp02) if(w != wp.wp03)
627                                         if(w != wp.wp04) if(w != wp.wp05) if(w != wp.wp06) if(w != wp.wp07)
628                                         if(w != wp.wp08) if(w != wp.wp09) if(w != wp.wp10) if(w != wp.wp11)
629                                         if(w != wp.wp12) if(w != wp.wp13) if(w != wp.wp14) if(w != wp.wp15)
630                                         if(w != wp.wp16) if(w != wp.wp17) if(w != wp.wp18) if(w != wp.wp19)
631                                         if(w != wp.wp20) if(w != wp.wp21) if(w != wp.wp22) if(w != wp.wp23)
632                                         if(w != wp.wp24) if(w != wp.wp25) if(w != wp.wp26) if(w != wp.wp27)
633                                         if(w != wp.wp28) if(w != wp.wp29) if(w != wp.wp30) if(w != wp.wp31)
634                                                 continue;
635                                         cost2 = cost + wp.dmg;
636                                         navigation_markroutes_checkwaypoint(w, wp, cost2, p);
637                                 }
638                         }
639                         w = w.chain;
640                 }
641         }
642 };
643
644 // updates the best goal according to a weighted calculation of travel cost and item value of a new proposed item
645 void navigation_routerating(entity e, float f, float rangebias)
646 {
647         entity nwp;
648         if (!e)
649                 return;
650
651         //print("routerating ", etos(e), " = ", ftos(f), " - ", ftos(rangebias), "\n");
652
653         // Evaluate path using jetpack
654         if(g_jetpack)
655         if(self.items & IT_JETPACK)
656         if(cvar("bot_ai_navigation_jetpack"))
657         if(vlen(self.origin - e.origin) > cvar("bot_ai_navigation_jetpack_mindistance"))
658         {
659                 vector pointa, pointb;
660
661         //      dprint("jetpack ai: evaluating path for ", e.classname,"\n");
662
663                 // Point A
664                 traceline(self.origin, self.origin + '0 0 65535', MOVE_NORMAL, self);
665                 pointa = trace_endpos - '0 0 1';
666
667                 // Point B
668                 traceline(e.origin, e.origin + '0 0 65535', MOVE_NORMAL, e);
669                 pointb = trace_endpos - '0 0 1';
670
671                 // Can I see these two points from the sky?
672                 traceline(pointa, pointb, MOVE_NORMAL, self);
673
674                 if(trace_fraction==1)
675                 {
676                 //      dprint("jetpack ai: can bridge these two points\n");
677
678                         // Lower the altitude of these points as much as possible
679                         local float zdistance, xydistance, cost, t, fuel;
680                         local vector down, npa, npb;
681
682                         down = '0 0 -1' * (PL_MAX_z - PL_MIN_z) * 10;
683
684                         do{
685                                 npa = pointa + down;
686                                 npb = pointb + down;
687
688                                 if(npa_z<=self.absmax_z)
689                                         break;
690
691                                 if(npb_z<=e.absmax_z)
692                                         break;
693
694                                 traceline(npa, npb, MOVE_NORMAL, self);
695                                 if(trace_fraction==1)
696                                 {
697                                         pointa = npa;
698                                         pointb = npb;
699                                 }
700                         }
701                         while(trace_fraction == 1);
702
703
704                         // Rough estimation of fuel consumption
705                         // (ignores acceleration and current xyz velocity)
706                         xydistance = vlen(pointa - pointb);
707                         zdistance = fabs(pointa_z - self.origin_z);
708
709                         t = zdistance / cvar("g_jetpack_maxspeed_up");
710                         t += xydistance / cvar("g_jetpack_maxspeed_side");
711                         fuel = t * cvar("g_jetpack_fuel") * 0.8;
712
713                 //      dprint("jetpack ai: required fuel ", ftos(fuel), " self.ammo_fuel ", ftos(self.ammo_fuel),"\n");
714
715                         // enough fuel ?
716                         if(self.ammo_fuel>fuel)
717                         {
718                                 // Estimate cost
719                                 // (as onground costs calculation is mostly based on distances, here we do the same establishing some relationship
720                                 //  - between air and ground speeds)
721
722                                 cost = xydistance / (cvar("g_jetpack_maxspeed_side")/cvar("sv_maxspeed"));
723                                 cost += zdistance / (cvar("g_jetpack_maxspeed_up")/cvar("sv_maxspeed"));
724                                 cost *= 1.5;
725
726                                 // Compare against other goals
727                                 f = f * rangebias / (rangebias + cost);
728
729                                 if (navigation_bestrating < f)
730                                 {
731                         //              dprint("jetpack path: added goal", e.classname, " (with rating ", ftos(f), ")\n");
732                                         navigation_bestrating = f;
733                                         navigation_bestgoal = e;
734                                         self.navigation_jetpack_goal = e;
735                                         self.navigation_jetpack_point = pointb;
736                                 }
737                                 return;
738                         }
739                 }
740         }
741
742         //te_wizspike(e.origin);
743         //bprint(etos(e));
744         //bprint("\n");
745         // update the cached spawnfunc_waypoint link on a dynamic item entity
746         if(e.classname == "waypoint" && !(e.wpflags & WAYPOINTFLAG_PERSONAL))
747         {
748                 nwp = e;
749         }
750         else
751         {
752                 if (time > e.nearestwaypointtimeout)
753                 {
754                         nwp = navigation_findnearestwaypoint(e, TRUE);
755                         if(nwp)
756                                 e.nearestwaypoint = nwp;
757                         else
758                                 dprint("FAILED to find a nearest waypoint to '", e.classname, "' #", etos(e), "\n");
759
760                         // TODO: Cleaner solution, probably handling this timeout from ctf.qc
761                         if(e.classname=="item_flag_team")
762                                 e.nearestwaypointtimeout = time + 2;
763                         else
764                                 e.nearestwaypointtimeout = time + random() * 3 + 5;
765                 }
766                 nwp = e.nearestwaypoint;
767         }
768
769         //dprint("-- checking ", e.classname, " (with cost ", ftos(nwp.wpcost), ")\n");
770         if (nwp)
771         if (nwp.wpcost < 10000000)
772         {
773                 //te_wizspike(nwp.wpnearestpoint);
774         //      dprint(e.classname, " ", ftos(f), "/(1+", ftos((nwp.wpcost + vlen(e.origin - nwp.wpnearestpoint))), "/", ftos(rangebias), ") = ");
775                 f = f * rangebias / (rangebias + (nwp.wpcost + vlen(e.origin - nwp.wpnearestpoint)));
776                 //dprint("considering ", e.classname, " (with rating ", ftos(f), ")\n");
777                 //dprint(ftos(f));
778                 if (navigation_bestrating < f)
779                 {
780                 //      dprint("ground path: added goal ", e.classname, " (with rating ", ftos(f), ")\n");
781                         navigation_bestrating = f;
782                         navigation_bestgoal = e;
783                 }
784         }
785         //dprint("\n");
786 };
787
788 // adds an item to the the goal stack with the path to a given item
789 float navigation_routetogoal(entity e, vector startposition)
790 {
791         self.goalentity = e;
792
793         // if there is no goal, just exit
794         if (!e)
795                 return FALSE;
796
797         self.navigation_hasgoals = TRUE;
798
799         // put the entity on the goal stack
800         //print("routetogoal ", etos(e), "\n");
801         navigation_pushroute(e);
802
803         if(g_jetpack)
804         if(e==self.navigation_jetpack_goal)
805                 return TRUE;
806
807         // if it can reach the goal there is nothing more to do
808         if (tracewalk(self, startposition, PL_MIN, PL_MAX, e.origin, bot_navigation_movemode))
809                 return TRUE;
810
811         // see if there are waypoints describing a path to the item
812         if(e.classname != "waypoint" || (e.wpflags & WAYPOINTFLAG_PERSONAL))
813                 e = e.nearestwaypoint;
814         else
815                 e = e.enemy; // we already have added it, so...
816
817         if(e == world)
818                 return FALSE;
819
820         for (;;)
821         {
822                 // add the spawnfunc_waypoint to the path
823                 navigation_pushroute(e);
824                 e = e.enemy;
825
826                 if(e==world)
827                         break;
828         }
829
830         return FALSE;
831 };
832
833 // removes any currently touching waypoints from the goal stack
834 // (this is how bots detect if they reached a goal)
835 void navigation_poptouchedgoals()
836 {
837         local vector org, m1, m2;
838         org = self.origin;
839         m1 = org + self.mins;
840         m2 = org + self.maxs;
841
842         if(self.goalcurrent.wpflags & WAYPOINTFLAG_TELEPORT)
843         {
844                 if(self.lastteleporttime>0)
845                 if(time-self.lastteleporttime<0.15)
846                 {
847                         navigation_poproute();
848                         return;
849                 }
850         }
851
852         // Loose goal touching check when running
853         if(self.aistatus & AI_STATUS_RUNNING)
854         if(self.goalcurrent.classname=="waypoint")
855         {
856                 if(vlen(self.origin - self.goalcurrent.origin)<150)
857                 {
858                         traceline(self.origin + self.view_ofs , self.goalcurrent.origin, TRUE, world);
859                         if(trace_fraction==1)
860                         {
861                                 // Detect personal waypoints
862                                 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
863                                 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
864                                 {
865                                         self.aistatus &~= AI_STATUS_WAYPOINT_PERSONAL_GOING;
866                                         self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
867                                 }
868
869                                 navigation_poproute();
870                         }
871                 }
872         }
873
874         while (self.goalcurrent && boxesoverlap(m1, m2, self.goalcurrent.absmin, self.goalcurrent.absmax))
875         {
876                 // Detect personal waypoints
877                 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
878                 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
879                 {
880                         self.aistatus &~= AI_STATUS_WAYPOINT_PERSONAL_GOING;
881                         self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
882                 }
883
884                 navigation_poproute();
885         }
886 }
887
888 // begin a goal selection session (queries spawnfunc_waypoint network)
889 void navigation_goalrating_start()
890 {
891         self.navigation_jetpack_goal = world;
892         navigation_bestrating = -1;
893         self.navigation_hasgoals = FALSE;
894         navigation_bestgoal = world;
895         navigation_markroutes(world);
896 };
897
898 // ends a goal selection session (updates goal stack to the best goal)
899 void navigation_goalrating_end()
900 {
901         navigation_routetogoal(navigation_bestgoal, self.origin);
902 //      dprint("best goal ", self.goalcurrent.classname , "\n");
903
904         // Hack: if it can't walk to any goal just move blindly to the first visible waypoint
905         if not (self.navigation_hasgoals)
906         {
907                 dprint(self.netname, " can't walk to any goal, going to a near waypoint\n");
908
909                 entity head;
910
911                 RandomSelection_Init();
912                 head = findradius(self.origin,1000);
913                 while(head)
914                 {
915                         if(head.classname=="waypoint")
916                         if(!(head.wpflags & WAYPOINTFLAG_GENERATED))
917                         if(vlen(self.origin-head.origin)>100)
918                         if(checkpvs(self.view_ofs,head))
919                                 RandomSelection_Add(head, 0, string_null, 1 + (vlen(self.origin-head.origin)<500), 0);
920                         head = head.chain;
921                 }
922                 if(RandomSelection_chosen_ent)
923                         navigation_routetogoal(RandomSelection_chosen_ent, self.origin);
924
925                 self.navigation_hasgoals = FALSE; // Reset this value
926         }
927 };
928
929 void botframe_updatedangerousobjects(float maxupdate)
930 {
931         local entity head, bot_dodgelist;
932         local vector m1, m2, v;
933         local float c, d, danger;
934         c = 0;
935         bot_dodgelist = findchainfloat(bot_dodge, TRUE);
936         botframe_dangerwaypoint = find(botframe_dangerwaypoint, classname, "waypoint");
937         while (botframe_dangerwaypoint != world)
938         {
939                 danger = 0;
940                 m1 = botframe_dangerwaypoint.mins;
941                 m2 = botframe_dangerwaypoint.maxs;
942                 head = bot_dodgelist;
943                 while (head)
944                 {
945                         v = head.origin;
946                         v_x = bound(m1_x, v_x, m2_x);
947                         v_y = bound(m1_y, v_y, m2_y);
948                         v_z = bound(m1_z, v_z, m2_z);
949                         d = head.bot_dodgerating - vlen(head.origin - v);
950                         if (d > 0)
951                         {
952                                 traceline(head.origin, v, TRUE, world);
953                                 if (trace_fraction == 1)
954                                         danger = danger + d;
955                         }
956                         head = head.chain;
957                 }
958                 botframe_dangerwaypoint.dmg = danger;
959                 c = c + 1;
960                 if (c >= maxupdate)
961                         break;
962                 botframe_dangerwaypoint = find(botframe_dangerwaypoint, classname, "waypoint");
963         }
964 };
965
966 #ifdef DEBUG_TRACEWALK
967
968 void debugresetnodes()
969 {
970         debuglastnode = '0 0 0';
971 }
972
973 void debugnode(vector node)
974 {
975         if not(self.classname=="player")
976                 return;
977
978         if(debuglastnode=='0 0 0')
979         {
980                 debuglastnode = node;
981                 return;
982         }
983
984         te_lightning2(world, node, debuglastnode);
985         debuglastnode = node;
986 }
987
988 void debugnodestatus(vector position, float status)
989 {
990         vector color;
991
992         switch (status)
993         {
994                 case DEBUG_NODE_SUCCESS:
995                         color = '0 15 0';
996                         break;
997                 case DEBUG_NODE_WARNING:
998                         color = '15 15 0';
999                         break;
1000                 case DEBUG_NODE_FAIL:
1001                         color = '15 0 0';
1002                         break;
1003                 default:
1004                         color = '15 15 15';
1005         }
1006
1007         te_customflash(position, 40,  2, color);
1008 }
1009
1010 #endif
1011
1012 #ifdef DEBUG_BOT_GOALSTACK
1013
1014 .float goalcounter;
1015 .vector lastposition;
1016
1017 // Debug the goal stack visually
1018 void debuggoalstack()
1019 {
1020         local entity target;
1021         local vector org;
1022
1023         if(self.goalcounter==0)target=self.goalcurrent;
1024         else if(self.goalcounter==1)target=self.goalstack01;
1025         else if(self.goalcounter==2)target=self.goalstack02;
1026         else if(self.goalcounter==3)target=self.goalstack03;
1027         else if(self.goalcounter==4)target=self.goalstack04;
1028         else if(self.goalcounter==5)target=self.goalstack05;
1029         else if(self.goalcounter==6)target=self.goalstack06;
1030         else if(self.goalcounter==7)target=self.goalstack07;
1031         else if(self.goalcounter==8)target=self.goalstack08;
1032         else if(self.goalcounter==9)target=self.goalstack09;
1033         else if(self.goalcounter==10)target=self.goalstack10;
1034         else if(self.goalcounter==11)target=self.goalstack11;
1035         else if(self.goalcounter==12)target=self.goalstack12;
1036         else if(self.goalcounter==13)target=self.goalstack13;
1037         else if(self.goalcounter==14)target=self.goalstack14;
1038         else if(self.goalcounter==15)target=self.goalstack15;
1039         else if(self.goalcounter==16)target=self.goalstack16;
1040         else if(self.goalcounter==17)target=self.goalstack17;
1041         else if(self.goalcounter==18)target=self.goalstack18;
1042         else if(self.goalcounter==19)target=self.goalstack19;
1043         else if(self.goalcounter==20)target=self.goalstack20;
1044         else if(self.goalcounter==21)target=self.goalstack21;
1045         else if(self.goalcounter==22)target=self.goalstack22;
1046         else if(self.goalcounter==23)target=self.goalstack23;
1047         else if(self.goalcounter==24)target=self.goalstack24;
1048         else if(self.goalcounter==25)target=self.goalstack25;
1049         else if(self.goalcounter==26)target=self.goalstack26;
1050         else if(self.goalcounter==27)target=self.goalstack27;
1051         else if(self.goalcounter==28)target=self.goalstack28;
1052         else if(self.goalcounter==29)target=self.goalstack29;
1053         else if(self.goalcounter==30)target=self.goalstack30;
1054         else if(self.goalcounter==31)target=self.goalstack31;
1055
1056         if(target==world)
1057         {
1058                 self.goalcounter = 0;
1059                 self.lastposition='0 0 0';
1060                 return;
1061         }
1062
1063         if(self.lastposition=='0 0 0')
1064                 org = self.origin;
1065         else
1066                 org = self.lastposition;
1067
1068
1069         te_lightning2(world, org, target.origin);
1070         self.lastposition = target.origin;
1071
1072         self.goalcounter++;
1073 }
1074
1075 #endif