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