Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

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