data/qcsrc/server/bots.qc

   1 .float aistatus;
   2 float AI_STATUS_ROAMING                         = 1;    // Bot is just crawling the map. No enemies at sight
   3 float AI_STATUS_ATTACKING                       = 2;    // There are enemies at sight
   4 float AI_STATUS_RUNNING                         = 4;    // Bot is bunny hopping
   5 float AI_STATUS_DANGER_AHEAD                    = 8;    // There is lava/slime/trigger_hurt ahead
   6 float AI_STATUS_OUT_JUMPPAD                     = 16;   // Trying to get out of a "vertical" jump pad
   7 float AI_STATUS_OUT_WATER                       = 32;   // Trying to get out of water
   8 float AI_STATUS_WAYPOINT_PERSONAL_LINKING       = 64;   // Waiting for the personal waypoint to be linked
   9 float AI_STATUS_WAYPOINT_PERSONAL_GOING         = 128;  // Going to a personal waypoint
  10 float AI_STATUS_WAYPOINT_PERSONAL_REACHED       = 256;  // Personal waypoint reached
  11 float AI_STATUS_JETPACK_FLYING                  = 512;
  12 float AI_STATUS_JETPACK_LANDING                 = 1024;
  13
  14 // utilities for path debugging
  15 #ifdef DEBUG_TRACEWALK
  16
  17 float DEBUG_NODE_SUCCESS        = 1;
  18 float DEBUG_NODE_WARNING        = 2;
  19 float DEBUG_NODE_FAIL           = 3;
  20
  21 vector debuglastnode;
  22
  23 void debugresetnodes()
  24 {
  25         debuglastnode = '0 0 0';
  26 }
  27
  28 void debugnode(vector node)
  29 {
  30         if not(self.classname=="player")
  31                 return;
  32
  33         if(debuglastnode=='0 0 0')
  34         {
  35                 debuglastnode = node;
  36                 return;
  37         }
  38
  39         te_lightning2(world, node, debuglastnode);
  40         debuglastnode = node;
  41 }
  42
  43 void debugnodestatus(vector position, float status)
  44 {
  45         vector color;
  46
  47         switch (status)
  48         {
  49                 case DEBUG_NODE_SUCCESS:
  50                         color = '0 15 0';
  51                         break;
  52                 case DEBUG_NODE_WARNING:
  53                         color = '15 15 0';
  54                         break;
  55                 case DEBUG_NODE_FAIL:
  56                         color = '15 0 0';
  57                         break;
  58                 default:
  59                         color = '15 15 15';
  60         }
  61
  62         te_customflash(position, 40,  2, color);
  63 }
  64
  65 #endif
  66
  67 // rough simulation of walking from one point to another to test if a path
  68 // can be traveled, used for waypoint linking and havocbot
  69
  70 vector stepheightvec;
  71 float bot_navigation_movemode;
  72 float navigation_testtracewalk;
  73 float tracewalk(entity e, vector start, vector m1, vector m2, vector end, float movemode)
  74 {
  75         local vector org;
  76         local vector move;
  77         local vector dir;
  78         local float dist;
  79         local float totaldist;
  80         local float stepdist;
  81         local float yaw;
  82         local float ignorehazards;
  83         local float swimming;
  84
  85         #ifdef DEBUG_TRACEWALK
  86                 debugresetnodes();
  87                 debugnode(start);
  88         #endif
  89
  90         move = end - start;
  91         move_z = 0;
  92         org = start;
  93         dist = totaldist = vlen(move);
  94         dir = normalize(move);
  95         stepdist = 32;
  96         ignorehazards = FALSE;
  97
  98         // Analyze starting point
  99         traceline(start, start, MOVE_NORMAL, e);
 100         if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
 101                 ignorehazards = TRUE;
 102         else
 103         {
 104                 traceline( start, start + '0 0 -65536', MOVE_NORMAL, e);
 105                 if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
 106                 {
 107                         ignorehazards = TRUE;
 108                         swimming = TRUE;
 109                 }
 110         }
 111         tracebox(start, m1, m2, start, MOVE_NOMONSTERS, e);
 112         if (trace_startsolid)
 113         {
 114                 // Bad start
 115                 #ifdef DEBUG_TRACEWALK
 116                         debugnodestatus(start, DEBUG_NODE_FAIL);
 117                 #endif
 118                 //print("tracewalk: ", vtos(start), " is a bad start\n");
 119                 return FALSE;
 120         }
 121
 122         // Movement loop
 123         yaw = vectoyaw(move);
 124         move = end - org;
 125         for (;;)
 126         {
 127                 if (boxesoverlap(end, end, org + m1 + '-1 -1 -1', org + m2 + '1 1 1'))
 128                 {
 129                         // Succeeded
 130                         #ifdef DEBUG_TRACEWALK
 131                                 debugnodestatus(org, DEBUG_NODE_SUCCESS);
 132                         #endif
 133                         //print("tracewalk: ", vtos(start), " can reach ", vtos(end), "\n");
 134                         return TRUE;
 135                 }
 136                 #ifdef DEBUG_TRACEWALK
 137                         debugnode(org);
 138                 #endif
 139
 140                 if (dist <= 0)
 141                         break;
 142                 if (stepdist > dist)
 143                         stepdist = dist;
 144                 dist = dist - stepdist;
 145                 traceline(org, org, MOVE_NORMAL, e);
 146                 if (!ignorehazards)
 147                 {
 148                         if (trace_dpstartcontents & (DPCONTENTS_SLIME | DPCONTENTS_LAVA))
 149                         {
 150                                 // hazards blocking path
 151                                 #ifdef DEBUG_TRACEWALK
 152                                         debugnodestatus(org, DEBUG_NODE_FAIL);
 153                                 #endif
 154                                 //print("tracewalk: ", vtos(start), " hits a hazard when trying to reach ", vtos(end), "\n");
 155                                 return FALSE;
 156                         }
 157                 }
 158                 if (trace_dpstartcontents & DPCONTENTS_LIQUIDSMASK)
 159                 {
 160                         move = normalize(end - org);
 161                         tracebox(org, m1, m2, org + move * stepdist, movemode, e);
 162
 163                         #ifdef DEBUG_TRACEWALK
 164                                 debugnode(trace_endpos);
 165                         #endif
 166
 167                         if (trace_fraction < 1)
 168                         {
 169                                 swimming = TRUE;
 170                                 org = trace_endpos - normalize(org - trace_endpos) * stepdist;
 171                                 for(; org_z < end_z + self.maxs_z; org_z += stepdist)
 172                                 {
 173                                                 #ifdef DEBUG_TRACEWALK
 174                                                         debugnode(org);
 175                                                 #endif
 176                                         if(pointcontents(org) == CONTENT_EMPTY)
 177                                                         break;
 178                                 }
 179
 180                                 if not (pointcontents(org + '0 0 1') == CONTENT_EMPTY)
 181                                 {
 182                                         #ifdef DEBUG_TRACEWALK
 183                                                 debugnodestatus(org, DEBUG_NODE_FAIL);
 184                                         #endif
 185                                         return FALSE;
 186                                         //print("tracewalk: ", vtos(start), " failed under water\n");
 187                                 }
 188                                 continue;
 189
 190                         }
 191                         else
 192                                 org = trace_endpos;
 193                 }
 194                 else
 195                 {
 196                         move = dir * stepdist + org;
 197                         tracebox(org, m1, m2, move, movemode, e);
 198
 199                         #ifdef DEBUG_TRACEWALK
 200                                 debugnode(trace_endpos);
 201                         #endif
 202
 203                         // hit something
 204                         if (trace_fraction < 1)
 205                         {
 206                                 // check if we can walk over this obstacle
 207                                 tracebox(org + stepheightvec, m1, m2, move + stepheightvec, movemode, e);
 208                                 if (trace_fraction < 1 || trace_startsolid)
 209                                 {
 210                                         #ifdef DEBUG_TRACEWALK
 211                                                 debugnodestatus(trace_endpos, DEBUG_NODE_WARNING);
 212                                         #endif
 213
 214                                         // check for doors
 215                                         traceline( org, move, movemode, e);
 216                                         if ( trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
 217                                         {
 218                                                 local vector nextmove;
 219                                                 move = trace_endpos;
 220                                                 while(trace_ent.classname == "door_rotating" || trace_ent.classname == "door")
 221                                                 {
 222                                                         nextmove = move + (dir * stepdist);
 223                                                         traceline( move, nextmove, movemode, e);
 224                                                         move = nextmove;
 225                                                 }
 226                                         }
 227                                         else
 228                                         {
 229                                                 #ifdef DEBUG_TRACEWALK
 230                                                         debugnodestatus(trace_endpos, DEBUG_NODE_FAIL);
 231                                                 #endif
 232                                                 //print("tracewalk: ", vtos(start), " hit something when trying to reach ", vtos(end), "\n");
 233                                                 //te_explosion(trace_endpos);
 234                                                 //print(ftos(e.dphitcontentsmask), "\n");
 235                                                 return FALSE; // failed
 236                                         }
 237                                 }
 238                                 else
 239                                         move = trace_endpos;
 240                         }
 241                         else
 242                                 move = trace_endpos;
 243
 244                         // trace down from stepheight as far as possible and move there,
 245                         // if this starts in solid we try again without the stepup, and
 246                         // if that also fails we assume it is a wall
 247                         // (this is the same logic as the Quake walkmove function used)
 248                         tracebox(move, m1, m2, move + '0 0 -65536', movemode, e);
 249
 250                         // moved successfully
 251                         if(swimming)
 252                         {
 253                                 local float c;
 254                                 c = pointcontents(org + '0 0 1');
 255                                 if not(c == CONTENT_WATER || c == CONTENT_LAVA || c == CONTENT_SLIME)
 256                                         swimming = FALSE;
 257                                 else
 258                                         continue;
 259                         }
 260
 261                         org = trace_endpos;
 262                 }
 263         }
 264
 265         //print("tracewalk: ", vtos(start), " did not arrive at ", vtos(end), " but at ", vtos(org), "\n");
 266
 267         // moved but didn't arrive at the intended destination
 268         #ifdef DEBUG_TRACEWALK
 269                 debugnodestatus(org, DEBUG_NODE_FAIL);
 270         #endif
 271
 272         return FALSE;
 273 };
 274
 275
 276 // grenade tracing to decide the best pitch to fire at
 277
 278 entity tracetossent;
 279 entity tracetossfaketarget;
 280
 281 // traces multiple trajectories to find one that will impact the target
 282 // 'end' vector is the place it aims for,
 283 // returns TRUE only if it hit targ (don't target non-solid entities)
 284 vector findtrajectory_velocity;
 285 float findtrajectorywithleading(vector org, vector m1, vector m2, entity targ, float shotspeed, float shotspeedupward, float maxtime, float shotdelay, entity ignore)
 286 {
 287         local float c, savesolid, shottime;
 288         local vector dir, end, v;
 289         if (shotspeed < 1)
 290                 return FALSE; // could cause division by zero if calculated
 291         if (targ.solid < SOLID_BBOX) // SOLID_NOT and SOLID_TRIGGER
 292                 return FALSE; // could never hit it
 293         if (!tracetossent)
 294                 tracetossent = spawn();
 295         tracetossent.owner = ignore;
 296         setsize(tracetossent, m1, m2);
 297         savesolid = targ.solid;
 298         targ.solid = SOLID_NOT;
 299         shottime = ((vlen(targ.origin - org) / shotspeed) + shotdelay);
 300         v = targ.velocity * shottime + targ.origin;
 301         tracebox(targ.origin, targ.mins, targ.maxs, v, FALSE, targ);
 302         v = trace_endpos;
 303         end = v + (targ.mins + targ.maxs) * 0.5;
 304         if ((vlen(end - org) / shotspeed + 0.2) > maxtime)
 305         {
 306                 // out of range
 307                 targ.solid = savesolid;
 308                 return FALSE;
 309         }
 310
 311         if (!tracetossfaketarget)
 312                 tracetossfaketarget = spawn();
 313         tracetossfaketarget.solid = savesolid;
 314         tracetossfaketarget.movetype = targ.movetype;
 315         setmodel(tracetossfaketarget, targ.model); // no low precision
 316         tracetossfaketarget.model = targ.model;
 317         tracetossfaketarget.modelindex = targ.modelindex;
 318         setsize(tracetossfaketarget, targ.mins, targ.maxs);
 319         setorigin(tracetossfaketarget, v);
 320
 321         c = 0;
 322         dir = normalize(end - org);
 323         while (c < 10) // 10 traces
 324         {
 325                 setorigin(tracetossent, org); // reset
 326                 tracetossent.velocity = findtrajectory_velocity = normalize(dir) * shotspeed + shotspeedupward * '0 0 1';
 327                 tracetoss(tracetossent, ignore); // love builtin functions...
 328                 if (trace_ent == tracetossfaketarget) // done
 329                 {
 330                         targ.solid = savesolid;
 331
 332                         // make it disappear
 333                         tracetossfaketarget.solid = SOLID_NOT;
 334                         tracetossfaketarget.movetype = MOVETYPE_NONE;
 335                         tracetossfaketarget.model = "";
 336                         tracetossfaketarget.modelindex = 0;
 337                         // relink to remove it from physics considerations
 338                         setorigin(tracetossfaketarget, v);
 339
 340                         return TRUE;
 341                 }
 342                 dir_z = dir_z + 0.1; // aim up a little more
 343                 c = c + 1;
 344         }
 345         targ.solid = savesolid;
 346
 347         // make it disappear
 348         tracetossfaketarget.solid = SOLID_NOT;
 349         tracetossfaketarget.movetype = MOVETYPE_NONE;
 350         tracetossfaketarget.model = "";
 351         tracetossfaketarget.modelindex = 0;
 352         // relink to remove it from physics considerations
 353         setorigin(tracetossfaketarget, v);
 354
 355         // leave a valid one even if it won't reach
 356         findtrajectory_velocity = normalize(end - org) * shotspeed + shotspeedupward * '0 0 1';
 357         return FALSE;
 358 };
 359
 360
 361
 362 // Lag simulation
 363 #define LAG_QUEUE_LENGTH 4
 364
 365 .void(float t, float f1, float f2, entity e1, vector v1, vector v2, vector v3, vector v4) lag_func;
 366
 367 .float lag_time[LAG_QUEUE_LENGTH];
 368 .float lag_float1[LAG_QUEUE_LENGTH];
 369 .float lag_float2[LAG_QUEUE_LENGTH];
 370 .vector lag_vec1[LAG_QUEUE_LENGTH];
 371 .vector lag_vec2[LAG_QUEUE_LENGTH];
 372 .vector lag_vec3[LAG_QUEUE_LENGTH];
 373 .vector lag_vec4[LAG_QUEUE_LENGTH];
 374 .entity lag_entity1[LAG_QUEUE_LENGTH];
 375
 376 void lag_update()
 377 {
 378         float i;
 379         for(i=0;i<LAG_QUEUE_LENGTH;++i)
 380         {
 381                 if (self.lag_time[i])
 382                 if (time > self.lag_time[i])
 383                 {
 384                         self.lag_func(
 385                                 self.lag_time[i], self.lag_float1[i], self.lag_float2[i],
 386                                 self.lag_entity1[i], self.lag_vec1[i], self.lag_vec2[i], self.lag_vec3[i],
 387                                 self.lag_vec4[i]
 388                         );
 389                         // Clear this position on the queue
 390                         self.(lag_time[i]) = 0;
 391                 }
 392         }
 393 };
 394
 395 float lag_additem(float t, float f1, float f2, entity e1, vector v1, vector v2, vector v3, vector v4)
 396 {
 397         float i;
 398         for(i=0;i<LAG_QUEUE_LENGTH;++i)
 399         {
 400                 // Find a free position on the queue
 401                 if (self.lag_time[i] == 0)
 402                 {
 403                         self.(lag_time[i]) = t;
 404                         self.(lag_vec1[i]) = v1;
 405                         self.(lag_vec2[i]) = v2;
 406                         self.(lag_vec3[i]) = v3;
 407                         self.(lag_vec4[i]) = v4;
 408                         self.(lag_float1[i]) = f1;
 409                         self.(lag_float2[i]) = f2;
 410                         self.(lag_entity1[i]) = e1;
 411                         return TRUE;
 412                 }
 413         }
 414         return FALSE;
 415 };
 416
 417
 418 // Random skill system
 419 .float bot_thinkskill;
 420 .float bot_mouseskill;
 421 .float bot_predictionskill;
 422 .float bot_offsetskill;
 423
 424
 425 // spawnfunc_waypoint navigation system
 426
 427 // itemscore = (howmuchmoreIwant / howmuchIcanwant) / itemdistance
 428 // waypointscore = 0.7 / waypointdistance
 429
 430 #define MAX_WAYPOINTS_LINKS 32
 431 .vector wpnearestpoint;
 432 .entity wlink[MAX_WAYPOINTS_LINKS];
 433 .float wpmincost[MAX_WAYPOINTS_LINKS];
 434 .float wpfire, wpcost, wpconsidered, wpisbox, wpflags, wplinked;
 435
 436 // stack of current goals (the last one of which may be an item or other
 437 // desirable object, the rest are typically waypoints to reach it)
 438 #define GOALSTACK_LENGTH 32
 439 .entity goalstack[GOALSTACK_LENGTH];
 440 .entity goalcurrent;
 441
 442
 443 .entity nearestwaypoint;
 444 .float nearestwaypointtimeout;
 445
 446 // used during navigation_goalrating_begin/end sessions
 447 #define MAX_BESTGOALS 3
 448 float bestgoalswindex;
 449 float bestgoalsrindex;
 450 float navigation_bestrating;
 451 entity navigation_bestgoals[MAX_BESTGOALS];
 452 .float navigation_hasgoals;
 453
 454 /////////////////////////////////////////////////////////////////////////////
 455 // spawnfunc_waypoint management
 456 /////////////////////////////////////////////////////////////////////////////
 457
 458 // waypoints with this flag are not saved, they are automatically generated
 459 // waypoints like jump pads, teleporters, and items
 460 float WAYPOINTFLAG_GENERATED = 8388608;
 461 float WAYPOINTFLAG_ITEM = 4194304;
 462 float WAYPOINTFLAG_TELEPORT = 2097152;
 463 float WAYPOINTFLAG_NORELINK = 1048576;
 464 float WAYPOINTFLAG_PERSONAL = 524288;
 465
 466 // add a new link to the spawnfunc_waypoint, replacing the furthest link it already has
 467 void waypoint_addlink(entity from, entity to)
 468 {
 469         local float c, i;
 470
 471         if (from == to)
 472                 return;
 473
 474         if (from.wpflags & WAYPOINTFLAG_NORELINK)
 475                 return;
 476
 477         // return if already linked
 478         for(i=0;i<MAX_WAYPOINTS_LINKS;++i)
 479         {
 480                 if(from.wlink[i]==to)
 481                         return;
 482         }
 483
 484         // if either is a box we have to find the nearest points on them to
 485         // calculate the distance properly
 486         if (to.wpisbox || from.wpisbox)
 487         {
 488                 local vector v1, v2, m1, m2;
 489                 v1 = from.origin;
 490                 m1 = to.absmin;
 491                 m2 = to.absmax;
 492                 v1_x = bound(m1_x, v1_x, m2_x);
 493                 v1_y = bound(m1_y, v1_y, m2_y);
 494                 v1_z = bound(m1_z, v1_z, m2_z);
 495                 v2 = to.origin;
 496                 m1 = from.absmin;
 497                 m2 = from.absmax;
 498                 v2_x = bound(m1_x, v2_x, m2_x);
 499                 v2_y = bound(m1_y, v2_y, m2_y);
 500                 v2_z = bound(m1_z, v2_z, m2_z);
 501                 v2 = to.origin;
 502                 c = vlen(v2 - v1);
 503         }
 504         else
 505                 c = vlen(to.origin - from.origin);
 506
 507         if (from.wpmincost[MAX_WAYPOINTS_LINKS - 1] < c)
 508                 return;
 509
 510         for(i=MAX_WAYPOINTS_LINKS - 2;i>0;--i)
 511         {
 512                 if (from.wpmincost[i] < c)
 513                 {
 514                         from.(wlink[i]) = to;
 515                         from.(wpmincost[i]) = c;
 516                         return;
 517                 }
 518                 from.(wlink[i]) = from.wlink[i-1];
 519                 from.(wpmincost[i]) = from.wpmincost[i-1];
 520         }
 521         from.(wlink[0]) = to;
 522         from.(wpmincost[0]) = c;
 523         return;
 524 };
 525
 526 // fields you can query using prvm_global server to get some statistics about waypoint linking culling
 527 float relink_total, relink_walkculled, relink_pvsculled, relink_lengthculled;
 528
 529 // relink this spawnfunc_waypoint
 530 // (precompile a list of all reachable waypoints from this spawnfunc_waypoint)
 531 // (SLOW!)
 532 void waypoint_think()
 533 {
 534         local entity e;
 535         local vector sv, sm1, sm2, ev, em1, em2, dv;
 536
 537         stepheightvec = cvar("sv_stepheight") * '0 0 1';
 538         bot_navigation_movemode = ((cvar("bot_navigation_ignoreplayers")) ? MOVE_NOMONSTERS : MOVE_NORMAL);
 539
 540         //dprint("waypoint_think wpisbox = ", ftos(self.wpisbox), "\n");
 541         sm1 = self.origin + self.mins;
 542         sm2 = self.origin + self.maxs;
 543         for(e = world; (e = find(e, classname, "waypoint")); )
 544         {
 545                 if (boxesoverlap(self.absmin, self.absmax, e.absmin, e.absmax))
 546                 {
 547                         waypoint_addlink(self, e);
 548                         waypoint_addlink(e, self);
 549                 }
 550                 else
 551                 {
 552                         ++relink_total;
 553                         if(!checkpvs(self.origin, e))
 554                         {
 555                                 ++relink_pvsculled;
 556                                 continue;
 557                         }
 558                         sv = e.origin;
 559                         sv_x = bound(sm1_x, sv_x, sm2_x);
 560                         sv_y = bound(sm1_y, sv_y, sm2_y);
 561                         sv_z = bound(sm1_z, sv_z, sm2_z);
 562                         ev = self.origin;
 563                         em1 = e.origin + e.mins;
 564                         em2 = e.origin + e.maxs;
 565                         ev_x = bound(em1_x, ev_x, em2_x);
 566                         ev_y = bound(em1_y, ev_y, em2_y);
 567                         ev_z = bound(em1_z, ev_z, em2_z);
 568                         dv = ev - sv;
 569                         dv_z = 0;
 570                         if (vlen(dv) >= 1050) // max search distance in XY
 571                         {
 572                                 ++relink_lengthculled;
 573                                 continue;
 574                         }
 575                         navigation_testtracewalk = 0;
 576                         if (!self.wpisbox)
 577                         {
 578                                 tracebox(sv - PL_MIN_z * '0 0 1', PL_MIN, PL_MAX, sv, FALSE, self);
 579                                 if (!trace_startsolid)
 580                                 {
 581                                         //dprint("sv deviation", vtos(trace_endpos - sv), "\n");
 582                                         sv = trace_endpos + '0 0 1';
 583                                 }
 584                         }
 585                         if (!e.wpisbox)
 586                         {
 587                                 tracebox(ev - PL_MIN_z * '0 0 1', PL_MIN, PL_MAX, ev, FALSE, e);
 588                                 if (!trace_startsolid)
 589                                 {
 590                                         //dprint("ev deviation", vtos(trace_endpos - ev), "\n");
 591                                         ev = trace_endpos + '0 0 1';
 592                                 }
 593                         }
 594                         //traceline(self.origin, e.origin, FALSE, world);
 595                         //if (trace_fraction == 1)
 596                         if (!self.wpisbox && tracewalk(self, sv, PL_MIN, PL_MAX, ev, MOVE_NOMONSTERS))
 597                                 waypoint_addlink(self, e);
 598                         else
 599                                 relink_walkculled += 0.5;
 600                         if (!e.wpisbox && tracewalk(e, ev, PL_MIN, PL_MAX, sv, MOVE_NOMONSTERS))
 601                                 waypoint_addlink(e, self);
 602                         else
 603                                 relink_walkculled += 0.5;
 604                 }
 605         }
 606         navigation_testtracewalk = 0;
 607         self.wplinked = TRUE;
 608 };
 609
 610 void waypoint_clearlinks(entity w)
 611 {
 612         // clear links to other waypoints
 613         float f, i;
 614         f = 10000000;
 615
 616         for(i=0;i<MAX_WAYPOINTS_LINKS;++i)
 617         {
 618                 w.(wlink[i]) = world;
 619                 w.(wpmincost[i]) = f;
 620         }
 621         w.wplinked = FALSE;
 622 };
 623
 624 // tell a spawnfunc_waypoint to relink
 625 void waypoint_schedulerelink(entity w)
 626 {
 627         if (w == world)
 628                 return;
 629
 630         // TODO: add some sort of visible box in edit mode for box waypoints
 631         if (cvar("g_waypointeditor"))
 632         {
 633                 local vector m1, m2;
 634                 m1 = w.mins;
 635                 m2 = w.maxs;
 636                 setmodel(w, "models/runematch/rune.mdl");
 637                 w.effects = EF_LOWPRECISION;
 638                 setsize(w, m1, m2);
 639                 if (w.wpflags & WAYPOINTFLAG_ITEM)
 640                         w.colormod = '1 0 0';
 641                 else if (w.wpflags & WAYPOINTFLAG_GENERATED)
 642                         w.colormod = '1 1 0';
 643                 else
 644                         w.colormod = '1 1 1';
 645         }
 646         else
 647                 w.model = "";
 648         w.wpisbox = vlen(w.size) > 0;
 649         w.enemy = world;
 650         if (!(w.wpflags & WAYPOINTFLAG_PERSONAL))
 651                 w.owner = world;
 652         if (!(w.wpflags & WAYPOINTFLAG_NORELINK))
 653                 waypoint_clearlinks(w);
 654         // schedule an actual relink on next frame
 655         w.think = waypoint_think;
 656         w.nextthink = time;
 657         w.effects = EF_LOWPRECISION;
 658 }
 659
 660 // create a new spawnfunc_waypoint and automatically link it to other waypoints, and link
 661 // them back to it as well
 662 // (suitable for spawnfunc_waypoint editor)
 663 entity waypoint_spawn(vector m1, vector m2, float f)
 664 {
 665         local entity w;
 666         local vector org;
 667         w = find(world, classname, "waypoint");
 668
 669         if not(f & WAYPOINTFLAG_PERSONAL)
 670         while (w)
 671         {
 672                 // if a matching spawnfunc_waypoint already exists, don't add a duplicate
 673                 if (boxesoverlap(m1, m2, w.absmin, w.absmax))
 674                         return w;
 675                 w = find(w, classname, "waypoint");
 676         }
 677
 678         w = spawn();
 679         w.dphitcontentsmask = DPCONTENTS_SOLID | DPCONTENTS_BODY | DPCONTENTS_PLAYERCLIP;
 680         w.classname = "waypoint";
 681         w.wpflags = f;
 682         setorigin(w, (m1 + m2) * 0.5);
 683         setsize(w, m1 - w.origin, m2 - w.origin);
 684         if (vlen(w.size) > 0)
 685                 w.wpisbox = TRUE;
 686
 687         if(!(f & WAYPOINTFLAG_GENERATED))
 688         if(!w.wpisbox)
 689         {
 690                 traceline(w.origin + '0 0 1', w.origin + PL_MIN_z * '0 0 1' - '0 0 1', MOVE_NOMONSTERS, w);
 691                 if (trace_fraction < 1)
 692                         setorigin(w, trace_endpos - PL_MIN_z * '0 0 1');
 693
 694                 // check if the start position is stuck
 695                 tracebox(w.origin, PL_MIN + '-1 -1 -1', PL_MAX + '1 1 1', w.origin, MOVE_NOMONSTERS, w);
 696                 if (trace_startsolid)
 697                 {
 698                         org = w.origin + '0 0 26';
 699                         tracebox(org, PL_MIN, PL_MAX, w.origin, MOVE_WORLDONLY, w);
 700                         if(trace_startsolid)
 701                         {
 702                                 org = w.origin + '2 2 2';
 703                                 tracebox(org, PL_MIN, PL_MAX, w.origin, MOVE_WORLDONLY, w);
 704                                 if(trace_startsolid)
 705                                 {
 706                                         org = w.origin + '-2 -2 2';
 707                                         tracebox(org, PL_MIN, PL_MAX, w.origin, MOVE_WORLDONLY, w);
 708                                         if(trace_startsolid)
 709                                         {
 710                                                 org = w.origin + '-2 2 2';
 711                                                 tracebox(org, PL_MIN, PL_MAX, w.origin, MOVE_WORLDONLY, w);
 712                                                 if(trace_startsolid)
 713                                                 {
 714                                                         org = w.origin + '2 -2 2';
 715                                                         tracebox(org, PL_MIN, PL_MAX, w.origin, MOVE_WORLDONLY, w);
 716                                                         if(trace_startsolid)
 717                                                         {
 718                                                                 // this WP is in solid, refuse it
 719                                                                 dprint("Killed a waypoint that was stuck in solid at ", vtos(org), "\n");
 720                                                                 remove(w);
 721                                                                 return world;
 722                                                         }
 723                                                 }
 724                                         }
 725                                 }
 726                         }
 727                         setorigin(w, org * 0.05 + trace_endpos * 0.95); // don't trust the trace fully
 728                 }
 729
 730                 tracebox(w.origin, PL_MIN, PL_MAX, w.origin - '0 0 128', MOVE_WORLDONLY, w);
 731                 if(trace_startsolid)
 732                 {
 733                         dprint("Killed a waypoint that was stuck in solid ", vtos(w.origin), "\n");
 734                         remove(w);
 735                         return world;
 736                 }
 737                 if (!trace_inwater)
 738                 {
 739                         if(trace_fraction == 1)
 740                         {
 741                                 dprint("Killed a waypoint that was stuck in air at ", vtos(w.origin), "\n");
 742                                 remove(w);
 743                                 return world;
 744                         }
 745                         trace_endpos_z += 0.1; // don't trust the trace fully
 746 //                      dprint("Moved waypoint at ", vtos(w.origin), " by ", ftos(vlen(w.origin - trace_endpos)));
 747 //                      dprint(" direction: ", vtos((trace_endpos - w.origin)), "\n");
 748                         setorigin(w, trace_endpos);
 749                 }
 750         }
 751
 752         waypoint_clearlinks(w);
 753         //waypoint_schedulerelink(w);
 754
 755         if (cvar("g_waypointeditor"))
 756         {
 757                 m1 = w.mins;
 758                 m2 = w.maxs;
 759                 setmodel(w, "models/runematch/rune.mdl"); w.effects = EF_LOWPRECISION;
 760                 setsize(w, m1, m2);
 761                 if (w.wpflags & WAYPOINTFLAG_ITEM)
 762                         w.colormod = '1 0 0';
 763                 else if (w.wpflags & WAYPOINTFLAG_GENERATED)
 764                         w.colormod = '1 1 0';
 765                 else
 766                         w.colormod = '1 1 1';
 767         }
 768         else
 769                 w.model = "";
 770
 771         return w;
 772 };
 773
 774 // spawnfunc_waypoint map entity
 775 void spawnfunc_waypoint()
 776 {
 777         setorigin(self, self.origin);
 778         // schedule a relink after other waypoints have had a chance to spawn
 779         waypoint_clearlinks(self);
 780         //waypoint_schedulerelink(self);
 781 };
 782
 783 // remove a spawnfunc_waypoint, and schedule all neighbors to relink
 784 void waypoint_remove(entity e)
 785 {
 786         float i;
 787
 788         // tell all linked waypoints that they need to relink
 789         for(i=0;i<MAX_WAYPOINTS_LINKS;++i)
 790         {
 791                 if(e.wlink[i])
 792                         waypoint_schedulerelink(e.wlink[i]);
 793         }
 794
 795         // and now remove the spawnfunc_waypoint
 796         remove(e);
 797 };
 798
 799 // empties the map of waypoints
 800 void waypoint_removeall()
 801 {
 802         local entity head, next;
 803         head = findchain(classname, "waypoint");
 804         while (head)
 805         {
 806                 next = head.chain;
 807                 remove(head);
 808                 head = next;
 809         }
 810 };
 811
 812 // tell all waypoints to relink
 813 // (is this useful at all?)
 814 void waypoint_schedulerelinkall()
 815 {
 816         local entity head;
 817         relink_total = relink_walkculled = relink_pvsculled = relink_lengthculled = 0;
 818         head = findchain(classname, "waypoint");
 819         while (head)
 820         {
 821                 waypoint_schedulerelink(head);
 822                 head = head.chain;
 823         }
 824 };
 825
 826 // Load waypoint links from file
 827 float botframe_cachedwaypointlinks;
 828 float waypoint_load_links()
 829 {
 830         local string filename, s;
 831         local float file, tokens, c, found;
 832         local entity wp_from, wp_to;
 833         local vector wp_to_pos, wp_from_pos;
 834         filename = strcat("maps/", mapname);
 835         filename = strcat(filename, ".waypoints.cache");
 836         file = fopen(filename, FILE_READ);
 837
 838         if (file < 0)
 839         {
 840                 dprint("waypoint links load from ");
 841                 dprint(filename);
 842                 dprint(" failed\n");
 843                 return FALSE;
 844         }
 845
 846         while (1)
 847         {
 848                 s = fgets(file);
 849                 if (!s)
 850                         break;
 851
 852                 tokens = tokenizebyseparator(s, "*");
 853
 854                 if (tokens!=2)
 855                 {
 856                         // bad file format
 857                         fclose(file);
 858                         return FALSE;
 859                 }
 860
 861                 wp_from_pos     = stov(argv(0));
 862                 wp_to_pos       = stov(argv(1));
 863
 864                 // Search "from" waypoint
 865                 if(wp_from.origin!=wp_from_pos)
 866                 {
 867                         wp_from = findradius(wp_from_pos, 1);
 868                         found = FALSE;
 869                         while(wp_from)
 870                         {
 871                                 if(vlen(wp_from.origin-wp_from_pos)<1)
 872                                 if(wp_from.classname == "waypoint")
 873                                 {
 874                                         found = TRUE;
 875                                         break;
 876                                 }
 877                                 wp_from = wp_from.chain;
 878                         }
 879
 880                         if(!found)
 881                         {
 882                                 // can't find that waypoint
 883                                 fclose(file);
 884                                 return FALSE;
 885                         }
 886                 }
 887
 888                 // Search "to" waypoint
 889                 wp_to = findradius(wp_to_pos, 1);
 890                 found = FALSE;
 891                 while(wp_to)
 892                 {
 893                         if(vlen(wp_to.origin-wp_to_pos)<1)
 894                         if(wp_to.classname == "waypoint")
 895                         {
 896                                 found = TRUE;
 897                                 break;
 898                         }
 899                         wp_to = wp_to.chain;
 900                 }
 901
 902                 if(!found)
 903                 {
 904                         // can't find that waypoint
 905                         fclose(file);
 906                         return FALSE;
 907                 }
 908
 909                 ++c;
 910                 waypoint_addlink(wp_from, wp_to);
 911         }
 912
 913         fclose(file);
 914
 915         dprint("loaded ");
 916         dprint(ftos(c));
 917         dprint(" waypoint links from maps/");
 918         dprint(mapname);
 919         dprint(".waypoints.cache\n");
 920
 921         botframe_cachedwaypointlinks = TRUE;
 922         return TRUE;
 923 };
 924
 925 float botframe_loadedforcedlinks;
 926 void waypoint_load_links_hardwired()
 927 {
 928         local string filename, s;
 929         local float file, tokens, c, found;
 930         local entity wp_from, wp_to;
 931         local vector wp_to_pos, wp_from_pos;
 932         filename = strcat("maps/", mapname);
 933         filename = strcat(filename, ".waypoints.hardwired");
 934         file = fopen(filename, FILE_READ);
 935
 936         botframe_loadedforcedlinks = TRUE;
 937
 938         if (file < 0)
 939         {
 940                 dprint("waypoint links load from ");
 941                 dprint(filename);
 942                 dprint(" failed\n");
 943                 return;
 944         }
 945
 946         for (;;)
 947         {
 948                 s = fgets(file);
 949                 if (!s)
 950                         break;
 951
 952                 if(substring(s, 0, 2)=="//")
 953                         continue;
 954
 955                 if(substring(s, 0, 1)=="#")
 956                         continue;
 957
 958                 tokens = tokenizebyseparator(s, "*");
 959
 960                 if (tokens!=2)
 961                         continue;
 962
 963                 wp_from_pos     = stov(argv(0));
 964                 wp_to_pos       = stov(argv(1));
 965
 966                 // Search "from" waypoint
 967                 if(wp_from.origin!=wp_from_pos)
 968                 {
 969                         wp_from = findradius(wp_from_pos, 1);
 970                         found = FALSE;
 971                         while(wp_from)
 972                         {
 973                                 if(vlen(wp_from.origin-wp_from_pos)<1)
 974                                 if(wp_from.classname == "waypoint")
 975                                 {
 976                                         found = TRUE;
 977                                         break;
 978                                 }
 979                                 wp_from = wp_from.chain;
 980                         }
 981
 982                         if(!found)
 983                         {
 984                                 print(strcat("NOTICE: Can not find waypoint at ", vtos(wp_from_pos), ". Path skipped\n"));
 985                                 continue;
 986                         }
 987                 }
 988
 989                 // Search "to" waypoint
 990                 wp_to = findradius(wp_to_pos, 1);
 991                 found = FALSE;
 992                 while(wp_to)
 993                 {
 994                         if(vlen(wp_to.origin-wp_to_pos)<1)
 995                         if(wp_to.classname == "waypoint")
 996                         {
 997                                 found = TRUE;
 998                                 break;
 999                         }
1000                         wp_to = wp_to.chain;
1001                 }
1002
1003                 if(!found)
1004                 {
1005                         print(strcat("NOTICE: Can not find waypoint at ", vtos(wp_to_pos), ". Path skipped\n"));
1006                         continue;
1007                 }
1008
1009                 ++c;
1010                 waypoint_addlink(wp_from, wp_to);
1011         }
1012
1013         fclose(file);
1014
1015         dprint("loaded ");
1016         dprint(ftos(c));
1017         dprint(" waypoint links from maps/");
1018         dprint(mapname);
1019         dprint(".waypoints.hardwired\n");
1020 };
1021
1022
1023 // Save all waypoint links to a file
1024 void waypoint_save_links()
1025 {
1026         local string filename, s;
1027         local float file, c, i;
1028         local entity w, link;
1029         filename = strcat("maps/", mapname);
1030         filename = strcat(filename, ".waypoints.cache");
1031         file = fopen(filename, FILE_WRITE);
1032         if (file < 0)
1033         {
1034                 print("waypoint links save to ");
1035                 print(filename);
1036                 print(" failed\n");
1037         }
1038         c = 0;
1039         w = findchain(classname, "waypoint");
1040         while (w)
1041         {
1042                 for(i=0;i<MAX_WAYPOINTS_LINKS;++i)
1043                 {
1044                         link = w.wlink[i];
1045
1046                         if(link==world)
1047                                 continue;
1048
1049                         s = strcat(vtos(w.origin), "*", vtos(link.origin), "\n");
1050                         fputs(file, s);
1051                         ++c;
1052                 }
1053                 w = w.chain;
1054         }
1055         fclose(file);
1056         botframe_cachedwaypointlinks = TRUE;
1057
1058         print("saved ");
1059         print(ftos(c));
1060         print(" waypoints links to maps/");
1061         print(mapname);
1062         print(".waypoints.cache\n");
1063 };
1064
1065 // save waypoints to gamedir/data/maps/mapname.waypoints
1066 void waypoint_saveall()
1067 {
1068         local string filename, s;
1069         local float file, c;
1070         local entity w;
1071         filename = strcat("maps/", mapname);
1072         filename = strcat(filename, ".waypoints");
1073         file = fopen(filename, FILE_WRITE);
1074         if (file >= 0)
1075         {
1076                 c = 0;
1077                 w = findchain(classname, "waypoint");
1078                 while (w)
1079                 {
1080                         if (!(w.wpflags & WAYPOINTFLAG_GENERATED))
1081                         {
1082                                 s = strcat(vtos(w.origin + w.mins), "\n");
1083                                 s = strcat(s, vtos(w.origin + w.maxs));
1084                                 s = strcat(s, "\n");
1085                                 s = strcat(s, ftos(w.wpflags));
1086                                 s = strcat(s, "\n");
1087                                 fputs(file, s);
1088                                 c = c + 1;
1089                         }
1090                         w = w.chain;
1091                 }
1092                 fclose(file);
1093                 bprint("saved ");
1094                 bprint(ftos(c));
1095                 bprint(" waypoints to maps/");
1096                 bprint(mapname);
1097                 bprint(".waypoints\n");
1098         }
1099         else
1100         {
1101                 bprint("waypoint save to ");
1102                 bprint(filename);
1103                 bprint(" failed\n");
1104         }
1105         waypoint_save_links();
1106         botframe_loadedforcedlinks = FALSE;
1107 };
1108
1109 // load waypoints from file
1110 float waypoint_loadall()
1111 {
1112         local string filename, s;
1113         local float file, cwp, cwb, fl;
1114         local vector m1, m2;
1115         cwp = 0;
1116         cwb = 0;
1117         filename = strcat("maps/", mapname);
1118         filename = strcat(filename, ".waypoints");
1119         file = fopen(filename, FILE_READ);
1120         if (file >= 0)
1121         {
1122                 while (1)
1123                 {
1124                         s = fgets(file);
1125                         if (!s)
1126                                 break;
1127                         m1 = stov(s);
1128                         s = fgets(file);
1129                         if (!s)
1130                                 break;
1131                         m2 = stov(s);
1132                         s = fgets(file);
1133                         if (!s)
1134                                 break;
1135                         fl = stof(s);
1136                         waypoint_spawn(m1, m2, fl);
1137                         if (m1 == m2)
1138                                 cwp = cwp + 1;
1139                         else
1140                                 cwb = cwb + 1;
1141                 }
1142                 fclose(file);
1143                 dprint("loaded ");
1144                 dprint(ftos(cwp));
1145                 dprint(" waypoints and ");
1146                 dprint(ftos(cwb));
1147                 dprint(" wayboxes from maps/");
1148                 dprint(mapname);
1149                 dprint(".waypoints\n");
1150         }
1151         else
1152         {
1153                 dprint("waypoint load from ");
1154                 dprint(filename);
1155                 dprint(" failed\n");
1156         }
1157         return cwp + cwb;
1158 };
1159
1160 void waypoint_spawnforitem_force(entity e, vector org)
1161 {
1162         local entity w;
1163
1164         // Fix the waypoint altitude if necessary
1165         traceline(org, org + '0 0 -65535', TRUE, e);
1166         if(
1167                 org_z - trace_endpos_z > PL_MAX_z - PL_MIN_z + 10 // If middle of entiy is above player heigth
1168                 || org_z - trace_endpos_z < (PL_MAX_z - PL_MIN_z) * 0.5 // or below half player height
1169         )
1170                 org_z = trace_endpos_z + PL_MAX_z - PL_MIN_z;
1171
1172         // don't spawn an item spawnfunc_waypoint if it already exists
1173         w = findchain(classname, "waypoint");
1174         while (w)
1175         {
1176                 if (w.wpisbox)
1177                 {
1178                         if (boxesoverlap(org, org, w.absmin, w.absmax))
1179                         {
1180                                 e.nearestwaypoint = w;
1181                                 return;
1182                         }
1183                 }
1184                 else
1185                 {
1186                         if (vlen(w.origin - org) < 16)
1187                         {
1188                                 e.nearestwaypoint = w;
1189                                 return;
1190                         }
1191                 }
1192                 w = w.chain;
1193         }
1194         e.nearestwaypoint = waypoint_spawn(org, org, WAYPOINTFLAG_GENERATED | WAYPOINTFLAG_ITEM);
1195 }
1196
1197 void waypoint_spawnforitem(entity e)
1198 {
1199         if(!bot_waypoints_for_items)
1200                 return;
1201
1202         waypoint_spawnforitem_force(e, e.origin);
1203 };
1204
1205 void waypoint_spawnforteleporter(entity e, vector destination, float timetaken)
1206 {
1207         local entity w;
1208         local entity dw;
1209         w = waypoint_spawn(e.absmin, e.absmax, WAYPOINTFLAG_GENERATED | WAYPOINTFLAG_TELEPORT | WAYPOINTFLAG_NORELINK);
1210         dw = waypoint_spawn(destination, destination, WAYPOINTFLAG_GENERATED);
1211         // one way link to the destination
1212         w.(wlink[0]) = dw;
1213         w.(wpmincost[0]) = timetaken; // this is just for jump pads
1214         // the teleporter's nearest spawnfunc_waypoint is this one
1215         // (teleporters are not goals, so this is probably useless)
1216         e.nearestwaypoint = w;
1217         e.nearestwaypointtimeout = time + 1000000000;
1218 };
1219
1220 entity waypoint_spawnpersonal(vector position)
1221 {
1222         entity w;
1223
1224         // drop the waypoint to a proper location:
1225         //   first move it up by a player height
1226         //   then move it down to hit the floor with player bbox size
1227         traceline(position, position + '0 0 1' * (PL_MAX_z - PL_MIN_z), MOVE_NOMONSTERS, world);
1228         tracebox(trace_endpos, PL_MIN, PL_MAX, trace_endpos + '0 0 -1024', MOVE_NOMONSTERS, world);
1229         if(trace_fraction < 1)
1230                 position = trace_endpos;
1231
1232         w = waypoint_spawn(position, position, WAYPOINTFLAG_GENERATED | WAYPOINTFLAG_PERSONAL);
1233         w.nearestwaypoint = world;
1234         w.nearestwaypointtimeout = 0;
1235         w.owner = self;
1236
1237         waypoint_schedulerelink(w);
1238
1239         return w;
1240 };
1241
1242 /////////////////////////////////////////////////////////////////////////////
1243 // goal stack
1244 /////////////////////////////////////////////////////////////////////////////
1245
1246 // completely empty the goal stack, used when deciding where to go
1247 void navigation_clearroute()
1248 {
1249         float i;
1250
1251         //print("bot ", etos(self), " clear\n");
1252         self.navigation_hasgoals = FALSE;
1253
1254         self.goalcurrent = world;
1255
1256         for(i=0; i<GOALSTACK_LENGTH; ++i)
1257                 self.(goalstack[i]) = world;
1258 };
1259
1260 // add a new goal at the beginning of the stack
1261 // (in other words: add a new prerequisite before going to the later goals)
1262 void navigation_pushroute(entity e)
1263 {
1264         float i;
1265
1266         //print("bot ", etos(self), " push ", etos(e), "\n");
1267         for(i=GOALSTACK_LENGTH-1; i>0; --i)
1268                 self.(goalstack[i]) = self.goalstack[i-1];
1269
1270         self.(goalstack[0]) = self.goalcurrent;
1271         self.goalcurrent = e;
1272 };
1273
1274 // remove first goal from stack
1275 // (in other words: remove a prerequisite for reaching the later goals)
1276 // (used when a spawnfunc_waypoint is reached)
1277 void navigation_poproute()
1278 {
1279         float i;
1280         //print("bot ", etos(self), " pop\n");
1281         self.goalcurrent = self.goalstack[0];
1282
1283         for(i=0; i<GOALSTACK_LENGTH-1; ++i)
1284         {
1285                 if(self.goalstack[i])
1286                         self.(goalstack[i]) = self.goalstack[i+1];
1287                 else
1288                         return;
1289         }
1290
1291         self.(goalstack[i]) = world;
1292 };
1293
1294 // find the spawnfunc_waypoint near a dynamic goal such as a dropped weapon
1295 entity navigation_findnearestwaypoint(entity ent, float walkfromwp)
1296 {
1297         local entity waylist, w, best;
1298         local float dist, bestdist;
1299         local vector v, org, pm1, pm2;
1300         pm1 = ent.origin + PL_MIN;
1301         pm2 = ent.origin + PL_MAX;
1302         waylist = findchain(classname, "waypoint");
1303
1304         // do two scans, because box test is cheaper
1305         w = waylist;
1306         while (w)
1307         {
1308                 // if object is touching spawnfunc_waypoint
1309                 if(w != ent)
1310                         if (boxesoverlap(pm1, pm2, w.absmin, w.absmax))
1311                                 return w;
1312                 w = w.chain;
1313         }
1314
1315         org = ent.origin + (ent.mins_z - PL_MIN_z) * '0 0 1';
1316         if(ent.tag_entity)
1317                 org = org + ent.tag_entity.origin;
1318         if (navigation_testtracewalk)
1319                 te_plasmaburn(org);
1320
1321         best = world;
1322         bestdist = 1050;
1323
1324         // box check failed, try walk
1325         w = waylist;
1326         while (w)
1327         {
1328                 // if object can walk from spawnfunc_waypoint
1329                 if(w != ent)
1330                 {
1331                         if (w.wpisbox)
1332                         {
1333                                 local vector wm1, wm2;
1334                                 wm1 = w.origin + w.mins;
1335                                 wm2 = w.origin + w.maxs;
1336                                 v_x = bound(wm1_x, org_x, wm2_x);
1337                                 v_y = bound(wm1_y, org_y, wm2_y);
1338                                 v_z = bound(wm1_z, org_z, wm2_z);
1339                         }
1340                         else
1341                                 v = w.origin;
1342                         dist = vlen(v - org);
1343                         if (bestdist > dist)
1344                         {
1345                                 traceline(v, org, TRUE, ent);
1346                                 if (trace_fraction == 1)
1347                                 {
1348                                         if (walkfromwp)
1349                                         {
1350                                                 //print("^1can I reach ", vtos(org), " from ", vtos(v), "?\n");
1351                                                 if (tracewalk(ent, v, PL_MIN, PL_MAX, org, bot_navigation_movemode))
1352                                                 {
1353                                                         bestdist = dist;
1354                                                         best = w;
1355                                                 }
1356                                         }
1357                                         else
1358                                         {
1359                                                 if (tracewalk(ent, org, PL_MIN, PL_MAX, v, bot_navigation_movemode))
1360                                                 {
1361                                                         bestdist = dist;
1362                                                         best = w;
1363                                                 }
1364                                         }
1365                                 }
1366                         }
1367                 }
1368                 w = w.chain;
1369         }
1370         return best;
1371 }
1372
1373 // finds the waypoints near the bot initiating a navigation query
1374 float navigation_markroutes_nearestwaypoints(entity waylist, float maxdist)
1375 {
1376         local entity head;
1377         local vector v, m1, m2, diff;
1378         local float c;
1379 //      navigation_testtracewalk = TRUE;
1380         c = 0;
1381         head = waylist;
1382         while (head)
1383         {
1384                 if (!head.wpconsidered)
1385                 {
1386                         if (head.wpisbox)
1387                         {
1388                                 m1 = head.origin + head.mins;
1389                                 m2 = head.origin + head.maxs;
1390                                 v = self.origin;
1391                                 v_x = bound(m1_x, v_x, m2_x);
1392                                 v_y = bound(m1_y, v_y, m2_y);
1393                                 v_z = bound(m1_z, v_z, m2_z);
1394                         }
1395                         else
1396                                 v = head.origin;
1397                         diff = v - self.origin;
1398                         diff_z = max(0, diff_z);
1399                         if (vlen(diff) < maxdist)
1400                         {
1401                                 head.wpconsidered = TRUE;
1402                                 if (tracewalk(self, self.origin, self.mins, self.maxs, v, bot_navigation_movemode))
1403                                 {
1404                                         head.wpnearestpoint = v;
1405                                         head.wpcost = vlen(v - self.origin) + head.dmg;
1406                                         head.wpfire = 1;
1407                                         head.enemy = world;
1408                                         c = c + 1;
1409                                 }
1410                         }
1411                 }
1412                 head = head.chain;
1413         }
1414         //navigation_testtracewalk = FALSE;
1415         return c;
1416 }
1417
1418 // updates a path link if a spawnfunc_waypoint link is better than the current one
1419 void navigation_markroutes_checkwaypoint(entity w, entity w2, float cost2, vector p)
1420 {
1421         local vector m1;
1422         local vector m2;
1423         local vector v;
1424         if (w2.wpisbox)
1425         {
1426                 m1 = w2.absmin;
1427                 m2 = w2.absmax;
1428                 v_x = bound(m1_x, p_x, m2_x);
1429                 v_y = bound(m1_y, p_y, m2_y);
1430                 v_z = bound(m1_z, p_z, m2_z);
1431         }
1432         else
1433                 v = w2.origin;
1434         cost2 = cost2 + vlen(v);
1435         if (w2.wpcost > cost2)
1436         {
1437                 w2.wpcost = cost2;
1438                 w2.enemy = w;
1439                 w2.wpfire = 1;
1440                 w2.wpnearestpoint = v;
1441         }
1442 };
1443
1444 // queries the entire spawnfunc_waypoint network for pathes leading away from the bot
1445 void navigation_markroutes()
1446 {
1447         local entity w, wp, waylist;
1448         local float searching, cost, cost2;
1449         local vector p;
1450         w = waylist = findchain(classname, "waypoint");
1451         while (w)
1452         {
1453                 w.wpconsidered = FALSE;
1454                 w.wpnearestpoint = '0 0 0';
1455                 w.wpcost = 10000000;
1456                 w.wpfire = 0;
1457                 w.enemy = world;
1458                 w = w.chain;
1459         }
1460
1461         // try a short range search for the nearest waypoints, and expand the search repeatedly if none are found
1462         // as this search is expensive we will use lower values if the bot is on the air
1463         local float i, increment, maxdistance;
1464         if(self.flags & FL_ONGROUND)
1465         {
1466                 increment = 750;
1467                 maxdistance = 50000;
1468         }
1469         else
1470         {
1471                 increment = 500;
1472                 maxdistance = 1500;
1473         }
1474
1475         for(i=increment;!navigation_markroutes_nearestwaypoints(waylist, i)&&i<maxdistance;i+=increment);
1476
1477         searching = TRUE;
1478         while (searching)
1479         {
1480                 searching = FALSE;
1481                 w = waylist;
1482                 while (w)
1483                 {
1484                         if (w.wpfire)
1485                         {
1486                                 searching = TRUE;
1487                                 w.wpfire = 0;
1488                                 cost = w.wpcost;
1489                                 p = w.wpnearestpoint;
1490
1491                                 for(i=0;i<MAX_WAYPOINTS_LINKS;++i)
1492                                 {
1493                                         wp = w.wlink[i];
1494
1495                                         if(wp)
1496                                         {
1497                                                 cost2 = cost + wp.dmg;
1498                                                 if (wp.wpcost > cost2 + wp.wpmincost[i])
1499                                                         navigation_markroutes_checkwaypoint(w, wp, cost2, p);
1500                                         }
1501                                         else
1502                                                 break;
1503                                 }
1504                         }
1505                         w = w.chain;
1506                 }
1507         }
1508 };
1509
1510 void navigation_bestgoals_reset()
1511 {
1512         local float i;
1513
1514         bestgoalswindex = 0;
1515         bestgoalsrindex = 0;
1516
1517         for(i=0;i>MAX_BESTGOALS-1;++i)
1518         {
1519                 navigation_bestgoals[i] = world;
1520         }
1521 }
1522
1523 void navigation_add_bestgoal(entity goal)
1524 {
1525         if(bestgoalsrindex>0)
1526         {
1527                 ++bestgoalsrindex;
1528
1529                 if(bestgoalsrindex==MAX_BESTGOALS)
1530                         bestgoalsrindex = 0;
1531         }
1532
1533         if(bestgoalswindex==MAX_BESTGOALS)
1534         {
1535                 bestgoalswindex=0;
1536                 if(bestgoalsrindex==0)
1537                         bestgoalsrindex=1;
1538         }
1539
1540         navigation_bestgoals[bestgoalswindex] = goal;
1541
1542         ++bestgoalswindex;
1543 }
1544
1545 entity navigation_get_bestgoal()
1546 {
1547         local entity ent;
1548
1549         ent = navigation_bestgoals[bestgoalsrindex];
1550         navigation_bestgoals[bestgoalsrindex] = world;
1551
1552         ++bestgoalsrindex;
1553
1554         if(bestgoalsrindex==MAX_BESTGOALS)
1555                 bestgoalsrindex = 0;
1556
1557         return ent;
1558 }
1559
1560 // fields required for jetpack navigation
1561 .entity navigation_jetpack_goal;
1562 .vector navigation_jetpack_point;
1563
1564 // updates the best goal according to a weighted calculation of travel cost and item value of a new proposed item
1565 .void() havocbot_role;
1566 void() havocbot_role_ctf_offense;
1567 void navigation_routerating(entity e, float f, float rangebias)
1568 {
1569         entity nwp;
1570         if (!e)
1571                 return;
1572
1573         // Evaluate path using jetpack
1574         if(g_jetpack)
1575         if(self.items & IT_JETPACK)
1576         if(cvar("bot_ai_navigation_jetpack"))
1577         if(vlen(self.origin - e.origin) > cvar("bot_ai_navigation_jetpack_mindistance"))
1578         {
1579                 vector pointa, pointb;
1580
1581         //      dprint("jetpack ai: evaluating path for ", e.classname,"\n");
1582
1583                 // Point A
1584                 traceline(self.origin, self.origin + '0 0 65535', MOVE_NORMAL, self);
1585                 pointa = trace_endpos - '0 0 1';
1586
1587                 // Point B
1588                 traceline(e.origin, e.origin + '0 0 65535', MOVE_NORMAL, e);
1589                 pointb = trace_endpos - '0 0 1';
1590
1591                 // Can I see these two points from the sky?
1592                 traceline(pointa, pointb, MOVE_NORMAL, self);
1593
1594                 if(trace_fraction==1)
1595                 {
1596                 //      dprint("jetpack ai: can bridge these two points\n");
1597
1598                         // Lower the altitude of these points as much as possible
1599                         local float zdistance, xydistance, cost, t, fuel;
1600                         local vector down, npa, npb;
1601
1602                         down = '0 0 -1' * (PL_MAX_z - PL_MIN_z) * 10;
1603
1604                         do{
1605                                 npa = pointa + down;
1606                                 npb = pointb + down;
1607
1608                                 if(npa_z<=self.absmax_z)
1609                                         break;
1610
1611                                 if(npb_z<=e.absmax_z)
1612                                         break;
1613
1614                                 traceline(npa, npb, MOVE_NORMAL, self);
1615                                 if(trace_fraction==1)
1616                                 {
1617                                         pointa = npa;
1618                                         pointb = npb;
1619                                 }
1620                         }
1621                         while(trace_fraction == 1);
1622
1623
1624                         // Rough estimation of fuel consumption
1625                         // (ignores acceleration and current xyz velocity)
1626                         xydistance = vlen(pointa - pointb);
1627                         zdistance = fabs(pointa_z - self.origin_z);
1628
1629                         t = zdistance / cvar("g_jetpack_maxspeed_up");
1630                         t += xydistance / cvar("g_jetpack_maxspeed_side");
1631                         fuel = t * cvar("g_jetpack_fuel") * 0.8;
1632
1633                 //      dprint("jetpack ai: required fuel ", ftos(fuel), " self.ammo_fuel ", ftos(self.ammo_fuel),"\n");
1634
1635                         // enough fuel ?
1636                         if(self.ammo_fuel>fuel)
1637                         {
1638                                 // Estimate cost
1639                                 // (as onground costs calculation is mostly based on distances, here we do the same establishing some relationship
1640                                 //  - between air and ground speeds)
1641
1642                                 cost = xydistance / (cvar("g_jetpack_maxspeed_side")/cvar("sv_maxspeed"));
1643                                 cost += zdistance / (cvar("g_jetpack_maxspeed_up")/cvar("sv_maxspeed"));
1644                                 cost *= 1.5;
1645
1646                                 // Compare against other goals
1647                                 f = f * rangebias / (rangebias + cost);
1648
1649                                 if (navigation_bestrating < f)
1650                                 {
1651                         //              dprint("jetpack path: added goal", e.classname, " (with rating ", ftos(f), ")\n");
1652                                         navigation_bestrating = f;
1653                                         navigation_add_bestgoal(e);
1654                                         self.navigation_jetpack_goal = e;
1655                                         self.navigation_jetpack_point = pointb;
1656                                 }
1657                                 return;
1658                         }
1659                 }
1660         }
1661
1662         //te_wizspike(e.origin);
1663         //bprint(etos(e));
1664         //bprint("\n");
1665         // update the cached spawnfunc_waypoint link on a dynamic item entity
1666         if(e.classname == "waypoint" && !(e.wpflags & WAYPOINTFLAG_PERSONAL))
1667         {
1668                 nwp = e;
1669         }
1670         else
1671         {
1672                 if (time > e.nearestwaypointtimeout)
1673                 {
1674                         e.nearestwaypoint = navigation_findnearestwaypoint(e, TRUE);
1675
1676                         // TODO: Cleaner solution, probably handling this timeout from ctf.qc
1677                         if(e.classname=="item_flag_team")
1678                                 e.nearestwaypointtimeout = time + 2;
1679                         else
1680                                 e.nearestwaypointtimeout = time + random() * 3 + 5;
1681                 }
1682                 nwp = e.nearestwaypoint;
1683         }
1684
1685         //dprint("-- checking ", e.classname, " (with cost ", ftos(nwp.wpcost), ")\n");
1686         if (nwp)
1687         if (nwp.wpcost < 10000000)
1688         {
1689                 //te_wizspike(nwp.wpnearestpoint);
1690         //      dprint(e.classname, " ", ftos(f), "/(1+", ftos((nwp.wpcost + vlen(e.origin - nwp.wpnearestpoint))), "/", ftos(rangebias), ") = ");
1691                 f = f * rangebias / (rangebias + (nwp.wpcost + vlen(e.origin - nwp.wpnearestpoint)));
1692                 //if (self.havocbot_role == havocbot_role_ctf_offense)
1693                 //dprint("considering ", e.classname, " (with rating ", ftos(f), ")\n");
1694                 //dprint(ftos(f));
1695                 if (navigation_bestrating < f)
1696                 {
1697                 //      dprint("ground path: added goal ", e.classname, " (with rating ", ftos(f), ")\n");
1698                         navigation_bestrating = f;
1699                         navigation_add_bestgoal(e);
1700                 }
1701         }
1702         //dprint("\n");
1703 };
1704
1705 // adds an item to the the goal stack with the path to a given item
1706 float navigation_routetogoal(entity e, vector startposition)
1707 {
1708         self.goalentity = e;
1709
1710         // if there is no goal, just exit
1711         if (!e)
1712                 return FALSE;
1713
1714         self.navigation_hasgoals = TRUE;
1715
1716         // put the entity on the goal stack
1717         navigation_pushroute(e);
1718
1719         if(g_jetpack)
1720         if(e==self.navigation_jetpack_goal)
1721                 return TRUE;
1722
1723         // if it can reach the goal there is nothing more to do
1724         if (tracewalk(self, startposition, PL_MIN, PL_MAX, e.origin, bot_navigation_movemode))
1725                 return TRUE;
1726
1727         // see if there are waypoints describing a path to the item
1728         if(e.classname != "waypoint" || (e.wpflags & WAYPOINTFLAG_PERSONAL))
1729                 e = e.nearestwaypoint;
1730         if(e == world)
1731                 return FALSE;
1732
1733         for (;;)
1734         {
1735                 // add the spawnfunc_waypoint to the path
1736                 navigation_pushroute(e);
1737                 e = e.enemy;
1738
1739                 if(e==world)
1740                         break;
1741         }
1742
1743         return FALSE;
1744 };
1745
1746 void navigation_routetogoals()
1747 {
1748         entity g1, g2;
1749
1750         navigation_clearroute();
1751
1752         g1 = navigation_get_bestgoal();
1753         for(;;)
1754         {
1755                 if(g2==world)
1756                         g2 = navigation_get_bestgoal();
1757
1758                 if(g2==world)
1759                 {
1760                         navigation_routetogoal(g1, self.origin);
1761                         return;
1762                 }
1763
1764                 if(navigation_routetogoal(g1, g2.origin))
1765                 {
1766                         g1 = g2;
1767                         g2 = world;
1768                         continue;
1769                 }
1770
1771                 navigation_clearroute();
1772                 g1 = g2;
1773                 g2 = world;
1774         }
1775 }
1776
1777 // removes any currently touching waypoints from the goal stack
1778 // (this is how bots detect if they have reached a goal)
1779 .float lastteleporttime;
1780
1781 void navigation_poptouchedgoals()
1782 {
1783         local vector org, m1, m2;
1784         org = self.origin;
1785         m1 = org + self.mins;
1786         m2 = org + self.maxs;
1787
1788         if(self.goalcurrent.wpflags & WAYPOINTFLAG_TELEPORT)
1789         {
1790                 if(self.lastteleporttime>0)
1791                 if(time-self.lastteleporttime<0.15)
1792                 {
1793                         navigation_poproute();
1794                         return;
1795                 }
1796         }
1797
1798         // Loose goal touching check when running
1799         if(self.aistatus & AI_STATUS_RUNNING)
1800         if(self.goalcurrent.classname=="waypoint")
1801         {
1802                 if(vlen(self.origin - self.goalcurrent.origin)<150)
1803                 {
1804                         traceline(self.origin + self.view_ofs , self.goalcurrent.origin, TRUE, world);
1805                         if(trace_fraction==1)
1806                         {
1807                                 // Detect personal waypoints
1808                                 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
1809                                 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
1810                                 {
1811                                         self.aistatus &~= AI_STATUS_WAYPOINT_PERSONAL_GOING;
1812                                         self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
1813                                 }
1814
1815                                 navigation_poproute();
1816                         }
1817                 }
1818         }
1819
1820         while (self.goalcurrent && boxesoverlap(m1, m2, self.goalcurrent.absmin, self.goalcurrent.absmax))
1821         {
1822                 // Detect personal waypoints
1823                 if(self.aistatus & AI_STATUS_WAYPOINT_PERSONAL_GOING)
1824                 if(self.goalcurrent.wpflags & WAYPOINTFLAG_PERSONAL && self.goalcurrent.owner==self)
1825                 {
1826                         self.aistatus &~= AI_STATUS_WAYPOINT_PERSONAL_GOING;
1827                         self.aistatus |= AI_STATUS_WAYPOINT_PERSONAL_REACHED;
1828                 }
1829
1830                 navigation_poproute();
1831         }
1832 }
1833
1834 // begin a goal selection session (queries spawnfunc_waypoint network)
1835 void navigation_goalrating_start()
1836 {
1837         self.navigation_jetpack_goal = world;
1838         navigation_bestrating = -1;
1839         self.navigation_hasgoals = FALSE;
1840         navigation_bestgoals_reset();
1841         navigation_markroutes();
1842 };
1843
1844 // ends a goal selection session (updates goal stack to the best goal)
1845 void navigation_goalrating_end()
1846 {
1847         navigation_routetogoals();
1848 //      dprint("best goal ", self.goalcurrent.classname , "\n");
1849
1850         // Hack: if it can't walk to any goal just move blindly to the first visible waypoint
1851         if not (self.navigation_hasgoals)
1852         {
1853                 dprint(self.netname, " can't walk to any goal, going to a near waypoint\n");
1854
1855                 entity head;
1856
1857                 RandomSelection_Init();
1858                 head = findradius(self.origin,1000);
1859                 while(head)
1860                 {
1861                         if(head.classname=="waypoint")
1862                         if(!(head.wpflags & WAYPOINTFLAG_GENERATED))
1863                         if(vlen(self.origin-head.origin)>100)
1864                         if(checkpvs(self.view_ofs,head))
1865                                 RandomSelection_Add(head, 0, string_null, 1 + (vlen(self.origin-head.origin)<500), 0);
1866                         head = head.chain;
1867                 }
1868                 if(RandomSelection_chosen_ent)
1869                         navigation_routetogoal(RandomSelection_chosen_ent, self.origin);
1870
1871                 self.navigation_hasgoals = FALSE; // Reset this value
1872         }
1873 };
1874
1875
1876 //////////////////////////////////////////////////////////////////////////////
1877 // general bot functions
1878 //////////////////////////////////////////////////////////////////////////////
1879
1880 .float isbot; // true if this client is actually a bot
1881
1882 float skill;
1883 entity bot_list;
1884 .entity nextbot;
1885 .string netname_freeme;
1886 .string playermodel_freeme;
1887 .string playerskin_freeme;
1888
1889 float sv_maxspeed;
1890 .float createdtime;
1891
1892 .float bot_preferredcolors;
1893
1894 .float bot_attack;
1895 .float bot_dodge;
1896 .float bot_dodgerating;
1897
1898 //.float bot_painintensity;
1899 .float bot_firetimer;
1900 //.float bot_oldhealth;
1901 .void() bot_ai;
1902
1903 .entity bot_aimtarg;
1904 .float bot_aimlatency;
1905 .vector bot_aimselforigin;
1906 .vector bot_aimselfvelocity;
1907 .vector bot_aimtargorigin;
1908 .vector bot_aimtargvelocity;
1909
1910 .float bot_pickup;
1911 .float(entity player, entity item) bot_pickupevalfunc;
1912 .float bot_pickupbasevalue;
1913 .float bot_canfire;
1914 .float bot_strategytime;
1915
1916 // used for aiming currently
1917 // FIXME: make the weapon code use these and then replace the calculations here with a call to the weapon code
1918 vector shotorg;
1919 vector shotdir;
1920
1921 .float bot_forced_team;
1922 .float bot_config_loaded;
1923
1924 void bot_setnameandstuff()
1925 {
1926         string readfile, s;
1927         float file, tokens, prio;
1928         entity p;
1929
1930         string bot_name, bot_model, bot_skin, bot_shirt, bot_pants;
1931         string name, prefix, suffix;
1932
1933         if(cvar("g_campaign"))
1934         {
1935                 prefix = "";
1936                 suffix = "";
1937         }
1938         else
1939         {
1940                 prefix = cvar_string("bot_prefix");
1941                 suffix = cvar_string("bot_suffix");
1942         }
1943
1944         file = fopen(cvar_string("bot_config_file"), FILE_READ);
1945
1946         if(file < 0)
1947                 print(strcat("Error: Can not open the bot configuration file '",cvar_string("bot_config_file"),"'\n"));
1948         else
1949         {
1950                 RandomSelection_Init();
1951                 for(;;)
1952                 {
1953                         readfile = fgets(file);
1954                         if(!readfile)
1955                                 break;
1956                         if(substring(readfile, 0, 2) == "//")
1957                                 continue;
1958                         if(substring(readfile, 0, 1) == "#")
1959                                 continue;
1960                         tokens = tokenizebyseparator(readfile, "\t");
1961                         s = argv(0);
1962                         prio = 1;
1963                         FOR_EACH_CLIENT(p)
1964                         {
1965                                 if(strcat(prefix, s, suffix) == p.netname)
1966                                 {
1967                                         prio = 0;
1968                                         break;
1969                                 }
1970                         }
1971                         RandomSelection_Add(world, 0, readfile, 1, prio);
1972                 }
1973                 readfile = RandomSelection_chosen_string;
1974                 fclose(file);
1975         }
1976
1977         tokens = tokenizebyseparator(readfile, "\t");
1978         if(argv(0) != "") bot_name = argv(0);
1979         else bot_name = "Bot";
1980
1981         if(argv(1) != "") bot_model = argv(1);
1982         else bot_model = "marine";
1983
1984         if(argv(2) != "") bot_skin = argv(2);
1985         else bot_skin = "0";
1986
1987         if(argv(3) != "" && stof(argv(3)) >= 0) bot_shirt = argv(3);
1988         else bot_shirt = ftos(floor(random() * 15));
1989
1990         if(argv(4) != "" && stof(argv(4)) >= 0) bot_pants = argv(4);
1991         else bot_pants = ftos(floor(random() * 15));
1992
1993         self.bot_forced_team = stof(argv(5));
1994         self.bot_config_loaded = TRUE;
1995
1996         // this is really only a default, JoinBestTeam is called later
1997         setcolor(self, stof(bot_shirt) * 16 + stof(bot_pants));
1998         self.bot_preferredcolors = self.clientcolors;
1999
2000         // pick the name
2001         if (cvar("bot_usemodelnames"))
2002                 name = bot_model;
2003         else
2004                 name = bot_name;
2005
2006         // pick the model and skin
2007         if(substring(bot_model, -4, 1) != ".")
2008                 bot_model = strcat(bot_model, ".zym");
2009         self.playermodel = self.playermodel_freeme = strzone(strcat("models/player/", bot_model));
2010         self.playerskin = self.playerskin_freeme = strzone(bot_skin);
2011
2012         self.netname = self.netname_freeme = strzone(strcat(prefix, name, suffix));
2013 };
2014
2015 float bot_custom_weapon;
2016 float bot_distance_far;
2017 float bot_distance_close;
2018
2019 float bot_weapons_far[WEP_LAST];
2020 float bot_weapons_mid[WEP_LAST];
2021 float bot_weapons_close[WEP_LAST];
2022
2023 void bot_custom_weapon_priority_setup()
2024 {
2025         local float tokens, i, c, w;
2026
2027         bot_custom_weapon = FALSE;
2028
2029         if(     cvar_string("bot_ai_custom_weapon_priority_far") == "" ||
2030                 cvar_string("bot_ai_custom_weapon_priority_mid") == "" ||
2031                 cvar_string("bot_ai_custom_weapon_priority_close") == "" ||
2032                 cvar_string("bot_ai_custom_weapon_priority_distances") == ""
2033         )
2034                 return;
2035
2036         // Parse distances
2037         tokens = tokenizebyseparator(cvar_string("bot_ai_custom_weapon_priority_distances")," ");
2038
2039         if (tokens!=2)
2040                 return;
2041
2042         bot_distance_far = stof(argv(0));
2043         bot_distance_close = stof(argv(1));
2044
2045         if(bot_distance_far < bot_distance_close){
2046                 bot_distance_far = stof(argv(1));
2047                 bot_distance_close = stof(argv(0));
2048         }
2049
2050         // Initialize list of weapons
2051         bot_weapons_far[0] = -1;
2052         bot_weapons_mid[0] = -1;
2053         bot_weapons_close[0] = -1;
2054
2055         // Parse far distance weapon priorities
2056         tokens = tokenizebyseparator(cvar_string("bot_ai_custom_weapon_priority_far")," ");
2057
2058         c = 0;
2059         for(i=0; i < tokens && c < WEP_COUNT; ++i){
2060                 w = stof(argv(i));
2061                 if ( w >= WEP_FIRST && w <= WEP_LAST) {
2062                         bot_weapons_far[c] = w;
2063                         ++c;
2064                 }
2065         }
2066         if(c < WEP_COUNT)
2067                 bot_weapons_far[c] = -1;
2068
2069         // Parse mid distance weapon priorities
2070         tokens = tokenizebyseparator(cvar_string("bot_ai_custom_weapon_priority_mid")," ");
2071
2072         c = 0;
2073         for(i=0; i < tokens && c < WEP_COUNT; ++i){
2074                 w = stof(argv(i));
2075                 if ( w >= WEP_FIRST && w <= WEP_LAST) {
2076                         bot_weapons_mid[c] = w;
2077                         ++c;
2078                 }
2079         }
2080         if(c < WEP_COUNT)
2081                 bot_weapons_mid[c] = -1;
2082
2083         // Parse close distance weapon priorities
2084         tokens = tokenizebyseparator(cvar_string("bot_ai_custom_weapon_priority_close")," ");
2085
2086         c = 0;
2087         for(i=0; i < tokens && i < WEP_COUNT; ++i){
2088                 w = stof(argv(i));
2089                 if ( w >= WEP_FIRST && w <= WEP_LAST) {
2090                         bot_weapons_close[c] = w;
2091                         ++c;
2092                 }
2093         }
2094         if(c < WEP_COUNT)
2095                 bot_weapons_close[c] = -1;
2096
2097         bot_custom_weapon = TRUE;
2098 };
2099
2100
2101 void bot_endgame()
2102 {
2103         local entity e;
2104         //dprint("bot_endgame\n");
2105         e = bot_list;
2106         while (e)
2107         {
2108                 setcolor(e, e.bot_preferredcolors);
2109                 e = e.nextbot;
2110         }
2111         // if dynamic waypoints are ever implemented, save them here
2112 };
2113
2114 float bot_ignore_bots; // let bots not attack other bots (only works in non-teamplay)
2115 float bot_shouldattack(entity e)
2116 {
2117         if (e.team == self.team)
2118         {
2119                 if (e == self)
2120                         return FALSE;
2121                 if (teams_matter)
2122                 if (e.team != 0)
2123                         return FALSE;
2124         }
2125
2126         if(teams_matter)
2127         {
2128                 if(e.team==0)
2129                         return FALSE;
2130         }
2131         else if(bot_ignore_bots)
2132                 if(clienttype(e) == CLIENTTYPE_BOT)
2133                         return FALSE;
2134
2135         if (!e.takedamage)
2136                 return FALSE;
2137         if (e.deadflag)
2138                 return FALSE;
2139         if (e.BUTTON_CHAT)
2140                 return FALSE;
2141         if(g_minstagib)
2142         if(e.items & IT_STRENGTH)
2143                 return FALSE;
2144         if(e.flags & FL_NOTARGET)
2145                 return FALSE;
2146         return TRUE;
2147 };
2148
2149 void bot_lagfunc(float t, float f1, float f2, entity e1, vector v1, vector v2, vector v3, vector v4)
2150 {
2151         if(self.flags & FL_INWATER)
2152         {
2153                 self.bot_aimtarg = world;
2154                 return;
2155         }
2156         self.bot_aimtarg = e1;
2157         self.bot_aimlatency = self.ping; // FIXME?  Shouldn't this be in the lag item?
2158         self.bot_aimselforigin = v1;
2159         self.bot_aimselfvelocity = v2;
2160         self.bot_aimtargorigin = v3;
2161         self.bot_aimtargvelocity = v4;
2162         if(skill <= 0)
2163                 self.bot_canfire = (random() < 0.8);
2164         else if(skill <= 1)
2165                 self.bot_canfire = (random() < 0.9);
2166         else if(skill <= 2)
2167                 self.bot_canfire = (random() < 0.95);
2168         else
2169                 self.bot_canfire = 1;
2170 };
2171
2172 .float bot_nextthink;
2173 .float bot_badaimtime;
2174 .float bot_aimthinktime;
2175 .float bot_prevaimtime;
2176 .vector bot_mouseaim;
2177 .vector bot_badaimoffset;
2178 .vector bot_1st_order_aimfilter;
2179 .vector bot_2nd_order_aimfilter;
2180 .vector bot_3th_order_aimfilter;
2181 .vector bot_4th_order_aimfilter;
2182 .vector bot_5th_order_aimfilter;
2183 .vector bot_olddesiredang;
2184 float bot_aimdir(vector v, float maxfiredeviation)
2185 {
2186         local float dist, delta_t, blend;
2187         local vector desiredang, diffang;
2188
2189         //dprint("aim ", self.netname, ": old:", vtos(self.v_angle));
2190         // make sure v_angle is sane first
2191         self.v_angle_y = self.v_angle_y - floor(self.v_angle_y / 360) * 360;
2192         self.v_angle_z = 0;
2193
2194         // get the desired angles to aim at
2195         //dprint(" at:", vtos(v));
2196         v = normalize(v);
2197         //te_lightning2(world, self.origin + self.view_ofs, self.origin + self.view_ofs + v * 200);
2198         if (time >= self.bot_badaimtime)
2199         {
2200                 self.bot_badaimtime = max(self.bot_badaimtime + 0.3, time);
2201                 self.bot_badaimoffset = randomvec() * bound(0, 5 - 0.5 * (skill+self.bot_offsetskill), 5) * cvar("bot_ai_aimskill_offset");
2202         }
2203         desiredang = vectoangles(v) + self.bot_badaimoffset;
2204         //dprint(" desired:", vtos(desiredang));
2205         if (desiredang_x >= 180)
2206                 desiredang_x = desiredang_x - 360;
2207         desiredang_x = bound(-90, 0 - desiredang_x, 90);
2208         desiredang_z = self.v_angle_z;
2209         //dprint(" / ", vtos(desiredang));
2210
2211         //// pain throws off aim
2212         //if (self.bot_painintensity)
2213         //{
2214         //      // shake from pain
2215         //      desiredang = desiredang + randomvec() * self.bot_painintensity * 0.2;
2216         //}
2217
2218         // calculate turn angles
2219         diffang = (desiredang - self.bot_olddesiredang);
2220         // wrap yaw turn
2221         diffang_y = diffang_y - floor(diffang_y / 360) * 360;
2222         if (diffang_y >= 180)
2223                 diffang_y = diffang_y - 360;
2224         self.bot_olddesiredang = desiredang;
2225         //dprint(" diff:", vtos(diffang));
2226
2227         delta_t = time-self.bot_prevaimtime;
2228         self.bot_prevaimtime = time;
2229         // Here we will try to anticipate the comming aiming direction
2230         self.bot_1st_order_aimfilter= self.bot_1st_order_aimfilter
2231                 + (diffang * (1 / delta_t)    - self.bot_1st_order_aimfilter) * bound(0, cvar("bot_ai_aimskill_order_filter_1st"),1);
2232         self.bot_2nd_order_aimfilter= self.bot_2nd_order_aimfilter
2233                 + (self.bot_1st_order_aimfilter - self.bot_2nd_order_aimfilter) * bound(0, cvar("bot_ai_aimskill_order_filter_2nd"),1);
2234         self.bot_3th_order_aimfilter= self.bot_3th_order_aimfilter
2235                 + (self.bot_2nd_order_aimfilter - self.bot_3th_order_aimfilter) * bound(0, cvar("bot_ai_aimskill_order_filter_3th"),1);
2236         self.bot_4th_order_aimfilter= self.bot_4th_order_aimfilter
2237                 + (self.bot_3th_order_aimfilter - self.bot_4th_order_aimfilter) * bound(0, cvar("bot_ai_aimskill_order_filter_4th"),1);
2238         self.bot_5th_order_aimfilter= self.bot_5th_order_aimfilter
2239                 + (self.bot_4th_order_aimfilter - self.bot_5th_order_aimfilter) * bound(0, cvar("bot_ai_aimskill_order_filter_5th"),1);
2240
2241         //blend = (bound(0,skill,10)*0.1)*pow(1-bound(0,skill,10)*0.05,2.5)*5.656854249; //Plot formule before changing !
2242         blend = bound(0,skill,10)*0.1;
2243         desiredang = desiredang + blend *
2244         (
2245                   self.bot_1st_order_aimfilter * cvar("bot_ai_aimskill_order_mix_1st")
2246                 + self.bot_2nd_order_aimfilter * cvar("bot_ai_aimskill_order_mix_2nd")
2247                 + self.bot_3th_order_aimfilter * cvar("bot_ai_aimskill_order_mix_3th")
2248                 + self.bot_4th_order_aimfilter * cvar("bot_ai_aimskill_order_mix_4th")
2249                 + self.bot_5th_order_aimfilter * cvar("bot_ai_aimskill_order_mix_5th")
2250         );
2251
2252         // calculate turn angles
2253         diffang = desiredang - self.bot_mouseaim;
2254         // wrap yaw turn
2255         diffang_y = diffang_y - floor(diffang_y / 360) * 360;
2256         if (diffang_y >= 180)
2257                 diffang_y = diffang_y - 360;
2258         //dprint(" diff:", vtos(diffang));
2259
2260         if (time >= self.bot_aimthinktime)
2261         {
2262                 self.bot_aimthinktime = max(self.bot_aimthinktime + 0.5 - 0.05*(skill+self.bot_thinkskill), time);
2263                 self.bot_mouseaim = self.bot_mouseaim + diffang * (1-random()*0.1*bound(1,10-skill,10));
2264         }
2265
2266         //self.v_angle = self.v_angle + diffang * bound(0, r * frametime * (skill * 0.5 + 2), 1);
2267
2268         diffang = self.bot_mouseaim - desiredang;
2269         // wrap yaw turn
2270         diffang_y = diffang_y - floor(diffang_y / 360) * 360;
2271         if (diffang_y >= 180)
2272                 diffang_y = diffang_y - 360;
2273         desiredang = desiredang + diffang * bound(0,cvar("bot_ai_aimskill_think"),1);
2274
2275         // calculate turn angles
2276         diffang = desiredang - self.v_angle;
2277         // wrap yaw turn
2278         diffang_y = diffang_y - floor(diffang_y / 360) * 360;
2279         if (diffang_y >= 180)
2280                 diffang_y = diffang_y - 360;
2281         //dprint(" diff:", vtos(diffang));
2282
2283         // jitter tracking
2284         dist = vlen(diffang);
2285         //diffang = diffang + randomvec() * (dist * 0.05 * (3.5 - bound(0, skill, 3)));
2286
2287         // turn
2288         local float r, fixedrate, blendrate;
2289         fixedrate = cvar("bot_ai_aimskill_fixedrate") / bound(1,dist,1000);
2290         blendrate = cvar("bot_ai_aimskill_blendrate");
2291         r = max(fixedrate, blendrate);
2292         //self.v_angle = self.v_angle + diffang * bound(frametime, r * frametime * (2+skill*skill*0.05-random()*0.05*(10-skill)), 1);
2293         self.v_angle = self.v_angle + diffang * bound(delta_t, r * delta_t * (2+pow(skill+self.bot_mouseskill,3)*0.005-random()), 1);
2294         self.v_angle = self.v_angle * bound(0,cvar("bot_ai_aimskill_mouse"),1) + desiredang * bound(0,(1-cvar("bot_ai_aimskill_mouse")),1);
2295         //self.v_angle = self.v_angle + diffang * bound(0, r * frametime * (skill * 0.5 + 2), 1);
2296         //self.v_angle = self.v_angle + diffang * (1/ blendrate);
2297         self.v_angle_z = 0;
2298         self.v_angle_y = self.v_angle_y - floor(self.v_angle_y / 360) * 360;
2299         //dprint(" turn:", vtos(self.v_angle));
2300
2301         makevectors(self.v_angle);
2302         shotorg = self.origin + self.view_ofs;
2303         shotdir = v_forward;
2304
2305         //dprint(" dir:", vtos(v_forward));
2306         //te_lightning2(world, shotorg, shotorg + shotdir * 100);
2307
2308         // calculate turn angles again
2309         //diffang = desiredang - self.v_angle;
2310         //diffang_y = diffang_y - floor(diffang_y / 360) * 360;
2311         //if (diffang_y >= 180)
2312         //      diffang_y = diffang_y - 360;
2313
2314         //dprint("e ", vtos(diffang), " < ", ftos(maxfiredeviation), "\n");
2315
2316         // decide whether to fire this time
2317         // note the maxfiredeviation is in degrees so this has to convert to radians first
2318         //if ((normalize(v) * shotdir) >= cos(maxfiredeviation * (3.14159265358979323846 / 180)))
2319         if ((normalize(v) * shotdir) >= cos(maxfiredeviation * (3.14159265358979323846 / 180)))
2320         if (vlen(trace_endpos-shotorg) < 500+500*bound(0, skill, 10) || random()*random()>bound(0,skill*0.05,1))
2321                 self.bot_firetimer = time + bound(0.1, 0.5-skill*0.05, 0.5);
2322         //traceline(shotorg,shotorg+shotdir*1000,FALSE,world);
2323         //dprint(ftos(maxfiredeviation),"\n");
2324         //dprint(" diff:", vtos(diffang), "\n");
2325
2326         return self.bot_canfire && (time < self.bot_firetimer);
2327 };
2328
2329 vector bot_shotlead(vector targorigin, vector targvelocity, float shotspeed, float shotdelay)
2330 {
2331         // Try to add code here that predicts gravity effect here, no clue HOW to though ... well not yet atleast...
2332         return targorigin + targvelocity * (shotdelay + vlen(targorigin - shotorg) / shotspeed);
2333 };
2334
2335 float bot_aim(float shotspeed, float shotspeedupward, float maxshottime, float applygravity)
2336 {
2337         local float f, r;
2338         local vector v;
2339         /*
2340         eprint(self);
2341         dprint("bot_aim(", ftos(shotspeed));
2342         dprint(", ", ftos(shotspeedupward));
2343         dprint(", ", ftos(maxshottime));
2344         dprint(", ", ftos(applygravity));
2345         dprint(");\n");
2346         */
2347         shotspeed *= g_weaponspeedfactor;
2348         shotspeedupward *= g_weaponspeedfactor;
2349         if (!shotspeed)
2350         {
2351                 dprint("bot_aim: WARNING: weapon ", W_Name(self.weapon), " shotspeed is zero!\n");
2352                 shotspeed = 1000000;
2353         }
2354         if (!maxshottime)
2355         {
2356                 dprint("bot_aim: WARNING: weapon ", W_Name(self.weapon), " maxshottime is zero!\n");
2357                 maxshottime = 1;
2358         }
2359         makevectors(self.v_angle);
2360         shotorg = self.origin + self.view_ofs;
2361         shotdir = v_forward;
2362         v = bot_shotlead(self.bot_aimtargorigin, self.bot_aimtargvelocity, shotspeed, self.bot_aimlatency);
2363         local float distanceratio;
2364         distanceratio =sqrt(bound(0,skill,10000))*0.3*(vlen(v-shotorg)-100)/cvar("bot_ai_aimskill_firetolerance_distdegrees");
2365         distanceratio = bound(0,distanceratio,1);
2366         r =  (cvar("bot_ai_aimskill_firetolerance_maxdegrees")-cvar("bot_ai_aimskill_firetolerance_mindegrees"))
2367                 * (1-distanceratio) + cvar("bot_ai_aimskill_firetolerance_mindegrees");
2368         if (applygravity && self.bot_aimtarg)
2369         {
2370                 if (!findtrajectorywithleading(shotorg, '0 0 0', '0 0 0', self.bot_aimtarg, shotspeed, shotspeedupward, maxshottime, 0, self))
2371                         return FALSE;
2372                 f = bot_aimdir(findtrajectory_velocity - shotspeedupward * '0 0 1', r);
2373         }
2374         else
2375         {
2376                 f = bot_aimdir(v - shotorg, r);
2377                 //dprint("AIM: ");dprint(vtos(self.bot_aimtargorigin));dprint(" + ");dprint(vtos(self.bot_aimtargvelocity));dprint(" * ");dprint(ftos(self.bot_aimlatency + vlen(self.bot_aimtargorigin - shotorg) / shotspeed));dprint(" = ");dprint(vtos(v));dprint(" : aimdir = ");dprint(vtos(normalize(v - shotorg)));dprint(" : ");dprint(vtos(shotdir));dprint("\n");
2378                 traceline(shotorg, shotorg + shotdir * 10000, FALSE, self);
2379                 if (trace_ent.takedamage)
2380                 if (trace_fraction < 1)
2381                 if (!bot_shouldattack(trace_ent))
2382                         return FALSE;
2383                 traceline(shotorg, self.bot_aimtargorigin, FALSE, self);
2384                 if (trace_fraction < 1)
2385                 if (trace_ent != self.enemy)
2386                 if (!bot_shouldattack(trace_ent))
2387                         return FALSE;
2388         }
2389         if (r > maxshottime * shotspeed)
2390                 return FALSE;
2391         return f;
2392 };
2393
2394 // TODO: move this painintensity code to the player damage code
2395 void bot_think()
2396 {
2397         if (self.bot_nextthink > time)
2398                 return;
2399
2400         self.flags &~= FL_GODMODE;
2401         if(cvar("bot_god"))
2402                 self.flags |= FL_GODMODE;
2403
2404         self.bot_nextthink = self.bot_nextthink + cvar("bot_ai_thinkinterval");
2405         //if (self.bot_painintensity > 0)
2406         //      self.bot_painintensity = self.bot_painintensity - (skill + 1) * 40 * frametime;
2407
2408         //self.bot_painintensity = self.bot_painintensity + self.bot_oldhealth - self.health;
2409         //self.bot_painintensity = bound(0, self.bot_painintensity, 100);
2410
2411         if(time < game_starttime || ((cvar("g_campaign") && !campaign_bots_may_start)))
2412         {
2413                 self.nextthink = time + 0.5;
2414                 return;
2415         }
2416
2417         if (self.fixangle)
2418         {
2419                 self.v_angle = self.angles;
2420                 self.v_angle_z = 0;
2421                 self.fixangle = FALSE;
2422         }
2423
2424         self.dmg_take = 0;
2425         self.dmg_save = 0;
2426         self.dmg_inflictor = world;
2427
2428         // calculate an aiming latency based on the skill setting
2429         // (simulated network latency + naturally delayed reflexes)
2430         //self.ping = 0.7 - bound(0, 0.05 * skill, 0.5); // moved the reflexes to bot_aimdir (under the name 'think')
2431         // minimum ping 20+10 random
2432         self.ping = bound(0,0.07 - bound(0, skill * 0.005,0.05)+random()*0.01,0.65); // Now holds real lag to server, and higer skill players take a less laggy server
2433         // skill 10 = ping 0.2 (adrenaline)
2434         // skill 0 = ping 0.7 (slightly drunk)
2435
2436         // clear buttons
2437         self.BUTTON_ATCK = 0;
2438         self.button1 = 0;
2439         self.BUTTON_JUMP = 0;
2440         self.BUTTON_ATCK2 = 0;
2441         self.BUTTON_ZOOM = 0;
2442         self.BUTTON_CROUCH = 0;
2443         self.BUTTON_HOOK = 0;
2444         self.BUTTON_INFO = 0;
2445         self.button8 = 0;
2446         self.BUTTON_CHAT = 0;
2447         self.BUTTON_USE = 0;
2448
2449         // if dead, just wait until we can respawn
2450         if (self.deadflag)
2451         {
2452                 if (self.deadflag == DEAD_DEAD)
2453                 {
2454                         self.BUTTON_JUMP = 1; // press jump to respawn
2455                         self.bot_strategytime = 0;
2456                 }
2457         }
2458
2459         // now call the current bot AI (havocbot for example)
2460         self.bot_ai();
2461 };
2462
2463 entity bot_strategytoken;
2464 float bot_strategytoken_taken;
2465 entity player_list;
2466 .entity nextplayer;
2467 void bot_relinkplayerlist()
2468 {
2469         local entity e;
2470         local entity prevbot;
2471         player_count = 0;
2472         currentbots = 0;
2473         player_list = e = findchainflags(flags, FL_CLIENT);
2474         bot_list = world;
2475         prevbot = world;
2476         while (e)
2477         {
2478                 player_count = player_count + 1;
2479                 e.nextplayer = e.chain;
2480                 if (clienttype(e) == CLIENTTYPE_BOT)
2481                 {
2482                         if (prevbot)
2483                                 prevbot.nextbot = e;
2484                         else
2485                         {
2486                                 bot_list = e;
2487                                 bot_list.nextbot = world;
2488                         }
2489                         prevbot = e;
2490                         currentbots = currentbots + 1;
2491                 }
2492                 e = e.chain;
2493         }
2494         dprint(strcat("relink: ", ftos(currentbots), " bots seen.\n"));
2495         bot_strategytoken = bot_list;
2496         bot_strategytoken_taken = TRUE;
2497 };
2498
2499 void() havocbot_setupbot;
2500 float JoinBestTeam(entity pl, float only_return_best, float forcebestteam);
2501
2502 void bot_clientdisconnect()
2503 {
2504         if (clienttype(self) != CLIENTTYPE_BOT)
2505                 return;
2506         if(self.netname_freeme)
2507                 strunzone(self.netname_freeme);
2508         if(self.playermodel_freeme)
2509                 strunzone(self.playermodel_freeme);
2510         if(self.playerskin_freeme)
2511                 strunzone(self.playerskin_freeme);
2512         self.netname_freeme = string_null;
2513         self.playermodel_freeme = string_null;
2514         self.playerskin_freeme = string_null;
2515 }
2516
2517 void bot_clientconnect()
2518 {
2519         if (clienttype(self) != CLIENTTYPE_BOT)
2520                 return;
2521         self.bot_preferredcolors = self.clientcolors;
2522         self.bot_nextthink = time - random();
2523         self.lag_func = bot_lagfunc;
2524         self.isbot = TRUE;
2525         self.createdtime = self.nextthink;
2526
2527         if(!self.bot_config_loaded) // This is needed so team overrider doesn't break between matches
2528                 bot_setnameandstuff();
2529
2530         if(self.bot_forced_team==1)
2531                 self.team = COLOR_TEAM1;
2532         else if(self.bot_forced_team==2)
2533                 self.team = COLOR_TEAM2;
2534         else if(self.bot_forced_team==3)
2535                 self.team = COLOR_TEAM3;
2536         else if(self.bot_forced_team==4)
2537                 self.team = COLOR_TEAM4;
2538         else
2539                 JoinBestTeam(self, FALSE, TRUE);
2540
2541         havocbot_setupbot();
2542         self.bot_mouseskill=random()-0.5;
2543         self.bot_thinkskill=random()-0.5;
2544         self.bot_predictionskill=random()-0.5;
2545         self.bot_offsetskill=random()-0.5;
2546 };
2547
2548 entity bot_spawn()
2549 {
2550         local entity oldself, bot;
2551         bot = spawnclient();
2552         if (bot)
2553         {
2554                 currentbots = currentbots + 1;
2555                 oldself = self;
2556                 self = bot;
2557                 bot_setnameandstuff();
2558                 ClientConnect();
2559                 PutClientInServer();
2560                 self = oldself;
2561         }
2562         return bot;
2563 };
2564
2565 void CheckAllowedTeams(entity for_whom); void GetTeamCounts(entity other); float c1, c2, c3, c4;
2566 void bot_removefromlargestteam()
2567 {
2568         local float besttime, bestcount, thiscount;
2569         local entity best, head;
2570         CheckAllowedTeams(world);
2571         GetTeamCounts(world);
2572         head = findchainfloat(isbot, TRUE);
2573         if (!head)
2574                 return;
2575         best = head;
2576         besttime = head.createdtime;
2577         bestcount = 0;
2578         while (head)
2579         {
2580                 if(head.team == COLOR_TEAM1)
2581                         thiscount = c1;
2582                 else if(head.team == COLOR_TEAM2)
2583                         thiscount = c2;
2584                 else if(head.team == COLOR_TEAM3)
2585                         thiscount = c3;
2586                 else if(head.team == COLOR_TEAM4)
2587                         thiscount = c4;
2588                 else
2589                         thiscount = 0;
2590                 if (thiscount > bestcount)
2591                 {
2592                         bestcount = thiscount;
2593                         besttime = head.createdtime;
2594                         best = head;
2595                 }
2596                 else if (thiscount == bestcount && besttime < head.createdtime)
2597                 {
2598                         besttime = head.createdtime;
2599                         best = head;
2600                 }
2601                 head = head.chain;
2602         }
2603         currentbots = currentbots - 1;
2604         dropclient(best);
2605 };
2606
2607 void bot_removenewest()
2608 {
2609         local float besttime;
2610         local entity best, head;
2611
2612         if(teams_matter)
2613         {
2614                 bot_removefromlargestteam();
2615                 return;
2616         }
2617
2618         head = findchainfloat(isbot, TRUE);
2619         if (!head)
2620                 return;
2621         best = head;
2622         besttime = head.createdtime;
2623         while (head)
2624         {
2625                 if (besttime < head.createdtime)
2626                 {
2627                         besttime = head.createdtime;
2628                         best = head;
2629                 }
2630                 head = head.chain;
2631         }
2632         currentbots = currentbots - 1;
2633         dropclient(best);
2634 };
2635
2636 float botframe_waypointeditorlightningtime;
2637 void botframe_showwaypointlinks()
2638 {
2639         local entity player, head, w;
2640         float i;
2641
2642         if (time < botframe_waypointeditorlightningtime)
2643                 return;
2644         botframe_waypointeditorlightningtime = time + 0.5;
2645         player = find(world, classname, "player");
2646         while (player)
2647         {
2648                 if (!player.isbot)
2649                 if (player.flags & FL_ONGROUND || player.waterlevel > WATERLEVEL_NONE)
2650                 {
2651                         //navigation_testtracewalk = TRUE;
2652                         head = navigation_findnearestwaypoint(player, FALSE);
2653                 //      print("currently selected WP is ", etos(head), "\n");
2654                         //navigation_testtracewalk = FALSE;
2655                         if (head)
2656                         {
2657                                 te_lightning2(world, head.origin, player.origin);
2658
2659                                 for(i=0;i<MAX_WAYPOINTS_LINKS;++i)
2660                                 {
2661                                         w = head.wlink[i];
2662                                         if (w)
2663                                                 te_lightning2(world, w.origin, head.origin);
2664                                 }
2665                         }
2666                 }
2667                 player = find(player, classname, "player");
2668         }
2669 };
2670
2671 entity botframe_dangerwaypoint;
2672 void botframe_updatedangerousobjects(float maxupdate)
2673 {
2674         local entity head, bot_dodgelist;
2675         local vector m1, m2, v;
2676         local float c, d, danger;
2677         c = 0;
2678         bot_dodgelist = findchainfloat(bot_dodge, TRUE);
2679         botframe_dangerwaypoint = find(botframe_dangerwaypoint, classname, "waypoint");
2680         while (botframe_dangerwaypoint != world)
2681         {
2682                 danger = 0;
2683                 m1 = botframe_dangerwaypoint.mins;
2684                 m2 = botframe_dangerwaypoint.maxs;
2685                 head = bot_dodgelist;
2686                 while (head)
2687                 {
2688                         v = head.origin;
2689                         v_x = bound(m1_x, v_x, m2_x);
2690                         v_y = bound(m1_y, v_y, m2_y);
2691                         v_z = bound(m1_z, v_z, m2_z);
2692                         d = head.bot_dodgerating - vlen(head.origin - v);
2693                         if (d > 0)
2694                         {
2695                                 traceline(head.origin, v, TRUE, world);
2696                                 if (trace_fraction == 1)
2697                                         danger = danger + d;
2698                         }
2699                         head = head.chain;
2700                 }
2701                 botframe_dangerwaypoint.dmg = danger;
2702                 c = c + 1;
2703                 if (c >= maxupdate)
2704                         break;
2705                 botframe_dangerwaypoint = find(botframe_dangerwaypoint, classname, "waypoint");
2706         }
2707 };
2708
2709
2710 float botframe_spawnedwaypoints;
2711 float botframe_nextthink;
2712 float botframe_nextdangertime;
2713
2714 float autoskill_nextthink;
2715 .float totalfrags_lastcheck;
2716 void autoskill(float factor)
2717 {
2718         float bestbot;
2719         float bestplayer;
2720         entity head;
2721
2722         bestbot = -1;
2723         bestplayer = -1;
2724         FOR_EACH_PLAYER(head)
2725         {
2726                 if(clienttype(head) == CLIENTTYPE_REAL)
2727                         bestplayer = max(bestplayer, head.totalfrags - head.totalfrags_lastcheck);
2728                 else
2729                         bestbot = max(bestbot, head.totalfrags - head.totalfrags_lastcheck);
2730         }
2731
2732         dprint("autoskill: best player got ", ftos(bestplayer), ", ");
2733         dprint("best bot got ", ftos(bestbot), "; ");
2734         if(bestbot < 0 || bestplayer < 0)
2735         {
2736                 dprint("not doing anything\n");
2737                 // don't return, let it reset all counters below
2738         }
2739         else if(bestbot <= bestplayer * factor - 2)
2740         {
2741                 if(cvar("skill") < 17)
2742                 {
2743                         dprint("2 frags difference, increasing skill\n");
2744                         cvar_set("skill", ftos(cvar("skill") + 1));
2745                         bprint("^2SKILL UP!^7 Now at level ", ftos(cvar("skill")), "\n");
2746                 }
2747         }
2748         else if(bestbot >= bestplayer * factor + 2)
2749         {
2750                 if(cvar("skill") > 0)
2751                 {
2752                         dprint("2 frags difference, decreasing skill\n");
2753                         cvar_set("skill", ftos(cvar("skill") - 1));
2754                         bprint("^1SKILL DOWN!^7 Now at level ", ftos(cvar("skill")), "\n");
2755                 }
2756         }
2757         else
2758         {
2759                 dprint("not doing anything\n");
2760                 return;
2761                 // don't reset counters, wait for them to accumulate
2762         }
2763
2764         FOR_EACH_PLAYER(head)
2765                 head.totalfrags_lastcheck = head.totalfrags;
2766 }
2767
2768 float bot_cvar_nextthink;
2769 void bot_serverframe()
2770 {
2771         float realplayers, bots, activerealplayers;
2772         entity head;
2773
2774         if (intermission_running)
2775                 return;
2776
2777         if (time < 2)
2778                 return;
2779
2780         stepheightvec = cvar("sv_stepheight") * '0 0 1';
2781         bot_navigation_movemode = ((cvar("bot_navigation_ignoreplayers")) ? MOVE_NOMONSTERS : MOVE_NORMAL);
2782
2783         if(time > autoskill_nextthink)
2784         {
2785                 float a;
2786                 a = cvar("skill_auto");
2787                 if(a)
2788                         autoskill(a);
2789                 autoskill_nextthink = time + 5;
2790         }
2791
2792         activerealplayers = 0;
2793         realplayers = 0;
2794
2795         FOR_EACH_REALCLIENT(head)
2796         {
2797                 if(head.classname == "player" || g_lms || g_arena)
2798                         ++activerealplayers;
2799                 ++realplayers;
2800         }
2801
2802         // add/remove bots if needed to make sure there are at least
2803         // minplayers+bot_number, or remove all bots if no one is playing
2804         // But don't remove bots immediately on level change, as the real players
2805         // usually haven't rejoined yet
2806         bots_would_leave = FALSE;
2807         if ((realplayers || cvar("bot_join_empty") || (currentbots > 0 && time < 5)))
2808         {
2809                 float realminplayers, minplayers;
2810                 realminplayers = cvar("minplayers");
2811                 minplayers = max(0, floor(realminplayers));
2812
2813                 float realminbots, minbots;
2814                 if(teamplay && cvar("bot_vs_human"))
2815                         realminbots = ceil(fabs(cvar("bot_vs_human")) * activerealplayers);
2816                 else
2817                         realminbots = cvar("bot_number");
2818                 minbots = max(0, floor(realminbots));
2819
2820                 bots = min(max(minbots, minplayers - activerealplayers), maxclients - realplayers);
2821                 if(bots > minbots)
2822                         bots_would_leave = TRUE;
2823         }
2824         else
2825         {
2826                 // if there are no players, remove bots
2827                 bots = 0;
2828         }
2829
2830         bot_ignore_bots = cvar("bot_ignore_bots");
2831
2832         // only add one bot per frame to avoid utter chaos
2833         if(time > botframe_nextthink)
2834         {
2835                 //dprint(ftos(bots), " ? ", ftos(currentbots), "\n");
2836                 while (currentbots < bots)
2837                 {
2838                         if (bot_spawn() == world)
2839                         {
2840                                 bprint("Can not add bot, server full.\n");
2841                                 botframe_nextthink = time + 10;
2842                                 break;
2843                         }
2844                 }
2845                 while (currentbots > bots)
2846                         bot_removenewest();
2847         }
2848
2849         if(botframe_spawnedwaypoints)
2850         {
2851                 if(cvar("waypoint_benchmark"))
2852                         localcmd("quit\n");
2853         }
2854
2855         if (currentbots > 0 || cvar("g_waypointeditor"))
2856         if (botframe_spawnedwaypoints)
2857         {
2858                 if(botframe_cachedwaypointlinks)
2859                 {
2860                         if(!botframe_loadedforcedlinks)
2861                                 waypoint_load_links_hardwired();
2862                 }
2863                 else
2864                 {
2865                         // TODO: Make this check cleaner
2866                         local entity w = findchain(classname, "waypoint");
2867                         if(time - w.nextthink > 10)
2868                                 waypoint_save_links();
2869                 }
2870         }
2871         else
2872         {
2873                 botframe_spawnedwaypoints = TRUE;
2874                 waypoint_loadall();
2875                 if(!waypoint_load_links())
2876                         waypoint_schedulerelinkall();
2877         }
2878
2879         if (bot_list)
2880         {
2881                 // cycle the goal token from one bot to the next each frame
2882                 // (this prevents them from all doing spawnfunc_waypoint searches on the same
2883                 //  frame, which causes choppy framerates)
2884                 if (bot_strategytoken_taken)
2885                 {
2886                         bot_strategytoken_taken = FALSE;
2887                         if (bot_strategytoken)
2888                                 bot_strategytoken = bot_strategytoken.nextbot;
2889                         if (!bot_strategytoken)
2890                                 bot_strategytoken = bot_list;
2891                 }
2892
2893                 if (botframe_nextdangertime < time)
2894                 {
2895                         local float interval;
2896                         interval = cvar("bot_ai_dangerdetectioninterval");
2897                         if (botframe_nextdangertime < time - interval * 1.5)
2898                                 botframe_nextdangertime = time;
2899                         botframe_nextdangertime = botframe_nextdangertime + interval;
2900                         botframe_updatedangerousobjects(cvar("bot_ai_dangerdetectionupdates"));
2901                 }
2902         }
2903
2904         if (cvar("g_waypointeditor"))
2905                 botframe_showwaypointlinks();
2906
2907         if(time > bot_cvar_nextthink)
2908         {
2909                 if(currentbots>0)
2910                         bot_custom_weapon_priority_setup();
2911                 bot_cvar_nextthink = time + 5;
2912         }
2913 };
2914
2915 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(lag_time);
2916 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(lag_float1);
2917 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(lag_float2);
2918 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(lag_vec1);
2919 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(lag_vec2);
2920 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(lag_vec3);
2921 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(lag_vec4);
2922 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(lag_entity1);
2923 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(wlink);
2924 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(wpmincost);
2925 FTEQCC_YOU_SUCK_THIS_IS_NOT_UNREFERENCED(goalstack);