base/p_sight.c

   1 // P_sight.c
   2
   3 #include "doomdef.h"
   4 #include "p_local.h"
   5
   6 /*
   7 ==============================================================================
   8
   9                                                         P_CheckSight
  10
  11 This uses specialized forms of the maputils routines for optimized performance
  12
  13 ==============================================================================
  14 */
  15
  16 fixed_t         sightzstart;                    // eye z of looker
  17 fixed_t         topslope, bottomslope;  // slopes to top and bottom of target
  18
  19 int                     sightcounts[3];
  20
  21 /*
  22 ==============
  23 =
  24 = PTR_SightTraverse
  25 =
  26 ==============
  27 */
  28
  29 boolean         PTR_SightTraverse (intercept_t *in)
  30 {
  31         line_t  *li;
  32         fixed_t slope;
  33
  34         li = in->d.line;
  35
  36 //
  37 // crosses a two sided line
  38 //
  39         P_LineOpening (li);
  40
  41         if (openbottom >= opentop)      // quick test for totally closed doors
  42                 return false;   // stop
  43
  44         if (li->frontsector->floorheight != li->backsector->floorheight)
  45         {
  46                 slope = FixedDiv (openbottom - sightzstart , in->frac);
  47                 if (slope > bottomslope)
  48                         bottomslope = slope;
  49         }
  50
  51         if (li->frontsector->ceilingheight != li->backsector->ceilingheight)
  52         {
  53                 slope = FixedDiv (opentop - sightzstart , in->frac);
  54                 if (slope < topslope)
  55                         topslope = slope;
  56         }
  57
  58         if (topslope <= bottomslope)
  59                 return false;   // stop
  60
  61         return true;    // keep going
  62 }
  63
  64
  65
  66 /*
  67 ==================
  68 =
  69 = P_SightBlockLinesIterator
  70 =
  71 ===================
  72 */
  73
  74 boolean P_SightBlockLinesIterator (int x, int y )
  75 {
  76         int                     offset;
  77         short           *list;
  78         line_t          *ld;
  79         int                     s1, s2;
  80         divline_t       dl;
  81
  82         offset = y*bmapwidth+x;
  83
  84         offset = *(blockmap+offset);
  85
  86         for ( list = blockmaplump+offset ; *list != -1 ; list++)
  87         {
  88                 ld = &lines[*list];
  89                 if (ld->validcount == validcount)
  90                         continue;               // line has already been checked
  91                 ld->validcount = validcount;
  92
  93                 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
  94                 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
  95                 if (s1 == s2)
  96                         continue;               // line isn't crossed
  97                 P_MakeDivline (ld, &dl);
  98                 s1 = P_PointOnDivlineSide (trace.x, trace.y, &dl);
  99                 s2 = P_PointOnDivlineSide (trace.x+trace.dx, trace.y+trace.dy, &dl);
 100                 if (s1 == s2)
 101                         continue;               // line isn't crossed
 102
 103         // try to early out the check
 104                 if (!ld->backsector)
 105                         return false;   // stop checking
 106
 107         // store the line for later intersection testing
 108                 intercept_p->d.line = ld;
 109                 intercept_p++;
 110
 111         }
 112
 113         return true;            // everything was checked
 114 }
 115
 116 /*
 117 ====================
 118 =
 119 = P_SightTraverseIntercepts
 120 =
 121 = Returns true if the traverser function returns true for all lines
 122 ====================
 123 */
 124
 125 boolean P_SightTraverseIntercepts ( void )
 126 {
 127         int                             count;
 128         fixed_t                 dist;
 129         intercept_t             *scan, *in;
 130         divline_t       dl;
 131
 132         count = intercept_p - intercepts;
 133 //
 134 // calculate intercept distance
 135 //
 136         for (scan = intercepts ; scan<intercept_p ; scan++)
 137         {
 138                 P_MakeDivline (scan->d.line, &dl);
 139                 scan->frac = P_InterceptVector (&trace, &dl);
 140         }
 141
 142 //
 143 // go through in order
 144 //
 145         in = 0;                 // shut up compiler warning
 146
 147         while (count--)
 148         {
 149                 dist = MAXINT;
 150                 for (scan = intercepts ; scan<intercept_p ; scan++)
 151                         if (scan->frac < dist)
 152                         {
 153                                 dist = scan->frac;
 154                                 in = scan;
 155                         }
 156
 157                 if ( !PTR_SightTraverse (in) )
 158                         return false;                   // don't bother going farther
 159                 in->frac = MAXINT;
 160         }
 161
 162         return true;            // everything was traversed
 163 }
 164
 165
 166
 167 /*
 168 ==================
 169 =
 170 = P_SightPathTraverse
 171 =
 172 = Traces a line from x1,y1 to x2,y2, calling the traverser function for each
 173 = Returns true if the traverser function returns true for all lines
 174 ==================
 175 */
 176
 177 boolean P_SightPathTraverse (fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2)
 178 {
 179         fixed_t xt1,yt1,xt2,yt2;
 180         fixed_t xstep,ystep;
 181         fixed_t partial;
 182         fixed_t xintercept, yintercept;
 183         int             mapx, mapy, mapxstep, mapystep;
 184         int             count;
 185
 186         validcount++;
 187         intercept_p = intercepts;
 188
 189         if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
 190                 x1 += FRACUNIT;                         // don't side exactly on a line
 191         if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
 192                 y1 += FRACUNIT;                         // don't side exactly on a line
 193         trace.x = x1;
 194         trace.y = y1;
 195         trace.dx = x2 - x1;
 196         trace.dy = y2 - y1;
 197
 198         x1 -= bmaporgx;
 199         y1 -= bmaporgy;
 200         xt1 = x1>>MAPBLOCKSHIFT;
 201         yt1 = y1>>MAPBLOCKSHIFT;
 202
 203         x2 -= bmaporgx;
 204         y2 -= bmaporgy;
 205         xt2 = x2>>MAPBLOCKSHIFT;
 206         yt2 = y2>>MAPBLOCKSHIFT;
 207
 208 // points should never be out of bounds, but check once instead of
 209 // each block
 210         if (xt1<0 || yt1<0 || xt1>=bmapwidth || yt1>=bmapheight
 211         ||  xt2<0 || yt2<0 || xt2>=bmapwidth || yt2>=bmapheight)
 212                 return false;
 213
 214         if (xt2 > xt1)
 215         {
 216                 mapxstep = 1;
 217                 partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
 218                 ystep = FixedDiv (y2-y1,abs(x2-x1));
 219         }
 220         else if (xt2 < xt1)
 221         {
 222                 mapxstep = -1;
 223                 partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
 224                 ystep = FixedDiv (y2-y1,abs(x2-x1));
 225         }
 226         else
 227         {
 228                 mapxstep = 0;
 229                 partial = FRACUNIT;
 230                 ystep = 256*FRACUNIT;
 231         }
 232         yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep);
 233
 234
 235         if (yt2 > yt1)
 236         {
 237                 mapystep = 1;
 238                 partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
 239                 xstep = FixedDiv (x2-x1,abs(y2-y1));
 240         }
 241         else if (yt2 < yt1)
 242         {
 243                 mapystep = -1;
 244                 partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
 245                 xstep = FixedDiv (x2-x1,abs(y2-y1));
 246         }
 247         else
 248         {
 249                 mapystep = 0;
 250                 partial = FRACUNIT;
 251                 xstep = 256*FRACUNIT;
 252         }
 253         xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
 254
 255
 256 //
 257 // step through map blocks
 258 // Count is present to prevent a round off error from skipping the break
 259         mapx = xt1;
 260         mapy = yt1;
 261
 262
 263         for (count = 0 ; count < 64 ; count++)
 264         {
 265                 if (!P_SightBlockLinesIterator (mapx, mapy))
 266                 {
 267 sightcounts[1]++;
 268                         return false;   // early out
 269                 }
 270
 271                 if (mapx == xt2 && mapy == yt2)
 272                         break;
 273
 274                 if ( (yintercept >> FRACBITS) == mapy)
 275                 {
 276                         yintercept += ystep;
 277                         mapx += mapxstep;
 278                 }
 279                 else if ( (xintercept >> FRACBITS) == mapx)
 280                 {
 281                         xintercept += xstep;
 282                         mapy += mapystep;
 283                 }
 284
 285         }
 286
 287
 288 //
 289 // couldn't early out, so go through the sorted list
 290 //
 291 sightcounts[2]++;
 292
 293         return P_SightTraverseIntercepts ( );
 294 }
 295
 296
 297
 298 /*
 299 =====================
 300 =
 301 = P_CheckSight
 302 =
 303 = Returns true if a straight line between t1 and t2 is unobstructed
 304 = look from eyes of t1 to any part of t2
 305 =
 306 =====================
 307 */
 308
 309 boolean P_CheckSight (mobj_t *t1, mobj_t *t2)
 310 {
 311         int             s1, s2;
 312         int             pnum, bytenum, bitnum;
 313
 314 //
 315 // check for trivial rejection
 316 //
 317         s1 = (t1->subsector->sector - sectors);
 318         s2 = (t2->subsector->sector - sectors);
 319         pnum = s1*numsectors + s2;
 320         bytenum = pnum>>3;
 321         bitnum = 1 << (pnum&7);
 322
 323         if (rejectmatrix[bytenum]&bitnum)
 324         {
 325 sightcounts[0]++;
 326                 return false;           // can't possibly be connected
 327         }
 328
 329 //
 330 // check precisely
 331 //
 332         sightzstart = t1->z + t1->height - (t1->height>>2);
 333         topslope = (t2->z+t2->height) - sightzstart;
 334         bottomslope = (t2->z) - sightzstart;
 335
 336         return P_SightPathTraverse ( t1->x, t1->y, t2->x, t2->y );
 337 }
 338
 339
 340