// Emacs style mode select -*- C++ -*- //----------------------------------------------------------------------------- // // $Id: p_sight.c 8 2005-07-23 16:44:57Z fraggle $ // // Copyright(C) 1993-1996 Id Software, Inc. // Copyright(C) 2005 Simon Howard // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License // as published by the Free Software Foundation; either version 2 // of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA // 02111-1307, USA. // // $Log$ // Revision 1.2 2005/07/23 16:44:56 fraggle // Update copyright to GNU GPL // // Revision 1.1.1.1 2005/07/23 16:20:45 fraggle // Initial import // // // DESCRIPTION: // LineOfSight/Visibility checks, uses REJECT Lookup Table. // //----------------------------------------------------------------------------- static const char rcsid[] = "$Id: p_sight.c 8 2005-07-23 16:44:57Z fraggle $"; #include "doomdef.h" #include "i_system.h" #include "p_local.h" // State. #include "r_state.h" // // P_CheckSight // fixed_t sightzstart; // eye z of looker fixed_t topslope; fixed_t bottomslope; // slopes to top and bottom of target divline_t strace; // from t1 to t2 fixed_t t2x; fixed_t t2y; int sightcounts[2]; // // P_DivlineSide // Returns side 0 (front), 1 (back), or 2 (on). // int P_DivlineSide ( fixed_t x, fixed_t y, divline_t* node ) { fixed_t dx; fixed_t dy; fixed_t left; fixed_t right; if (!node->dx) { if (x==node->x) return 2; if (x <= node->x) return node->dy > 0; return node->dy < 0; } if (!node->dy) { if (x==node->y) return 2; if (y <= node->y) return node->dx < 0; return node->dx > 0; } dx = (x - node->x); dy = (y - node->y); left = (node->dy>>FRACBITS) * (dx>>FRACBITS); right = (dy>>FRACBITS) * (node->dx>>FRACBITS); if (right < left) return 0; // front side if (left == right) return 2; return 1; // back side } // // P_InterceptVector2 // Returns the fractional intercept point // along the first divline. // This is only called by the addthings and addlines traversers. // fixed_t P_InterceptVector2 ( divline_t* v2, divline_t* v1 ) { fixed_t frac; fixed_t num; fixed_t den; den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy); if (den == 0) return 0; // I_Error ("P_InterceptVector: parallel"); num = FixedMul ( (v1->x - v2->x)>>8 ,v1->dy) + FixedMul ( (v2->y - v1->y)>>8 , v1->dx); frac = FixedDiv (num , den); return frac; } // // P_CrossSubsector // Returns true // if strace crosses the given subsector successfully. // boolean P_CrossSubsector (int num) { seg_t* seg; line_t* line; int s1; int s2; int count; subsector_t* sub; sector_t* front; sector_t* back; fixed_t opentop; fixed_t openbottom; divline_t divl; vertex_t* v1; vertex_t* v2; fixed_t frac; fixed_t slope; #ifdef RANGECHECK if (num>=numsubsectors) I_Error ("P_CrossSubsector: ss %i with numss = %i", num, numsubsectors); #endif sub = &subsectors[num]; // check lines count = sub->numlines; seg = &segs[sub->firstline]; for ( ; count ; seg++, count--) { line = seg->linedef; // allready checked other side? if (line->validcount == validcount) continue; line->validcount = validcount; v1 = line->v1; v2 = line->v2; s1 = P_DivlineSide (v1->x,v1->y, &strace); s2 = P_DivlineSide (v2->x, v2->y, &strace); // line isn't crossed? if (s1 == s2) continue; divl.x = v1->x; divl.y = v1->y; divl.dx = v2->x - v1->x; divl.dy = v2->y - v1->y; s1 = P_DivlineSide (strace.x, strace.y, &divl); s2 = P_DivlineSide (t2x, t2y, &divl); // line isn't crossed? if (s1 == s2) continue; // stop because it is not two sided anyway // might do this after updating validcount? if ( !(line->flags & ML_TWOSIDED) ) return false; // crosses a two sided line front = seg->frontsector; back = seg->backsector; // no wall to block sight with? if (front->floorheight == back->floorheight && front->ceilingheight == back->ceilingheight) continue; // possible occluder // because of ceiling height differences if (front->ceilingheight < back->ceilingheight) opentop = front->ceilingheight; else opentop = back->ceilingheight; // because of ceiling height differences if (front->floorheight > back->floorheight) openbottom = front->floorheight; else openbottom = back->floorheight; // quick test for totally closed doors if (openbottom >= opentop) return false; // stop frac = P_InterceptVector2 (&strace, &divl); if (front->floorheight != back->floorheight) { slope = FixedDiv (openbottom - sightzstart , frac); if (slope > bottomslope) bottomslope = slope; } if (front->ceilingheight != back->ceilingheight) { slope = FixedDiv (opentop - sightzstart , frac); if (slope < topslope) topslope = slope; } if (topslope <= bottomslope) return false; // stop } // passed the subsector ok return true; } // // P_CrossBSPNode // Returns true // if strace crosses the given node successfully. // boolean P_CrossBSPNode (int bspnum) { node_t* bsp; int side; if (bspnum & NF_SUBSECTOR) { if (bspnum == -1) return P_CrossSubsector (0); else return P_CrossSubsector (bspnum&(~NF_SUBSECTOR)); } bsp = &nodes[bspnum]; // decide which side the start point is on side = P_DivlineSide (strace.x, strace.y, (divline_t *)bsp); if (side == 2) side = 0; // an "on" should cross both sides // cross the starting side if (!P_CrossBSPNode (bsp->children[side]) ) return false; // the partition plane is crossed here if (side == P_DivlineSide (t2x, t2y,(divline_t *)bsp)) { // the line doesn't touch the other side return true; } // cross the ending side return P_CrossBSPNode (bsp->children[side^1]); } // // P_CheckSight // Returns true // if a straight line between t1 and t2 is unobstructed. // Uses REJECT. // boolean P_CheckSight ( mobj_t* t1, mobj_t* t2 ) { int s1; int s2; int pnum; int bytenum; int bitnum; // First check for trivial rejection. // Determine subsector entries in REJECT table. s1 = (t1->subsector->sector - sectors); s2 = (t2->subsector->sector - sectors); pnum = s1*numsectors + s2; bytenum = pnum>>3; bitnum = 1 << (pnum&7); // Check in REJECT table. if (rejectmatrix[bytenum]&bitnum) { sightcounts[0]++; // can't possibly be connected return false; } // An unobstructed LOS is possible. // Now look from eyes of t1 to any part of t2. sightcounts[1]++; validcount++; sightzstart = t1->z + t1->height - (t1->height>>2); topslope = (t2->z+t2->height) - sightzstart; bottomslope = (t2->z) - sightzstart; strace.x = t1->x; strace.y = t1->y; t2x = t2->x; t2y = t2->y; strace.dx = t2->x - t1->x; strace.dy = t2->y - t1->y; // the head node is the last node output return P_CrossBSPNode (numnodes-1); }