base/p_maputl.c

   1
   2 //**************************************************************************
   3 //**
   4 //** p_maputl.c : Heretic 2 : Raven Software, Corp.
   5 //**
   6 //** $RCSfile$
   7 //** $Revision$
   8 //** $Date$
   9 //** $Author$
  10 //**
  11 //**************************************************************************
  12
  13 #include "h2def.h"
  14 #include "p_local.h"
  15
  16 static mobj_t *RoughBlockCheck(mobj_t *mo, int index);
  17
  18 /*
  19 ===================
  20 =
  21 = P_AproxDistance
  22 =
  23 = Gives an estimation of distance (not exact)
  24 =
  25 ===================
  26 */
  27
  28 fixed_t P_AproxDistance (fixed_t dx, fixed_t dy)
  29 {
  30         dx = abs(dx);
  31         dy = abs(dy);
  32         if (dx < dy)
  33                 return dx+dy-(dx>>1);
  34         return dx+dy-(dy>>1);
  35 }
  36
  37
  38 /*
  39 ==================
  40 =
  41 = P_PointOnLineSide
  42 =
  43 = Returns 0 or 1
  44 ==================
  45 */
  46
  47 int P_PointOnLineSide (fixed_t x, fixed_t y, line_t *line)
  48 {
  49         fixed_t dx,dy;
  50         fixed_t left, right;
  51
  52         if (!line->dx)
  53         {
  54                 if (x <= line->v1->x)
  55                         return line->dy > 0;
  56                 return line->dy < 0;
  57         }
  58         if (!line->dy)
  59         {
  60                 if (y <= line->v1->y)
  61                         return line->dx < 0;
  62                 return line->dx > 0;
  63         }
  64
  65         dx = (x - line->v1->x);
  66         dy = (y - line->v1->y);
  67
  68         left = FixedMul ( line->dy>>FRACBITS , dx );
  69         right = FixedMul ( dy , line->dx>>FRACBITS );
  70
  71         if (right < left)
  72                 return 0;               // front side
  73         return 1;                       // back side
  74 }
  75
  76
  77 /*
  78 =================
  79 =
  80 = P_BoxOnLineSide
  81 =
  82 = Considers the line to be infinite
  83 = Returns side 0 or 1, -1 if box crosses the line
  84 =================
  85 */
  86
  87 int P_BoxOnLineSide (fixed_t *tmbox, line_t *ld)
  88 {
  89         int             p1 = 0, p2 = 0; /* jim initialisers added */
  90
  91         switch (ld->slopetype)
  92         {
  93         case ST_HORIZONTAL:
  94                 p1 = tmbox[BOXTOP] > ld->v1->y;
  95                 p2 = tmbox[BOXBOTTOM] > ld->v1->y;
  96                 if (ld->dx < 0)
  97                 {
  98                         p1 ^= 1;
  99                         p2 ^= 1;
 100                 }
 101                 break;
 102         case ST_VERTICAL:
 103                 p1 = tmbox[BOXRIGHT] < ld->v1->x;
 104                 p2 = tmbox[BOXLEFT] < ld->v1->x;
 105                 if (ld->dy < 0)
 106                 {
 107                         p1 ^= 1;
 108                         p2 ^= 1;
 109                 }
 110                 break;
 111         case ST_POSITIVE:
 112                 p1 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXTOP], ld);
 113                 p2 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld);
 114                 break;
 115         case ST_NEGATIVE:
 116                 p1 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXTOP], ld);
 117                 p2 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld);
 118                 break;
 119         }
 120
 121         if (p1 == p2)
 122                 return p1;
 123         return -1;
 124 }
 125
 126 /*
 127 ==================
 128 =
 129 = P_PointOnDivlineSide
 130 =
 131 = Returns 0 or 1
 132 ==================
 133 */
 134
 135 int P_PointOnDivlineSide (fixed_t x, fixed_t y, divline_t *line)
 136 {
 137         fixed_t dx,dy;
 138         fixed_t left, right;
 139
 140         if (!line->dx)
 141         {
 142                 if (x <= line->x)
 143                         return line->dy > 0;
 144                 return line->dy < 0;
 145         }
 146         if (!line->dy)
 147         {
 148                 if (y <= line->y)
 149                         return line->dx < 0;
 150                 return line->dx > 0;
 151         }
 152
 153         dx = (x - line->x);
 154         dy = (y - line->y);
 155
 156 // try to quickly decide by looking at sign bits
 157         if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
 158         {
 159                 if ( (line->dy ^ dx) & 0x80000000 )
 160                         return 1;       // (left is negative)
 161                 return 0;
 162         }
 163
 164         left = FixedMul ( line->dy>>8, dx>>8 );
 165         right = FixedMul ( dy>>8 , line->dx>>8 );
 166
 167         if (right < left)
 168                 return 0;               // front side
 169         return 1;                       // back side
 170 }
 171
 172
 173
 174 /*
 175 ==============
 176 =
 177 = P_MakeDivline
 178 =
 179 ==============
 180 */
 181
 182 void P_MakeDivline (line_t *li, divline_t *dl)
 183 {
 184         dl->x = li->v1->x;
 185         dl->y = li->v1->y;
 186         dl->dx = li->dx;
 187         dl->dy = li->dy;
 188 }
 189
 190
 191 /*
 192 ===============
 193 =
 194 = P_InterceptVector
 195 =
 196 = Returns the fractional intercept point along the first divline
 197 =
 198 = This is only called by the addthings and addlines traversers
 199 ===============
 200 */
 201
 202 fixed_t P_InterceptVector (divline_t *v2, divline_t *v1)
 203 {
 204 #if 1
 205         fixed_t frac, num, den;
 206
 207         den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
 208         if (den == 0)
 209                 return 0;
 210 //              I_Error ("P_InterceptVector: parallel");
 211         num = FixedMul ( (v1->x - v2->x)>>8 ,v1->dy) +
 212                 FixedMul ( (v2->y - v1->y)>>8 , v1->dx);
 213         frac = FixedDiv (num , den);
 214
 215         return frac;
 216 #else
 217 float   frac, num, den, v1x,v1y,v1dx,v1dy,v2x,v2y,v2dx,v2dy;
 218
 219         v1x = (float)v1->x/FRACUNIT;
 220         v1y = (float)v1->y/FRACUNIT;
 221         v1dx = (float)v1->dx/FRACUNIT;
 222         v1dy = (float)v1->dy/FRACUNIT;
 223         v2x = (float)v2->x/FRACUNIT;
 224         v2y = (float)v2->y/FRACUNIT;
 225         v2dx = (float)v2->dx/FRACUNIT;
 226         v2dy = (float)v2->dy/FRACUNIT;
 227
 228         den = v1dy*v2dx - v1dx*v2dy;
 229         if (den == 0)
 230                 return 0;       // parallel
 231         num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx;
 232         frac = num / den;
 233
 234         return frac*FRACUNIT;
 235 #endif
 236 }
 237
 238 /*
 239 ==================
 240 =
 241 = P_LineOpening
 242 =
 243 = Sets opentop and openbottom to the window through a two sided line
 244 = OPTIMIZE: keep this precalculated
 245 ==================
 246 */
 247
 248 fixed_t opentop, openbottom, openrange;
 249 fixed_t lowfloor;
 250
 251 void P_LineOpening (line_t *linedef)
 252 {
 253         sector_t        *front, *back;
 254
 255         if (linedef->sidenum[1] == -1)
 256         {       // single sided line
 257                 openrange = 0;
 258                 return;
 259         }
 260
 261         front = linedef->frontsector;
 262         back = linedef->backsector;
 263
 264         if (front->ceilingheight < back->ceilingheight)
 265                 opentop = front->ceilingheight;
 266         else
 267                 opentop = back->ceilingheight;
 268         if (front->floorheight > back->floorheight)
 269         {
 270                 openbottom = front->floorheight;
 271                 lowfloor = back->floorheight;
 272                 tmfloorpic = front->floorpic;
 273         }
 274         else
 275         {
 276                 openbottom = back->floorheight;
 277                 lowfloor = front->floorheight;
 278                 tmfloorpic = back->floorpic;
 279         }
 280
 281         openrange = opentop - openbottom;
 282 }
 283
 284 /*
 285 ===============================================================================
 286
 287                                                 THING POSITION SETTING
 288
 289 ===============================================================================
 290 */
 291
 292 /*
 293 ===================
 294 =
 295 = P_UnsetThingPosition
 296 =
 297 = Unlinks a thing from block map and sectors
 298 =
 299 ===================
 300 */
 301
 302 void P_UnsetThingPosition (mobj_t *thing)
 303 {
 304         int                             blockx, blocky;
 305
 306         if ( ! (thing->flags & MF_NOSECTOR) )
 307         {       // inert things don't need to be in blockmap
 308 // unlink from subsector
 309                 if (thing->snext)
 310                         thing->snext->sprev = thing->sprev;
 311                 if (thing->sprev)
 312                         thing->sprev->snext = thing->snext;
 313                 else
 314                         thing->subsector->sector->thinglist = thing->snext;
 315         }
 316
 317         if ( ! (thing->flags & MF_NOBLOCKMAP) )
 318         {       // inert things don't need to be in blockmap
 319 // unlink from block map
 320                 if (thing->bnext)
 321                         thing->bnext->bprev = thing->bprev;
 322                 if (thing->bprev)
 323                         thing->bprev->bnext = thing->bnext;
 324                 else
 325                 {
 326                         blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
 327                         blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
 328                         if (blockx>=0 && blockx < bmapwidth
 329                         && blocky>=0 && blocky <bmapheight)
 330                         blocklinks[blocky*bmapwidth+blockx] = thing->bnext;
 331                 }
 332         }
 333 }
 334
 335
 336 /*
 337 ===================
 338 =
 339 = P_SetThingPosition
 340 =
 341 = Links a thing into both a block and a subsector based on it's x y
 342 = Sets thing->subsector properly
 343 =
 344 ===================
 345 */
 346
 347 void P_SetThingPosition (mobj_t *thing)
 348 {
 349         subsector_t             *ss;
 350         sector_t                *sec;
 351         int                             blockx, blocky;
 352         mobj_t                  **link;
 353
 354 //
 355 // link into subsector
 356 //
 357         ss = R_PointInSubsector (thing->x,thing->y);
 358         thing->subsector = ss;
 359         if ( ! (thing->flags & MF_NOSECTOR) )
 360         {       // invisible things don't go into the sector links
 361                 sec = ss->sector;
 362
 363                 thing->sprev = NULL;
 364                 thing->snext = sec->thinglist;
 365                 if (sec->thinglist)
 366                         sec->thinglist->sprev = thing;
 367                 sec->thinglist = thing;
 368         }
 369
 370 //
 371 // link into blockmap
 372 //
 373         if ( ! (thing->flags & MF_NOBLOCKMAP) )
 374         {       // inert things don't need to be in blockmap
 375                 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
 376                 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
 377                 if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky <bmapheight)
 378                 {
 379                         link = &blocklinks[blocky*bmapwidth+blockx];
 380                         thing->bprev = NULL;
 381                         thing->bnext = *link;
 382                         if (*link)
 383                                 (*link)->bprev = thing;
 384                         *link = thing;
 385                 }
 386                 else
 387                 {       // thing is off the map
 388                         thing->bnext = thing->bprev = NULL;
 389                 }
 390         }
 391 }
 392
 393
 394
 395 /*
 396 ===============================================================================
 397
 398                                                 BLOCK MAP ITERATORS
 399
 400 For each line/thing in the given mapblock, call the passed function.
 401 If the function returns false, exit with false without checking anything else.
 402
 403 ===============================================================================
 404 */
 405
 406 /*
 407 ==================
 408 =
 409 = P_BlockLinesIterator
 410 =
 411 = The validcount flags are used to avoid checking lines
 412 = that are marked in multiple mapblocks, so increment validcount before
 413 = the first call to P_BlockLinesIterator, then make one or more calls to it
 414 ===================
 415 */
 416
 417 boolean P_BlockLinesIterator (int x, int y, boolean(*func)(line_t*) )
 418 {
 419         int                     offset;
 420         short           *list;
 421         line_t          *ld;
 422
 423         int i;
 424         polyblock_t *polyLink;
 425         seg_t **tempSeg;
 426         extern polyblock_t **PolyBlockMap;
 427
 428         if (x < 0 || y<0 || x>=bmapwidth || y>=bmapheight)
 429                 return true;
 430         offset = y*bmapwidth+x;
 431
 432         polyLink = PolyBlockMap[offset];
 433         while(polyLink)
 434         {
 435                 if(polyLink->polyobj)
 436                 {
 437                         if(polyLink->polyobj->validcount != validcount)
 438                         {
 439                                 polyLink->polyobj->validcount = validcount;
 440                                 tempSeg = polyLink->polyobj->segs;
 441                                 for(i = 0; i < polyLink->polyobj->numsegs; i++, tempSeg++)
 442                                 {
 443                                         if((*tempSeg)->linedef->validcount == validcount)
 444                                         {
 445                                                 continue;
 446                                         }
 447                                         (*tempSeg)->linedef->validcount = validcount;
 448                                         if(!func((*tempSeg)->linedef))
 449                                         {
 450                                                 return false;
 451                                         }
 452                                 }
 453                         }
 454                 }
 455                 polyLink = polyLink->next;
 456         }
 457
 458         offset = *(blockmap+offset);
 459
 460         for ( list = blockmaplump+offset ; *list != -1 ; list++)
 461         {
 462                 ld = &lines[*list];
 463                 if (ld->validcount == validcount)
 464                         continue;               // line has already been checked
 465                 ld->validcount = validcount;
 466
 467                 if ( !func(ld) )
 468                         return false;
 469         }
 470
 471         return true;            // everything was checked
 472 }
 473
 474
 475 /*
 476 ==================
 477 =
 478 = P_BlockThingsIterator
 479 =
 480 ==================
 481 */
 482
 483 boolean P_BlockThingsIterator (int x, int y, boolean(*func)(mobj_t*) )
 484 {
 485         mobj_t          *mobj;
 486
 487         if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
 488                 return true;
 489
 490         for (mobj = blocklinks[y*bmapwidth+x] ; mobj ; mobj = mobj->bnext)
 491                 if (!func( mobj ) )
 492                         return false;
 493
 494         return true;
 495 }
 496
 497 /*
 498 ===============================================================================
 499
 500                                         INTERCEPT ROUTINES
 501
 502 ===============================================================================
 503 */
 504
 505 intercept_t             intercepts[MAXINTERCEPTS], *intercept_p;
 506
 507 divline_t       trace;
 508 boolean         earlyout;
 509 int                     ptflags;
 510
 511 /*
 512 ==================
 513 =
 514 = PIT_AddLineIntercepts
 515 =
 516 = Looks for lines in the given block that intercept the given trace
 517 = to add to the intercepts list
 518 = A line is crossed if its endpoints are on opposite sides of the trace
 519 = Returns true if earlyout and a solid line hit
 520 ==================
 521 */
 522
 523 boolean PIT_AddLineIntercepts (line_t *ld)
 524 {
 525         int                     s1, s2;
 526         fixed_t         frac;
 527         divline_t       dl;
 528
 529 // avoid precision problems with two routines
 530         if ( trace.dx > FRACUNIT*16 || trace.dy > FRACUNIT*16
 531         || trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16)
 532         {
 533                 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
 534                 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
 535         }
 536         else
 537         {
 538                 s1 = P_PointOnLineSide (trace.x, trace.y, ld);
 539                 s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
 540         }
 541         if (s1 == s2)
 542                 return true;            // line isn't crossed
 543
 544 //
 545 // hit the line
 546 //
 547         P_MakeDivline (ld, &dl);
 548         frac = P_InterceptVector (&trace, &dl);
 549         if (frac < 0)
 550                 return true;            // behind source
 551
 552 // try to early out the check
 553         if (earlyout && frac < FRACUNIT && !ld->backsector)
 554                 return false;   // stop checking
 555
 556         intercept_p->frac = frac;
 557         intercept_p->isaline = true;
 558         intercept_p->d.line = ld;
 559         intercept_p++;
 560
 561         return true;            // continue
 562 }
 563
 564
 565
 566 /*
 567 ==================
 568 =
 569 = PIT_AddThingIntercepts
 570 =
 571 ==================
 572 */
 573
 574 boolean PIT_AddThingIntercepts (mobj_t  *thing)
 575 {
 576         fixed_t         x1,y1, x2,y2;
 577         int                     s1, s2;
 578         boolean         tracepositive;
 579         divline_t       dl;
 580         fixed_t         frac;
 581
 582         tracepositive = (trace.dx ^ trace.dy)>0;
 583
 584         // check a corner to corner crossection for hit
 585
 586         if (tracepositive)
 587         {
 588                 x1 = thing->x - thing->radius;
 589                 y1 = thing->y + thing->radius;
 590
 591                 x2 = thing->x + thing->radius;
 592                 y2 = thing->y - thing->radius;
 593         }
 594         else
 595         {
 596                 x1 = thing->x - thing->radius;
 597                 y1 = thing->y - thing->radius;
 598
 599                 x2 = thing->x + thing->radius;
 600                 y2 = thing->y + thing->radius;
 601         }
 602         s1 = P_PointOnDivlineSide (x1, y1, &trace);
 603         s2 = P_PointOnDivlineSide (x2, y2, &trace);
 604         if (s1 == s2)
 605                 return true;    // line isn't crossed
 606
 607         dl.x = x1;
 608         dl.y = y1;
 609         dl.dx = x2-x1;
 610         dl.dy = y2-y1;
 611         frac = P_InterceptVector (&trace, &dl);
 612         if (frac < 0)
 613                 return true;            // behind source
 614         intercept_p->frac = frac;
 615         intercept_p->isaline = false;
 616         intercept_p->d.thing = thing;
 617         intercept_p++;
 618
 619         return true;                    // keep going
 620 }
 621
 622
 623 /*
 624 ====================
 625 =
 626 = P_TraverseIntercepts
 627 =
 628 = Returns true if the traverser function returns true for all lines
 629 ====================
 630 */
 631
 632 boolean P_TraverseIntercepts ( traverser_t func, fixed_t maxfrac )
 633 {
 634         int                             count;
 635         fixed_t                 dist;
 636         intercept_t             *scan, *in;
 637
 638         count = intercept_p - intercepts;
 639         in = 0;                 // shut up compiler warning
 640
 641         while (count--)
 642         {
 643                 dist = MAXINT;
 644                 for (scan = intercepts ; scan<intercept_p ; scan++)
 645                         if (scan->frac < dist)
 646                         {
 647                                 dist = scan->frac;
 648                                 in = scan;
 649                         }
 650
 651                 if (dist > maxfrac)
 652                         return true;                    // checked everything in range
 653 #if 0
 654                 {       // don't check these yet, ther may be others inserted
 655                         in = scan = intercepts;
 656                         for ( scan = intercepts ; scan<intercept_p ; scan++)
 657                                 if (scan->frac > maxfrac)
 658                                         *in++ = *scan;
 659                         intercept_p = in;
 660                         return false;
 661                 }
 662 #endif
 663
 664                 if ( !func (in) )
 665                         return false;                   // don't bother going farther
 666                 in->frac = MAXINT;
 667         }
 668
 669         return true;            // everything was traversed
 670 }
 671
 672
 673
 674 /*
 675 ==================
 676 =
 677 = P_PathTraverse
 678 =
 679 = Traces a line from x1,y1 to x2,y2, calling the traverser function for each
 680 = Returns true if the traverser function returns true for all lines
 681 ==================
 682 */
 683
 684 boolean P_PathTraverse (fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2,
 685         int flags, boolean (*trav) (intercept_t *))
 686 {
 687         fixed_t xt1,yt1,xt2,yt2;
 688         fixed_t xstep,ystep;
 689         fixed_t partial;
 690         fixed_t xintercept, yintercept;
 691         int             mapx, mapy, mapxstep, mapystep;
 692         int             count;
 693
 694         earlyout = flags & PT_EARLYOUT;
 695
 696         validcount++;
 697         intercept_p = intercepts;
 698
 699         if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
 700                 x1 += FRACUNIT;                         // don't side exactly on a line
 701         if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
 702                 y1 += FRACUNIT;                         // don't side exactly on a line
 703         trace.x = x1;
 704         trace.y = y1;
 705         trace.dx = x2 - x1;
 706         trace.dy = y2 - y1;
 707
 708         x1 -= bmaporgx;
 709         y1 -= bmaporgy;
 710         xt1 = x1>>MAPBLOCKSHIFT;
 711         yt1 = y1>>MAPBLOCKSHIFT;
 712
 713         x2 -= bmaporgx;
 714         y2 -= bmaporgy;
 715         xt2 = x2>>MAPBLOCKSHIFT;
 716         yt2 = y2>>MAPBLOCKSHIFT;
 717
 718         if (xt2 > xt1)
 719         {
 720                 mapxstep = 1;
 721                 partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
 722                 ystep = FixedDiv (y2-y1,abs(x2-x1));
 723         }
 724         else if (xt2 < xt1)
 725         {
 726                 mapxstep = -1;
 727                 partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
 728                 ystep = FixedDiv (y2-y1,abs(x2-x1));
 729         }
 730         else
 731         {
 732                 mapxstep = 0;
 733                 partial = FRACUNIT;
 734                 ystep = 256*FRACUNIT;
 735         }
 736         yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep);
 737
 738
 739         if (yt2 > yt1)
 740         {
 741                 mapystep = 1;
 742                 partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
 743                 xstep = FixedDiv (x2-x1,abs(y2-y1));
 744         }
 745         else if (yt2 < yt1)
 746         {
 747                 mapystep = -1;
 748                 partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
 749                 xstep = FixedDiv (x2-x1,abs(y2-y1));
 750         }
 751         else
 752         {
 753                 mapystep = 0;
 754                 partial = FRACUNIT;
 755                 xstep = 256*FRACUNIT;
 756         }
 757         xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
 758
 759
 760 //
 761 // step through map blocks
 762 // Count is present to prevent a round off error from skipping the break
 763         mapx = xt1;
 764         mapy = yt1;
 765
 766         for (count = 0 ; count < 64 ; count++)
 767         {
 768                 if (flags & PT_ADDLINES)
 769                 {
 770                         if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts))
 771                                 return false;   // early out
 772                 }
 773                 if (flags & PT_ADDTHINGS)
 774                 {
 775                         if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts))
 776                                 return false;   // early out
 777                 }
 778
 779                 if (mapx == xt2 && mapy == yt2)
 780                         break;
 781
 782                 if ( (yintercept >> FRACBITS) == mapy)
 783                 {
 784                         yintercept += ystep;
 785                         mapx += mapxstep;
 786                 }
 787                 else if ( (xintercept >> FRACBITS) == mapx)
 788                 {
 789                         xintercept += xstep;
 790                         mapy += mapystep;
 791                 }
 792
 793         }
 794
 795
 796 //
 797 // go through the sorted list
 798 //
 799         return P_TraverseIntercepts ( trav, FRACUNIT );
 800 }
 801
 802 //===========================================================================
 803 //
 804 // P_RoughMonsterSearch
 805 //
 806 // Searches though the surrounding mapblocks for monsters/players
 807 //              distance is in MAPBLOCKUNITS
 808 //===========================================================================
 809
 810 mobj_t *P_RoughMonsterSearch(mobj_t *mo, int distance)
 811 {
 812         int blockX;
 813         int blockY;
 814         int startX, startY;
 815         int blockIndex;
 816         int firstStop;
 817         int secondStop;
 818         int thirdStop;
 819         int finalStop;
 820         int count;
 821         mobj_t *target;
 822
 823         startX = (mo->x-bmaporgx)>>MAPBLOCKSHIFT;
 824         startY = (mo->y-bmaporgy)>>MAPBLOCKSHIFT;
 825
 826         if(startX >= 0 && startX < bmapwidth && startY >= 0 && startY < bmapheight)
 827         {
 828           /* jim parens added for gcc */
 829                 if((target = RoughBlockCheck(mo, startY*bmapwidth+startX)))
 830                 { // found a target right away
 831                         return target;
 832                 }
 833         }
 834         for(count = 1; count <= distance; count++)
 835         {
 836                 blockX = startX-count;
 837                 blockY = startY-count;
 838
 839                 if(blockY < 0)
 840                 {
 841                         blockY = 0;
 842                 }
 843                 else if(blockY >= bmapheight)
 844                 {
 845                         blockY = bmapheight-1;
 846                 }
 847                 if(blockX < 0)
 848                 {
 849                         blockX = 0;
 850                 }
 851                 else if(blockX >= bmapwidth)
 852                 {
 853                         blockX = bmapwidth-1;
 854                 }
 855                 blockIndex = blockY*bmapwidth+blockX;
 856                 firstStop = startX+count;
 857                 if(firstStop < 0)
 858                 {
 859                         continue;
 860                 }
 861                 if(firstStop >= bmapwidth)
 862                 {
 863                         firstStop = bmapwidth-1;
 864                 }
 865                 secondStop = startY+count;
 866                 if(secondStop < 0)
 867                 {
 868                         continue;
 869                 }
 870                 if(secondStop >= bmapheight)
 871                 {
 872                         secondStop = bmapheight-1;
 873                 }
 874                 thirdStop = secondStop*bmapwidth+blockX;
 875                 secondStop = secondStop*bmapwidth+firstStop;
 876                 firstStop += blockY*bmapwidth;
 877                 finalStop = blockIndex;
 878
 879                 // Trace the first block section (along the top)
 880                 for(; blockIndex <= firstStop; blockIndex++)
 881                 {
 882                   /* jim parens added for gcc */
 883                   if((target = RoughBlockCheck(mo, blockIndex)))
 884                         {
 885                                 return target;
 886                         }
 887                 }
 888                 // Trace the second block section (right edge)
 889                 for(blockIndex--; blockIndex <= secondStop; blockIndex += bmapwidth)
 890                 {
 891                   /* jim parens added for gcc */
 892                   if((target = RoughBlockCheck(mo, blockIndex)))
 893                         {
 894                                 return target;
 895                         }
 896                 }
 897                 // Trace the third block section (bottom edge)
 898                 for(blockIndex -= bmapwidth; blockIndex >= thirdStop; blockIndex--)
 899                 {
 900                   /* jim parens added for gcc */
 901                   if((target = RoughBlockCheck(mo, blockIndex)))
 902                         {
 903                                 return target;
 904                         }
 905                 }
 906                 // Trace the final block section (left edge)
 907                 for(blockIndex++; blockIndex > finalStop; blockIndex -= bmapwidth)
 908                 {
 909                   /* jim parens added for gcc */
 910                   if((target = RoughBlockCheck(mo, blockIndex)))
 911                         {
 912                                 return target;
 913                         }
 914                 }
 915         }
 916         return NULL;
 917 }
 918
 919 //===========================================================================
 920 //
 921 // RoughBlockCheck
 922 //
 923 //===========================================================================
 924
 925 static mobj_t *RoughBlockCheck(mobj_t *mo, int index)
 926 {
 927         mobj_t *link;
 928         mobj_t *master;
 929         angle_t angle;
 930
 931         link = blocklinks[index];
 932         while(link)
 933         {
 934                 if (mo->player)                         // Minotaur looking around player
 935                 {
 936                         if ((link->flags&MF_COUNTKILL) ||
 937                                 (link->player && (link != mo)))
 938                         {
 939                                 if (!(link->flags&MF_SHOOTABLE))
 940                                 {
 941                                         link = link->bnext;
 942                                         continue;
 943                                 }
 944                                 if (link->flags2&MF2_DORMANT)
 945                                 {
 946                                         link = link->bnext;
 947                                         continue;
 948                                 }
 949                                 if ((link->type == MT_MINOTAUR) &&
 950                                         (((mobj_t *)link->special1) == mo))
 951                                 {
 952                                         link = link->bnext;
 953                                         continue;
 954                                 }
 955                                 if(netgame && !deathmatch && link->player)
 956                                 {
 957                                         link = link->bnext;
 958                                         continue;
 959                                 }
 960                                 if(P_CheckSight(mo, link))
 961                                 {
 962                                         return link;
 963                                 }
 964                         }
 965                         link = link->bnext;
 966                 }
 967                 else if (mo->type == MT_MINOTAUR)       // looking around minotaur
 968                 {
 969                         master = (mobj_t *)mo->special1;
 970                         if ((link->flags&MF_COUNTKILL) ||
 971                                 (link->player && (link != master)))
 972                         {
 973                                 if (!(link->flags&MF_SHOOTABLE))
 974                                 {
 975                                         link = link->bnext;
 976                                         continue;
 977                                 }
 978                                 if (link->flags2&MF2_DORMANT)
 979                                 {
 980                                         link = link->bnext;
 981                                         continue;
 982                                 }
 983                                 if ((link->type == MT_MINOTAUR) &&
 984                                         (link->special1 == mo->special1))
 985                                 {
 986                                         link = link->bnext;
 987                                         continue;
 988                                 }
 989                                 if(netgame && !deathmatch && link->player)
 990                                 {
 991                                         link = link->bnext;
 992                                         continue;
 993                                 }
 994                                 if(P_CheckSight(mo, link))
 995                                 {
 996                                         return link;
 997                                 }
 998                         }
 999                         link = link->bnext;
1000                 }
1001                 else if (mo->type == MT_MSTAFF_FX2)             // bloodscourge
1002                 {
1003                         if ((link->flags&MF_COUNTKILL ||
1004                                 (link->player && link != mo->target))
1005                                 && !(link->flags2&MF2_DORMANT))
1006                         {
1007                                 if (!(link->flags&MF_SHOOTABLE))
1008                                 {
1009                                         link = link->bnext;
1010                                         continue;
1011                                 }
1012                                 if(netgame && !deathmatch && link->player)
1013                                 {
1014                                         link = link->bnext;
1015                                         continue;
1016                                 }
1017                                 else if(P_CheckSight(mo, link))
1018                                 {
1019                                         master = mo->target;
1020                                         angle = R_PointToAngle2(master->x, master->y,
1021                                                                         link->x, link->y) - master->angle;
1022                                         angle >>= 24;
1023                                         if (angle>226 || angle<30)
1024                                         {
1025                                                 return link;
1026                                         }
1027                                 }
1028                         }
1029                         link = link->bnext;
1030                 }
1031                 else                                                            // spirits
1032                 {
1033                         if ((link->flags&MF_COUNTKILL ||
1034                                 (link->player && link != mo->target))
1035                                 && !(link->flags2&MF2_DORMANT))
1036                         {
1037                                 if (!(link->flags&MF_SHOOTABLE))
1038                                 {
1039                                         link = link->bnext;
1040                                         continue;
1041                                 }
1042                                 if(netgame && !deathmatch && link->player)
1043                                 {
1044                                         link = link->bnext;
1045                                         continue;
1046                                 }
1047                                 if (link == mo->target)
1048                                 {
1049                                         link = link->bnext;
1050                                         continue;
1051                                 }
1052                                 else if(P_CheckSight(mo, link))
1053                                 {
1054                                         return link;
1055                                 }
1056                         }
1057                         link = link->bnext;
1058                 }
1059         }
1060         return NULL;
1061 }
1062