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