apps/plugins/doom/p_maputl.c

   1 /* Emacs style mode select   -*- C++ -*-
   2  *-----------------------------------------------------------------------------
   3  *
   4  *
   5  *  PrBoom a Doom port merged with LxDoom and LSDLDoom
   6  *  based on BOOM, a modified and improved DOOM engine
   7  *  Copyright (C) 1999 by
   8  *  id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman
   9  *  Copyright (C) 1999-2000 by
  10  *  Jess Haas, Nicolas Kalkhof, Colin Phipps, Florian Schulze
  11  *
  12  *  This program is free software; you can redistribute it and/or
  13  *  modify it under the terms of the GNU General Public License
  14  *  as published by the Free Software Foundation; either version 2
  15  *  of the License, or (at your option) any later version.
  16  *
  17  *  This program is distributed in the hope that it will be useful,
  18  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  *  GNU General Public License for more details.
  21  *
  22  *  You should have received a copy of the GNU General Public License
  23  *  along with this program; if not, write to the Free Software
  24  *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  25  *  02111-1307, USA.
  26  *
  27  * DESCRIPTION:
  28  *      Movement/collision utility functions,
  29  *      as used by function in p_map.c.
  30  *      BLOCKMAP Iterator functions,
  31  *      and some PIT_* functions to use for iteration.
  32  *
  33  *-----------------------------------------------------------------------------*/
  34
  35 #include "doomstat.h"
  36 #include "m_bbox.h"
  37 #include "r_main.h"
  38 #include "p_maputl.h"
  39 #include "p_map.h"
  40 #include "p_setup.h"
  41 #include "rockmacros.h"
  42 //
  43 // P_AproxDistance
  44 // Gives an estimation of distance (not exact)
  45 //
  46
  47 fixed_t CONSTFUNC P_AproxDistance(fixed_t dx, fixed_t dy)
  48 {
  49    dx = D_abs(dx);
  50    dy = D_abs(dy);
  51    if (dx < dy)
  52       return dx+dy-(dx>>1);
  53    return dx+dy-(dy>>1);
  54 }
  55
  56 //
  57 // P_PointOnLineSide
  58 // Returns 0 or 1
  59 //
  60 // killough 5/3/98: reformatted, cleaned up
  61
  62 int CONSTFUNC P_PointOnLineSide(fixed_t x, fixed_t y, const line_t *line)
  63 {
  64    return
  65    !line->dx ? x <= line->v1->x ? line->dy > 0 : line->dy < 0 :
  66    !line->dy ? y <= line->v1->y ? line->dx < 0 : line->dx > 0 :
  67       FixedMul(y-line->v1->y, line->dx>>FRACBITS) >=
  68       FixedMul(line->dy>>FRACBITS, x-line->v1->x);
  69 }
  70
  71 //
  72 // P_BoxOnLineSide
  73 // Considers the line to be infinite
  74 // Returns side 0 or 1, -1 if box crosses the line.
  75 //
  76 // killough 5/3/98: reformatted, cleaned up
  77
  78 int CONSTFUNC P_BoxOnLineSide(const fixed_t *tmbox, const line_t *ld)
  79 {
  80    switch (ld->slopetype)
  81    {
  82       int p;
  83    default: // shut up compiler warnings -- killough
  84    case ST_HORIZONTAL:
  85       return
  86          (tmbox[BOXBOTTOM] > ld->v1->y) == (p = tmbox[BOXTOP] > ld->v1->y) ?
  87          p ^ (ld->dx < 0) : -1;
  88    case ST_VERTICAL:
  89       return
  90          (tmbox[BOXLEFT] < ld->v1->x) == (p = tmbox[BOXRIGHT] < ld->v1->x) ?
  91          p ^ (ld->dy < 0) : -1;
  92    case ST_POSITIVE:
  93       return
  94          P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld) ==
  95          (p = P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXTOP], ld)) ? p : -1;
  96    case ST_NEGATIVE:
  97       return
  98          (P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld)) ==
  99          (p = P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXTOP], ld)) ? p : -1;
 100    }
 101 }
 102
 103 //
 104 // P_PointOnDivlineSide
 105 // Returns 0 or 1.
 106 //
 107 // killough 5/3/98: reformatted, cleaned up
 108
 109 int CONSTFUNC P_PointOnDivlineSide(fixed_t x, fixed_t y, const divline_t *line)
 110 {
 111    return
 112    !line->dx ? x <= line->x ? line->dy > 0 : line->dy < 0 :
 113    !line->dy ? y <= line->y ? line->dx < 0 : line->dx > 0 :
 114       (line->dy^line->dx^(x -= line->x)^(y -= line->y)) < 0 ? (line->dy^x) < 0 :
 115       FixedMul(y>>8, line->dx>>8) >= FixedMul(line->dy>>8, x>>8);
 116 }
 117
 118 //
 119 // P_MakeDivline
 120 //
 121
 122 void P_MakeDivline(const line_t *li, divline_t *dl)
 123 {
 124    dl->x = li->v1->x;
 125    dl->y = li->v1->y;
 126    dl->dx = li->dx;
 127    dl->dy = li->dy;
 128 }
 129
 130 //
 131 // P_InterceptVector
 132 // Returns the fractional intercept point
 133 // along the first divline.
 134 // This is only called by the addthings
 135 // and addlines traversers.
 136 //
 137 // killough 5/3/98: reformatted, cleaned up
 138
 139 fixed_t CONSTFUNC P_InterceptVector(const divline_t *v2, const divline_t *v1)
 140 {
 141    fixed_t den = FixedMul(v1->dy>>8, v2->dx) - FixedMul(v1->dx>>8, v2->dy);
 142    return den ? FixedDiv((FixedMul((v1->x-v2->x)>>8, v1->dy) +
 143                           FixedMul((v2->y-v1->y)>>8, v1->dx)), den) : 0;
 144 }
 145
 146 //
 147 // P_LineOpening
 148 // Sets opentop and openbottom to the window
 149 // through a two sided line.
 150 // OPTIMIZE: keep this precalculated
 151 //
 152
 153 fixed_t opentop;
 154 fixed_t openbottom;
 155 fixed_t openrange;
 156 fixed_t lowfloor;
 157
 158 // moved front and back outside P-LineOpening and changed    // phares 3/7/98
 159 // them to these so we can pick up the new friction value
 160 // in PIT_CheckLine()
 161 sector_t *openfrontsector; // made global                    // phares
 162 sector_t *openbacksector;  // made global
 163
 164 void P_LineOpening(const line_t *linedef)
 165 {
 166    if (linedef->sidenum[1] == -1)      // single sided line
 167    {
 168       openrange = 0;
 169       return;
 170    }
 171
 172    openfrontsector = linedef->frontsector;
 173    openbacksector = linedef->backsector;
 174
 175    if (openfrontsector->ceilingheight < openbacksector->ceilingheight)
 176       opentop = openfrontsector->ceilingheight;
 177    else
 178       opentop = openbacksector->ceilingheight;
 179
 180    if (openfrontsector->floorheight > openbacksector->floorheight)
 181    {
 182       openbottom = openfrontsector->floorheight;
 183       lowfloor = openbacksector->floorheight;
 184    }
 185    else
 186    {
 187       openbottom = openbacksector->floorheight;
 188       lowfloor = openfrontsector->floorheight;
 189    }
 190    openrange = opentop - openbottom;
 191 }
 192
 193 //
 194 // THING POSITION SETTING
 195 //
 196
 197 //
 198 // P_UnsetThingPosition
 199 // Unlinks a thing from block map and sectors.
 200 // On each position change, BLOCKMAP and other
 201 // lookups maintaining lists ot things inside
 202 // these structures need to be updated.
 203 //
 204
 205 void P_UnsetThingPosition (mobj_t *thing)
 206 {
 207    if (!(thing->flags & MF_NOSECTOR))
 208    {
 209       /* invisible things don't need to be in sector list
 210        * unlink from subsector
 211        *
 212        * killough 8/11/98: simpler scheme using pointers-to-pointers for prev
 213        * pointers, allows head node pointers to be treated like everything else
 214        */
 215
 216       mobj_t **sprev = thing->sprev;
 217       mobj_t  *snext = thing->snext;
 218       if ((*sprev = snext))  // unlink from sector list
 219          snext->sprev = sprev;
 220
 221       // phares 3/14/98
 222       //
 223       // Save the sector list pointed to by touching_sectorlist.
 224       // In P_SetThingPosition, we'll keep any nodes that represent
 225       // sectors the Thing still touches. We'll add new ones then, and
 226       // delete any nodes for sectors the Thing has vacated. Then we'll
 227       // put it back into touching_sectorlist. It's done this way to
 228       // avoid a lot of deleting/creating for nodes, when most of the
 229       // time you just get back what you deleted anyway.
 230       //
 231       // If this Thing is being removed entirely, then the calling
 232       // routine will clear out the nodes in sector_list.
 233
 234       sector_list = thing->touching_sectorlist;
 235       thing->touching_sectorlist = NULL; //to be restored by P_SetThingPosition
 236    }
 237
 238    if (!(thing->flags & MF_NOBLOCKMAP))
 239    {
 240       /* inert things don't need to be in blockmap
 241        *
 242        * killough 8/11/98: simpler scheme using pointers-to-pointers for prev
 243        * pointers, allows head node pointers to be treated like everything else
 244        *
 245        * Also more robust, since it doesn't depend on current position for
 246        * unlinking. Old method required computing head node based on position
 247        * at time of unlinking, assuming it was the same position as during
 248        * linking.
 249        */
 250
 251       mobj_t *bnext, **bprev = thing->bprev;
 252       if (bprev && (*bprev = bnext = thing->bnext))  // unlink from block map
 253          bnext->bprev = bprev;
 254    }
 255 }
 256
 257 //
 258 // P_SetThingPosition
 259 // Links a thing into both a block and a subsector
 260 // based on it's x y.
 261 // Sets thing->subsector properly
 262 //
 263 // killough 5/3/98: reformatted, cleaned up
 264
 265 void P_SetThingPosition(mobj_t *thing)
 266 {                                                      // link into subsector
 267    subsector_t *ss = thing->subsector = R_PointInSubsector(thing->x, thing->y);
 268    if (!(thing->flags & MF_NOSECTOR))
 269    {
 270       // invisible things don't go into the sector links
 271
 272       // killough 8/11/98: simpler scheme using pointer-to-pointer prev
 273       // pointers, allows head nodes to be treated like everything else
 274
 275       mobj_t **link = &ss->sector->thinglist;
 276       mobj_t *snext = *link;
 277       if ((thing->snext = snext))
 278          snext->sprev = &thing->snext;
 279       thing->sprev = link;
 280       *link = thing;
 281
 282       // phares 3/16/98
 283       //
 284       // If sector_list isn't NULL, it has a collection of sector
 285       // nodes that were just removed from this Thing.
 286
 287       // Collect the sectors the object will live in by looking at
 288       // the existing sector_list and adding new nodes and deleting
 289       // obsolete ones.
 290
 291       // When a node is deleted, its sector links (the links starting
 292       // at sector_t->touching_thinglist) are broken. When a node is
 293       // added, new sector links are created.
 294
 295       P_CreateSecNodeList(thing,thing->x,thing->y);
 296       thing->touching_sectorlist = sector_list; // Attach to Thing's mobj_t
 297       sector_list = NULL; // clear for next time
 298    }
 299
 300    // link into blockmap
 301    if (!(thing->flags & MF_NOBLOCKMAP))
 302    {
 303       // inert things don't need to be in blockmap
 304       int blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
 305       int blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
 306       if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky < bmapheight)
 307       {
 308          // killough 8/11/98: simpler scheme using pointer-to-pointer prev
 309          // pointers, allows head nodes to be treated like everything else
 310
 311          mobj_t **link = &blocklinks[blocky*bmapwidth+blockx];
 312          mobj_t *bnext = *link;
 313          if ((thing->bnext = bnext))
 314             bnext->bprev = &thing->bnext;
 315          thing->bprev = link;
 316          *link = thing;
 317       }
 318       else        // thing is off the map
 319          thing->bnext = NULL, thing->bprev = NULL;
 320    }
 321 }
 322
 323 // killough 3/15/98:
 324 //
 325 // A fast function for testing intersections between things and linedefs.
 326
 327 boolean CONSTFUNC ThingIsOnLine(const mobj_t *t, const line_t *l)
 328 {
 329    int dx = l->dx >> FRACBITS;                             // Linedef vector
 330    int dy = l->dy >> FRACBITS;
 331    int a = (l->v1->x >> FRACBITS) - (t->x >> FRACBITS);    // Thing-->v1 vector
 332    int b = (l->v1->y >> FRACBITS) - (t->y >> FRACBITS);
 333    int r = t->radius >> FRACBITS;                          // Thing radius
 334
 335    // First make sure bounding boxes of linedef and thing intersect.
 336    // Leads to quick rejection using only shifts and adds/subs/compares.
 337
 338    if (D_abs(a*2+dx)-D_abs(dx) > r*2 || D_abs(b*2+dy)-D_abs(dy) > r*2)
 339       return 0;
 340
 341    // Next, make sure that at least one thing crosshair intersects linedef's
 342    // extension. Requires only 3-4 multiplications, the rest adds/subs/
 343    // shifts/xors (writing the steps out this way leads to better codegen).
 344
 345    a *= dy;
 346    b *= dx;
 347    a -= b;
 348    b = dx + dy;
 349    b *= r;
 350    if (((a-b)^(a+b)) < 0)
 351       return 1;
 352    dy -= dx;
 353    dy *= r;
 354    b = a+dy;
 355    a -= dy;
 356    return (a^b) < 0;
 357 }
 358
 359 //
 360 // BLOCK MAP ITERATORS
 361 // For each line/thing in the given mapblock,
 362 // call the passed PIT_* function.
 363 // If the function returns false,
 364 // exit with false without checking anything else.
 365 //
 366
 367 //
 368 // P_BlockLinesIterator
 369 // The validcount flags are used to avoid checking lines
 370 // that are marked in multiple mapblocks,
 371 // so increment validcount before the first call
 372 // to P_BlockLinesIterator, then make one or more calls
 373 // to it.
 374 //
 375 // killough 5/3/98: reformatted, cleaned up
 376
 377 boolean P_BlockLinesIterator(int x, int y, boolean func(line_t*))
 378 {
 379    int        offset;
 380    const long *list;   // killough 3/1/98: for removal of blockmap limit
 381
 382    if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
 383       return true;
 384    offset = y*bmapwidth+x;
 385    offset = *(blockmap+offset);
 386    list = blockmaplump+offset;     // original was reading         // phares
 387    // delmiting 0 as linedef 0     // phares
 388
 389    // killough 1/31/98: for compatibility we need to use the old method.
 390    // Most demos go out of sync, and maybe other problems happen, if we
 391    // don't consider linedef 0. For safety this should be qualified.
 392
 393    if (!demo_compatibility) // killough 2/22/98: demo_compatibility check
 394       list++;     // skip 0 starting delimiter                      // phares
 395    for ( ; *list != -1 ; list++)                                   // phares
 396    {
 397       line_t *ld = &lines[*list];
 398       if (ld->validcount == validcount)
 399          continue;       // line has already been checked
 400       ld->validcount = validcount;
 401       if (!func(ld))
 402          return false;
 403    }
 404    return true;  // everything was checked
 405 }
 406
 407 //
 408 // P_BlockThingsIterator
 409 //
 410 // killough 5/3/98: reformatted, cleaned up
 411
 412 boolean P_BlockThingsIterator(int x, int y, boolean func(mobj_t*))
 413 {
 414    mobj_t *mobj;
 415    if (!(x<0 || y<0 || x>=bmapwidth || y>=bmapheight))
 416       for (mobj = blocklinks[y*bmapwidth+x]; mobj; mobj = mobj->bnext)
 417          if (!func(mobj))
 418             return false;
 419    return true;
 420 }
 421
 422 //
 423 // INTERCEPT ROUTINES
 424 //
 425
 426 // 1/11/98 killough: Intercept limit removed
 427 static intercept_t *intercepts, *intercept_p;
 428
 429 // Check for limit and double size if necessary -- killough
 430 static void check_intercept(void)
 431 {
 432    static size_t num_intercepts;
 433    size_t offset = intercept_p - intercepts;
 434    if (offset >= num_intercepts)
 435    {
 436       num_intercepts = num_intercepts ? num_intercepts*2 : 128;
 437       intercepts = realloc(intercepts, sizeof(*intercepts)*num_intercepts);
 438       intercept_p = intercepts + offset;
 439    }
 440 }
 441
 442 divline_t trace;
 443
 444 // PIT_AddLineIntercepts.
 445 // Looks for lines in the given block
 446 // that intercept the given trace
 447 // to add to the intercepts list.
 448 //
 449 // A line is crossed if its endpoints
 450 // are on opposite sides of the trace.
 451 //
 452 // killough 5/3/98: reformatted, cleaned up
 453
 454 boolean PIT_AddLineIntercepts(line_t *ld)
 455 {
 456    int       s1;
 457    int       s2;
 458    fixed_t   frac;
 459    divline_t dl;
 460
 461    // avoid precision problems with two routines
 462    if (trace.dx >  FRACUNIT*16 || trace.dy >  FRACUNIT*16 ||
 463          trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16)
 464    {
 465       s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
 466       s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
 467    }
 468    else
 469    {
 470       s1 = P_PointOnLineSide (trace.x, trace.y, ld);
 471       s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
 472    }
 473
 474    if (s1 == s2)
 475       return true;        // line isn't crossed
 476
 477    // hit the line
 478    P_MakeDivline(ld, &dl);
 479    frac = P_InterceptVector(&trace, &dl);
 480
 481    if (frac < 0)
 482       return true;        // behind source
 483
 484    check_intercept();    // killough
 485
 486    intercept_p->frac = frac;
 487    intercept_p->isaline = true;
 488    intercept_p->d.line = ld;
 489    intercept_p++;
 490
 491    return true;  // continue
 492 }
 493
 494 //
 495 // PIT_AddThingIntercepts
 496 //
 497 // killough 5/3/98: reformatted, cleaned up
 498
 499 boolean PIT_AddThingIntercepts(mobj_t *thing)
 500 {
 501    fixed_t   x1, y1;
 502    fixed_t   x2, y2;
 503    int       s1, s2;
 504    divline_t dl;
 505    fixed_t   frac;
 506
 507    // check a corner to corner crossection for hit
 508    if ((trace.dx ^ trace.dy) > 0)
 509    {
 510       x1 = thing->x - thing->radius;
 511       y1 = thing->y + thing->radius;
 512       x2 = thing->x + thing->radius;
 513       y2 = thing->y - thing->radius;
 514    }
 515    else
 516    {
 517       x1 = thing->x - thing->radius;
 518       y1 = thing->y - thing->radius;
 519       x2 = thing->x + thing->radius;
 520       y2 = thing->y + thing->radius;
 521    }
 522
 523    s1 = P_PointOnDivlineSide (x1, y1, &trace);
 524    s2 = P_PointOnDivlineSide (x2, y2, &trace);
 525
 526    if (s1 == s2)
 527       return true;                // line isn't crossed
 528
 529    dl.x = x1;
 530    dl.y = y1;
 531    dl.dx = x2-x1;
 532    dl.dy = y2-y1;
 533
 534    frac = P_InterceptVector (&trace, &dl);
 535
 536    if (frac < 0)
 537       return true;                // behind source
 538
 539    check_intercept();            // killough
 540
 541    intercept_p->frac = frac;
 542    intercept_p->isaline = false;
 543    intercept_p->d.thing = thing;
 544    intercept_p++;
 545
 546    return true;          // keep going
 547 }
 548
 549 //
 550 // P_TraverseIntercepts
 551 // Returns true if the traverser function returns true
 552 // for all lines.
 553 //
 554 // killough 5/3/98: reformatted, cleaned up
 555
 556 boolean P_TraverseIntercepts(traverser_t func, fixed_t maxfrac)
 557 {
 558    intercept_t *in = NULL;
 559    int count = intercept_p - intercepts;
 560    while (count--)
 561    {
 562       fixed_t dist = INT_MAX;
 563       intercept_t *scan;
 564       for (scan = intercepts; scan < intercept_p; scan++)
 565          if (scan->frac < dist)
 566             dist = (in=scan)->frac;
 567       if (dist > maxfrac)
 568          return true;    // checked everything in range
 569       if (!func(in))
 570          return false;           // don't bother going farther
 571       in->frac = INT_MAX;
 572    }
 573    return true;                  // everything was traversed
 574 }
 575
 576 //
 577 // P_PathTraverse
 578 // Traces a line from x1,y1 to x2,y2,
 579 // calling the traverser function for each.
 580 // Returns true if the traverser function returns true
 581 // for all lines.
 582 //
 583 // killough 5/3/98: reformatted, cleaned up
 584
 585 boolean P_PathTraverse(fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2,
 586                        int flags, boolean trav(intercept_t *))
 587 {
 588    fixed_t xt1, yt1;
 589    fixed_t xt2, yt2;
 590    fixed_t xstep, ystep;
 591    fixed_t partial;
 592    fixed_t xintercept, yintercept;
 593    int     mapx, mapy;
 594    int     mapxstep, mapystep;
 595    int     count;
 596
 597    validcount++;
 598    intercept_p = intercepts;
 599
 600    if (!((x1-bmaporgx)&(MAPBLOCKSIZE-1)))
 601       x1 += FRACUNIT;     // don't side exactly on a line
 602
 603    if (!((y1-bmaporgy)&(MAPBLOCKSIZE-1)))
 604       y1 += FRACUNIT;     // don't side exactly on a line
 605
 606    trace.x = x1;
 607    trace.y = y1;
 608    trace.dx = x2 - x1;
 609    trace.dy = y2 - y1;
 610
 611    x1 -= bmaporgx;
 612    y1 -= bmaporgy;
 613    xt1 = x1>>MAPBLOCKSHIFT;
 614    yt1 = y1>>MAPBLOCKSHIFT;
 615
 616    x2 -= bmaporgx;
 617    y2 -= bmaporgy;
 618    xt2 = x2>>MAPBLOCKSHIFT;
 619    yt2 = y2>>MAPBLOCKSHIFT;
 620
 621    if (xt2 > xt1)
 622    {
 623       mapxstep = 1;
 624       partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
 625       ystep = FixedDiv (y2-y1,D_abs(x2-x1));
 626    }
 627    else
 628       if (xt2 < xt1)
 629       {
 630          mapxstep = -1;
 631          partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
 632          ystep = FixedDiv (y2-y1,D_abs(x2-x1));
 633       }
 634       else
 635       {
 636          mapxstep = 0;
 637          partial = FRACUNIT;
 638          ystep = 256*FRACUNIT;
 639       }
 640
 641    yintercept = (y1>>MAPBTOFRAC) + FixedMul(partial, ystep);
 642
 643    if (yt2 > yt1)
 644    {
 645       mapystep = 1;
 646       partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
 647       xstep = FixedDiv (x2-x1,D_abs(y2-y1));
 648    }
 649    else
 650       if (yt2 < yt1)
 651       {
 652          mapystep = -1;
 653          partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
 654          xstep = FixedDiv (x2-x1,D_abs(y2-y1));
 655       }
 656       else
 657       {
 658          mapystep = 0;
 659          partial = FRACUNIT;
 660          xstep = 256*FRACUNIT;
 661       }
 662
 663    xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
 664
 665    // Step through map blocks.
 666    // Count is present to prevent a round off error
 667    // from skipping the break.
 668
 669    mapx = xt1;
 670    mapy = yt1;
 671
 672    for (count = 0; count < 64; count++)
 673    {
 674       if (flags & PT_ADDLINES)
 675          if (!P_BlockLinesIterator(mapx, mapy,PIT_AddLineIntercepts))
 676             return false; // early out
 677
 678       if (flags & PT_ADDTHINGS)
 679          if (!P_BlockThingsIterator(mapx, mapy,PIT_AddThingIntercepts))
 680             return false; // early out
 681
 682       if (mapx == xt2 && mapy == yt2)
 683          break;
 684
 685       if ((yintercept >> FRACBITS) == mapy)
 686       {
 687          yintercept += ystep;
 688          mapx += mapxstep;
 689       }
 690       else
 691          if ((xintercept >> FRACBITS) == mapx)
 692          {
 693             xintercept += xstep;
 694             mapy += mapystep;
 695          }
 696    }
 697
 698    // go through the sorted list
 699    return P_TraverseIntercepts(trav, FRACUNIT);
 700 }