sys/src/games/doom/p_sight.c

   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 //      LineOfSight/Visibility checks, uses REJECT Lookup Table.
  21 //
  22 //-----------------------------------------------------------------------------
  23
  24 static const char
  25 rcsid[] = "$Id: p_sight.c,v 1.3 1997/01/28 22:08:28 b1 Exp $";
  26
  27
  28 #include "doomdef.h"
  29
  30 #include "i_system.h"
  31 #include "p_local.h"
  32
  33 // State.
  34 #include "r_state.h"
  35
  36 //
  37 // P_CheckSight
  38 //
  39 fixed_t         sightzstart;            // eye z of looker
  40 fixed_t         topslope;
  41 fixed_t         bottomslope;            // slopes to top and bottom of target
  42
  43 divline_t       strace;                 // from t1 to t2
  44 fixed_t         t2x;
  45 fixed_t         t2y;
  46
  47 int             sightcounts[2];
  48
  49
  50 //
  51 // P_DivlineSide
  52 // Returns side 0 (front), 1 (back), or 2 (on).
  53 //
  54 int
  55 P_DivlineSide
  56 ( fixed_t       x,
  57   fixed_t       y,
  58   divline_t*    node )
  59 {
  60     fixed_t     dx;
  61     fixed_t     dy;
  62     fixed_t     left;
  63     fixed_t     right;
  64
  65     if (!node->dx)
  66     {
  67         if (x==node->x)
  68             return 2;
  69
  70         if (x <= node->x)
  71             return node->dy > 0;
  72
  73         return node->dy < 0;
  74     }
  75
  76     if (!node->dy)
  77     {
  78         if (x==node->y)
  79             return 2;
  80
  81         if (y <= node->y)
  82             return node->dx < 0;
  83
  84         return node->dx > 0;
  85     }
  86
  87     dx = (x - node->x);
  88     dy = (y - node->y);
  89
  90     left =  (node->dy>>FRACBITS) * (dx>>FRACBITS);
  91     right = (dy>>FRACBITS) * (node->dx>>FRACBITS);
  92
  93     if (right < left)
  94         return 0;       // front side
  95
  96     if (left == right)
  97         return 2;
  98     return 1;           // back side
  99 }
 100
 101
 102 //
 103 // P_InterceptVector2
 104 // Returns the fractional intercept point
 105 // along the first divline.
 106 // This is only called by the addthings and addlines traversers.
 107 //
 108 fixed_t
 109 P_InterceptVector2
 110 ( divline_t*    v2,
 111   divline_t*    v1 )
 112 {
 113     fixed_t     frac;
 114     fixed_t     num;
 115     fixed_t     den;
 116
 117     den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
 118
 119     if (den == 0)
 120         return 0;
 121     //  I_Error ("P_InterceptVector: parallel");
 122
 123     num = FixedMul ( (v1->x - v2->x)>>8 ,v1->dy) +
 124         FixedMul ( (v2->y - v1->y)>>8 , v1->dx);
 125     frac = FixedDiv (num , den);
 126
 127     return frac;
 128 }
 129
 130 //
 131 // P_CrossSubsector
 132 // Returns true
 133 //  if strace crosses the given subsector successfully.
 134 //
 135 boolean P_CrossSubsector (int num)
 136 {
 137     seg_t*              seg;
 138     line_t*             line;
 139     int                 s1;
 140     int                 s2;
 141     int                 count;
 142     subsector_t*        sub;
 143     sector_t*           front;
 144     sector_t*           back;
 145     fixed_t             opentop;
 146     fixed_t             openbottom;
 147     divline_t           divl;
 148     vertex_t*           v1;
 149     vertex_t*           v2;
 150     fixed_t             frac;
 151     fixed_t             slope;
 152
 153 #ifdef RANGECHECK
 154     if (num>=numsubsectors)
 155         I_Error ("P_CrossSubsector: ss %i with numss = %i",
 156                  num,
 157                  numsubsectors);
 158 #endif
 159
 160     sub = &subsectors[num];
 161
 162     // check lines
 163     count = sub->numlines;
 164     seg = &segs[sub->firstline];
 165
 166     for ( ; count ; seg++, count--)
 167     {
 168         line = seg->linedef;
 169
 170         // allready checked other side?
 171         if (line->validcount == validcount)
 172             continue;
 173
 174         line->validcount = validcount;
 175
 176         v1 = line->v1;
 177         v2 = line->v2;
 178         s1 = P_DivlineSide (v1->x,v1->y, &strace);
 179         s2 = P_DivlineSide (v2->x, v2->y, &strace);
 180
 181         // line isn't crossed?
 182         if (s1 == s2)
 183             continue;
 184
 185         divl.x = v1->x;
 186         divl.y = v1->y;
 187         divl.dx = v2->x - v1->x;
 188         divl.dy = v2->y - v1->y;
 189         s1 = P_DivlineSide (strace.x, strace.y, &divl);
 190         s2 = P_DivlineSide (t2x, t2y, &divl);
 191
 192         // line isn't crossed?
 193         if (s1 == s2)
 194             continue;
 195
 196         // stop because it is not two sided anyway
 197         // might do this after updating validcount?
 198         if ( !(line->flags & ML_TWOSIDED) )
 199             return false;
 200
 201         // crosses a two sided line
 202         front = seg->frontsector;
 203         back = seg->backsector;
 204
 205         // no wall to block sight with?
 206         if (front->floorheight == back->floorheight
 207             && front->ceilingheight == back->ceilingheight)
 208             continue;
 209
 210         // possible occluder
 211         // because of ceiling height differences
 212         if (front->ceilingheight < back->ceilingheight)
 213             opentop = front->ceilingheight;
 214         else
 215             opentop = back->ceilingheight;
 216
 217         // because of ceiling height differences
 218         if (front->floorheight > back->floorheight)
 219             openbottom = front->floorheight;
 220         else
 221             openbottom = back->floorheight;
 222
 223         // quick test for totally closed doors
 224         if (openbottom >= opentop)
 225             return false;               // stop
 226
 227         frac = P_InterceptVector2 (&strace, &divl);
 228
 229         if (front->floorheight != back->floorheight)
 230         {
 231             slope = FixedDiv (openbottom - sightzstart , frac);
 232             if (slope > bottomslope)
 233                 bottomslope = slope;
 234         }
 235
 236         if (front->ceilingheight != back->ceilingheight)
 237         {
 238             slope = FixedDiv (opentop - sightzstart , frac);
 239             if (slope < topslope)
 240                 topslope = slope;
 241         }
 242
 243         if (topslope <= bottomslope)
 244             return false;               // stop
 245     }
 246     // passed the subsector ok
 247     return true;
 248 }
 249
 250
 251
 252 //
 253 // P_CrossBSPNode
 254 // Returns true
 255 //  if strace crosses the given node successfully.
 256 //
 257 boolean P_CrossBSPNode (int bspnum)
 258 {
 259     node_t*     bsp;
 260     int         side;
 261
 262     if (bspnum & NF_SUBSECTOR)
 263     {
 264         if (bspnum == -1)
 265             return P_CrossSubsector (0);
 266         else
 267             return P_CrossSubsector (bspnum&(~NF_SUBSECTOR));
 268     }
 269
 270     bsp = &nodes[bspnum];
 271
 272     // decide which side the start point is on
 273     side = P_DivlineSide (strace.x, strace.y, (divline_t *)bsp);
 274     if (side == 2)
 275         side = 0;       // an "on" should cross both sides
 276
 277     // cross the starting side
 278     if (!P_CrossBSPNode (bsp->children[side]) )
 279         return false;
 280
 281     // the partition plane is crossed here
 282     if (side == P_DivlineSide (t2x, t2y,(divline_t *)bsp))
 283     {
 284         // the line doesn't touch the other side
 285         return true;
 286     }
 287
 288     // cross the ending side
 289     return P_CrossBSPNode (bsp->children[side^1]);
 290 }
 291
 292
 293 //
 294 // P_CheckSight
 295 // Returns true
 296 //  if a straight line between t1 and t2 is unobstructed.
 297 // Uses REJECT.
 298 //
 299 boolean
 300 P_CheckSight
 301 ( mobj_t*       t1,
 302   mobj_t*       t2 )
 303 {
 304     int         s1;
 305     int         s2;
 306     int         pnum;
 307     int         bytenum;
 308     int         bitnum;
 309
 310     // First check for trivial rejection.
 311
 312     // Determine subsector entries in REJECT table.
 313     s1 = (t1->subsector->sector - sectors);
 314     s2 = (t2->subsector->sector - sectors);
 315     pnum = s1*numsectors + s2;
 316     bytenum = pnum>>3;
 317     bitnum = 1 << (pnum&7);
 318
 319     // Check in REJECT table.
 320     if (rejectmatrix[bytenum]&bitnum)
 321     {
 322         sightcounts[0]++;
 323
 324         // can't possibly be connected
 325         return false;
 326     }
 327
 328     // An unobstructed LOS is possible.
 329     // Now look from eyes of t1 to any part of t2.
 330     sightcounts[1]++;
 331
 332     validcount++;
 333
 334     sightzstart = t1->z + t1->height - (t1->height>>2);
 335     topslope = (t2->z+t2->height) - sightzstart;
 336     bottomslope = (t2->z) - sightzstart;
 337
 338     strace.x = t1->x;
 339     strace.y = t1->y;
 340     t2x = t2->x;
 341     t2y = t2->y;
 342     strace.dx = t2->x - t1->x;
 343     strace.dy = t2->y - t1->y;
 344
 345     // the head node is the last node output
 346     return P_CrossBSPNode (numnodes-1);
 347 }
 348
 349