qcsrc/server/bot/default/navigation.qc

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