main/aipath.c

   1 /* $Id: aipath.c,v 1.5 2003-10-04 03:14:47 btb Exp $ */
   2 /*
   3 THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
   4 SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
   5 END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
   6 ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
   7 IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
   8 SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
   9 FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
  10 CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  11 AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.
  12 COPYRIGHT 1993-1999 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  13 */
  14
  15 /*
  16  *
  17  * AI path forming stuff.
  18  *
  19  * Old Log:
  20  * Revision 1.5  1995/10/26  14:12:03  allender
  21  * prototype functions for mcc compiler
  22  *
  23  * Revision 1.4  1995/10/25  09:38:22  allender
  24  * prototype some functions causing mcc grief
  25  *
  26  * Revision 1.3  1995/10/10  11:48:43  allender
  27  * PC ai code
  28  *
  29  * Revision 2.0  1995/02/27  11:30:48  john
  30  * New version 2.0, which has no anonymous unions, builds with
  31  * Watcom 10.0, and doesn't require parsing BITMAPS.TBL.
  32  *
  33  * Revision 1.101  1995/02/22  13:42:44  allender
  34  * remove anonymous unions for object structure
  35  *
  36  * Revision 1.100  1995/02/10  16:20:04  mike
  37  * fix bogosity in create_path_points, assumed all objects were robots.
  38  *
  39  * Revision 1.99  1995/02/07  21:09:30  mike
  40  * make run_from guys have diff level based speed.
  41  *
  42  * Revision 1.98  1995/02/04  17:28:29  mike
  43  * make station guys return better.
  44  *
  45  * Revision 1.97  1995/02/04  10:28:39  mike
  46  * fix compile error!
  47  *
  48  * Revision 1.96  1995/02/04  10:03:37  mike
  49  * Fly to exit cheat.
  50  *
  51  * Revision 1.95  1995/02/01  21:10:36  mike
  52  * Array name was dereferenced.  Not a bug, but unclean.
  53  *
  54  * Revision 1.94  1995/02/01  17:14:12  mike
  55  * comment out some common mprintfs which didn't matter.
  56  *
  57  * Revision 1.93  1995/01/30  13:01:23  mike
  58  * Make robots fire at player other than one they are controlled by sometimes.
  59  *
  60  * Revision 1.92  1995/01/29  22:29:32  mike
  61  * add more debug info for guys that get lost.
  62  *
  63  * Revision 1.91  1995/01/20  16:56:05  mike
  64  * station stuff.
  65  *
  66  * Revision 1.90  1995/01/18  10:59:45  mike
  67  * comment out some mprintfs.
  68  *
  69  * Revision 1.89  1995/01/17  16:58:34  mike
  70  * make path following work for multiplayer.
  71  *
  72  * Revision 1.88  1995/01/17  14:21:44  mike
  73  * make run_from guys run better.
  74  *
  75  * Revision 1.87  1995/01/14  17:09:04  mike
  76  * playing with crazy josh, he's kinda slow and dumb now.
  77  *
  78  * Revision 1.86  1995/01/13  18:52:28  mike
  79  * comment out int3.
  80  *
  81  * Revision 1.85  1995/01/05  09:42:11  mike
  82  * compile out code based on SHAREWARE.
  83  *
  84  * Revision 1.84  1995/01/02  12:38:32  mike
  85  * make crazy josh turn faster, therefore evade player better.
  86  *
  87  * Revision 1.83  1994/12/27  15:59:40  mike
  88  * tweak ai_multiplayer_awareness constants.
  89  *
  90  * Revision 1.82  1994/12/19  17:07:10  mike
  91  * deal with new ai_multiplayer_awareness which returns a value saying whether this object can be moved by this player.
  92  *
  93  * Revision 1.81  1994/12/15  13:04:30  mike
  94  * Replace Players[Player_num].time_total references with GameTime.
  95  *
  96  * Revision 1.80  1994/12/09  16:13:23  mike
  97  * remove debug code.
  98  *
  99  * Revision 1.79  1994/12/07  00:36:54  mike
 100  * make robots get out of matcens better and be aware of player.
 101  *
 102  * Revision 1.78  1994/11/30  00:59:05  mike
 103  * optimizations.
 104  *
 105  * Revision 1.77  1994/11/27  23:13:39  matt
 106  * Made changes for new mprintf calling convention
 107  *
 108  * Revision 1.76  1994/11/23  21:59:34  mike
 109  * comment out some mprintfs.
 110  *
 111  * Revision 1.75  1994/11/21  16:07:14  mike
 112  * flip PARALLAX flag, prevent annoying debug information.
 113  *
 114  * Revision 1.74  1994/11/19  15:13:28  mike
 115  * remove unused code and data.
 116  *
 117  * Revision 1.73  1994/11/17  14:53:15  mike
 118  * segment validation functions moved from editor to main.
 119  *
 120  * Revision 1.72  1994/11/16  23:38:42  mike
 121  * new improved boss teleportation behavior.
 122  *
 123  * Revision 1.71  1994/11/13  17:18:30  mike
 124  * debug code, then comment it out.
 125  *
 126  * Revision 1.70  1994/11/11  16:41:43  mike
 127  * flip the PARALLAX flag.
 128  *
 129  * Revision 1.69  1994/11/11  16:33:45  mike
 130  * twiddle the PARALLAX flag.
 131  *
 132  *
 133  * Revision 1.68  1994/11/10  21:32:29  mike
 134  * debug code.
 135  *
 136  * Revision 1.67  1994/11/10  20:15:07  mike
 137  * fix stupid bug: uninitialized pointer.
 138  *
 139  * Revision 1.66  1994/11/10  17:45:15  mike
 140  * debugging.
 141  *
 142  * Revision 1.65  1994/11/10  17:28:10  mike
 143  * debugging.
 144  *
 145  */
 146
 147 #ifdef HAVE_CONFIG_H
 148 #include <conf.h>
 149 #endif
 150
 151 #include <stdio.h>              //      for printf()
 152 #include <stdlib.h>             // for d_rand() and qsort()
 153 #include <string.h>             // for memset()
 154
 155 #include "inferno.h"
 156 #include "mono.h"
 157 #include "3d.h"
 158
 159 #include "object.h"
 160 #include "error.h"
 161 #include "ai.h"
 162 #include "robot.h"
 163 #include "fvi.h"
 164 #include "physics.h"
 165 #include "wall.h"
 166 #ifdef EDITOR
 167 #include "editor/editor.h"
 168 #endif
 169 #include "player.h"
 170 #include "fireball.h"
 171 #include "game.h"
 172
 173 #define PARALLAX        0               //      If !0, then special debugging for Parallax eyes enabled.
 174
 175 //      Length in segments of avoidance path
 176 #define AVOID_SEG_LENGTH        7
 177
 178 #ifdef NDEBUG
 179 #define PATH_VALIDATION 0
 180 #else
 181 #define PATH_VALIDATION 1
 182 #endif
 183
 184 void validate_all_paths(void);
 185 void ai_path_set_orient_and_vel(object *objp, vms_vector* goal_point, int player_visibility, vms_vector *vec_to_player);
 186 void maybe_ai_path_garbage_collect(void);
 187 void ai_path_garbage_collect(void);
 188 #if PATH_VALIDATION
 189 int validate_path(int debug_flag, point_seg* psegs, int num_points);
 190 #endif
 191
 192 //      ------------------------------------------------------------------------
 193 void create_random_xlate(sbyte *xt)
 194 {
 195         int     i;
 196
 197         for (i=0; i<MAX_SIDES_PER_SEGMENT; i++)
 198                 xt[i] = i;
 199
 200         for (i=0; i<MAX_SIDES_PER_SEGMENT; i++) {
 201                 int     j = (d_rand()*MAX_SIDES_PER_SEGMENT)/(D_RAND_MAX+1);
 202                 sbyte temp_byte;
 203                 Assert((j >= 0) && (j < MAX_SIDES_PER_SEGMENT));
 204
 205                 temp_byte = xt[j];
 206                 xt[j] = xt[i];
 207                 xt[i] = temp_byte;
 208         }
 209
 210 }
 211
 212 //      -----------------------------------------------------------------------------------------------------------
 213 //      Insert the point at the center of the side connecting two segments between the two points.
 214 // This is messy because we must insert into the list.  The simplest (and not too slow) way to do this is to start
 215 // at the end of the list and go backwards.
 216 void insert_center_points(point_seg *psegs, int *num_points)
 217 {
 218         int     i, j, last_point;
 219         int     count=*num_points;
 220
 221         last_point = *num_points-1;
 222
 223         for (i=last_point; i>0; i--) {
 224                 int                     connect_side, temp_segnum;
 225                 vms_vector      center_point, new_point;
 226
 227                 psegs[2*i] = psegs[i];
 228                 connect_side = find_connect_side(&Segments[psegs[i].segnum], &Segments[psegs[i-1].segnum]);
 229                 Assert(connect_side != -1);     //      Impossible!  These two segments must be connected, they were created by create_path_points (which was created by mk!)
 230                 if (connect_side == -1)                 //      Try to blow past the assert, this should at least prevent a hang.
 231                         connect_side = 0;
 232                 compute_center_point_on_side(&center_point, &Segments[psegs[i-1].segnum], connect_side);
 233                 vm_vec_sub(&new_point, &psegs[i-1].point, &center_point);
 234                 new_point.x /= 16;
 235                 new_point.y /= 16;
 236                 new_point.z /= 16;
 237                 vm_vec_sub(&psegs[2*i-1].point, &center_point, &new_point);
 238                 temp_segnum = find_point_seg(&psegs[2*i-1].point, psegs[2*i].segnum);
 239                 if (temp_segnum == -1) {
 240                         mprintf((1, "Warning: point not in ANY segment in aipath.c/insert_center_points.\n"));
 241                         psegs[2*i-1].point = center_point;
 242                         find_point_seg(&psegs[2*i-1].point, psegs[2*i].segnum);
 243                 }
 244
 245                 psegs[2*i-1].segnum = psegs[2*i].segnum;
 246                 count++;
 247         }
 248
 249         //      Now, remove unnecessary center points.
 250         //      A center point is unnecessary if it is close to the line between the two adjacent points.
 251         //      MK, OPTIMIZE!  Can get away with about half the math since every vector gets computed twice.
 252         for (i=1; i<count-1; i+=2) {
 253                 vms_vector      temp1, temp2;
 254                 fix                     dot;
 255
 256                 dot = vm_vec_dot(vm_vec_sub(&temp1, &psegs[i].point, &psegs[i-1].point), vm_vec_sub(&temp2, &psegs[i+1].point, &psegs[i].point));
 257
 258                 if (dot * 9/8 > fixmul(vm_vec_mag(&temp1), vm_vec_mag(&temp2)))
 259                         psegs[i].segnum = -1;
 260
 261         }
 262
 263         //      Now, scan for points with segnum == -1
 264         j = 0;
 265         for (i=0; i<count; i++)
 266                 if (psegs[i].segnum != -1)
 267                         psegs[j++] = psegs[i];
 268
 269         *num_points = j;
 270 }
 271
 272 #ifdef EDITOR
 273 int     Safety_flag_override = 0;
 274 int     Random_flag_override = 0;
 275 int     Ai_path_debug=0;
 276 #endif
 277
 278 //      -----------------------------------------------------------------------------------------------------------
 279 //      Move points halfway to outside of segment.
 280 void move_towards_outside(point_seg *psegs, int *num_points, object *objp, int rand_flag)
 281 {
 282         int     i;
 283         point_seg       new_psegs[200];
 284
 285         Assert(*num_points < 200);
 286
 287         for (i=1; i<*num_points-1; i++) {
 288                 int                     new_segnum;
 289                 fix                     segment_size;
 290                 int                     segnum;
 291                 vms_vector      a, b, c, d, e;
 292                 vms_vector      goal_pos;
 293                 int                     count;
 294                 int                     temp_segnum;
 295
 296                 // -- psegs[i].segnum = find_point_seg(&psegs[i].point, psegs[i].segnum);
 297                 temp_segnum = find_point_seg(&psegs[i].point, psegs[i].segnum);
 298                 Assert(temp_segnum != -1);
 299                 psegs[i].segnum = temp_segnum;
 300                 segnum = psegs[i].segnum;
 301
 302                 vm_vec_sub(&a, &psegs[i].point, &psegs[i-1].point);
 303                 vm_vec_sub(&b, &psegs[i+1].point, &psegs[i].point);
 304                 vm_vec_sub(&c, &psegs[i+1].point, &psegs[i-1].point);
 305                 //      I don't think we can use quick version here and this is _very_ rarely called. --MK, 07/03/95
 306                 vm_vec_normalize_quick(&a);
 307                 vm_vec_normalize_quick(&b);
 308                 if (abs(vm_vec_dot(&a, &b)) > 3*F1_0/4 ) {
 309                         if (abs(a.z) < F1_0/2) {
 310                                 if (rand_flag) {
 311                                         e.x = (d_rand()-16384)/2;
 312                                         e.y = (d_rand()-16384)/2;
 313                                         e.z = abs(e.x) + abs(e.y) + 1;
 314                                         vm_vec_normalize_quick(&e);
 315                                 } else {
 316                                         e.x = 0;
 317                                         e.y = 0;
 318                                         e.z = F1_0;
 319                                 }
 320                         } else {
 321                                 if (rand_flag) {
 322                                         e.y = (d_rand()-16384)/2;
 323                                         e.z = (d_rand()-16384)/2;
 324                                         e.x = abs(e.y) + abs(e.z) + 1;
 325                                         vm_vec_normalize_quick(&e);
 326                                 } else {
 327                                         e.x = F1_0;
 328                                         e.y = 0;
 329                                         e.z = 0;
 330                                 }
 331                         }
 332                 } else {
 333                         vm_vec_cross(&d, &a, &b);
 334                         vm_vec_cross(&e, &c, &d);
 335                         vm_vec_normalize_quick(&e);
 336                 }
 337
 338 if (vm_vec_mag_quick(&e) < F1_0/2)
 339         Int3();
 340
 341 //mprintf((0, "(%i) Moving to side: %6.3f %6.3f %6.3f\n", i, f2fl(e.x), f2fl(e.y), f2fl(e.z)));
 342
 343                 segment_size = vm_vec_dist_quick(&Vertices[Segments[segnum].verts[0]], &Vertices[Segments[segnum].verts[6]]);
 344                 if (segment_size > F1_0*40)
 345                         segment_size = F1_0*40;
 346
 347                 vm_vec_scale_add(&goal_pos, &psegs[i].point, &e, segment_size/4);
 348
 349                 count = 3;
 350                 while (count) {
 351                         fvi_query       fq;
 352                         fvi_info                hit_data;
 353                         int                     hit_type;
 354
 355                         fq.p0                                           = &psegs[i].point;
 356                         fq.startseg                             = psegs[i].segnum;
 357                         fq.p1                                           = &goal_pos;
 358                         fq.rad                                  = objp->size;
 359                         fq.thisobjnum                   = objp-Objects;
 360                         fq.ignore_obj_list      = NULL;
 361                         fq.flags                                        = 0;
 362
 363                         hit_type = find_vector_intersection(&fq, &hit_data);
 364
 365                         if (hit_type == HIT_NONE)
 366                                 count = 0;
 367                         else {
 368                                 if ((count == 3) && (hit_type == HIT_BAD_P0))
 369                                         Int3();
 370                                 goal_pos.x = (fq.p0->x + hit_data.hit_pnt.x)/2;
 371                                 goal_pos.y = (fq.p0->y + hit_data.hit_pnt.y)/2;
 372                                 goal_pos.z = (fq.p0->z + hit_data.hit_pnt.z)/2;
 373                                 count--;
 374                                 if (count == 0) {       //      Couldn't move towards outside, that's ok, sometimes things can't be moved.
 375                                         goal_pos = psegs[i].point;
 376                                 }
 377                         }
 378                 }
 379
 380                 //      Only move towards outside if remained inside segment.
 381                 new_segnum = find_point_seg(&goal_pos, psegs[i].segnum);
 382                 if (new_segnum == psegs[i].segnum) {
 383                         new_psegs[i].point = goal_pos;
 384                         new_psegs[i].segnum = new_segnum;
 385                 } else {
 386                         new_psegs[i].point = psegs[i].point;
 387                         new_psegs[i].segnum = psegs[i].segnum;
 388                 }
 389
 390         }
 391
 392         for (i=1; i<*num_points-1; i++)
 393                 psegs[i] = new_psegs[i];
 394 }
 395
 396
 397 //      -----------------------------------------------------------------------------------------------------------
 398 //      Create a path from objp->pos to the center of end_seg.
 399 //      Return a list of (segment_num, point_locations) at psegs
 400 //      Return number of points in *num_points.
 401 //      if max_depth == -1, then there is no maximum depth.
 402 //      If unable to create path, return -1, else return 0.
 403 //      If random_flag !0, then introduce randomness into path by looking at sides in random order.  This means
 404 //      that a path between two segments won't always be the same, unless it is unique.
 405 //      If safety_flag is set, then additional points are added to "make sure" that points are reachable.  I would
 406 //      like to say that it ensures that the object can move between the points, but that would require knowing what
 407 //      the object is (which isn't passed, right?) and making fvi calls (slow, right?).  So, consider it the more_or_less_safe_flag.
 408 //      If end_seg == -2, then end seg will never be found and this routine will drop out due to depth (probably called by create_n_segment_path).
 409 int create_path_points(object *objp, int start_seg, int end_seg, point_seg *psegs, short *num_points, int max_depth, int random_flag, int safety_flag, int avoid_seg)
 410 {
 411         int             cur_seg;
 412         int             sidenum;
 413         int             qtail = 0, qhead = 0;
 414         int             i;
 415         sbyte   visited[MAX_SEGMENTS];
 416         seg_seg seg_queue[MAX_SEGMENTS];
 417         short           depth[MAX_SEGMENTS];
 418         int             cur_depth;
 419         sbyte   random_xlate[MAX_SIDES_PER_SEGMENT];
 420         point_seg       *original_psegs = psegs;
 421         int             l_num_points;
 422
 423 // -- mprintf((0, "cpp: frame = %4i obj %3i, psegs = %5i\n", FrameCount, objp-Objects, psegs-Point_segs));
 424 #if PATH_VALIDATION
 425         validate_all_paths();
 426 #endif
 427
 428 if ((objp->type == OBJ_ROBOT) && (objp->ctype.ai_info.behavior == AIB_RUN_FROM)) {
 429         random_flag = 1;
 430         avoid_seg = ConsoleObject->segnum;
 431         // Int3();
 432 }
 433
 434         if (max_depth == -1)
 435                 max_depth = MAX_PATH_LENGTH;
 436
 437         l_num_points = 0;
 438 //random_flag = Random_flag_override; //!! debug!!
 439 //safety_flag = Safety_flag_override; //!! debug!!
 440
 441 //      for (i=0; i<=Highest_segment_index; i++) {
 442 //              visited[i] = 0;
 443 //              depth[i] = 0;
 444 //      }
 445         memset(visited, 0, sizeof(visited[0])*(Highest_segment_index+1));
 446         memset(depth, 0, sizeof(depth[0])*(Highest_segment_index+1));
 447
 448         //      If there is a segment we're not allowed to visit, mark it.
 449         if (avoid_seg != -1) {
 450                 Assert(avoid_seg <= Highest_segment_index);
 451                 if ((start_seg != avoid_seg) && (end_seg != avoid_seg)) {
 452                         visited[avoid_seg] = 1;
 453                         depth[avoid_seg] = 0;
 454                 } else
 455                         ; // -- mprintf((0, "Start/End/Avoid = %i %i %i\n", start_seg, end_seg, avoid_seg));
 456         }
 457
 458         if (random_flag)
 459                 create_random_xlate(random_xlate);
 460
 461         cur_seg = start_seg;
 462         visited[cur_seg] = 1;
 463         cur_depth = 0;
 464
 465         while (cur_seg != end_seg) {
 466                 segment *segp = &Segments[cur_seg];
 467
 468                 if (random_flag)
 469                         if (d_rand() < 8192)
 470                                 create_random_xlate(random_xlate);
 471
 472                 // mprintf((0, "\n"));
 473                 for (sidenum = 0; sidenum < MAX_SIDES_PER_SEGMENT; sidenum++) {
 474
 475                         int     snum = sidenum;
 476
 477                         if (random_flag)
 478                                 snum = random_xlate[sidenum];
 479
 480                         if (IS_CHILD(segp->children[snum]) && ((WALL_IS_DOORWAY(segp, snum) & WID_FLY_FLAG) || (ai_door_is_openable(objp, segp, snum)))) {
 481                                 int                     this_seg = segp->children[snum];
 482                                 Assert(this_seg != -1);
 483                                 if (((cur_seg == avoid_seg) || (this_seg == avoid_seg)) && (ConsoleObject->segnum == avoid_seg)) {
 484                                         vms_vector      center_point;
 485
 486                                         fvi_query       fq;
 487                                         fvi_info                hit_data;
 488                                         int                     hit_type;
 489
 490                                         compute_center_point_on_side(&center_point, segp, snum);
 491
 492                                         fq.p0                                           = &objp->pos;
 493                                         fq.startseg                             = objp->segnum;
 494                                         fq.p1                                           = &center_point;
 495                                         fq.rad                                  = objp->size;
 496                                         fq.thisobjnum                   = objp-Objects;
 497                                         fq.ignore_obj_list      = NULL;
 498                                         fq.flags                                        = 0;
 499
 500                                         hit_type = find_vector_intersection(&fq, &hit_data);
 501                                         if (hit_type != HIT_NONE) {
 502                                                 // -- mprintf((0, "hit_type = %i, object = %i\n", hit_type, hit_data.hit_object));
 503                                                 goto dont_add;
 504                                         }
 505                                 }
 506
 507                                 if (!visited[this_seg]) {
 508                                         seg_queue[qtail].start = cur_seg;
 509                                         seg_queue[qtail].end = this_seg;
 510                                         visited[this_seg] = 1;
 511                                         depth[qtail++] = cur_depth+1;
 512                                         if (depth[qtail-1] == max_depth) {
 513                                                 // mprintf((0, "\ndepth == max_depth == %i\n", max_depth));
 514                                                 end_seg = seg_queue[qtail-1].end;
 515                                                 goto cpp_done1;
 516                                         }       // end if (depth[...
 517                                 }       // end if (!visited...
 518                         }       // if (WALL_IS_DOORWAY(...
 519 dont_add: ;
 520                 }       //      for (sidenum...
 521
 522                 if (qhead >= qtail) {
 523                         //      Couldn't get to goal, return a path as far as we got, which probably acceptable to the unparticular caller.
 524                         end_seg = seg_queue[qtail-1].end;
 525                         break;
 526                 }
 527
 528                 cur_seg = seg_queue[qhead].end;
 529                 cur_depth = depth[qhead];
 530                 qhead++;
 531
 532 cpp_done1: ;
 533         }       //      while (cur_seg ...
 534
 535         //      Set qtail to the segment which ends at the goal.
 536         while (seg_queue[--qtail].end != end_seg)
 537                 if (qtail < 0) {
 538                         // mprintf((0, "\nNo path!\n"));
 539                         // printf("UNABLE TO FORM PATH");
 540                         // Int3();
 541                         *num_points = l_num_points;
 542                         return -1;
 543                 }
 544
 545         #ifdef EDITOR
 546         // -- N_selected_segs = 0;
 547         #endif
 548 //printf("Object #%3i, start: %3i ", objp-Objects, psegs-Point_segs);
 549         while (qtail >= 0) {
 550                 int     parent_seg, this_seg;
 551
 552                 this_seg = seg_queue[qtail].end;
 553                 parent_seg = seg_queue[qtail].start;
 554                 Assert((this_seg >= 0) && (this_seg <= Highest_segment_index));
 555                 psegs->segnum = this_seg;
 556 //printf("%3i ", this_seg);
 557                 compute_segment_center(&psegs->point,&Segments[this_seg]);
 558                 psegs++;
 559                 l_num_points++;
 560                 #ifdef EDITOR
 561                 // -- Selected_segs[N_selected_segs++] = this_seg;
 562                 #endif
 563
 564                 if (parent_seg == start_seg)
 565                         break;
 566
 567                 while (seg_queue[--qtail].end != parent_seg)
 568                         Assert(qtail >= 0);
 569         }
 570
 571         Assert((start_seg >= 0) && (start_seg <= Highest_segment_index));
 572         psegs->segnum = start_seg;
 573 //printf("%3i\n", start_seg);
 574         compute_segment_center(&psegs->point,&Segments[start_seg]);
 575         psegs++;
 576         l_num_points++;
 577
 578 #if PATH_VALIDATION
 579         validate_path(1, original_psegs, l_num_points);
 580 #endif
 581
 582         //      Now, reverse point_segs in place.
 583         for (i=0; i< l_num_points/2; i++) {
 584                 point_seg               temp_point_seg = *(original_psegs + i);
 585                 *(original_psegs + i) = *(original_psegs + l_num_points - i - 1);
 586                 *(original_psegs + l_num_points - i - 1) = temp_point_seg;
 587         }
 588 #if PATH_VALIDATION
 589         validate_path(2, original_psegs, l_num_points);
 590 #endif
 591
 592         //      Now, if safety_flag set, then insert the point at the center of the side connecting two segments
 593         //      between the two points.  This is messy because we must insert into the list.  The simplest (and not too slow)
 594         //      way to do this is to start at the end of the list and go backwards.
 595         if (safety_flag) {
 596                 if (psegs - Point_segs + l_num_points + 2 > MAX_POINT_SEGS) {
 597                         //      Ouch!  Cannot insert center points in path.  So return unsafe path.
 598 //                      Int3(); // Contact Mike:  This is impossible.
 599 //                      force_dump_ai_objects_all("Error in create_path_points");
 600                         mprintf((0, "Resetting all paths because of safety_flag.\n"));
 601                         ai_reset_all_paths();
 602                         *num_points = l_num_points;
 603                         return -1;
 604                 } else {
 605                         // int  old_num_points = l_num_points;
 606                         insert_center_points(original_psegs, &l_num_points);
 607                         // mprintf((0, "Saved %i/%i points.\n", 2*old_num_points - l_num_points - 1, old_num_points-1));
 608                 }
 609         }
 610
 611 #if PATH_VALIDATION
 612         validate_path(3, original_psegs, l_num_points);
 613 #endif
 614
 615 // -- MK, 10/30/95 -- This code causes apparent discontinuities in the path, moving a point
 616 //      into a new segment.  It is not necessarily bad, but it makes it hard to track down actual
 617 //      discontinuity problems.
 618         if (objp->type == OBJ_ROBOT)
 619                 if (Robot_info[objp->id].companion)
 620                         move_towards_outside(original_psegs, &l_num_points, objp, 0);
 621
 622 #if PATH_VALIDATION
 623         validate_path(4, original_psegs, l_num_points);
 624 #endif
 625
 626         *num_points = l_num_points;
 627         return 0;
 628 }
 629
 630 int     Last_buddy_polish_path_frame;
 631
 632 //      -------------------------------------------------------------------------------------------------------
 633 //      polish_path
 634 //      Takes an existing path and makes it nicer.
 635 //      Drops as many leading points as possible still maintaining direct accessibility
 636 //      from current position to first point.
 637 //      Will not shorten path to fewer than 3 points.
 638 //      Returns number of points.
 639 //      Starting position in psegs doesn't change.
 640 //      Changed, MK, 10/18/95.  I think this was causing robots to get hung up on walls.
 641 //                              Only drop up to the first three points.
 642 int polish_path(object *objp, point_seg *psegs, int num_points)
 643 {
 644         int     i, first_point=0;
 645
 646         if (num_points <= 4)
 647                 return num_points;
 648
 649         //      Prevent the buddy from polishing his path twice in one frame, which can cause him to get hung up.  Pretty ugly, huh?
 650         if (Robot_info[objp->id].companion)
 651         {
 652                 if (FrameCount == Last_buddy_polish_path_frame)
 653                         return num_points;
 654                 else
 655                         Last_buddy_polish_path_frame = FrameCount;
 656         }
 657
 658         // -- MK: 10/18/95: for (i=0; i<num_points-3; i++) {
 659         for (i=0; i<2; i++) {
 660                 fvi_query       fq;
 661                 fvi_info                hit_data;
 662                 int                     hit_type;
 663
 664                 fq.p0                                           = &objp->pos;
 665                 fq.startseg                             = objp->segnum;
 666                 fq.p1                                           = &psegs[i].point;
 667                 fq.rad                                  = objp->size;
 668                 fq.thisobjnum                   = objp-Objects;
 669                 fq.ignore_obj_list      = NULL;
 670                 fq.flags                                        = 0;
 671
 672                 hit_type = find_vector_intersection(&fq, &hit_data);
 673
 674                 if (hit_type == HIT_NONE)
 675                         first_point = i+1;
 676                 else
 677                         break;
 678         }
 679
 680         if (first_point) {
 681                 //      Scrunch down all the psegs.
 682                 for (i=first_point; i<num_points; i++)
 683                         psegs[i-first_point] = psegs[i];
 684         }
 685
 686         return num_points - first_point;
 687 }
 688
 689 #ifndef NDEBUG
 690 //      -------------------------------------------------------------------------------------------------------
 691 //      Make sure that there are connections between all segments on path.
 692 //      Note that if path has been optimized, connections may not be direct, so this function is useless, or worse.
 693 //      Return true if valid, else return false.
 694 int validate_path(int debug_flag, point_seg *psegs, int num_points)
 695 {
 696 #if PATH_VALIDATION
 697         int             i, curseg;
 698
 699         curseg = psegs->segnum;
 700         if ((curseg < 0) || (curseg > Highest_segment_index)) {
 701                 mprintf((0, "Path beginning at index %i, length=%i is bogus!\n", psegs-Point_segs, num_points));
 702                 Int3();         //      Contact Mike: Debug trap for elusive, nasty bug.
 703                 return 0;
 704         }
 705
 706 if (debug_flag == 999)
 707         mprintf((0, "That's curious...\n"));
 708
 709 if (num_points == 0)
 710         return 1;
 711
 712 // printf("(%i) Validating path at psegs=%i, num_points=%i, segments = %3i ", debug_flag, psegs-Point_segs, num_points, psegs[0].segnum);
 713         for (i=1; i<num_points; i++) {
 714                 int     sidenum;
 715                 int     nextseg = psegs[i].segnum;
 716
 717                 if ((nextseg < 0) || (nextseg > Highest_segment_index)) {
 718                         mprintf((0, "Path beginning at index %i, length=%i is bogus!\n", psegs-Point_segs, num_points));
 719                         Int3();         //      Contact Mike: Debug trap for elusive, nasty bug.
 720                         return 0;
 721                 }
 722
 723 // printf("%3i ", nextseg);
 724                 if (curseg != nextseg) {
 725                         for (sidenum=0; sidenum<MAX_SIDES_PER_SEGMENT; sidenum++)
 726                                 if (Segments[curseg].children[sidenum] == nextseg)
 727                                         break;
 728
 729                         // Assert(sidenum != MAX_SIDES_PER_SEGMENT);    //      Hey, created path is not contiguous, why!?
 730                         if (sidenum == MAX_SIDES_PER_SEGMENT) {
 731                                 mprintf((0, "Path beginning at index %i, length=%i is bogus!\n", psegs-Point_segs, num_points));
 732                                 // printf("BOGUS");
 733                                 Int3();
 734                                 return 0;
 735                         }
 736                         curseg = nextseg;
 737                 }
 738         }
 739 //printf("\n");
 740 #endif
 741         return 1;
 742
 743 }
 744 #endif
 745
 746 #ifndef NDEBUG
 747 //      -----------------------------------------------------------------------------------------------------------
 748 void validate_all_paths(void)
 749 {
 750
 751 #if PATH_VALIDATION
 752         int     i;
 753
 754         for (i=0; i<=Highest_object_index; i++) {
 755                 if (Objects[i].type == OBJ_ROBOT) {
 756                         object          *objp = &Objects[i];
 757                         ai_static       *aip = &objp->ctype.ai_info;
 758                         //ai_local              *ailp = &Ai_local_info[i];
 759
 760                         if (objp->control_type == CT_AI) {
 761                                 if ((aip->hide_index != -1) && (aip->path_length > 0))
 762                                         if (!validate_path(4, &Point_segs[aip->hide_index], aip->path_length)) {
 763                                                 Int3(); //      This path is bogus!  Who corrupted it!  Danger! Danger!
 764                                                                         //      Contact Mike, he caused this mess.
 765                                                 //force_dump_ai_objects_all("Error in validate_all_paths");
 766                                                 aip->path_length=0;     //      This allows people to resume without harm...
 767                                         }
 768                         }
 769                 }
 770         }
 771 #endif
 772
 773 }
 774 #endif
 775
 776 // -- //        -------------------------------------------------------------------------------------------------------
 777 // -- //        Creates a path from the objects current segment (objp->segnum) to the specified segment for the object to
 778 // -- //        hide in Ai_local_info[objnum].goal_segment.
 779 // -- //        Sets    objp->ctype.ai_info.hide_index,         a pointer into Point_segs, the first point_seg of the path.
 780 // -- //                        objp->ctype.ai_info.path_length,                length of path
 781 // -- //                        Point_segs_free_ptr                             global pointer into Point_segs array
 782 // -- void create_path(object *objp)
 783 // -- {
 784 // --   ai_static       *aip = &objp->ctype.ai_info;
 785 // --   ai_local                *ailp = &Ai_local_info[objp-Objects];
 786 // --   int                     start_seg, end_seg;
 787 // --
 788 // --   start_seg = objp->segnum;
 789 // --   end_seg = ailp->goal_segment;
 790 // --
 791 // --   if (end_seg == -1)
 792 // --           create_n_segment_path(objp, 3, -1);
 793 // --
 794 // --   if (end_seg == -1) {
 795 // --           ; //mprintf((0, "Object %i, hide_segment = -1, not creating path.\n", objp-Objects));
 796 // --   } else {
 797 // --           create_path_points(objp, start_seg, end_seg, Point_segs_free_ptr, &aip->path_length, -1, 0, 0, -1);
 798 // --           aip->hide_index = Point_segs_free_ptr - Point_segs;
 799 // --           aip->cur_path_index = 0;
 800 // -- #if PATH_VALIDATION
 801 // --           validate_path(5, Point_segs_free_ptr, aip->path_length);
 802 // -- #endif
 803 // --           Point_segs_free_ptr += aip->path_length;
 804 // --           if (Point_segs_free_ptr - Point_segs + MAX_PATH_LENGTH*2 > MAX_POINT_SEGS) {
 805 // --                   //Int3();       //      Contact Mike: This is curious, though not deadly. /eip++;g
 806 // --                   //force_dump_ai_objects_all("Error in create_path");
 807 // --                   ai_reset_all_paths();
 808 // --           }
 809 // --           aip->PATH_DIR = 1;              //      Initialize to moving forward.
 810 // --           aip->SUBMODE = AISM_HIDING;             //      Pretend we are hiding, so we sit here until bothered.
 811 // --   }
 812 // --
 813 // --   maybe_ai_path_garbage_collect();
 814 // --
 815 // -- }
 816
 817 //      -------------------------------------------------------------------------------------------------------
 818 //      Creates a path from the objects current segment (objp->segnum) to the specified segment for the object to
 819 //      hide in Ai_local_info[objnum].goal_segment.
 820 //      Sets    objp->ctype.ai_info.hide_index,         a pointer into Point_segs, the first point_seg of the path.
 821 //                      objp->ctype.ai_info.path_length,                length of path
 822 //                      Point_segs_free_ptr                             global pointer into Point_segs array
 823 //      Change, 10/07/95: Used to create path to ConsoleObject->pos.  Now creates path to Believed_player_pos.
 824 void create_path_to_player(object *objp, int max_length, int safety_flag)
 825 {
 826         ai_static       *aip = &objp->ctype.ai_info;
 827         ai_local                *ailp = &Ai_local_info[objp-Objects];
 828         int                     start_seg, end_seg;
 829
 830 //mprintf((0, "Creating path to player.\n"));
 831         if (max_length == -1)
 832                 max_length = MAX_DEPTH_TO_SEARCH_FOR_PLAYER;
 833
 834         ailp->time_player_seen = GameTime;                      //      Prevent from resetting path quickly.
 835         ailp->goal_segment = Believed_player_seg;
 836
 837         start_seg = objp->segnum;
 838         end_seg = ailp->goal_segment;
 839
 840         // mprintf((0, "Creating path for object #%i, from segment #%i to #%i\n", objp-Objects, start_seg, end_seg));
 841
 842         if (end_seg == -1) {
 843                 ; //mprintf((0, "Object %i, hide_segment = -1, not creating path.\n", objp-Objects));
 844         } else {
 845                 create_path_points(objp, start_seg, end_seg, Point_segs_free_ptr, &aip->path_length, max_length, 1, safety_flag, -1);
 846                 aip->path_length = polish_path(objp, Point_segs_free_ptr, aip->path_length);
 847                 aip->hide_index = Point_segs_free_ptr - Point_segs;
 848                 aip->cur_path_index = 0;
 849                 Point_segs_free_ptr += aip->path_length;
 850                 if (Point_segs_free_ptr - Point_segs + MAX_PATH_LENGTH*2 > MAX_POINT_SEGS) {
 851                         //Int3();       //      Contact Mike: This is stupid.  Should call maybe_ai_garbage_collect before the add.
 852                         //force_dump_ai_objects_all("Error in create_path_to_player");
 853                         ai_reset_all_paths();
 854                         return;
 855                 }
 856 //              Assert(Point_segs_free_ptr - Point_segs + MAX_PATH_LENGTH*2 < MAX_POINT_SEGS);
 857                 aip->PATH_DIR = 1;              //      Initialize to moving forward.
 858                 // -- UNUSED! aip->SUBMODE = AISM_GOHIDE;               //      This forces immediate movement.
 859                 ailp->mode = AIM_FOLLOW_PATH;
 860                 ailp->player_awareness_type = 0;                //      If robot too aware of player, will set mode to chase
 861                 // mprintf((0, "Created %i segment path to player.\n", aip->path_length));
 862         }
 863
 864         maybe_ai_path_garbage_collect();
 865
 866 }
 867
 868 //      -------------------------------------------------------------------------------------------------------
 869 //      Creates a path from the object's current segment (objp->segnum) to segment goalseg.
 870 void create_path_to_segment(object *objp, int goalseg, int max_length, int safety_flag)
 871 {
 872         ai_static       *aip = &objp->ctype.ai_info;
 873         ai_local                *ailp = &Ai_local_info[objp-Objects];
 874         int                     start_seg, end_seg;
 875
 876         if (max_length == -1)
 877                 max_length = MAX_DEPTH_TO_SEARCH_FOR_PLAYER;
 878
 879         ailp->time_player_seen = GameTime;                      //      Prevent from resetting path quickly.
 880         ailp->goal_segment = goalseg;
 881
 882         start_seg = objp->segnum;
 883         end_seg = ailp->goal_segment;
 884
 885         if (end_seg == -1) {
 886                 ;
 887         } else {
 888                 create_path_points(objp, start_seg, end_seg, Point_segs_free_ptr, &aip->path_length, max_length, 1, safety_flag, -1);
 889                 aip->hide_index = Point_segs_free_ptr - Point_segs;
 890                 aip->cur_path_index = 0;
 891                 Point_segs_free_ptr += aip->path_length;
 892                 if (Point_segs_free_ptr - Point_segs + MAX_PATH_LENGTH*2 > MAX_POINT_SEGS) {
 893                         ai_reset_all_paths();
 894                         return;
 895                 }
 896
 897                 aip->PATH_DIR = 1;              //      Initialize to moving forward.
 898                 // -- UNUSED! aip->SUBMODE = AISM_GOHIDE;               //      This forces immediate movement.
 899                 ailp->player_awareness_type = 0;                //      If robot too aware of player, will set mode to chase
 900         }
 901
 902         maybe_ai_path_garbage_collect();
 903
 904 }
 905
 906 //      -------------------------------------------------------------------------------------------------------
 907 //      Creates a path from the objects current segment (objp->segnum) to the specified segment for the object to
 908 //      hide in Ai_local_info[objnum].goal_segment
 909 //      Sets    objp->ctype.ai_info.hide_index,         a pointer into Point_segs, the first point_seg of the path.
 910 //                      objp->ctype.ai_info.path_length,                length of path
 911 //                      Point_segs_free_ptr                             global pointer into Point_segs array
 912 void create_path_to_station(object *objp, int max_length)
 913 {
 914         ai_static       *aip = &objp->ctype.ai_info;
 915         ai_local                *ailp = &Ai_local_info[objp-Objects];
 916         int                     start_seg, end_seg;
 917
 918         if (max_length == -1)
 919                 max_length = MAX_DEPTH_TO_SEARCH_FOR_PLAYER;
 920
 921         ailp->time_player_seen = GameTime;                      //      Prevent from resetting path quickly.
 922
 923         start_seg = objp->segnum;
 924         end_seg = aip->hide_segment;
 925
 926         //1001: mprintf((0, "Back to station for object #%i, from segment #%i to #%i\n", objp-Objects, start_seg, end_seg));
 927
 928         if (end_seg == -1) {
 929                 ; //mprintf((0, "Object %i, hide_segment = -1, not creating path.\n", objp-Objects));
 930         } else {
 931                 create_path_points(objp, start_seg, end_seg, Point_segs_free_ptr, &aip->path_length, max_length, 1, 1, -1);
 932                 aip->path_length = polish_path(objp, Point_segs_free_ptr, aip->path_length);
 933                 aip->hide_index = Point_segs_free_ptr - Point_segs;
 934                 aip->cur_path_index = 0;
 935
 936                 Point_segs_free_ptr += aip->path_length;
 937                 if (Point_segs_free_ptr - Point_segs + MAX_PATH_LENGTH*2 > MAX_POINT_SEGS) {
 938                         //Int3();       //      Contact Mike: Stupid.
 939                         //force_dump_ai_objects_all("Error in create_path_to_station");
 940                         ai_reset_all_paths();
 941                         return;
 942                 }
 943 //              Assert(Point_segs_free_ptr - Point_segs + MAX_PATH_LENGTH*2 < MAX_POINT_SEGS);
 944                 aip->PATH_DIR = 1;              //      Initialize to moving forward.
 945                 // aip->SUBMODE = AISM_GOHIDE;          //      This forces immediate movement.
 946                 ailp->mode = AIM_FOLLOW_PATH;
 947                 ailp->player_awareness_type = 0;
 948         }
 949
 950
 951         maybe_ai_path_garbage_collect();
 952
 953 }
 954
 955
 956 //      -------------------------------------------------------------------------------------------------------
 957 //      Create a path of length path_length for an object, stuffing info in ai_info field.
 958 void create_n_segment_path(object *objp, int path_length, int avoid_seg)
 959 {
 960         ai_static       *aip=&objp->ctype.ai_info;
 961         ai_local                *ailp = &Ai_local_info[objp-Objects];
 962
 963 //mprintf((0, "Creating %i segment path.\n", path_length));
 964
 965         if (create_path_points(objp, objp->segnum, -2, Point_segs_free_ptr, &aip->path_length, path_length, 1, 0, avoid_seg) == -1) {
 966                 Point_segs_free_ptr += aip->path_length;
 967                 while ((create_path_points(objp, objp->segnum, -2, Point_segs_free_ptr, &aip->path_length, --path_length, 1, 0, -1) == -1)) {
 968                         //mprintf((0, "R"));
 969                         Assert(path_length);
 970                 }
 971         }
 972
 973         aip->hide_index = Point_segs_free_ptr - Point_segs;
 974         aip->cur_path_index = 0;
 975 #if PATH_VALIDATION
 976         validate_path(8, Point_segs_free_ptr, aip->path_length);
 977 #endif
 978         Point_segs_free_ptr += aip->path_length;
 979         if (Point_segs_free_ptr - Point_segs + MAX_PATH_LENGTH*2 > MAX_POINT_SEGS) {
 980                 //Int3();       //      Contact Mike: This is curious, though not deadly. /eip++;g
 981                 //force_dump_ai_objects_all("Error in crete_n_segment_path 2");
 982                 ai_reset_all_paths();
 983         }
 984
 985         aip->PATH_DIR = 1;              //      Initialize to moving forward.
 986         // -- UNUSED! aip->SUBMODE = -1;                //      Don't know what this means.
 987         ailp->mode = AIM_FOLLOW_PATH;
 988
 989         //      If this robot is visible (player_visibility is not available) and it's running away, move towards outside with
 990         //      randomness to prevent a stream of bots from going away down the center of a corridor.
 991         if (Ai_local_info[objp-Objects].previous_visibility) {
 992                 if (aip->path_length) {
 993                         int     t_num_points = aip->path_length;
 994                         move_towards_outside(&Point_segs[aip->hide_index], &t_num_points, objp, 1);
 995                         aip->path_length = t_num_points;
 996                 }
 997         }
 998         //mprintf((0, "\n"));
 999
1000         maybe_ai_path_garbage_collect();
1001
1002 }
1003
1004 //      -------------------------------------------------------------------------------------------------------
1005 void create_n_segment_path_to_door(object *objp, int path_length, int avoid_seg)
1006 {
1007         create_n_segment_path(objp, path_length, avoid_seg);
1008 }
1009
1010 extern int Connected_segment_distance;
1011
1012 #define Int3_if(cond) if (!cond) Int3();
1013
1014 //      ----------------------------------------------------------------------------------------------------
1015 void move_object_to_goal(object *objp, vms_vector *goal_point, int goal_seg)
1016 {
1017         ai_static       *aip = &objp->ctype.ai_info;
1018         int                     segnum;
1019
1020         if (aip->path_length < 2)
1021                 return;
1022
1023         Assert(objp->segnum != -1);
1024
1025         // mprintf((0, "[%i -> %i]\n", objp-Objects, goal_seg));
1026
1027 #ifndef NDEBUG
1028         if (objp->segnum != goal_seg)
1029                 if (find_connect_side(&Segments[objp->segnum], &Segments[goal_seg]) == -1) {
1030                         fix     dist;
1031                         dist = find_connected_distance(&objp->pos, objp->segnum, goal_point, goal_seg, 30, WID_FLY_FLAG);
1032                         if (Connected_segment_distance > 2) {   //      This global is set in find_connected_distance
1033                                 // -- Int3();
1034                                 mprintf((1, "Warning: Object %i hopped across %i segments, a distance of %7.3f.\n", objp-Objects, Connected_segment_distance, f2fl(dist)));
1035                         }
1036                 }
1037 #endif
1038
1039         Assert(aip->path_length >= 2);
1040
1041         if (aip->cur_path_index <= 0) {
1042                 if (aip->behavior == AIB_STATION) {
1043                         // mprintf((0, "Object #%i, creating path back to station.\n", objp-Objects));
1044                         create_path_to_station(objp, 15);
1045                         return;
1046                 }
1047                 aip->cur_path_index = 1;
1048                 aip->PATH_DIR = 1;
1049         } else if (aip->cur_path_index >= aip->path_length - 1) {
1050                 if (aip->behavior == AIB_STATION) {
1051                         // mprintf((0, "Object #%i, creating path back to station.\n", objp-Objects));
1052                         create_path_to_station(objp, 15);
1053                         if (aip->path_length == 0) {
1054                                 ai_local                *ailp = &Ai_local_info[objp-Objects];
1055                                 ailp->mode = AIM_STILL;
1056                         }
1057                         return;
1058                 }
1059                 Assert(aip->path_length != 0);
1060                 aip->cur_path_index = aip->path_length-2;
1061                 aip->PATH_DIR = -1;
1062         } else
1063                 aip->cur_path_index += aip->PATH_DIR;
1064
1065         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1066
1067         objp->pos = *goal_point;
1068         segnum = find_object_seg(objp);
1069         if (segnum != goal_seg)
1070                 mprintf((1, "Object #%i goal supposed to be in segment #%i, but in segment #%i\n", objp-Objects, goal_seg, segnum));
1071
1072         if (segnum == -1) {
1073                 Int3(); //      Oops, object is not in any segment.
1074                                         // Contact Mike: This is impossible.
1075                 //      Hack, move object to center of segment it used to be in.
1076                 compute_segment_center(&objp->pos, &Segments[objp->segnum]);
1077         } else
1078                 obj_relink(objp-Objects, segnum);
1079 }
1080
1081 // -- too much work -- //       ----------------------------------------------------------------------------------------------------------
1082 // -- too much work -- //       Return true if the object the companion wants to kill is reachable.
1083 // -- too much work -- int attack_kill_object(object *objp)
1084 // -- too much work -- {
1085 // -- too much work --  object          *kill_objp;
1086 // -- too much work --  fvi_info                hit_data;
1087 // -- too much work --  int                     fate;
1088 // -- too much work --  fvi_query       fq;
1089 // -- too much work --
1090 // -- too much work --  if (Escort_kill_object == -1)
1091 // -- too much work --          return 0;
1092 // -- too much work --
1093 // -- too much work --  kill_objp = &Objects[Escort_kill_object];
1094 // -- too much work --
1095 // -- too much work --  fq.p0                                           = &objp->pos;
1096 // -- too much work --  fq.startseg                             = objp->segnum;
1097 // -- too much work --  fq.p1                                           = &kill_objp->pos;
1098 // -- too much work --  fq.rad                                  = objp->size;
1099 // -- too much work --  fq.thisobjnum                   = objp-Objects;
1100 // -- too much work --  fq.ignore_obj_list      = NULL;
1101 // -- too much work --  fq.flags                                        = 0;
1102 // -- too much work --
1103 // -- too much work --  fate = find_vector_intersection(&fq,&hit_data);
1104 // -- too much work --
1105 // -- too much work --  if (fate == HIT_NONE)
1106 // -- too much work --          return 1;
1107 // -- too much work --  else
1108 // -- too much work --          return 0;
1109 // -- too much work -- }
1110
1111 //      ----------------------------------------------------------------------------------------------------------
1112 //      Optimization: If current velocity will take robot near goal, don't change velocity
1113 void ai_follow_path(object *objp, int player_visibility, int previous_visibility, vms_vector *vec_to_player)
1114 {
1115         ai_static               *aip = &objp->ctype.ai_info;
1116
1117         vms_vector      goal_point, new_goal_point;
1118         fix                     dist_to_goal;
1119         robot_info      *robptr = &Robot_info[objp->id];
1120         int                     forced_break, original_dir, original_index;
1121         fix                     dist_to_player;
1122         int                     goal_seg;
1123         ai_local                *ailp = &Ai_local_info[objp-Objects];
1124         fix                     threshold_distance;
1125
1126
1127 // mprintf((0, "Obj %i, dist=%6.1f index=%i len=%i seg=%i pos = %6.1f %6.1f %6.1f.\n", objp-Objects, f2fl(vm_vec_dist_quick(&objp->pos, &ConsoleObject->pos)), aip->cur_path_index, aip->path_length, objp->segnum, f2fl(objp->pos.x), f2fl(objp->pos.y), f2
1128
1129         if ((aip->hide_index == -1) || (aip->path_length == 0))
1130         {
1131                 if (ailp->mode == AIM_RUN_FROM_OBJECT) {
1132                         create_n_segment_path(objp, 5, -1);
1133                         //--Int3_if((aip->path_length != 0));
1134                         ailp->mode = AIM_RUN_FROM_OBJECT;
1135                 } else {
1136                         // -- mprintf((0, "Object %i creating path for no apparent reason.\n", objp-Objects));
1137                         create_n_segment_path(objp, 5, -1);
1138                         //--Int3_if((aip->path_length != 0));
1139                 }
1140         }
1141
1142         if ((aip->hide_index + aip->path_length > Point_segs_free_ptr - Point_segs) && (aip->path_length>0)) {
1143                 Int3(); //      Contact Mike: Bad.  Path goes into what is believed to be free space.
1144                 //      This is debugging code.  Figure out why garbage collection
1145                 //      didn't compress this object's path information.
1146                 ai_path_garbage_collect();
1147                 //force_dump_ai_objects_all("Error in ai_follow_path");
1148                 ai_reset_all_paths();
1149         }
1150
1151         if (aip->path_length < 2) {
1152                 if ((aip->behavior == AIB_SNIPE) || (ailp->mode == AIM_RUN_FROM_OBJECT)) {
1153                         if (ConsoleObject->segnum == objp->segnum) {
1154                                 create_n_segment_path(objp, AVOID_SEG_LENGTH, -1);                      //      Can't avoid segment player is in, robot is already in it! (That's what the -1 is for)
1155                                 //--Int3_if((aip->path_length != 0));
1156                         } else {
1157                                 create_n_segment_path(objp, AVOID_SEG_LENGTH, ConsoleObject->segnum);
1158                                 //--Int3_if((aip->path_length != 0));
1159                         }
1160                         if (aip->behavior == AIB_SNIPE) {
1161                                 if (robptr->thief)
1162                                         ailp->mode = AIM_THIEF_ATTACK;  //      It gets bashed in create_n_segment_path
1163                                 else
1164                                         ailp->mode = AIM_SNIPE_FIRE;    //      It gets bashed in create_n_segment_path
1165                         } else {
1166                                 ailp->mode = AIM_RUN_FROM_OBJECT;       //      It gets bashed in create_n_segment_path
1167                         }
1168                 } else if (robptr->companion == 0) {
1169                         ailp->mode = AIM_STILL;
1170                         aip->path_length = 0;
1171                         return;
1172                 }
1173         }
1174
1175         //--Int3_if(((aip->PATH_DIR == -1) || (aip->PATH_DIR == 1)));
1176         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1177
1178         goal_point = Point_segs[aip->hide_index + aip->cur_path_index].point;
1179         goal_seg = Point_segs[aip->hide_index + aip->cur_path_index].segnum;
1180         dist_to_goal = vm_vec_dist_quick(&goal_point, &objp->pos);
1181
1182         if (Player_is_dead)
1183                 dist_to_player = vm_vec_dist_quick(&objp->pos, &Viewer->pos);
1184         else
1185                 dist_to_player = vm_vec_dist_quick(&objp->pos, &ConsoleObject->pos);
1186
1187         //      Efficiency hack: If far away from player, move in big quantized jumps.
1188         if (!(player_visibility || previous_visibility) && (dist_to_player > F1_0*200) && !(Game_mode & GM_MULTI)) {
1189                 if (dist_to_goal < F1_0*2) {
1190                         move_object_to_goal(objp, &goal_point, goal_seg);
1191                         return;
1192                 } else {
1193                         robot_info      *robptr = &Robot_info[objp->id];
1194                         fix     cur_speed = robptr->max_speed[Difficulty_level]/2;
1195                         fix     distance_travellable = fixmul(FrameTime, cur_speed);
1196
1197                         // int  connect_side = find_connect_side(objp->segnum, goal_seg);
1198                         //      Only move to goal if allowed to fly through the side.
1199                         //      Buddy-bot can create paths he can't fly, waiting for player.
1200                         // -- bah, this isn't good enough, buddy will fail to get through any door! if (WALL_IS_DOORWAY(&Segments]objp->segnum], connect_side) & WID_FLY_FLAG) {
1201                         if (!Robot_info[objp->id].companion && !Robot_info[objp->id].thief) {
1202                                 if (distance_travellable >= dist_to_goal) {
1203                                         move_object_to_goal(objp, &goal_point, goal_seg);
1204                                 } else {
1205                                         fix     prob = fixdiv(distance_travellable, dist_to_goal);
1206
1207                                         int     rand_num = d_rand();
1208                                         if ( (rand_num >> 1) < prob) {
1209                                                 move_object_to_goal(objp, &goal_point, goal_seg);
1210                                         }
1211                                 }
1212                                 return;
1213                         }
1214                 }
1215
1216         }
1217
1218         //      If running from player, only run until can't be seen.
1219         if (ailp->mode == AIM_RUN_FROM_OBJECT) {
1220                 if ((player_visibility == 0) && (ailp->player_awareness_type == 0)) {
1221                         fix     vel_scale;
1222
1223                         vel_scale = F1_0 - FrameTime/2;
1224                         if (vel_scale < F1_0/2)
1225                                 vel_scale = F1_0/2;
1226
1227                         vm_vec_scale(&objp->mtype.phys_info.velocity, vel_scale);
1228
1229                         return;
1230                 } else if (!(FrameCount ^ ((objp-Objects) & 0x07))) {           //      Done 1/8 frames.
1231                         //      If player on path (beyond point robot is now at), then create a new path.
1232                         point_seg       *curpsp = &Point_segs[aip->hide_index];
1233                         int                     player_segnum = ConsoleObject->segnum;
1234                         int                     i;
1235
1236                         //      This is probably being done every frame, which is wasteful.
1237                         for (i=aip->cur_path_index; i<aip->path_length; i++) {
1238                                 if (curpsp[i].segnum == player_segnum) {
1239                                         if (player_segnum != objp->segnum) {
1240                                                 create_n_segment_path(objp, AVOID_SEG_LENGTH, player_segnum);
1241                                         } else {
1242                                                 create_n_segment_path(objp, AVOID_SEG_LENGTH, -1);
1243                                         }
1244                                         Assert(aip->path_length != 0);
1245                                         ailp->mode = AIM_RUN_FROM_OBJECT;       //      It gets bashed in create_n_segment_path
1246                                         break;
1247                                 }
1248                         }
1249                         if (player_visibility) {
1250                                 ailp->player_awareness_type = 1;
1251                                 ailp->player_awareness_time = F1_0;
1252                         }
1253                 }
1254         }
1255
1256         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1257
1258         if (aip->cur_path_index < 0) {
1259                 aip->cur_path_index = 0;
1260         } else if (aip->cur_path_index >= aip->path_length) {
1261                 if (ailp->mode == AIM_RUN_FROM_OBJECT) {
1262                         create_n_segment_path(objp, AVOID_SEG_LENGTH, ConsoleObject->segnum);
1263                         ailp->mode = AIM_RUN_FROM_OBJECT;       //      It gets bashed in create_n_segment_path
1264                         Assert(aip->path_length != 0);
1265                 } else {
1266                         aip->cur_path_index = aip->path_length-1;
1267                 }
1268         }
1269
1270         goal_point = Point_segs[aip->hide_index + aip->cur_path_index].point;
1271
1272         //      If near goal, pick another goal point.
1273         forced_break = 0;               //      Gets set for short paths.
1274         original_dir = aip->PATH_DIR;
1275         original_index = aip->cur_path_index;
1276         threshold_distance = fixmul(vm_vec_mag_quick(&objp->mtype.phys_info.velocity), FrameTime)*2 + F1_0*2;
1277
1278         new_goal_point = Point_segs[aip->hide_index + aip->cur_path_index].point;
1279
1280         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1281
1282         while ((dist_to_goal < threshold_distance) && !forced_break) {
1283
1284                 //      Advance to next point on path.
1285                 aip->cur_path_index += aip->PATH_DIR;
1286
1287                 //      See if next point wraps past end of path (in either direction), and if so, deal with it based on mode.
1288                 if ((aip->cur_path_index >= aip->path_length) || (aip->cur_path_index < 0)) {
1289
1290                         //mprintf((0, "Object %i reached end of the line!\n", objp-Objects));
1291                         //      If mode = hiding, then stay here until get bonked or hit by player.
1292                         // --   if (ailp->mode == AIM_BEHIND) {
1293                         // --           ailp->mode = AIM_STILL;
1294                         // --           return;         // Stay here until bonked or hit by player.
1295                         // --   } else
1296
1297                         //      Buddy bot.  If he's in mode to get away from player and at end of line,
1298                         //      if player visible, then make a new path, else just return.
1299                         if (robptr->companion) {
1300                                 if (Escort_special_goal == ESCORT_GOAL_SCRAM)
1301                                 {
1302                                         if (player_visibility) {
1303                                                 create_n_segment_path(objp, 16 + d_rand() * 16, -1);
1304                                                 aip->path_length = polish_path(objp, &Point_segs[aip->hide_index], aip->path_length);
1305                                                 Assert(aip->path_length != 0);
1306                                                 // -- mprintf((0, "Buddy: Creating new path!\n"));
1307                                                 ailp->mode = AIM_WANDER;        //      Special buddy mode.
1308                                                 //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1309                                                 return;
1310                                         } else {
1311                                                 ailp->mode = AIM_WANDER;        //      Special buddy mode.
1312                                                 vm_vec_zero(&objp->mtype.phys_info.velocity);
1313                                                 vm_vec_zero(&objp->mtype.phys_info.rotvel);
1314                                                 // -- mprintf((0, "Buddy: I'm hidden!\n"));
1315                                                 //!!Assert((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length));
1316                                                 return;
1317                                         }
1318                                 }
1319                         }
1320
1321                         if (aip->behavior == AIB_FOLLOW) {
1322                                 // mprintf((0, "AIB_FOLLOW: Making new path.\n"));
1323                                 create_n_segment_path(objp, 10, ConsoleObject->segnum);
1324                                 //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1325                         } else if (aip->behavior == AIB_STATION) {
1326                                 // mprintf((0, "Object %i reached end of line, creating path back to station.\n", objp-Objects));
1327                                 create_path_to_station(objp, 15);
1328                                 if ((aip->hide_segment != Point_segs[aip->hide_index+aip->path_length-1].segnum) || (aip->path_length == 0)) {
1329                                         ailp->mode = AIM_STILL;
1330                                 } else {
1331                                         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1332                                 }
1333                                 return;
1334                         } else if (ailp->mode == AIM_FOLLOW_PATH) {
1335                                 create_path_to_player(objp, 10, 1);
1336                                 if (aip->hide_segment != Point_segs[aip->hide_index+aip->path_length-1].segnum) {
1337                                         ailp->mode = AIM_STILL;
1338                                         return;
1339                                 } else {
1340                                         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1341                                 }
1342                         } else if (ailp->mode == AIM_RUN_FROM_OBJECT) {
1343                                 create_n_segment_path(objp, AVOID_SEG_LENGTH, ConsoleObject->segnum);
1344                                 ailp->mode = AIM_RUN_FROM_OBJECT;       //      It gets bashed in create_n_segment_path
1345                                 if (aip->path_length < 1) {
1346                                         create_n_segment_path(objp, AVOID_SEG_LENGTH, ConsoleObject->segnum);
1347                                         ailp->mode = AIM_RUN_FROM_OBJECT;       //      It gets bashed in create_n_segment_path
1348                                         if (aip->path_length < 1) {
1349                                                 aip->behavior = AIB_NORMAL;
1350                                                 ailp->mode = AIM_STILL;
1351                                                 return;
1352                                         }
1353                                 }
1354                                 //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1355                         } else {
1356                                 //      Reached end of the line.  First see if opposite end point is reachable, and if so, go there.
1357                                 //      If not, turn around.
1358                                 int                     opposite_end_index;
1359                                 vms_vector      *opposite_end_point;
1360                                 fvi_info                hit_data;
1361                                 int                     fate;
1362                                 fvi_query       fq;
1363
1364                                 // See which end we're nearer and look at the opposite end point.
1365                                 if (abs(aip->cur_path_index - aip->path_length) < aip->cur_path_index) {
1366                                         //      Nearer to far end (ie, index not 0), so try to reach 0.
1367                                         opposite_end_index = 0;
1368                                 } else {
1369                                         //      Nearer to 0 end, so try to reach far end.
1370                                         opposite_end_index = aip->path_length-1;
1371                                 }
1372
1373                                 //--Int3_if(((opposite_end_index >= 0) && (opposite_end_index < aip->path_length)));
1374
1375                                 opposite_end_point = &Point_segs[aip->hide_index + opposite_end_index].point;
1376
1377                                 fq.p0                                           = &objp->pos;
1378                                 fq.startseg                             = objp->segnum;
1379                                 fq.p1                                           = opposite_end_point;
1380                                 fq.rad                                  = objp->size;
1381                                 fq.thisobjnum                   = objp-Objects;
1382                                 fq.ignore_obj_list      = NULL;
1383                                 fq.flags                                        = 0;                            //what about trans walls???
1384
1385                                 fate = find_vector_intersection(&fq,&hit_data);
1386
1387                                 if (fate != HIT_WALL) {
1388                                         //      We can be circular!  Do it!
1389                                         //      Path direction is unchanged.
1390                                         aip->cur_path_index = opposite_end_index;
1391                                 } else {
1392                                         aip->PATH_DIR = -aip->PATH_DIR;
1393                                         aip->cur_path_index += aip->PATH_DIR;
1394                                 }
1395                                 //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1396                         }
1397                         break;
1398                 } else {
1399                         new_goal_point = Point_segs[aip->hide_index + aip->cur_path_index].point;
1400                         goal_point = new_goal_point;
1401                         dist_to_goal = vm_vec_dist_quick(&goal_point, &objp->pos);
1402                         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1403                 }
1404
1405                 //      If went all the way around to original point, in same direction, then get out of here!
1406                 if ((aip->cur_path_index == original_index) && (aip->PATH_DIR == original_dir)) {
1407                         create_path_to_player(objp, 3, 1);
1408                         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1409                         forced_break = 1;
1410                 }
1411                 //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1412         }       //      end while
1413
1414         //      Set velocity (objp->mtype.phys_info.velocity) and orientation (objp->orient) for this object.
1415         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1416         ai_path_set_orient_and_vel(objp, &goal_point, player_visibility, vec_to_player);
1417         //--Int3_if(((aip->cur_path_index >= 0) && (aip->cur_path_index < aip->path_length)));
1418
1419 }
1420
1421 typedef struct {
1422         short   path_start, objnum;
1423 } obj_path;
1424
1425 int path_index_compare(obj_path *i1, obj_path *i2)
1426 {
1427         if (i1->path_start < i2->path_start)
1428                 return -1;
1429         else if (i1->path_start == i2->path_start)
1430                 return 0;
1431         else
1432                 return 1;
1433 }
1434
1435 //      ----------------------------------------------------------------------------------------------------------
1436 //      Set orientation matrix and velocity for objp based on its desire to get to a point.
1437 void ai_path_set_orient_and_vel(object *objp, vms_vector *goal_point, int player_visibility, vms_vector *vec_to_player)
1438 {
1439         vms_vector      cur_vel = objp->mtype.phys_info.velocity;
1440         vms_vector      norm_cur_vel;
1441         vms_vector      norm_vec_to_goal;
1442         vms_vector      cur_pos = objp->pos;
1443         vms_vector      norm_fvec;
1444         fix                     speed_scale;
1445         fix                     dot;
1446         robot_info      *robptr = &Robot_info[objp->id];
1447         fix                     max_speed;
1448
1449         //      If evading player, use highest difficulty level speed, plus something based on diff level
1450         max_speed = robptr->max_speed[Difficulty_level];
1451         if ((Ai_local_info[objp-Objects].mode == AIM_RUN_FROM_OBJECT) || (objp->ctype.ai_info.behavior == AIB_SNIPE))
1452                 max_speed = max_speed*3/2;
1453
1454         vm_vec_sub(&norm_vec_to_goal, goal_point, &cur_pos);
1455         vm_vec_normalize_quick(&norm_vec_to_goal);
1456
1457         norm_cur_vel = cur_vel;
1458         vm_vec_normalize_quick(&norm_cur_vel);
1459
1460         norm_fvec = objp->orient.fvec;
1461         vm_vec_normalize_quick(&norm_fvec);
1462
1463         dot = vm_vec_dot(&norm_vec_to_goal, &norm_fvec);
1464
1465         //      If very close to facing opposite desired vector, perturb vector
1466         if (dot < -15*F1_0/16) {
1467                 //mprintf((0, "Facing away from goal, abruptly turning\n"));
1468                 norm_cur_vel = norm_vec_to_goal;
1469         } else {
1470                 norm_cur_vel.x += norm_vec_to_goal.x/2;
1471                 norm_cur_vel.y += norm_vec_to_goal.y/2;
1472                 norm_cur_vel.z += norm_vec_to_goal.z/2;
1473         }
1474
1475         vm_vec_normalize_quick(&norm_cur_vel);
1476
1477         //      Set speed based on this robot type's maximum allowed speed and how hard it is turning.
1478         //      How hard it is turning is based on the dot product of (vector to goal) and (current velocity vector)
1479         //      Note that since 3*F1_0/4 is added to dot product, it is possible for the robot to back up.
1480
1481         //      Set speed and orientation.
1482         if (dot < 0)
1483                 dot /= -4;
1484
1485         //      If in snipe mode, can move fast even if not facing that direction.
1486         if (objp->ctype.ai_info.behavior == AIB_SNIPE)
1487                 if (dot < F1_0/2)
1488                         dot = (dot + F1_0)/2;
1489
1490         speed_scale = fixmul(max_speed, dot);
1491         vm_vec_scale(&norm_cur_vel, speed_scale);
1492         objp->mtype.phys_info.velocity = norm_cur_vel;
1493
1494         if ((Ai_local_info[objp-Objects].mode == AIM_RUN_FROM_OBJECT) || (robptr->companion == 1) || (objp->ctype.ai_info.behavior == AIB_SNIPE)) {
1495                 if (Ai_local_info[objp-Objects].mode == AIM_SNIPE_RETREAT_BACKWARDS) {
1496                         if ((player_visibility) && (vec_to_player != NULL))
1497                                 norm_vec_to_goal = *vec_to_player;
1498                         else
1499                                 vm_vec_negate(&norm_vec_to_goal);
1500                 }
1501                 ai_turn_towards_vector(&norm_vec_to_goal, objp, robptr->turn_time[NDL-1]/2);
1502         } else
1503                 ai_turn_towards_vector(&norm_vec_to_goal, objp, robptr->turn_time[Difficulty_level]);
1504
1505 }
1506
1507 int     Last_frame_garbage_collected = 0;
1508
1509 //      ----------------------------------------------------------------------------------------------------------
1510 //      Garbage colledion -- Free all unused records in Point_segs and compress all paths.
1511 void ai_path_garbage_collect(void)
1512 {
1513         int     free_path_index = 0;
1514         int     num_path_objects = 0;
1515         int     objnum;
1516         int     objind;
1517         obj_path                object_list[MAX_OBJECTS];
1518
1519 #ifndef NDEBUG
1520         force_dump_ai_objects_all("***** Start ai_path_garbage_collect *****");
1521 #endif
1522
1523         // -- mprintf((0, "Garbage collection frame %i, last frame %i!  Old free index = %i ", FrameCount, Last_frame_garbage_collected, Point_segs_free_ptr - Point_segs));
1524
1525         Last_frame_garbage_collected = FrameCount;
1526
1527 #if PATH_VALIDATION
1528         validate_all_paths();
1529 #endif
1530         //      Create a list of objects which have paths of length 1 or more.
1531         for (objnum=0; objnum <= Highest_object_index; objnum++) {
1532                 object  *objp = &Objects[objnum];
1533
1534                 if ((objp->type == OBJ_ROBOT) && ((objp->control_type == CT_AI) || (objp->control_type == CT_MORPH))) {
1535                         ai_static       *aip = &objp->ctype.ai_info;
1536
1537                         if (aip->path_length) {
1538                                 object_list[num_path_objects].path_start = aip->hide_index;
1539                                 object_list[num_path_objects++].objnum = objnum;
1540                         }
1541                 }
1542         }
1543
1544         qsort(object_list, num_path_objects, sizeof(object_list[0]),
1545                         (int (*)(void const *,void const *))path_index_compare);
1546
1547         for (objind=0; objind < num_path_objects; objind++) {
1548                 object          *objp;
1549                 ai_static       *aip;
1550                 int                     i;
1551                 int                     old_index;
1552
1553                 objnum = object_list[objind].objnum;
1554                 objp = &Objects[objnum];
1555                 aip = &objp->ctype.ai_info;
1556                 old_index = aip->hide_index;
1557
1558                 aip->hide_index = free_path_index;
1559                 for (i=0; i<aip->path_length; i++)
1560                         Point_segs[free_path_index++] = Point_segs[old_index++];
1561         }
1562
1563         Point_segs_free_ptr = &Point_segs[free_path_index];
1564
1565         // mprintf((0, "new = %i\n", free_path_index));
1566 //printf("After garbage collection, free index = %i\n", Point_segs_free_ptr - Point_segs);
1567 #ifndef NDEBUG
1568         {
1569         int i;
1570
1571         force_dump_ai_objects_all("***** Finish ai_path_garbage_collect *****");
1572
1573         for (i=0; i<=Highest_object_index; i++) {
1574                 ai_static       *aip = &Objects[i].ctype.ai_info;
1575
1576                 if ((Objects[i].type == OBJ_ROBOT) && (Objects[i].control_type == CT_AI))
1577                         if ((aip->hide_index + aip->path_length > Point_segs_free_ptr - Point_segs) && (aip->path_length>0))
1578                                 Int3();         //      Contact Mike: Debug trap for nasty, elusive bug.
1579         }
1580
1581         validate_all_paths();
1582         }
1583 #endif
1584
1585 }
1586
1587 //      -----------------------------------------------------------------------------
1588 //      Do garbage collection if not been done for awhile, or things getting really critical.
1589 void maybe_ai_path_garbage_collect(void)
1590 {
1591         if (Point_segs_free_ptr - Point_segs > MAX_POINT_SEGS - MAX_PATH_LENGTH) {
1592                 if (Last_frame_garbage_collected+1 >= FrameCount) {
1593                         //      This is kind of bad.  Garbage collected last frame or this frame.
1594                         //      Just destroy all paths.  Too bad for the robots.  They are memory wasteful.
1595                         ai_reset_all_paths();
1596                         mprintf((1, "Warning: Resetting all paths.  Point_segs buffer nearly exhausted.\n"));
1597                 } else {
1598                         //      We are really close to full, but didn't just garbage collect, so maybe this is recoverable.
1599                         mprintf((1, "Warning: Almost full garbage collection being performed: "));
1600                         ai_path_garbage_collect();
1601                         mprintf((1, "Free records = %i/%i\n", MAX_POINT_SEGS - (Point_segs_free_ptr - Point_segs), MAX_POINT_SEGS));
1602                 }
1603         } else if (Point_segs_free_ptr - Point_segs > 3*MAX_POINT_SEGS/4) {
1604                 if (Last_frame_garbage_collected + 16 < FrameCount) {
1605                         ai_path_garbage_collect();
1606                 }
1607         } else if (Point_segs_free_ptr - Point_segs > MAX_POINT_SEGS/2) {
1608                 if (Last_frame_garbage_collected + 256 < FrameCount) {
1609                         ai_path_garbage_collect();
1610                 }
1611         }
1612 }
1613
1614 //      -----------------------------------------------------------------------------
1615 //      Reset all paths.  Do garbage collection.
1616 //      Should be called at the start of each level.
1617 void ai_reset_all_paths(void)
1618 {
1619         int     i;
1620
1621         for (i=0; i<=Highest_object_index; i++)
1622                 if (Objects[i].control_type == CT_AI) {
1623                         Objects[i].ctype.ai_info.hide_index = -1;
1624                         Objects[i].ctype.ai_info.path_length = 0;
1625                 }
1626
1627         ai_path_garbage_collect();
1628
1629 }
1630
1631 //      ---------------------------------------------------------------------------------------------------------
1632 //      Probably called because a robot bashed a wall, getting a bunch of retries.
1633 //      Try to resume path.
1634 void attempt_to_resume_path(object *objp)
1635 {
1636         //int                           objnum = objp-Objects;
1637         ai_static               *aip = &objp->ctype.ai_info;
1638 //      int                             goal_segnum, object_segnum,
1639         int                             abs_index, new_path_index;
1640
1641         // mprintf((0, "Object %i trying to resume path at index %i\n", objp-Objects, aip->cur_path_index));
1642
1643         if ((aip->behavior == AIB_STATION) && (Robot_info[objp->id].companion != 1))
1644                 if (d_rand() > 8192) {
1645                         ai_local                        *ailp = &Ai_local_info[objp-Objects];
1646
1647                         aip->hide_segment = objp->segnum;
1648 //Int3();
1649                         ailp->mode = AIM_STILL;
1650                         mprintf((1, "Note: Bashing hide segment of robot %i to current segment because he's lost.\n", objp-Objects));
1651                 }
1652
1653 //      object_segnum = objp->segnum;
1654         abs_index = aip->hide_index+aip->cur_path_index;
1655 //      goal_segnum = Point_segs[abs_index].segnum;
1656
1657 //      if (object_segnum == goal_segnum)
1658 //              mprintf((0, "Very peculiar, goal segnum = object's segnum = %i.\n", goal_segnum));
1659
1660         new_path_index = aip->cur_path_index - aip->PATH_DIR;
1661
1662         if ((new_path_index >= 0) && (new_path_index < aip->path_length)) {
1663                 // mprintf((0, "Trying path index of %i\n", new_path_index));
1664                 aip->cur_path_index = new_path_index;
1665         } else {
1666                 //      At end of line and have nowhere to go.
1667                 // mprintf((0, "At end of line and can't get to goal.  Creating new path.  Frame %i\n", FrameCount));
1668                 move_towards_segment_center(objp);
1669                 create_path_to_station(objp, 15);
1670         }
1671
1672 }
1673
1674 //      ----------------------------------------------------------------------------------------------------------
1675 //                                      DEBUG FUNCTIONS FOLLOW
1676 //      ----------------------------------------------------------------------------------------------------------
1677
1678 #ifdef EDITOR
1679 int     Test_size = 1000;
1680
1681 void test_create_path_many(void)
1682 {
1683         point_seg       point_segs[200];
1684         short                   num_points;
1685
1686         int                     i;
1687
1688         for (i=0; i<Test_size; i++) {
1689                 Cursegp = &Segments[(d_rand() * (Highest_segment_index + 1)) / D_RAND_MAX];
1690                 Markedsegp = &Segments[(d_rand() * (Highest_segment_index + 1)) / D_RAND_MAX];
1691                 create_path_points(&Objects[0], Cursegp-Segments, Markedsegp-Segments, point_segs, &num_points, -1, 0, 0, -1);
1692         }
1693
1694 }
1695
1696 void test_create_path(void)
1697 {
1698         point_seg       point_segs[200];
1699         short                   num_points;
1700
1701         create_path_points(&Objects[0], Cursegp-Segments, Markedsegp-Segments, point_segs, &num_points, -1, 0, 0, -1);
1702
1703 }
1704
1705 void show_path(int start_seg, int end_seg, point_seg *psp, short length)
1706 {
1707         printf("[%3i:%3i (%3i):] ", start_seg, end_seg, length);
1708
1709         while (length--)
1710                 printf("%3i ", psp[length].segnum);
1711
1712         printf("\n");
1713 }
1714
1715 //      For all segments in mine, create paths to all segments in mine, print results.
1716 void test_create_all_paths(void)
1717 {
1718         int     start_seg, end_seg;
1719         short   resultant_length;
1720
1721         Point_segs_free_ptr = Point_segs;
1722
1723         for (start_seg=0; start_seg<=Highest_segment_index-1; start_seg++) {
1724                 // -- mprintf((0, "."));
1725                 if (Segments[start_seg].segnum != -1) {
1726                         for (end_seg=start_seg+1; end_seg<=Highest_segment_index; end_seg++) {
1727                                 if (Segments[end_seg].segnum != -1) {
1728                                         create_path_points(&Objects[0], start_seg, end_seg, Point_segs_free_ptr, &resultant_length, -1, 0, 0, -1);
1729                                         show_path(start_seg, end_seg, Point_segs_free_ptr, resultant_length);
1730                                 }
1731                         }
1732                 }
1733         }
1734 }
1735
1736 //--anchor--int Num_anchors;
1737 //--anchor--int Anchor_distance = 3;
1738 //--anchor--int End_distance = 1;
1739 //--anchor--int Anchors[MAX_SEGMENTS];
1740
1741 //--anchor--int get_nearest_anchor_distance(int segnum)
1742 //--anchor--{
1743 //--anchor--    short   resultant_length, minimum_length;
1744 //--anchor--    int     anchor_index;
1745 //--anchor--
1746 //--anchor--    minimum_length = 16383;
1747 //--anchor--
1748 //--anchor--    for (anchor_index=0; anchor_index<Num_anchors; anchor_index++) {
1749 //--anchor--            create_path_points(&Objects[0], segnum, Anchors[anchor_index], Point_segs_free_ptr, &resultant_length, -1, 0, 0, -1);
1750 //--anchor--            if (resultant_length != 0)
1751 //--anchor--                    if (resultant_length < minimum_length)
1752 //--anchor--                            minimum_length = resultant_length;
1753 //--anchor--    }
1754 //--anchor--
1755 //--anchor--    return minimum_length;
1756 //--anchor--
1757 //--anchor--}
1758 //--anchor--
1759 //--anchor--void create_new_anchor(int segnum)
1760 //--anchor--{
1761 //--anchor--    Anchors[Num_anchors++] = segnum;
1762 //--anchor--}
1763 //--anchor--
1764 //--anchor--//  A set of anchors is within N units of all segments in the graph.
1765 //--anchor--//  Anchor_distance = how close anchors can be.
1766 //--anchor--//  End_distance = how close you can be to the end.
1767 //--anchor--void test_create_all_anchors(void)
1768 //--anchor--{
1769 //--anchor--    int     nearest_anchor_distance;
1770 //--anchor--    int     segnum,i;
1771 //--anchor--
1772 //--anchor--    Num_anchors = 0;
1773 //--anchor--
1774 //--anchor--    for (segnum=0; segnum<=Highest_segment_index; segnum++) {
1775 //--anchor--            if (Segments[segnum].segnum != -1) {
1776 //--anchor--                    nearest_anchor_distance = get_nearest_anchor_distance(segnum);
1777 //--anchor--                    if (nearest_anchor_distance > Anchor_distance)
1778 //--anchor--                            create_new_anchor(segnum);
1779 //--anchor--            }
1780 //--anchor--    }
1781 //--anchor--
1782 //--anchor--    //      Set selected segs.
1783 //--anchor--    for (i=0; i<Num_anchors; i++)
1784 //--anchor--            Selected_segs[i] = Anchors[i];
1785 //--anchor--    N_selected_segs = Num_anchors;
1786 //--anchor--
1787 //--anchor--}
1788 //--anchor--
1789 //--anchor--int Test_path_length = 5;
1790 //--anchor--
1791 //--anchor--void test_create_n_segment_path(void)
1792 //--anchor--{
1793 //--anchor--    point_seg       point_segs[200];
1794 //--anchor--    short                   num_points;
1795 //--anchor--
1796 //--anchor--    create_path_points(&Objects[0], Cursegp-Segments, -2, point_segs, &num_points, Test_path_length, 0, 0, -1);
1797 //--anchor--}
1798
1799 short   Player_path_length=0;
1800 int     Player_hide_index=-1;
1801 int     Player_cur_path_index=0;
1802 int     Player_following_path_flag=0;
1803
1804 //      ------------------------------------------------------------------------------------------------------------------
1805 //      Set orientation matrix and velocity for objp based on its desire to get to a point.
1806 void player_path_set_orient_and_vel(object *objp, vms_vector *goal_point)
1807 {
1808         vms_vector      cur_vel = objp->mtype.phys_info.velocity;
1809         vms_vector      norm_cur_vel;
1810         vms_vector      norm_vec_to_goal;
1811         vms_vector      cur_pos = objp->pos;
1812         vms_vector      norm_fvec;
1813         fix                     speed_scale;
1814         fix                     dot;
1815         fix                     max_speed;
1816
1817         max_speed = Robot_info[objp->id].max_speed[Difficulty_level];
1818
1819         vm_vec_sub(&norm_vec_to_goal, goal_point, &cur_pos);
1820         vm_vec_normalize_quick(&norm_vec_to_goal);
1821
1822         norm_cur_vel = cur_vel;
1823         vm_vec_normalize_quick(&norm_cur_vel);
1824
1825         norm_fvec = objp->orient.fvec;
1826         vm_vec_normalize_quick(&norm_fvec);
1827
1828         dot = vm_vec_dot(&norm_vec_to_goal, &norm_fvec);
1829         if (Ai_local_info[objp-Objects].mode == AIM_SNIPE_RETREAT_BACKWARDS) {
1830                 dot = -dot;
1831         }
1832
1833         //      If very close to facing opposite desired vector, perturb vector
1834         if (dot < -15*F1_0/16) {
1835                 //mprintf((0, "Facing away from goal, abruptly turning\n"));
1836                 norm_cur_vel = norm_vec_to_goal;
1837         } else {
1838                 norm_cur_vel.x += norm_vec_to_goal.x/2;
1839                 norm_cur_vel.y += norm_vec_to_goal.y/2;
1840                 norm_cur_vel.z += norm_vec_to_goal.z/2;
1841         }
1842
1843         vm_vec_normalize_quick(&norm_cur_vel);
1844
1845         //      Set speed based on this robot type's maximum allowed speed and how hard it is turning.
1846         //      How hard it is turning is based on the dot product of (vector to goal) and (current velocity vector)
1847         //      Note that since 3*F1_0/4 is added to dot product, it is possible for the robot to back up.
1848
1849         //      Set speed and orientation.
1850         if (dot < 0)
1851                 dot /= 4;
1852
1853         speed_scale = fixmul(max_speed, dot);
1854         vm_vec_scale(&norm_cur_vel, speed_scale);
1855         objp->mtype.phys_info.velocity = norm_cur_vel;
1856         ai_turn_towards_vector(&norm_vec_to_goal, objp, F1_0);
1857
1858 }
1859
1860 //      ----------------------------------------------------------------------------------------------------------
1861 //      Optimization: If current velocity will take robot near goal, don't change velocity
1862 void player_follow_path(object *objp)
1863 {
1864         vms_vector      goal_point;
1865         fix                     dist_to_goal;
1866         int                     count, forced_break, original_index;
1867         int                     goal_seg;
1868         fix                     threshold_distance;
1869
1870         if (!Player_following_path_flag)
1871                 return;
1872
1873         if (Player_hide_index == -1)
1874                 return;
1875
1876         if (Player_path_length < 2)
1877                 return;
1878
1879         goal_point = Point_segs[Player_hide_index + Player_cur_path_index].point;
1880         goal_seg = Point_segs[Player_hide_index + Player_cur_path_index].segnum;
1881         Assert((goal_seg >= 0) && (goal_seg <= Highest_segment_index));
1882         dist_to_goal = vm_vec_dist_quick(&goal_point, &objp->pos);
1883
1884         if (Player_cur_path_index < 0)
1885                 Player_cur_path_index = 0;
1886         else if (Player_cur_path_index >= Player_path_length)
1887                 Player_cur_path_index = Player_path_length-1;
1888
1889         goal_point = Point_segs[Player_hide_index + Player_cur_path_index].point;
1890
1891         count=0;
1892
1893         //      If near goal, pick another goal point.
1894         forced_break = 0;               //      Gets set for short paths.
1895         //original_dir = 1;
1896         original_index = Player_cur_path_index;
1897         threshold_distance = fixmul(vm_vec_mag_quick(&objp->mtype.phys_info.velocity), FrameTime)*2 + F1_0*2;
1898
1899         while ((dist_to_goal < threshold_distance) && !forced_break) {
1900
1901 // --           if (count > 1)
1902 // --                   mprintf((0, "."));
1903
1904                 //      ----- Debug stuff -----
1905                 if (count++ > 20) {
1906                         mprintf((1,"Problem following path for player.  Aborting.\n"));
1907                         break;
1908                 }
1909
1910                 //      Advance to next point on path.
1911                 Player_cur_path_index += 1;
1912
1913                 //      See if next point wraps past end of path (in either direction), and if so, deal with it based on mode.
1914                 if ((Player_cur_path_index >= Player_path_length) || (Player_cur_path_index < 0)) {
1915                         Player_following_path_flag = 0;
1916                         forced_break = 1;
1917                 }
1918
1919                 //      If went all the way around to original point, in same direction, then get out of here!
1920                 if (Player_cur_path_index == original_index) {
1921                         mprintf((0, "Forcing break because player path wrapped, count = %i.\n", count));
1922                         Player_following_path_flag = 0;
1923                         forced_break = 1;
1924                 }
1925
1926                 goal_point = Point_segs[Player_hide_index + Player_cur_path_index].point;
1927                 dist_to_goal = vm_vec_dist_quick(&goal_point, &objp->pos);
1928
1929         }       //      end while
1930
1931         //      Set velocity (objp->mtype.phys_info.velocity) and orientation (objp->orient) for this object.
1932         player_path_set_orient_and_vel(objp, &goal_point);
1933
1934 }
1935
1936
1937 //      ------------------------------------------------------------------------------------------------------------------
1938 //      Create path for player from current segment to goal segment.
1939 void create_player_path_to_segment(int segnum)
1940 {
1941         object          *objp = ConsoleObject;
1942
1943         Player_path_length=0;
1944         Player_hide_index=-1;
1945         Player_cur_path_index=0;
1946         Player_following_path_flag=0;
1947
1948         if (create_path_points(objp, objp->segnum, segnum, Point_segs_free_ptr, &Player_path_length, 100, 0, 0, -1) == -1)
1949                 mprintf((0, "Unable to form path of length %i for myself\n", 100));
1950
1951         Player_following_path_flag = 1;
1952
1953         Player_hide_index = Point_segs_free_ptr - Point_segs;
1954         Player_cur_path_index = 0;
1955         Point_segs_free_ptr += Player_path_length;
1956         if (Point_segs_free_ptr - Point_segs + MAX_PATH_LENGTH*2 > MAX_POINT_SEGS) {
1957                 //Int3();       //      Contact Mike: This is curious, though not deadly. /eip++;g
1958                 ai_reset_all_paths();
1959         }
1960
1961 }
1962
1963 int     Player_goal_segment = -1;
1964
1965 void check_create_player_path(void)
1966 {
1967         if (Player_goal_segment != -1)
1968                 create_player_path_to_segment(Player_goal_segment);
1969
1970         Player_goal_segment = -1;
1971 }
1972
1973 #endif
1974
1975 //      ----------------------------------------------------------------------------------------------------------
1976 //                                      DEBUG FUNCTIONS ENDED
1977 //      ----------------------------------------------------------------------------------------------------------
1978