base/p_sight.c

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