Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 350 lines (280 sloc) 7.176 kb
4eb368a @tbradshaw The DOOM sources as originally released on December 23, 1997
tbradshaw authored
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
Something went wrong with that request. Please try again.