Games/Doom/p_maputl.c

   1 // Emacs style mode select   -*- C++ -*-
   2 //-----------------------------------------------------------------------------
   3 //
   4 // $Id$
   5 //
   6 // Copyright (C) 1993-1996 by id Software, Inc.
   7 //
   8 // This source is available for distribution and/or modification
   9 // only under the terms of the DOOM Source Code License as
  10 // published by id Software. All rights reserved.
  11 //
  12 // The source is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License
  15 // for more details.
  16 //
  17 // $Log$
  18 // Revision 1.1  2000/02/29 18:21:04  stegerg
  19 // Doom port based on ADoomPPC. Read README.AROS!
  20 //
  21 //
  22 // DESCRIPTION:
  23 //      Movement/collision utility functions,
  24 //      as used by function in p_map.c.
  25 //      BLOCKMAP Iterator functions,
  26 //      and some PIT_* functions to use for iteration.
  27 //
  28 //-----------------------------------------------------------------------------
  29
  30 static const char
  31 rcsid[] = "$Id$";
  32
  33
  34 #include <stdlib.h>
  35
  36
  37 #include "m_bbox.h"
  38
  39 #include "doomdef.h"
  40 #include "p_local.h"
  41
  42
  43 // State.
  44 #include "r_state.h"
  45
  46 //
  47 // P_AproxDistance
  48 // Gives an estimation of distance (not exact)
  49 //
  50
  51 fixed_t
  52 P_AproxDistance
  53 ( fixed_t       dx,
  54   fixed_t       dy )
  55 {
  56     dx = iabs(dx);
  57     dy = iabs(dy);
  58     if (dx < dy)
  59         return dx+dy-(dx>>1);
  60     return dx+dy-(dy>>1);
  61 }
  62
  63
  64 //
  65 // P_PointOnLineSide
  66 // Returns 0 or 1
  67 //
  68 int
  69 P_PointOnLineSide
  70 ( fixed_t       x,
  71   fixed_t       y,
  72   line_t*       line )
  73 {
  74     fixed_t     dx;
  75     fixed_t     dy;
  76     fixed_t     left;
  77     fixed_t     right;
  78
  79     if (!line->dx)
  80     {
  81         if (x <= line->v1->x)
  82             return line->dy > 0;
  83
  84         return line->dy < 0;
  85     }
  86     if (!line->dy)
  87     {
  88         if (y <= line->v1->y)
  89             return line->dx < 0;
  90
  91         return line->dx > 0;
  92     }
  93
  94     dx = (x - line->v1->x);
  95     dy = (y - line->v1->y);
  96
  97     left = FixedMul ( line->dy>>FRACBITS , dx );
  98     right = FixedMul ( dy , line->dx>>FRACBITS );
  99
 100     if (right < left)
 101         return 0;               // front side
 102     return 1;                   // back side
 103 }
 104
 105
 106
 107 //
 108 // P_BoxOnLineSide
 109 // Considers the line to be infinite
 110 // Returns side 0 or 1, -1 if box crosses the line.
 111 //
 112 int
 113 P_BoxOnLineSide
 114 ( fixed_t*      tmbox,
 115   line_t*       ld )
 116 {
 117     int         p1 = 0;
 118     int         p2 = 0;
 119
 120     switch (ld->slopetype)
 121     {
 122       case ST_HORIZONTAL:
 123         p1 = tmbox[BOXTOP] > ld->v1->y;
 124         p2 = tmbox[BOXBOTTOM] > ld->v1->y;
 125         if (ld->dx < 0)
 126         {
 127             p1 ^= 1;
 128             p2 ^= 1;
 129         }
 130         break;
 131
 132       case ST_VERTICAL:
 133         p1 = tmbox[BOXRIGHT] < ld->v1->x;
 134         p2 = tmbox[BOXLEFT] < ld->v1->x;
 135         if (ld->dy < 0)
 136         {
 137             p1 ^= 1;
 138             p2 ^= 1;
 139         }
 140         break;
 141
 142       case ST_POSITIVE:
 143         p1 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXTOP], ld);
 144         p2 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld);
 145         break;
 146
 147       case ST_NEGATIVE:
 148         p1 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXTOP], ld);
 149         p2 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld);
 150         break;
 151     }
 152
 153     if (p1 == p2)
 154         return p1;
 155     return -1;
 156 }
 157
 158
 159 //
 160 // P_PointOnDivlineSide
 161 // Returns 0 or 1.
 162 //
 163 int
 164 P_PointOnDivlineSide
 165 ( fixed_t       x,
 166   fixed_t       y,
 167   divline_t*    line )
 168 {
 169     fixed_t     dx;
 170     fixed_t     dy;
 171     fixed_t     left;
 172     fixed_t     right;
 173
 174     if (!line->dx)
 175     {
 176         if (x <= line->x)
 177             return line->dy > 0;
 178
 179         return line->dy < 0;
 180     }
 181     if (!line->dy)
 182     {
 183         if (y <= line->y)
 184             return line->dx < 0;
 185
 186         return line->dx > 0;
 187     }
 188
 189     dx = (x - line->x);
 190     dy = (y - line->y);
 191
 192     // try to quickly decide by looking at sign bits
 193     if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
 194     {
 195         if ( (line->dy ^ dx) & 0x80000000 )
 196             return 1;           // (left is negative)
 197         return 0;
 198     }
 199
 200     left = FixedMul ( line->dy>>8, dx>>8 );
 201     right = FixedMul ( dy>>8 , line->dx>>8 );
 202
 203     if (right < left)
 204         return 0;               // front side
 205     return 1;                   // back side
 206 }
 207
 208
 209
 210 //
 211 // P_MakeDivline
 212 //
 213 void
 214 P_MakeDivline
 215 ( line_t*       li,
 216   divline_t*    dl )
 217 {
 218     dl->x = li->v1->x;
 219     dl->y = li->v1->y;
 220     dl->dx = li->dx;
 221     dl->dy = li->dy;
 222 }
 223
 224
 225
 226 //
 227 // P_InterceptVector
 228 // Returns the fractional intercept point
 229 // along the first divline.
 230 // This is only called by the addthings
 231 // and addlines traversers.
 232 //
 233 fixed_t
 234 P_InterceptVector
 235 ( divline_t*    v2,
 236   divline_t*    v1 )
 237 {
 238 #if 1
 239     fixed_t     frac;
 240     fixed_t     num;
 241     fixed_t     den;
 242
 243     den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
 244
 245     if (den == 0)
 246         return 0;
 247     //  I_Error ("P_InterceptVector: parallel");
 248
 249     num =
 250         FixedMul ( (v1->x - v2->x)>>8 ,v1->dy )
 251         +FixedMul ( (v2->y - v1->y)>>8, v1->dx );
 252
 253     frac = FixedDiv (num , den);
 254
 255     return frac;
 256 #else   // UNUSED, float debug.
 257     float       frac;
 258     float       num;
 259     float       den;
 260     float       v1x;
 261     float       v1y;
 262     float       v1dx;
 263     float       v1dy;
 264     float       v2x;
 265     float       v2y;
 266     float       v2dx;
 267     float       v2dy;
 268
 269     v1x = (float)v1->x/FRACUNIT;
 270     v1y = (float)v1->y/FRACUNIT;
 271     v1dx = (float)v1->dx/FRACUNIT;
 272     v1dy = (float)v1->dy/FRACUNIT;
 273     v2x = (float)v2->x/FRACUNIT;
 274     v2y = (float)v2->y/FRACUNIT;
 275     v2dx = (float)v2->dx/FRACUNIT;
 276     v2dy = (float)v2->dy/FRACUNIT;
 277
 278     den = v1dy*v2dx - v1dx*v2dy;
 279
 280     if (den == 0)
 281         return 0;       // parallel
 282
 283     num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx;
 284     frac = num / den;
 285
 286     return frac*FRACUNIT;
 287 #endif
 288 }
 289
 290
 291 //
 292 // P_LineOpening
 293 // Sets opentop and openbottom to the window
 294 // through a two sided line.
 295 // OPTIMIZE: keep this precalculated
 296 //
 297 fixed_t opentop;
 298 fixed_t openbottom;
 299 fixed_t openrange;
 300 fixed_t lowfloor;
 301
 302
 303 void P_LineOpening (line_t* linedef)
 304 {
 305     sector_t*   front;
 306     sector_t*   back;
 307
 308     if (linedef->sidenum[1] == -1)
 309     {
 310         // single sided line
 311         openrange = 0;
 312         return;
 313     }
 314
 315     front = linedef->frontsector;
 316     back = linedef->backsector;
 317
 318     if (front->ceilingheight < back->ceilingheight)
 319         opentop = front->ceilingheight;
 320     else
 321         opentop = back->ceilingheight;
 322
 323     if (front->floorheight > back->floorheight)
 324     {
 325         openbottom = front->floorheight;
 326         lowfloor = back->floorheight;
 327     }
 328     else
 329     {
 330         openbottom = back->floorheight;
 331         lowfloor = front->floorheight;
 332     }
 333
 334     openrange = opentop - openbottom;
 335 }
 336
 337
 338 //
 339 // THING POSITION SETTING
 340 //
 341
 342
 343 //
 344 // P_UnsetThingPosition
 345 // Unlinks a thing from block map and sectors.
 346 // On each position change, BLOCKMAP and other
 347 // lookups maintaining lists ot things inside
 348 // these structures need to be updated.
 349 //
 350 void P_UnsetThingPosition (mobj_t* thing)
 351 {
 352     int         blockx;
 353     int         blocky;
 354
 355     if ( ! (thing->flags & MF_NOSECTOR) )
 356     {
 357         // inert things don't need to be in blockmap?
 358         // unlink from subsector
 359         if (thing->snext)
 360             thing->snext->sprev = thing->sprev;
 361
 362         if (thing->sprev)
 363             thing->sprev->snext = thing->snext;
 364         else
 365             thing->subsector->sector->thinglist = thing->snext;
 366     }
 367
 368     if ( ! (thing->flags & MF_NOBLOCKMAP) )
 369     {
 370         // inert things don't need to be in blockmap
 371         // unlink from block map
 372         if (thing->bnext)
 373             thing->bnext->bprev = thing->bprev;
 374
 375         if (thing->bprev)
 376             thing->bprev->bnext = thing->bnext;
 377         else
 378         {
 379             blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
 380             blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
 381
 382             if (blockx>=0 && blockx < bmapwidth
 383                 && blocky>=0 && blocky <bmapheight)
 384             {
 385                 blocklinks[blocky*bmapwidth+blockx] = thing->bnext;
 386             }
 387         }
 388     }
 389 }
 390
 391
 392 //
 393 // P_SetThingPosition
 394 // Links a thing into both a block and a subsector
 395 // based on it's x y.
 396 // Sets thing->subsector properly
 397 //
 398 void
 399 P_SetThingPosition (mobj_t* thing)
 400 {
 401     subsector_t*        ss;
 402     sector_t*           sec;
 403     int                 blockx;
 404     int                 blocky;
 405     mobj_t**            link;
 406
 407
 408     // link into subsector
 409     ss = R_PointInSubsector (thing->x,thing->y);
 410     thing->subsector = ss;
 411
 412     if ( ! (thing->flags & MF_NOSECTOR) )
 413     {
 414         // invisible things don't go into the sector links
 415         sec = ss->sector;
 416
 417         thing->sprev = NULL;
 418         thing->snext = sec->thinglist;
 419
 420         if (sec->thinglist)
 421             sec->thinglist->sprev = thing;
 422
 423         sec->thinglist = thing;
 424     }
 425
 426
 427     // link into blockmap
 428     if ( ! (thing->flags & MF_NOBLOCKMAP) )
 429     {
 430         // inert things don't need to be in blockmap
 431         blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
 432         blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
 433
 434         if (blockx>=0
 435             && blockx < bmapwidth
 436             && blocky>=0
 437             && blocky < bmapheight)
 438         {
 439             link = &blocklinks[blocky*bmapwidth+blockx];
 440             thing->bprev = NULL;
 441             thing->bnext = *link;
 442             if (*link)
 443                 (*link)->bprev = thing;
 444
 445             *link = thing;
 446         }
 447         else
 448         {
 449             // thing is off the map
 450             thing->bnext = thing->bprev = NULL;
 451         }
 452     }
 453 }
 454
 455
 456
 457 //
 458 // BLOCK MAP ITERATORS
 459 // For each line/thing in the given mapblock,
 460 // call the passed PIT_* function.
 461 // If the function returns false,
 462 // exit with false without checking anything else.
 463 //
 464
 465
 466 //
 467 // P_BlockLinesIterator
 468 // The validcount flags are used to avoid checking lines
 469 // that are marked in multiple mapblocks,
 470 // so increment validcount before the first call
 471 // to P_BlockLinesIterator, then make one or more calls
 472 // to it.
 473 //
 474 boolean
 475 P_BlockLinesIterator
 476 ( int                   x,
 477   int                   y,
 478   boolean(*func)(line_t*) )
 479 {
 480     int                 offset;
 481     short*              list;
 482     line_t*             ld;
 483
 484     if (x<0
 485         || y<0
 486         || x>=bmapwidth
 487         || y>=bmapheight)
 488     {
 489         return true;
 490     }
 491
 492     offset = y*bmapwidth+x;
 493
 494     offset = *(blockmap+offset);
 495
 496     for ( list = blockmaplump+offset ; *list != -1 ; list++)
 497     {
 498         ld = &lines[*list];
 499
 500         if (ld->validcount == validcount)
 501             continue;   // line has already been checked
 502
 503         ld->validcount = validcount;
 504
 505         if ( !func(ld) )
 506             return false;
 507     }
 508     return true;        // everything was checked
 509 }
 510
 511
 512 //
 513 // P_BlockThingsIterator
 514 //
 515 boolean
 516 P_BlockThingsIterator
 517 ( int                   x,
 518   int                   y,
 519   boolean(*func)(mobj_t*) )
 520 {
 521     mobj_t*             mobj;
 522
 523     if ( x<0
 524          || y<0
 525          || x>=bmapwidth
 526          || y>=bmapheight)
 527     {
 528         return true;
 529     }
 530
 531
 532     for (mobj = blocklinks[y*bmapwidth+x] ;
 533          mobj ;
 534          mobj = mobj->bnext)
 535     {
 536         if (!func( mobj ) )
 537             return false;
 538     }
 539     return true;
 540 }
 541
 542
 543
 544 //
 545 // INTERCEPT ROUTINES
 546 //
 547 intercept_t     intercepts[MAXINTERCEPTS];
 548 intercept_t*    intercept_p;
 549
 550 divline_t       trace;
 551 boolean         earlyout;
 552 int             ptflags;
 553
 554 //
 555 // PIT_AddLineIntercepts.
 556 // Looks for lines in the given block
 557 // that intercept the given trace
 558 // to add to the intercepts list.
 559 //
 560 // A line is crossed if its endpoints
 561 // are on opposite sides of the trace.
 562 // Returns true if earlyout and a solid line hit.
 563 //
 564 boolean
 565 PIT_AddLineIntercepts (line_t* ld)
 566 {
 567     int                 s1;
 568     int                 s2;
 569     fixed_t             frac;
 570     divline_t           dl;
 571
 572     // avoid precision problems with two routines
 573     if ( trace.dx > FRACUNIT*16
 574          || trace.dy > FRACUNIT*16
 575          || trace.dx < -FRACUNIT*16
 576          || trace.dy < -FRACUNIT*16)
 577     {
 578         s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
 579         s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
 580     }
 581     else
 582     {
 583         s1 = P_PointOnLineSide (trace.x, trace.y, ld);
 584         s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
 585     }
 586
 587     if (s1 == s2)
 588         return true;    // line isn't crossed
 589
 590     // hit the line
 591     P_MakeDivline (ld, &dl);
 592     frac = P_InterceptVector (&trace, &dl);
 593
 594     if (frac < 0)
 595         return true;    // behind source
 596
 597     // try to early out the check
 598     if (earlyout
 599         && frac < FRACUNIT
 600         && !ld->backsector)
 601     {
 602         return false;   // stop checking
 603     }
 604
 605
 606     intercept_p->frac = frac;
 607     intercept_p->isaline = true;
 608     intercept_p->d.line = ld;
 609     intercept_p++;
 610
 611     return true;        // continue
 612 }
 613
 614
 615
 616 //
 617 // PIT_AddThingIntercepts
 618 //
 619 boolean PIT_AddThingIntercepts (mobj_t* thing)
 620 {
 621     fixed_t             x1;
 622     fixed_t             y1;
 623     fixed_t             x2;
 624     fixed_t             y2;
 625
 626     int                 s1;
 627     int                 s2;
 628
 629     boolean             tracepositive;
 630
 631     divline_t           dl;
 632
 633     fixed_t             frac;
 634
 635     tracepositive = (trace.dx ^ trace.dy)>0;
 636
 637     // check a corner to corner crossection for hit
 638     if (tracepositive)
 639     {
 640         x1 = thing->x - thing->radius;
 641         y1 = thing->y + thing->radius;
 642
 643         x2 = thing->x + thing->radius;
 644         y2 = thing->y - thing->radius;
 645     }
 646     else
 647     {
 648         x1 = thing->x - thing->radius;
 649         y1 = thing->y - thing->radius;
 650
 651         x2 = thing->x + thing->radius;
 652         y2 = thing->y + thing->radius;
 653     }
 654
 655     s1 = P_PointOnDivlineSide (x1, y1, &trace);
 656     s2 = P_PointOnDivlineSide (x2, y2, &trace);
 657
 658     if (s1 == s2)
 659         return true;            // line isn't crossed
 660
 661     dl.x = x1;
 662     dl.y = y1;
 663     dl.dx = x2-x1;
 664     dl.dy = y2-y1;
 665
 666     frac = P_InterceptVector (&trace, &dl);
 667
 668     if (frac < 0)
 669         return true;            // behind source
 670
 671     intercept_p->frac = frac;
 672     intercept_p->isaline = false;
 673     intercept_p->d.thing = thing;
 674     intercept_p++;
 675
 676     return true;                // keep going
 677 }
 678
 679
 680 //
 681 // P_TraverseIntercepts
 682 // Returns true if the traverser function returns true
 683 // for all lines.
 684 //
 685 boolean
 686 P_TraverseIntercepts
 687 ( traverser_t   func,
 688   fixed_t       maxfrac )
 689 {
 690     int                 count;
 691     fixed_t             dist;
 692     intercept_t*        scan;
 693     intercept_t*        in;
 694
 695     count = intercept_p - intercepts;
 696
 697     in = 0;                     // shut up compiler warning
 698
 699     while (count--)
 700     {
 701         dist = MAXINT;
 702         for (scan = intercepts ; scan<intercept_p ; scan++)
 703         {
 704             if (scan->frac < dist)
 705             {
 706                 dist = scan->frac;
 707                 in = scan;
 708             }
 709         }
 710
 711         if (dist > maxfrac)
 712             return true;        // checked everything in range
 713
 714 #if 0  // UNUSED
 715     {
 716         // don't check these yet, there may be others inserted
 717         in = scan = intercepts;
 718         for ( scan = intercepts ; scan<intercept_p ; scan++)
 719             if (scan->frac > maxfrac)
 720                 *in++ = *scan;
 721         intercept_p = in;
 722         return false;
 723     }
 724 #endif
 725
 726         if ( !func (in) )
 727             return false;       // don't bother going farther
 728
 729         in->frac = MAXINT;
 730     }
 731
 732     return true;                // everything was traversed
 733 }
 734
 735
 736
 737
 738 //
 739 // P_PathTraverse
 740 // Traces a line from x1,y1 to x2,y2,
 741 // calling the traverser function for each.
 742 // Returns true if the traverser function returns true
 743 // for all lines.
 744 //
 745 boolean
 746 P_PathTraverse
 747 ( fixed_t               x1,
 748   fixed_t               y1,
 749   fixed_t               x2,
 750   fixed_t               y2,
 751   int                   flags,
 752   boolean (*trav) (intercept_t *))
 753 {
 754     fixed_t     xt1;
 755     fixed_t     yt1;
 756     fixed_t     xt2;
 757     fixed_t     yt2;
 758
 759     fixed_t     xstep;
 760     fixed_t     ystep;
 761
 762     fixed_t     partial;
 763
 764     fixed_t     xintercept;
 765     fixed_t     yintercept;
 766
 767     int         mapx;
 768     int         mapy;
 769
 770     int         mapxstep;
 771     int         mapystep;
 772
 773     int         count;
 774
 775     earlyout = flags & PT_EARLYOUT;
 776
 777     validcount++;
 778     intercept_p = intercepts;
 779
 780     if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
 781         x1 += FRACUNIT; // don't side exactly on a line
 782
 783     if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
 784         y1 += FRACUNIT; // don't side exactly on a line
 785
 786     trace.x = x1;
 787     trace.y = y1;
 788     trace.dx = x2 - x1;
 789     trace.dy = y2 - y1;
 790
 791     x1 -= bmaporgx;
 792     y1 -= bmaporgy;
 793     xt1 = x1>>MAPBLOCKSHIFT;
 794     yt1 = y1>>MAPBLOCKSHIFT;
 795
 796     x2 -= bmaporgx;
 797     y2 -= bmaporgy;
 798     xt2 = x2>>MAPBLOCKSHIFT;
 799     yt2 = y2>>MAPBLOCKSHIFT;
 800
 801     if (xt2 > xt1)
 802     {
 803         mapxstep = 1;
 804         partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
 805         ystep = FixedDiv (y2-y1,iabs(x2-x1));
 806     }
 807     else if (xt2 < xt1)
 808     {
 809         mapxstep = -1;
 810         partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
 811         ystep = FixedDiv (y2-y1,iabs(x2-x1));
 812     }
 813     else
 814     {
 815         mapxstep = 0;
 816         partial = FRACUNIT;
 817         ystep = 256*FRACUNIT;
 818     }
 819
 820     yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep);
 821
 822
 823     if (yt2 > yt1)
 824     {
 825         mapystep = 1;
 826         partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
 827         xstep = FixedDiv (x2-x1,iabs(y2-y1));
 828     }
 829     else if (yt2 < yt1)
 830     {
 831         mapystep = -1;
 832         partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
 833         xstep = FixedDiv (x2-x1,iabs(y2-y1));
 834     }
 835     else
 836     {
 837         mapystep = 0;
 838         partial = FRACUNIT;
 839         xstep = 256*FRACUNIT;
 840     }
 841     xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
 842
 843     // Step through map blocks.
 844     // Count is present to prevent a round off error
 845     // from skipping the break.
 846     mapx = xt1;
 847     mapy = yt1;
 848
 849     for (count = 0 ; count < 64 ; count++)
 850     {
 851         if (flags & PT_ADDLINES)
 852         {
 853             if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts))
 854                 return false;   // early out
 855         }
 856
 857         if (flags & PT_ADDTHINGS)
 858         {
 859             if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts))
 860                 return false;   // early out
 861         }
 862
 863         if (mapx == xt2
 864             && mapy == yt2)
 865         {
 866             break;
 867         }
 868
 869         if ( (yintercept >> FRACBITS) == mapy)
 870         {
 871             yintercept += ystep;
 872             mapx += mapxstep;
 873         }
 874         else if ( (xintercept >> FRACBITS) == mapx)
 875         {
 876             xintercept += xstep;
 877             mapy += mapystep;
 878         }
 879
 880     }
 881     // go through the sorted list
 882     return P_TraverseIntercepts ( trav, FRACUNIT );
 883 }
 884
 885
 886