main/aipath.c

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