base/p_sight.c

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