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