1 /* Emacs style mode select -*- C++ -*-
2 *-----------------------------------------------------------------------------
3 *
4 *
5 * PrBoom: a Doom port merged with LxDoom and LSDLDoom
6 * based on BOOM, a modified and improved DOOM engine
7 * Copyright (C) 1999 by
8 * id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman
9 * Copyright (C) 1999-2000 by
10 * Jess Haas, Nicolas Kalkhof, Colin Phipps, Florian Schulze
11 * Copyright 2005, 2006 by
12 * Florian Schulze, Colin Phipps, Neil Stevens, Andrey Budko
13 *
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * as published by the Free Software Foundation; either version 2
17 * of the License, or (at your option) any later version.
18 *
19 * This program is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License
25 * along with this program; if not, write to the Free Software
26 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
27 * 02111-1307, USA.
28 *
29 * DESCRIPTION:
30 * LineOfSight/Visibility checks, uses REJECT Lookup Table.
31 *
32 *-----------------------------------------------------------------------------*/
33
34 #include "doomstat.h"
35 #include "r_main.h"
36 #include "p_map.h"
37 #include "p_maputl.h"
38 #include "p_setup.h"
39 #include "m_bbox.h"
40 #include "lprintf.h"
41
42 //
43 // P_CheckSight
44 //
45 // killough 4/19/98:
46 // Convert LOS info to struct for reentrancy and efficiency of data locality
47
48 typedef struct {
49 fixed_t sightzstart, t2x, t2y; // eye z of looker
50 divline_t strace; // from t1 to t2
51 fixed_t topslope, bottomslope; // slopes to top and bottom of target
52 fixed_t bbox[4];
53 fixed_t maxz,minz; // cph - z optimisations for 2sided lines
54 } los_t;
55
56 static los_t los; // cph - made static
57
58 //
59 // P_DivlineSide
60 // Returns side 0 (front), 1 (back), or 2 (on).
61 //
62 // killough 4/19/98: made static, cleaned up
63
P_DivlineSide(fixed_t x,fixed_t y,const divline_t * node)64 static INLINE int P_DivlineSide(fixed_t x, fixed_t y, const divline_t *node)
65 {
66 fixed_t left, right;
67 return
68 !node->dx ? x == node->x ? 2 : x <= node->x ? node->dy > 0 : node->dy < 0 :
69 !node->dy ? ( compatibility_level < prboom_4_compatibility ? x : y) == node->y ? 2 : y <= node->y ? node->dx < 0 : node->dx > 0 :
70 (right = ((y - node->y) >> FRACBITS) * (node->dx >> FRACBITS)) <
71 (left = ((x - node->x) >> FRACBITS) * (node->dy >> FRACBITS)) ? 0 :
72 right == left ? 2 : 1;
73 }
74
75 //
76 // P_CrossSubsector
77 // Returns TRUE
78 // if strace crosses the given subsector successfully.
79 //
80 // killough 4/19/98: made static and cleaned up
81
P_CrossSubsector(int num)82 static dbool P_CrossSubsector(int num)
83 {
84 seg_t *seg = segs + subsectors[num].firstline;
85 int count;
86 fixed_t opentop = 0, openbottom = 0;
87 const sector_t *front = NULL, *back = NULL;
88
89 for (count = subsectors[num].numlines; --count >= 0; seg++) { // check lines
90 line_t *line = seg->linedef;
91 divline_t divl;
92
93 if(!line) // figgi -- skip minisegs
94 continue;
95
96 // allready checked other side?
97 if (line->validcount == validcount)
98 continue;
99
100 line->validcount = validcount;
101
102 /* OPTIMIZE: killough 4/20/98: Added quick bounding-box rejection test
103 * cph - this is causing demo desyncs on original Doom demos.
104 * Who knows why. Exclude test for those.
105 */
106 if (!demo_compatibility)
107 if (line->bbox[BOXLEFT ] > los.bbox[BOXRIGHT ] ||
108 line->bbox[BOXRIGHT ] < los.bbox[BOXLEFT ] ||
109 line->bbox[BOXBOTTOM] > los.bbox[BOXTOP ] ||
110 line->bbox[BOXTOP] < los.bbox[BOXBOTTOM])
111 continue;
112
113 // cph - do what we can before forced to check intersection
114 if (line->flags & ML_TWOSIDED) {
115
116 // no wall to block sight with?
117 if ((front = seg->frontsector)->floorheight ==
118 (back = seg->backsector)->floorheight &&
119 front->ceilingheight == back->ceilingheight)
120 continue;
121
122 // possible occluder
123 // because of ceiling height differences
124 opentop = front->ceilingheight < back->ceilingheight ?
125 front->ceilingheight : back->ceilingheight ;
126
127 // because of floor height differences
128 openbottom = front->floorheight > back->floorheight ?
129 front->floorheight : back->floorheight ;
130
131 // cph - reject if does not intrude in the z-space of the possible LOS
132 if ((opentop >= los.maxz) && (openbottom <= los.minz))
133 continue;
134 }
135
136 { // Forget this line if it doesn't cross the line of sight
137 const vertex_t *v1,*v2;
138
139 v1 = line->v1;
140 v2 = line->v2;
141
142 if (P_DivlineSide(v1->x, v1->y, &los.strace) ==
143 P_DivlineSide(v2->x, v2->y, &los.strace))
144 continue;
145
146 divl.dx = v2->x - (divl.x = v1->x);
147 divl.dy = v2->y - (divl.y = v1->y);
148
149 // line isn't crossed?
150 if (P_DivlineSide(los.strace.x, los.strace.y, &divl) ==
151 P_DivlineSide(los.t2x, los.t2y, &divl))
152 continue;
153 }
154
155 // cph - if bottom >= top or top < minz or bottom > maxz then it must be
156 // solid wrt this LOS
157 if (!(line->flags & ML_TWOSIDED) || (openbottom >= opentop) ||
158 (opentop < los.minz) || (openbottom > los.maxz))
159 return FALSE;
160
161 { // crosses a two sided line
162 /* cph 2006/07/15 - oops, we missed this in 2.4.0 & .1;
163 * use P_InterceptVector2 for those compat levels only. */
164 fixed_t frac = (compatibility_level == prboom_5_compatibility || compatibility_level == prboom_6_compatibility) ?
165 P_InterceptVector2(&los.strace, &divl) :
166 P_InterceptVector(&los.strace, &divl);
167
168 if (front->floorheight != back->floorheight) {
169 fixed_t slope = FixedDiv(openbottom - los.sightzstart , frac);
170 if (slope > los.bottomslope)
171 los.bottomslope = slope;
172 }
173
174 if (front->ceilingheight != back->ceilingheight)
175 {
176 fixed_t slope = FixedDiv(opentop - los.sightzstart , frac);
177 if (slope < los.topslope)
178 los.topslope = slope;
179 }
180
181 if (los.topslope <= los.bottomslope)
182 return FALSE; // stop
183 }
184 }
185 // passed the subsector ok
186 return TRUE;
187 }
188
189 //
190 // P_CrossBSPNode
191 // Returns TRUE
192 // if strace crosses the given node successfully.
193 //
194 // killough 4/20/98: rewritten to remove tail recursion, clean up, and optimize
195 // cph - Made to use R_PointOnSide instead of P_DivlineSide, since the latter
196 // could return 2 which was ambigous, and the former is
197 // better optimised; also removes two casts :-)
198
P_CrossBSPNode_LxDoom(int bspnum)199 static dbool P_CrossBSPNode_LxDoom(int bspnum)
200 {
201 while (!(bspnum & NF_SUBSECTOR))
202 {
203 register const node_t *bsp = nodes + bspnum;
204 int side,side2;
205 side = R_PointOnSide(los.strace.x, los.strace.y, bsp);
206 side2 = R_PointOnSide(los.t2x, los.t2y, bsp);
207 if (side == side2)
208 bspnum = bsp->children[side]; // doesn't touch the other side
209 else // the partition plane is crossed here
210 if (!P_CrossBSPNode_LxDoom(bsp->children[side]))
211 return 0; // cross the starting side
212 else
213 bspnum = bsp->children[side^1]; // cross the ending side
214 }
215 return P_CrossSubsector(bspnum == -1 ? 0 : bspnum & ~NF_SUBSECTOR);
216 }
217
P_CrossBSPNode_PrBoom(int bspnum)218 static dbool P_CrossBSPNode_PrBoom(int bspnum)
219 {
220 while (!(bspnum & NF_SUBSECTOR))
221 {
222 register const node_t *bsp = nodes + bspnum;
223 int side,side2;
224 side = P_DivlineSide(los.strace.x,los.strace.y,(const divline_t *)bsp)&1;
225 side2= P_DivlineSide(los.t2x, los.t2y, (const divline_t *) bsp);
226 if (side == side2)
227 bspnum = bsp->children[side]; // doesn't touch the other side
228 else // the partition plane is crossed here
229 if (!P_CrossBSPNode_PrBoom(bsp->children[side]))
230 return 0; // cross the starting side
231 else
232 bspnum = bsp->children[side^1]; // cross the ending side
233 }
234 return P_CrossSubsector(bspnum == -1 ? 0 : bspnum & ~NF_SUBSECTOR);
235 }
236
237 /* proff - Moved the compatibility check outside the functions
238 * this gives a slight speedup
239 */
P_CrossBSPNode(int bspnum)240 static dbool P_CrossBSPNode(int bspnum)
241 {
242 /* cph - LxDoom used some R_* funcs here */
243 if (compatibility_level == lxdoom_1_compatibility)
244 return P_CrossBSPNode_LxDoom(bspnum);
245 else
246 return P_CrossBSPNode_PrBoom(bspnum);
247 }
248
249 //
250 // P_CheckSight
251 // Returns TRUE
252 // if a straight line between t1 and t2 is unobstructed.
253 // Uses REJECT.
254 //
255 // killough 4/20/98: cleaned up, made to use new LOS struct
256
P_CheckSight(mobj_t * t1,mobj_t * t2)257 dbool P_CheckSight(mobj_t *t1, mobj_t *t2)
258 {
259 const sector_t *s1 = t1->subsector->sector;
260 const sector_t *s2 = t2->subsector->sector;
261 int pnum = (s1-sectors)*numsectors + (s2-sectors);
262
263 // First check for trivial rejection.
264 // Determine subsector entries in REJECT table.
265 //
266 // Check in REJECT table.
267
268 if (rejectmatrix[pnum>>3] & (1 << (pnum&7))) // can't possibly be connected
269 return FALSE;
270
271 // killough 4/19/98: make fake floors and ceilings block monster view
272
273 if ((s1->heightsec != -1 &&
274 ((t1->z + t1->height <= sectors[s1->heightsec].floorheight &&
275 t2->z >= sectors[s1->heightsec].floorheight) ||
276 (t1->z >= sectors[s1->heightsec].ceilingheight &&
277 t2->z + t1->height <= sectors[s1->heightsec].ceilingheight)))
278 ||
279 (s2->heightsec != -1 &&
280 ((t2->z + t2->height <= sectors[s2->heightsec].floorheight &&
281 t1->z >= sectors[s2->heightsec].floorheight) ||
282 (t2->z >= sectors[s2->heightsec].ceilingheight &&
283 t1->z + t2->height <= sectors[s2->heightsec].ceilingheight))))
284 return FALSE;
285
286 /* killough 11/98: shortcut for melee situations
287 * same subsector? obviously visible
288 * cph - compatibility optioned for demo sync, cf HR06-UV.LMP */
289 if ((t1->subsector == t2->subsector) &&
290 (compatibility_level >= mbf_compatibility))
291 return TRUE;
292
293 // An unobstructed LOS is possible.
294 // Now look from eyes of t1 to any part of t2.
295
296 validcount++;
297
298 los.topslope = (los.bottomslope = t2->z - (los.sightzstart =
299 t1->z + t1->height -
300 (t1->height>>2))) + t2->height;
301 los.strace.dx = (los.t2x = t2->x) - (los.strace.x = t1->x);
302 los.strace.dy = (los.t2y = t2->y) - (los.strace.y = t1->y);
303
304 if (t1->x > t2->x)
305 los.bbox[BOXRIGHT] = t1->x, los.bbox[BOXLEFT] = t2->x;
306 else
307 los.bbox[BOXRIGHT] = t2->x, los.bbox[BOXLEFT] = t1->x;
308
309 if (t1->y > t2->y)
310 los.bbox[BOXTOP] = t1->y, los.bbox[BOXBOTTOM] = t2->y;
311 else
312 los.bbox[BOXTOP] = t2->y, los.bbox[BOXBOTTOM] = t1->y;
313
314 /* cph - calculate min and max z of the potential line of sight
315 * For old demos, we disable this optimisation by setting them to
316 * the extremes */
317 switch (compatibility_level) {
318 case lxdoom_1_compatibility:
319 if (los.sightzstart < t2->z) {
320 los.maxz = t2->z + t2->height; los.minz = los.sightzstart;
321 } else if (los.sightzstart > t2->z + t2->height) {
322 los.maxz = los.sightzstart; los.minz = t2->z;
323 } else {
324 los.maxz = t2->z + t2->height; los.minz = t2->z;
325 }
326 break;
327 default:
328 los.maxz = INT_MAX; los.minz = INT_MIN;
329 }
330
331 // the head node is the last node output
332 return P_CrossBSPNode(numnodes-1);
333 }
334