1 // SONIC ROBO BLAST 2
2 //-----------------------------------------------------------------------------
3 // Copyright (C) 1993-1996 by id Software, Inc.
4 // Copyright (C) 1998-2000 by DooM Legacy Team.
5 // Copyright (C) 1999-2020 by Sonic Team Junior.
6 //
7 // This program is free software distributed under the
8 // terms of the GNU General Public License, version 2.
9 // See the 'LICENSE' file for more details.
10 //-----------------------------------------------------------------------------
11 /// \file p_maputl.c
12 /// \brief Movement/collision utility functions, as used by functions in p_map.c
13 /// Blockmap iterator functions, and some PIT_* functions to use for iteration
14
15 #include "doomdef.h"
16 #include "doomstat.h"
17
18 #include "p_local.h"
19 #include "r_main.h"
20 #include "r_data.h"
21 #include "r_textures.h"
22 #include "p_maputl.h"
23 #include "p_polyobj.h"
24 #include "p_slopes.h"
25 #include "z_zone.h"
26
27 //
28 // P_AproxDistance
29 // Gives an estimation of distance (not exact)
30 //
P_AproxDistance(fixed_t dx,fixed_t dy)31 fixed_t P_AproxDistance(fixed_t dx, fixed_t dy)
32 {
33 dx = abs(dx);
34 dy = abs(dy);
35 if (dx < dy)
36 return dx + dy - (dx>>1);
37 return dx + dy - (dy>>1);
38 }
39
40 //
41 // P_ClosestPointOnLine
42 // Finds the closest point on a given line to the supplied point
43 //
P_ClosestPointOnLine(fixed_t x,fixed_t y,line_t * line,vertex_t * result)44 void P_ClosestPointOnLine(fixed_t x, fixed_t y, line_t *line, vertex_t *result)
45 {
46 fixed_t startx = line->v1->x;
47 fixed_t starty = line->v1->y;
48 fixed_t dx = line->dx;
49 fixed_t dy = line->dy;
50
51 // Determine t (the length of the vector from �Line[0]� to �p�)
52 fixed_t cx, cy;
53 fixed_t vx, vy;
54 fixed_t magnitude;
55 fixed_t t;
56
57 //Sub (p, &Line[0], &c);
58 cx = x - startx;
59 cy = y - starty;
60
61 //Sub (&Line[1], &Line[0], &V);
62 vx = dx;
63 vy = dy;
64
65 //Normalize (&V, &V);
66 magnitude = R_PointToDist2(line->v2->x, line->v2->y, startx, starty);
67 vx = FixedDiv(vx, magnitude);
68 vy = FixedDiv(vy, magnitude);
69
70 t = (FixedMul(vx, cx) + FixedMul(vy, cy));
71
72 // Return the point between �Line[0]� and �Line[1]�
73 vx = FixedMul(vx, t);
74 vy = FixedMul(vy, t);
75
76 //Add (&Line[0], &V, out);
77 result->x = startx + vx;
78 result->y = starty + vy;
79 return;
80 }
81
82 /// Similar to FV3_ClosestPointOnLine() except it actually works.
P_ClosestPointOnLine3D(const vector3_t * p,const vector3_t * Line,vector3_t * result)83 void P_ClosestPointOnLine3D(const vector3_t *p, const vector3_t *Line, vector3_t *result)
84 {
85 const vector3_t* v1 = &Line[0];
86 const vector3_t* v2 = &Line[1];
87 vector3_t c, V, n;
88 fixed_t t, d;
89 FV3_SubEx(v2, v1, &V);
90 FV3_SubEx(p, v1, &c);
91
92 d = R_PointToDist2(0, v2->z, R_PointToDist2(v2->x, v2->y, v1->x, v1->y), v1->z);
93 FV3_Copy(&n, &V);
94 FV3_Divide(&n, d);
95
96 t = FV3_Dot(&n, &c);
97
98 // Set closest point to the end if it extends past -Red
99 if (t <= 0)
100 {
101 FV3_Copy(result, v1);
102 return;
103 }
104 else if (t >= d)
105 {
106 FV3_Copy(result, v2);
107 return;
108 }
109
110 FV3_Mul(&n, t);
111
112 FV3_AddEx(v1, &n, result);
113 return;
114 }
115
116 //
117 // P_PointOnLineSide
118 // Returns 0 or 1
119 //
P_PointOnLineSide(fixed_t x,fixed_t y,line_t * line)120 INT32 P_PointOnLineSide(fixed_t x, fixed_t y, line_t *line)
121 {
122 const vertex_t *v1 = line->v1;
123 fixed_t dx, dy, left, right;
124
125 if (!line->dx)
126 {
127 if (x <= v1->x)
128 return (line->dy > 0);
129
130 return (line->dy < 0);
131 }
132 if (!line->dy)
133 {
134 if (y <= v1->y)
135 return (line->dx < 0);
136
137 return (line->dx > 0);
138 }
139
140 dx = (x - v1->x);
141 dy = (y - v1->y);
142
143 left = FixedMul(line->dy>>FRACBITS, dx);
144 right = FixedMul(dy, line->dx>>FRACBITS);
145
146 if (right < left)
147 return 0; // front side
148 return 1; // back side
149 }
150
151 //
152 // P_BoxOnLineSide
153 // Considers the line to be infinite
154 // Returns side 0 or 1, -1 if box crosses the line.
155 //
P_BoxOnLineSide(fixed_t * tmbox,line_t * ld)156 INT32 P_BoxOnLineSide(fixed_t *tmbox, line_t *ld)
157 {
158 INT32 p1, p2;
159
160 switch (ld->slopetype)
161 {
162 case ST_HORIZONTAL:
163 p1 = tmbox[BOXTOP] > ld->v1->y;
164 p2 = tmbox[BOXBOTTOM] > ld->v1->y;
165 if (ld->dx < 0)
166 {
167 p1 ^= 1;
168 p2 ^= 1;
169 }
170 break;
171
172 case ST_VERTICAL:
173 p1 = tmbox[BOXRIGHT] < ld->v1->x;
174 p2 = tmbox[BOXLEFT] < ld->v1->x;
175 if (ld->dy < 0)
176 {
177 p1 ^= 1;
178 p2 ^= 1;
179 }
180 break;
181
182 case ST_POSITIVE:
183 p1 = P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXTOP], ld);
184 p2 = P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld);
185 break;
186
187 case ST_NEGATIVE:
188 p1 = P_PointOnLineSide(tmbox[BOXRIGHT], tmbox[BOXTOP], ld);
189 p2 = P_PointOnLineSide(tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld);
190 break;
191
192 default:
193 I_Error("P_BoxOnLineSide: unknown slopetype %d\n", ld->slopetype);
194 return -1;
195 }
196
197 if (p1 == p2)
198 return p1;
199 return -1;
200 }
201
202 //
203 // P_PointOnDivlineSide
204 // Returns 0 or 1.
205 //
P_PointOnDivlineSide(fixed_t x,fixed_t y,divline_t * line)206 static INT32 P_PointOnDivlineSide(fixed_t x, fixed_t y, divline_t *line)
207 {
208 fixed_t dx, dy, left, right;
209
210 if (!line->dx)
211 {
212 if (x <= line->x)
213 return line->dy > 0;
214
215 return line->dy < 0;
216 }
217 if (!line->dy)
218 {
219 if (y <= line->y)
220 return line->dx < 0;
221
222 return line->dx > 0;
223 }
224
225 dx = (x - line->x);
226 dy = (y - line->y);
227
228 // try to quickly decide by looking at sign bits
229 if ((line->dy ^ line->dx ^ dx ^ dy) & 0x80000000)
230 {
231 if ((line->dy ^ dx) & 0x80000000)
232 return 1; // left is negative
233 return 0;
234 }
235
236 left = FixedMul(line->dy>>8, dx>>8);
237 right = FixedMul(dy>>8, line->dx>>8);
238
239 if (right < left)
240 return 0; // front side
241 return 1; // back side
242 }
243
244 //
245 // P_MakeDivline
246 //
P_MakeDivline(line_t * li,divline_t * dl)247 void P_MakeDivline(line_t *li, divline_t *dl)
248 {
249 dl->x = li->v1->x;
250 dl->y = li->v1->y;
251 dl->dx = li->dx;
252 dl->dy = li->dy;
253 }
254
255 //
256 // P_InterceptVector
257 // Returns the fractional intercept point along the first divline.
258 // This is only called by the addthings and addlines traversers.
259 //
P_InterceptVector(divline_t * v2,divline_t * v1)260 fixed_t P_InterceptVector(divline_t *v2, divline_t *v1)
261 {
262 fixed_t frac, num, den;
263
264 den = FixedMul(v1->dy>>8, v2->dx) - FixedMul(v1->dx>>8, v2->dy);
265
266 if (!den)
267 return 0;
268
269 num = FixedMul((v1->x - v2->x)>>8, v1->dy) + FixedMul((v2->y - v1->y)>>8, v1->dx);
270 frac = FixedDiv(num, den);
271
272 return frac;
273 }
274
275 //
276 // P_LineOpening
277 // Sets opentop and openbottom to the window through a two sided line.
278 // OPTIMIZE: keep this precalculated
279 //
280 fixed_t opentop, openbottom, openrange, lowfloor, highceiling;
281 pslope_t *opentopslope, *openbottomslope;
282 ffloor_t *openfloorrover, *openceilingrover;
283
284 // P_CameraLineOpening
285 // P_LineOpening, but for camera
286 // Tails 09-29-2002
P_CameraLineOpening(line_t * linedef)287 void P_CameraLineOpening(line_t *linedef)
288 {
289 sector_t *front;
290 sector_t *back;
291 fixed_t frontfloor, frontceiling, backfloor, backceiling;
292
293 if (linedef->sidenum[1] == 0xffff)
294 {
295 // single sided line
296 openrange = 0;
297 return;
298 }
299
300 front = linedef->frontsector;
301 back = linedef->backsector;
302
303 // Cameras use the heightsec's heights rather then the actual sector heights.
304 // If you can see through it, why not move the camera through it too?
305 if (front->camsec >= 0)
306 {
307 // SRB2CBTODO: ESLOPE (sectors[front->heightsec].f_slope)
308 frontfloor = P_GetSectorFloorZAt (§ors[front->camsec], camera.x, camera.y);
309 frontceiling = P_GetSectorCeilingZAt(§ors[front->camsec], camera.x, camera.y);
310
311 }
312 else if (front->heightsec >= 0)
313 {
314 // SRB2CBTODO: ESLOPE (sectors[front->heightsec].f_slope)
315 frontfloor = P_GetSectorFloorZAt (§ors[front->heightsec], camera.x, camera.y);
316 frontceiling = P_GetSectorCeilingZAt(§ors[front->heightsec], camera.x, camera.y);
317 }
318 else
319 {
320 frontfloor = P_CameraGetFloorZ (mapcampointer, front, tmx, tmy, linedef);
321 frontceiling = P_CameraGetCeilingZ(mapcampointer, front, tmx, tmy, linedef);
322 }
323 if (back->camsec >= 0)
324 {
325 // SRB2CBTODO: ESLOPE (sectors[back->heightsec].f_slope)
326 backfloor = P_GetSectorFloorZAt (§ors[back->camsec], camera.x, camera.y);
327 backceiling = P_GetSectorCeilingZAt(§ors[back->camsec], camera.x, camera.y);
328 }
329 else if (back->heightsec >= 0)
330 {
331 // SRB2CBTODO: ESLOPE (sectors[back->heightsec].f_slope)
332 backfloor = P_GetSectorFloorZAt (§ors[back->heightsec], camera.x, camera.y);
333 backceiling = P_GetSectorCeilingZAt(§ors[back->heightsec], camera.x, camera.y);
334 }
335 else
336 {
337 backfloor = P_CameraGetFloorZ(mapcampointer, back, tmx, tmy, linedef);
338 backceiling = P_CameraGetCeilingZ(mapcampointer, back, tmx, tmy, linedef);
339 }
340
341 {
342 fixed_t thingtop = mapcampointer->z + mapcampointer->height;
343
344 if (frontceiling < backceiling)
345 {
346 opentop = frontceiling;
347 highceiling = backceiling;
348 }
349 else
350 {
351 opentop = backceiling;
352 highceiling = frontceiling;
353 }
354
355 if (frontfloor > backfloor)
356 {
357 openbottom = frontfloor;
358 lowfloor = backfloor;
359 }
360 else
361 {
362 openbottom = backfloor;
363 lowfloor = frontfloor;
364 }
365
366 // Check for fake floors in the sector.
367 if (front->ffloors || back->ffloors)
368 {
369 ffloor_t *rover;
370 fixed_t delta1, delta2;
371
372 // Check for frontsector's fake floors
373 if (front->ffloors)
374 for (rover = front->ffloors; rover; rover = rover->next)
375 {
376 fixed_t topheight, bottomheight;
377 if (!(rover->flags & FF_BLOCKOTHERS) || !(rover->flags & FF_RENDERALL) || !(rover->flags & FF_EXISTS) || GETSECSPECIAL(rover->master->frontsector->special, 4) == 12)
378 continue;
379
380 topheight = P_CameraGetFOFTopZ(mapcampointer, front, rover, tmx, tmy, linedef);
381 bottomheight = P_CameraGetFOFBottomZ(mapcampointer, front, rover, tmx, tmy, linedef);
382
383 delta1 = abs(mapcampointer->z - (bottomheight + ((topheight - bottomheight)/2)));
384 delta2 = abs(thingtop - (bottomheight + ((topheight - bottomheight)/2)));
385 if (bottomheight < opentop && delta1 >= delta2)
386 opentop = bottomheight;
387 else if (bottomheight < highceiling && delta1 >= delta2)
388 highceiling = bottomheight;
389
390 if (topheight > openbottom && delta1 < delta2)
391 openbottom = topheight;
392 else if (topheight > lowfloor && delta1 < delta2)
393 lowfloor = topheight;
394 }
395
396 // Check for backsectors fake floors
397 if (back->ffloors)
398 for (rover = back->ffloors; rover; rover = rover->next)
399 {
400 fixed_t topheight, bottomheight;
401 if (!(rover->flags & FF_BLOCKOTHERS) || !(rover->flags & FF_RENDERALL) || !(rover->flags & FF_EXISTS) || GETSECSPECIAL(rover->master->frontsector->special, 4) == 12)
402 continue;
403
404 topheight = P_CameraGetFOFTopZ(mapcampointer, back, rover, tmx, tmy, linedef);
405 bottomheight = P_CameraGetFOFBottomZ(mapcampointer, back, rover, tmx, tmy, linedef);
406
407 delta1 = abs(mapcampointer->z - (bottomheight + ((topheight - bottomheight)/2)));
408 delta2 = abs(thingtop - (bottomheight + ((topheight - bottomheight)/2)));
409 if (bottomheight < opentop && delta1 >= delta2)
410 opentop = bottomheight;
411 else if (bottomheight < highceiling && delta1 >= delta2)
412 highceiling = bottomheight;
413
414 if (topheight > openbottom && delta1 < delta2)
415 openbottom = topheight;
416 else if (topheight > lowfloor && delta1 < delta2)
417 lowfloor = topheight;
418 }
419 }
420 openrange = opentop - openbottom;
421 return;
422 }
423 }
424
P_LineOpening(line_t * linedef,mobj_t * mobj)425 void P_LineOpening(line_t *linedef, mobj_t *mobj)
426 {
427 sector_t *front, *back;
428
429 if (linedef->sidenum[1] == 0xffff)
430 {
431 // single sided line
432 openrange = 0;
433 return;
434 }
435
436 front = linedef->frontsector;
437 back = linedef->backsector;
438
439 I_Assert(front != NULL);
440 I_Assert(back != NULL);
441
442 openfloorrover = openceilingrover = NULL;
443 if (linedef->polyobj)
444 {
445 // set these defaults so that polyobjects don't interfere with collision above or below them
446 opentop = INT32_MAX;
447 openbottom = INT32_MIN;
448 highceiling = INT32_MIN;
449 lowfloor = INT32_MAX;
450 opentopslope = openbottomslope = NULL;
451 }
452 else
453 { // Set open and high/low values here
454 fixed_t frontheight, backheight;
455
456 frontheight = P_GetCeilingZ(mobj, front, tmx, tmy, linedef);
457 backheight = P_GetCeilingZ(mobj, back, tmx, tmy, linedef);
458
459 if (frontheight < backheight)
460 {
461 opentop = frontheight;
462 highceiling = backheight;
463 opentopslope = front->c_slope;
464 }
465 else
466 {
467 opentop = backheight;
468 highceiling = frontheight;
469 opentopslope = back->c_slope;
470 }
471
472 frontheight = P_GetFloorZ(mobj, front, tmx, tmy, linedef);
473 backheight = P_GetFloorZ(mobj, back, tmx, tmy, linedef);
474
475 if (frontheight > backheight)
476 {
477 openbottom = frontheight;
478 lowfloor = backheight;
479 openbottomslope = front->f_slope;
480 }
481 else
482 {
483 openbottom = backheight;
484 lowfloor = frontheight;
485 openbottomslope = back->f_slope;
486 }
487 }
488
489 if (mobj)
490 {
491 fixed_t thingtop = mobj->z + mobj->height;
492
493 // Check for collision with front side's midtexture if Effect 4 is set
494 if (linedef->flags & ML_EFFECT4
495 && !linedef->polyobj // don't do anything for polyobjects! ...for now
496 ) {
497 side_t *side = &sides[linedef->sidenum[0]];
498 fixed_t textop, texbottom, texheight;
499 fixed_t texmid, delta1, delta2;
500 INT32 texnum = R_GetTextureNum(side->midtexture); // make sure the texture is actually valid
501
502 if (texnum) {
503 // Get the midtexture's height
504 texheight = textures[texnum]->height << FRACBITS;
505
506 // Set texbottom and textop to the Z coordinates of the texture's boundaries
507 #if 0
508 // don't remove this code unless solid midtextures
509 // on non-solid polyobjects should NEVER happen in the future
510 if (linedef->polyobj && (linedef->polyobj->flags & POF_TESTHEIGHT)) {
511 if (linedef->flags & ML_EFFECT5 && !side->repeatcnt) { // "infinite" repeat
512 texbottom = back->floorheight + side->rowoffset;
513 textop = back->ceilingheight + side->rowoffset;
514 } else if (!!(linedef->flags & ML_DONTPEGBOTTOM) ^ !!(linedef->flags & ML_EFFECT3)) {
515 texbottom = back->floorheight + side->rowoffset;
516 textop = texbottom + texheight*(side->repeatcnt+1);
517 } else {
518 textop = back->ceilingheight + side->rowoffset;
519 texbottom = textop - texheight*(side->repeatcnt+1);
520 }
521 } else
522 #endif
523 {
524 if (linedef->flags & ML_EFFECT5 && !side->repeatcnt) { // "infinite" repeat
525 texbottom = openbottom + side->rowoffset;
526 textop = opentop + side->rowoffset;
527 } else if (!!(linedef->flags & ML_DONTPEGBOTTOM) ^ !!(linedef->flags & ML_EFFECT3)) {
528 texbottom = openbottom + side->rowoffset;
529 textop = texbottom + texheight*(side->repeatcnt+1);
530 } else {
531 textop = opentop + side->rowoffset;
532 texbottom = textop - texheight*(side->repeatcnt+1);
533 }
534 }
535
536 texmid = texbottom+(textop-texbottom)/2;
537
538 delta1 = abs(mobj->z - texmid);
539 delta2 = abs(thingtop - texmid);
540
541 if (delta1 > delta2) { // Below
542 if (opentop > texbottom)
543 opentop = texbottom;
544 } else { // Above
545 if (openbottom < textop)
546 openbottom = textop;
547 }
548 }
549 }
550 if (linedef->polyobj)
551 {
552 // Treat polyobj's backsector like a 3D Floor
553 if (linedef->polyobj->flags & POF_TESTHEIGHT)
554 {
555 const sector_t *polysec = linedef->backsector;
556 fixed_t polytop, polybottom;
557 fixed_t delta1, delta2;
558
559 if (linedef->polyobj->flags & POF_CLIPPLANES)
560 {
561 polytop = polysec->ceilingheight;
562 polybottom = polysec->floorheight;
563 }
564 else
565 {
566 polytop = INT32_MAX;
567 polybottom = INT32_MIN;
568 }
569
570 delta1 = abs(mobj->z - (polybottom + ((polytop - polybottom)/2)));
571 delta2 = abs(thingtop - (polybottom + ((polytop - polybottom)/2)));
572
573 if (polybottom < opentop && delta1 >= delta2)
574 opentop = polybottom;
575 else if (polybottom < highceiling && delta1 >= delta2)
576 highceiling = polybottom;
577
578 if (polytop > openbottom && delta1 < delta2)
579 openbottom = polytop;
580 else if (polytop > lowfloor && delta1 < delta2)
581 lowfloor = polytop;
582 }
583 // otherwise don't do anything special, pretend there's nothing else there
584 }
585 else
586 {
587 // Check for fake floors in the sector.
588 if (front->ffloors || back->ffloors)
589 {
590 ffloor_t *rover;
591 fixed_t delta1, delta2;
592
593 // Check for frontsector's fake floors
594 for (rover = front->ffloors; rover; rover = rover->next)
595 {
596 fixed_t topheight, bottomheight;
597 if (!(rover->flags & FF_EXISTS))
598 continue;
599
600 if (mobj->player && (P_CheckSolidLava(rover) || P_CanRunOnWater(mobj->player, rover)))
601 ;
602 else if (!((rover->flags & FF_BLOCKPLAYER && mobj->player)
603 || (rover->flags & FF_BLOCKOTHERS && !mobj->player)))
604 continue;
605
606 topheight = P_GetFOFTopZ(mobj, front, rover, tmx, tmy, linedef);
607 bottomheight = P_GetFOFBottomZ(mobj, front, rover, tmx, tmy, linedef);
608
609 delta1 = abs(mobj->z - (bottomheight + ((topheight - bottomheight)/2)));
610 delta2 = abs(thingtop - (bottomheight + ((topheight - bottomheight)/2)));
611
612 if (delta1 >= delta2 && (rover->flags & FF_INTANGIBLEFLATS) != FF_PLATFORM) // thing is below FOF
613 {
614 if (bottomheight < opentop) {
615 opentop = bottomheight;
616 opentopslope = *rover->b_slope;
617 openceilingrover = rover;
618 }
619 else if (bottomheight < highceiling)
620 highceiling = bottomheight;
621 }
622
623 if (delta1 < delta2 && (rover->flags & FF_INTANGIBLEFLATS) != FF_REVERSEPLATFORM) // thing is above FOF
624 {
625 if (topheight > openbottom) {
626 openbottom = topheight;
627 openbottomslope = *rover->t_slope;
628 openfloorrover = rover;
629 }
630 else if (topheight > lowfloor)
631 lowfloor = topheight;
632 }
633 }
634
635 // Check for backsectors fake floors
636 for (rover = back->ffloors; rover; rover = rover->next)
637 {
638 fixed_t topheight, bottomheight;
639 if (!(rover->flags & FF_EXISTS))
640 continue;
641
642 if (mobj->player && (P_CheckSolidLava(rover) || P_CanRunOnWater(mobj->player, rover)))
643 ;
644 else if (!((rover->flags & FF_BLOCKPLAYER && mobj->player)
645 || (rover->flags & FF_BLOCKOTHERS && !mobj->player)))
646 continue;
647
648 topheight = P_GetFOFTopZ(mobj, back, rover, tmx, tmy, linedef);
649 bottomheight = P_GetFOFBottomZ(mobj, back, rover, tmx, tmy, linedef);
650
651 delta1 = abs(mobj->z - (bottomheight + ((topheight - bottomheight)/2)));
652 delta2 = abs(thingtop - (bottomheight + ((topheight - bottomheight)/2)));
653
654 if (delta1 >= delta2 && (rover->flags & FF_INTANGIBLEFLATS) != FF_PLATFORM) // thing is below FOF
655 {
656 if (bottomheight < opentop) {
657 opentop = bottomheight;
658 opentopslope = *rover->b_slope;
659 openceilingrover = rover;
660 }
661 else if (bottomheight < highceiling)
662 highceiling = bottomheight;
663 }
664
665 if (delta1 < delta2 && (rover->flags & FF_INTANGIBLEFLATS) != FF_REVERSEPLATFORM) // thing is above FOF
666 {
667 if (topheight > openbottom) {
668 openbottom = topheight;
669 openbottomslope = *rover->t_slope;
670 openfloorrover = rover;
671 }
672 else if (topheight > lowfloor)
673 lowfloor = topheight;
674 }
675 }
676 }
677 }
678 }
679
680 openrange = opentop - openbottom;
681 }
682
683
684 //
685 // THING POSITION SETTING
686 //
687
688 //
689 // P_UnsetThingPosition
690 // Unlinks a thing from block map and sectors.
691 // On each position change, BLOCKMAP and other
692 // lookups maintaining lists ot things inside
693 // these structures need to be updated.
694 //
P_UnsetThingPosition(mobj_t * thing)695 void P_UnsetThingPosition(mobj_t *thing)
696 {
697 I_Assert(thing != NULL);
698 I_Assert(!P_MobjWasRemoved(thing));
699
700 if (!(thing->flags & MF_NOSECTOR))
701 {
702 /* invisible things don't need to be in sector list
703 * unlink from subsector
704 *
705 * killough 8/11/98: simpler scheme using pointers-to-pointers for prev
706 * pointers, allows head node pointers to be treated like everything else
707 */
708
709 mobj_t **sprev = thing->sprev;
710 mobj_t *snext = thing->snext;
711 if ((*sprev = snext) != NULL) // unlink from sector list
712 snext->sprev = sprev;
713
714 // phares 3/14/98
715 //
716 // Save the sector list pointed to by touching_sectorlist.
717 // In P_SetThingPosition, we'll keep any nodes that represent
718 // sectors the Thing still touches. We'll add new ones then, and
719 // delete any nodes for sectors the Thing has vacated. Then we'll
720 // put it back into touching_sectorlist. It's done this way to
721 // avoid a lot of deleting/creating for nodes, when most of the
722 // time you just get back what you deleted anyway.
723 //
724 // If this Thing is being removed entirely, then the calling
725 // routine will clear out the nodes in sector_list.
726
727 sector_list = thing->touching_sectorlist;
728 thing->touching_sectorlist = NULL; //to be restored by P_SetThingPosition
729 }
730
731 if (!(thing->flags & MF_NOBLOCKMAP))
732 {
733 /* inert things don't need to be in blockmap
734 *
735 * killough 8/11/98: simpler scheme using pointers-to-pointers for prev
736 * pointers, allows head node pointers to be treated like everything else
737 *
738 * Also more robust, since it doesn't depend on current position for
739 * unlinking. Old method required computing head node based on position
740 * at time of unlinking, assuming it was the same position as during
741 * linking.
742 */
743
744 mobj_t *bnext, **bprev = thing->bprev;
745 if (bprev && (*bprev = bnext = thing->bnext) != NULL) // unlink from block map
746 bnext->bprev = bprev;
747 }
748 }
749
P_UnsetPrecipThingPosition(precipmobj_t * thing)750 void P_UnsetPrecipThingPosition(precipmobj_t *thing)
751 {
752 precipmobj_t **sprev = thing->sprev;
753 precipmobj_t *snext = thing->snext;
754 if ((*sprev = snext) != NULL) // unlink from sector list
755 snext->sprev = sprev;
756
757 precipsector_list = thing->touching_sectorlist;
758 thing->touching_sectorlist = NULL; //to be restored by P_SetPrecipThingPosition
759 }
760
761 //
762 // P_SetThingPosition
763 // Links a thing into both a block and a subsector
764 // based on it's x y.
765 // Sets thing->subsector properly
766 //
P_SetThingPosition(mobj_t * thing)767 void P_SetThingPosition(mobj_t *thing)
768 { // link into subsector
769 subsector_t *ss;
770 sector_t *oldsec = NULL;
771 fixed_t tfloorz, tceilz;
772
773 I_Assert(thing != NULL);
774 I_Assert(!P_MobjWasRemoved(thing));
775
776 if (thing->player && thing->z <= thing->floorz && thing->subsector)
777 oldsec = thing->subsector->sector;
778
779 ss = thing->subsector = R_PointInSubsector(thing->x, thing->y);
780
781 if (!(thing->flags & MF_NOSECTOR))
782 {
783 // invisible things don't go into the sector links
784
785 // killough 8/11/98: simpler scheme using pointer-to-pointer prev
786 // pointers, allows head nodes to be treated like everything else
787
788 mobj_t **link = &ss->sector->thinglist;
789 mobj_t *snext = *link;
790 if ((thing->snext = snext) != NULL)
791 snext->sprev = &thing->snext;
792 thing->sprev = link;
793 *link = thing;
794
795 // phares 3/16/98
796 //
797 // If sector_list isn't NULL, it has a collection of sector
798 // nodes that were just removed from this Thing.
799
800 // Collect the sectors the object will live in by looking at
801 // the existing sector_list and adding new nodes and deleting
802 // obsolete ones.
803
804 // When a node is deleted, its sector links (the links starting
805 // at sector_t->touching_thinglist) are broken. When a node is
806 // added, new sector links are created.
807
808 P_CreateSecNodeList(thing,thing->x,thing->y);
809 thing->touching_sectorlist = sector_list; // Attach to Thing's mobj_t
810 sector_list = NULL; // clear for next time
811 }
812
813 // link into blockmap
814 if (!(thing->flags & MF_NOBLOCKMAP))
815 {
816 // inert things don't need to be in blockmap
817 const INT32 blockx = (unsigned)(thing->x - bmaporgx)>>MAPBLOCKSHIFT;
818 const INT32 blocky = (unsigned)(thing->y - bmaporgy)>>MAPBLOCKSHIFT;
819 if (blockx >= 0 && blockx < bmapwidth
820 && blocky >= 0 && blocky < bmapheight)
821 {
822 // killough 8/11/98: simpler scheme using
823 // pointer-to-pointer prev pointers --
824 // allows head nodes to be treated like everything else
825
826 mobj_t **link = &blocklinks[blocky*bmapwidth + blockx];
827 mobj_t *bnext = *link;
828 if ((thing->bnext = bnext) != NULL)
829 bnext->bprev = &thing->bnext;
830 thing->bprev = link;
831 *link = thing;
832 }
833 else // thing is off the map
834 thing->bnext = NULL, thing->bprev = NULL;
835 }
836
837 // Allows you to 'step' on a new linedef exec when the previous
838 // sector's floor is the same height.
839 if (thing->player && oldsec != NULL && thing->subsector && oldsec != thing->subsector->sector)
840 {
841 tfloorz = P_GetFloorZ(thing, ss->sector, thing->x, thing->y, NULL);
842 tceilz = P_GetCeilingZ(thing, ss->sector, thing->x, thing->y, NULL);
843
844 if (thing->eflags & MFE_VERTICALFLIP)
845 {
846 if (thing->z + thing->height >= tceilz)
847 thing->eflags |= MFE_JUSTSTEPPEDDOWN;
848 }
849 else if (thing->z <= tfloorz)
850 thing->eflags |= MFE_JUSTSTEPPEDDOWN;
851 }
852 }
853
854 //
855 // P_SetUnderlayPosition
856 // Links a thing into a subsector at the other end of the stack,
857 // so it appears behind all other sprites in that subsector.
858 // Sets thing->subsector properly
859 //
P_SetUnderlayPosition(mobj_t * thing)860 void P_SetUnderlayPosition(mobj_t *thing)
861 { // link into subsector
862 subsector_t *ss;
863 mobj_t **link, *lend;
864 I_Assert(thing);
865
866 ss = thing->subsector = R_PointInSubsector(thing->x, thing->y);
867 link = &ss->sector->thinglist;
868 for (lend = *link; lend && lend->snext; lend = lend->snext)
869 ;
870 thing->snext = NULL;
871 if (!lend)
872 {
873 thing->sprev = link;
874 *link = thing;
875 }
876 else
877 {
878 thing->sprev = &lend->snext;
879 lend->snext = thing;
880 }
881
882 P_CreateSecNodeList(thing,thing->x,thing->y);
883 thing->touching_sectorlist = sector_list; // Attach to Thing's mobj_t
884 sector_list = NULL; // clear for next time
885 }
886
P_SetPrecipitationThingPosition(precipmobj_t * thing)887 void P_SetPrecipitationThingPosition(precipmobj_t *thing)
888 {
889 subsector_t *ss = thing->subsector = R_PointInSubsector(thing->x, thing->y);
890
891 precipmobj_t **link = &ss->sector->preciplist;
892 precipmobj_t *snext = *link;
893 if ((thing->snext = snext) != NULL)
894 snext->sprev = &thing->snext;
895 thing->sprev = link;
896 *link = thing;
897
898 P_CreatePrecipSecNodeList(thing, thing->x, thing->y);
899 thing->touching_sectorlist = precipsector_list; // Attach to Thing's precipmobj_t
900 precipsector_list = NULL; // clear for next time
901 }
902
903 //
904 // BLOCK MAP ITERATORS
905 // For each line/thing in the given mapblock,
906 // call the passed PIT_* function.
907 // If the function returns false,
908 // exit with false without checking anything else.
909 //
910
911
912 //
913 // P_BlockLinesIterator
914 // The validcount flags are used to avoid checking lines
915 // that are marked in multiple mapblocks,
916 // so increment validcount before the first call
917 // to P_BlockLinesIterator, then make one or more calls
918 // to it.
919 //
P_BlockLinesIterator(INT32 x,INT32 y,boolean (* func)(line_t *))920 boolean P_BlockLinesIterator(INT32 x, INT32 y, boolean (*func)(line_t *))
921 {
922 INT32 offset;
923 const INT32 *list; // Big blockmap
924 polymaplink_t *plink; // haleyjd 02/22/06
925 line_t *ld;
926
927 if (x < 0 || y < 0 || x >= bmapwidth || y >= bmapheight)
928 return true;
929
930 offset = y*bmapwidth + x;
931
932 // haleyjd 02/22/06: consider polyobject lines
933 plink = polyblocklinks[offset];
934
935 while (plink)
936 {
937 polyobj_t *po = plink->po;
938
939 if (po->validcount != validcount) // if polyobj hasn't been checked
940 {
941 size_t i;
942 po->validcount = validcount;
943
944 for (i = 0; i < po->numLines; ++i)
945 {
946 if (po->lines[i]->validcount == validcount) // line has been checked
947 continue;
948 po->lines[i]->validcount = validcount;
949 if (!func(po->lines[i]))
950 return false;
951 }
952 }
953 plink = (polymaplink_t *)(plink->link.next);
954 }
955
956 offset = *(blockmap + offset); // offset = blockmap[y*bmapwidth+x];
957
958 // First index is really empty, so +1 it.
959 for (list = blockmaplump + offset + 1; *list != -1; list++)
960 {
961 ld = &lines[*list];
962
963 if (ld->validcount == validcount)
964 continue; // Line has already been checked.
965
966 ld->validcount = validcount;
967
968 if (!func(ld))
969 return false;
970 }
971 return true; // Everything was checked.
972 }
973
974
975 //
976 // P_BlockThingsIterator
977 //
P_BlockThingsIterator(INT32 x,INT32 y,boolean (* func)(mobj_t *))978 boolean P_BlockThingsIterator(INT32 x, INT32 y, boolean (*func)(mobj_t *))
979 {
980 mobj_t *mobj, *bnext = NULL;
981
982 if (x < 0 || y < 0 || x >= bmapwidth || y >= bmapheight)
983 return true;
984
985 // Check interaction with the objects in the blockmap.
986 for (mobj = blocklinks[y*bmapwidth + x]; mobj; mobj = bnext)
987 {
988 P_SetTarget(&bnext, mobj->bnext); // We want to note our reference to bnext here incase it is MF_NOTHINK and gets removed!
989 if (!func(mobj))
990 {
991 P_SetTarget(&bnext, NULL);
992 return false;
993 }
994 if (P_MobjWasRemoved(tmthing) // func just popped our tmthing, cannot continue.
995 || (bnext && P_MobjWasRemoved(bnext))) // func just broke blockmap chain, cannot continue.
996 {
997 P_SetTarget(&bnext, NULL);
998 return true;
999 }
1000 }
1001 return true;
1002 }
1003
1004 //
1005 // INTERCEPT ROUTINES
1006 //
1007
1008 //SoM: 4/6/2000: Limit removal
1009 static intercept_t *intercepts = NULL;
1010 static intercept_t *intercept_p = NULL;
1011
1012 divline_t trace;
1013 static boolean earlyout;
1014
1015 //SoM: 4/6/2000: Remove limit on intercepts.
P_CheckIntercepts(void)1016 static void P_CheckIntercepts(void)
1017 {
1018 static size_t max_intercepts = 0;
1019 size_t count = intercept_p - intercepts;
1020
1021 if (max_intercepts <= count)
1022 {
1023 if (!max_intercepts)
1024 max_intercepts = 128;
1025 else
1026 max_intercepts *= 2;
1027
1028 intercepts = Z_Realloc(intercepts, sizeof (*intercepts) * max_intercepts, PU_STATIC, NULL);
1029
1030 intercept_p = intercepts + count;
1031 }
1032 }
1033
1034 //
1035 // PIT_AddLineIntercepts.
1036 // Looks for lines in the given block
1037 // that intercept the given trace
1038 // to add to the intercepts list.
1039 //
1040 // A line is crossed if its endpoints
1041 // are on opposite sides of the trace.
1042 // Returns true if earlyout and a solid line hit.
1043 //
PIT_AddLineIntercepts(line_t * ld)1044 static boolean PIT_AddLineIntercepts(line_t *ld)
1045 {
1046 INT32 s1, s2;
1047 fixed_t frac;
1048 divline_t dl;
1049
1050 // avoid precision problems with two routines
1051 if (trace.dx > FRACUNIT*16 || trace.dy > FRACUNIT*16
1052 || trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16)
1053 {
1054 // Hurdler: crash here with phobia when you shoot
1055 // on the door next the stone bridge
1056 // stack overflow???
1057 s1 = P_PointOnDivlineSide(ld->v1->x, ld->v1->y, &trace);
1058 s2 = P_PointOnDivlineSide(ld->v2->x, ld->v2->y, &trace);
1059 }
1060 else
1061 {
1062 s1 = P_PointOnLineSide(trace.x, trace.y, ld);
1063 s2 = P_PointOnLineSide(trace.x+trace.dx, trace.y+trace.dy, ld);
1064 }
1065
1066 if (s1 == s2)
1067 return true; // Line isn't crossed.
1068
1069 // Hit the line.
1070 P_MakeDivline(ld, &dl);
1071 frac = P_InterceptVector(&trace, &dl);
1072
1073 if (frac < 0)
1074 return true; // Behind source.
1075
1076 // Try to take an early out of the check.
1077 if (earlyout && frac < FRACUNIT && !ld->backsector)
1078 return false; // stop checking
1079
1080 P_CheckIntercepts();
1081
1082 intercept_p->frac = frac;
1083 intercept_p->isaline = true;
1084 intercept_p->d.line = ld;
1085 intercept_p++;
1086
1087 return true; // continue
1088 }
1089
1090 //
1091 // PIT_AddThingIntercepts
1092 //
PIT_AddThingIntercepts(mobj_t * thing)1093 static boolean PIT_AddThingIntercepts(mobj_t *thing)
1094 {
1095 fixed_t px1, py1, px2, py2, frac;
1096 INT32 s1, s2;
1097 boolean tracepositive;
1098 divline_t dl;
1099
1100 tracepositive = (trace.dx ^ trace.dy) > 0;
1101
1102 // check a corner to corner crossection for hit
1103 if (tracepositive)
1104 {
1105 px1 = thing->x - thing->radius;
1106 py1 = thing->y + thing->radius;
1107
1108 px2 = thing->x + thing->radius;
1109 py2 = thing->y - thing->radius;
1110 }
1111 else
1112 {
1113 px1 = thing->x - thing->radius;
1114 py1 = thing->y - thing->radius;
1115
1116 px2 = thing->x + thing->radius;
1117 py2 = thing->y + thing->radius;
1118 }
1119
1120 s1 = P_PointOnDivlineSide(px1, py1, &trace);
1121 s2 = P_PointOnDivlineSide(px2, py2, &trace);
1122
1123 if (s1 == s2)
1124 return true; // Line isn't crossed.
1125
1126 dl.x = px1;
1127 dl.y = py1;
1128 dl.dx = px2 - px1;
1129 dl.dy = py2 - py1;
1130
1131 frac = P_InterceptVector(&trace, &dl);
1132
1133 if (frac < 0)
1134 return true; // Behind source.
1135
1136 P_CheckIntercepts();
1137
1138 intercept_p->frac = frac;
1139 intercept_p->isaline = false;
1140 intercept_p->d.thing = thing;
1141 intercept_p++;
1142
1143 return true; // Keep going.
1144 }
1145
1146 //
1147 // P_TraverseIntercepts
1148 // Returns true if the traverser function returns true
1149 // for all lines.
1150 //
P_TraverseIntercepts(traverser_t func,fixed_t maxfrac)1151 static boolean P_TraverseIntercepts(traverser_t func, fixed_t maxfrac)
1152 {
1153 size_t count;
1154 fixed_t dist;
1155 intercept_t *scan, *in = NULL;
1156
1157 count = intercept_p - intercepts;
1158
1159 while (count--)
1160 {
1161 dist = INT32_MAX;
1162 for (scan = intercepts; scan < intercept_p; scan++)
1163 {
1164 if (scan->frac < dist)
1165 {
1166 dist = scan->frac;
1167 in = scan;
1168 }
1169 }
1170
1171 if (dist > maxfrac)
1172 return true; // Checked everything in range.
1173
1174 if (!func(in))
1175 return false; // Don't bother going farther.
1176
1177 in->frac = INT32_MAX;
1178 }
1179
1180 return true; // Everything was traversed.
1181 }
1182
1183 //
1184 // P_PathTraverse
1185 // Traces a line from x1, y1 to x2, y2,
1186 // calling the traverser function for each.
1187 // Returns true if the traverser function returns true
1188 // for all lines.
1189 //
P_PathTraverse(fixed_t px1,fixed_t py1,fixed_t px2,fixed_t py2,INT32 flags,traverser_t trav)1190 boolean P_PathTraverse(fixed_t px1, fixed_t py1, fixed_t px2, fixed_t py2,
1191 INT32 flags, traverser_t trav)
1192 {
1193 fixed_t xt1, yt1, xt2, yt2;
1194 fixed_t xstep, ystep, partial, xintercept, yintercept;
1195 INT32 mapx, mapy, mapxstep, mapystep, count;
1196
1197 earlyout = flags & PT_EARLYOUT;
1198
1199 validcount++;
1200 intercept_p = intercepts;
1201
1202 if (((px1 - bmaporgx) & (MAPBLOCKSIZE-1)) == 0)
1203 px1 += FRACUNIT; // Don't side exactly on a line.
1204
1205 if (((py1 - bmaporgy) & (MAPBLOCKSIZE-1)) == 0)
1206 py1 += FRACUNIT; // Don't side exactly on a line.
1207
1208 trace.x = px1;
1209 trace.y = py1;
1210 trace.dx = px2 - px1;
1211 trace.dy = py2 - py1;
1212
1213 px1 -= bmaporgx;
1214 py1 -= bmaporgy;
1215 xt1 = (unsigned)px1>>MAPBLOCKSHIFT;
1216 yt1 = (unsigned)py1>>MAPBLOCKSHIFT;
1217
1218 px2 -= bmaporgx;
1219 py2 -= bmaporgy;
1220 xt2 = (unsigned)px2>>MAPBLOCKSHIFT;
1221 yt2 = (unsigned)py2>>MAPBLOCKSHIFT;
1222
1223 if (xt2 > xt1)
1224 {
1225 mapxstep = 1;
1226 partial = FRACUNIT - ((px1>>MAPBTOFRAC) & FRACMASK);
1227 ystep = FixedDiv(py2 - py1, abs(px2 - px1));
1228 }
1229 else if (xt2 < xt1)
1230 {
1231 mapxstep = -1;
1232 partial = (px1>>MAPBTOFRAC) & FRACMASK;
1233 ystep = FixedDiv(py2 - py1, abs(px2 - px1));
1234 }
1235 else
1236 {
1237 mapxstep = 0;
1238 partial = FRACUNIT;
1239 ystep = 256*FRACUNIT;
1240 }
1241
1242 yintercept = (py1>>MAPBTOFRAC) + FixedMul(partial, ystep);
1243
1244 if (yt2 > yt1)
1245 {
1246 mapystep = 1;
1247 partial = FRACUNIT - ((py1>>MAPBTOFRAC) & FRACMASK);
1248 xstep = FixedDiv(px2 - px1, abs(py2 - py1));
1249 }
1250 else if (yt2 < yt1)
1251 {
1252 mapystep = -1;
1253 partial = (py1>>MAPBTOFRAC) & FRACMASK;
1254 xstep = FixedDiv(px2 - px1, abs(py2 - py1));
1255 }
1256 else
1257 {
1258 mapystep = 0;
1259 partial = FRACUNIT;
1260 xstep = 256*FRACUNIT;
1261 }
1262 xintercept = (px1>>MAPBTOFRAC) + FixedMul(partial, xstep);
1263
1264 // Step through map blocks.
1265 // Count is present to prevent a round off error
1266 // from skipping the break.
1267 mapx = xt1;
1268 mapy = yt1;
1269
1270 for (count = 0; count < 64; count++)
1271 {
1272 if (flags & PT_ADDLINES)
1273 if (!P_BlockLinesIterator(mapx, mapy, PIT_AddLineIntercepts))
1274 return false; // early out
1275
1276 if (flags & PT_ADDTHINGS)
1277 if (!P_BlockThingsIterator(mapx, mapy, PIT_AddThingIntercepts))
1278 return false; // early out
1279
1280 if (mapx == xt2 && mapy == yt2)
1281 break;
1282
1283 if ((yintercept >> FRACBITS) == mapy)
1284 {
1285 yintercept += ystep;
1286 mapx += mapxstep;
1287 }
1288 else if ((xintercept >> FRACBITS) == mapx)
1289 {
1290 xintercept += xstep;
1291 mapy += mapystep;
1292 }
1293 }
1294 // Go through the sorted list
1295 return P_TraverseIntercepts(trav, FRACUNIT);
1296 }
1297
1298
1299 // =========================================================================
1300 // BLOCKMAP ITERATORS
1301 // =========================================================================
1302
1303 // blockmap iterator for all sorts of use
1304 // your routine must return FALSE to exit the loop earlier
1305 // returns FALSE if the loop exited early after a false return
1306 // value from your user function
1307
1308 //abandoned, maybe I'll need it someday..
1309 /*
1310 boolean P_RadiusLinesCheck(fixed_t radius, fixed_t x, fixed_t y,
1311 boolean (*func)(line_t *))
1312 {
1313 INT32 xl, xh, yl, yh;
1314 INT32 bx, by;
1315
1316 tmbbox[BOXTOP] = y + radius;
1317 tmbbox[BOXBOTTOM] = y - radius;
1318 tmbbox[BOXRIGHT] = x + radius;
1319 tmbbox[BOXLEFT] = x - radius;
1320
1321 // check lines
1322 xl = (unsigned)(tmbbox[BOXLEFT] - bmaporgx)>>MAPBLOCKSHIFT;
1323 xh = (unsigned)(tmbbox[BOXRIGHT] - bmaporgx)>>MAPBLOCKSHIFT;
1324 yl = (unsigned)(tmbbox[BOXBOTTOM] - bmaporgy)>>MAPBLOCKSHIFT;
1325 yh = (unsigned)(tmbbox[BOXTOP] - bmaporgy)>>MAPBLOCKSHIFT;
1326
1327 for (bx = xl; bx <= xh; bx++)
1328 for (by = yl; by <= yh; by++)
1329 if (!P_BlockLinesIterator(bx, by, func))
1330 return false;
1331 return true;
1332 }
1333 */
1334