1 //
2 // Copyright(C) 1993-1996 Id Software, Inc.
3 // Copyright(C) 2005-2014 Simon Howard
4 // Copyright(C) 2005, 2006 Andrey Budko
5 //
6 // This program is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU General Public License
8 // as published by the Free Software Foundation; either version 2
9 // of the License, or (at your option) any later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // DESCRIPTION:
17 // Movement/collision utility functions,
18 // as used by function in p_map.c.
19 // BLOCKMAP Iterator functions,
20 // and some PIT_* functions to use for iteration.
21 //
22
23
24
25 #include <stdlib.h>
26
27
28 #include "i_system.h" // [crispy] I_Realloc()
29 #include "m_bbox.h"
30
31 #include "doomdef.h"
32 #include "doomstat.h"
33 #include "p_local.h"
34
35
36 // State.
37 #include "r_state.h"
38
39 //
40 // P_AproxDistance
41 // Gives an estimation of distance (not exact)
42 //
43
44 fixed_t
P_AproxDistance(fixed_t dx,fixed_t dy)45 P_AproxDistance
46 ( fixed_t dx,
47 fixed_t dy )
48 {
49 dx = abs(dx);
50 dy = abs(dy);
51 if (dx < dy)
52 return dx+dy-(dx>>1);
53 return dx+dy-(dy>>1);
54 }
55
56
57 //
58 // P_PointOnLineSide
59 // Returns 0 or 1
60 //
61 int
P_PointOnLineSide(fixed_t x,fixed_t y,line_t * line)62 P_PointOnLineSide
63 ( fixed_t x,
64 fixed_t y,
65 line_t* line )
66 {
67 fixed_t dx;
68 fixed_t dy;
69 fixed_t left;
70 fixed_t right;
71
72 if (!line->dx)
73 {
74 if (x <= line->v1->x)
75 return line->dy > 0;
76
77 return line->dy < 0;
78 }
79 if (!line->dy)
80 {
81 if (y <= line->v1->y)
82 return line->dx < 0;
83
84 return line->dx > 0;
85 }
86
87 dx = (x - line->v1->x);
88 dy = (y - line->v1->y);
89
90 left = FixedMul ( line->dy>>FRACBITS , dx );
91 right = FixedMul ( dy , line->dx>>FRACBITS );
92
93 if (right < left)
94 return 0; // front side
95 return 1; // back side
96 }
97
98
99
100 //
101 // P_BoxOnLineSide
102 // Considers the line to be infinite
103 // Returns side 0 or 1, -1 if box crosses the line.
104 //
105 int
P_BoxOnLineSide(fixed_t * tmbox,line_t * ld)106 P_BoxOnLineSide
107 ( fixed_t* tmbox,
108 line_t* ld )
109 {
110 int p1 = 0;
111 int p2 = 0;
112
113 switch (ld->slopetype)
114 {
115 case ST_HORIZONTAL:
116 p1 = tmbox[BOXTOP] > ld->v1->y;
117 p2 = tmbox[BOXBOTTOM] > ld->v1->y;
118 if (ld->dx < 0)
119 {
120 p1 ^= 1;
121 p2 ^= 1;
122 }
123 break;
124
125 case ST_VERTICAL:
126 p1 = tmbox[BOXRIGHT] < ld->v1->x;
127 p2 = tmbox[BOXLEFT] < ld->v1->x;
128 if (ld->dy < 0)
129 {
130 p1 ^= 1;
131 p2 ^= 1;
132 }
133 break;
134
135 case ST_POSITIVE:
136 p1 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXTOP], ld);
137 p2 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld);
138 break;
139
140 case ST_NEGATIVE:
141 p1 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXTOP], ld);
142 p2 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld);
143 break;
144 }
145
146 if (p1 == p2)
147 return p1;
148 return -1;
149 }
150
151
152 //
153 // P_PointOnDivlineSide
154 // Returns 0 or 1.
155 //
156 int
P_PointOnDivlineSide(fixed_t x,fixed_t y,divline_t * line)157 P_PointOnDivlineSide
158 ( fixed_t x,
159 fixed_t y,
160 divline_t* line )
161 {
162 fixed_t dx;
163 fixed_t dy;
164 fixed_t left;
165 fixed_t right;
166
167 if (!line->dx)
168 {
169 if (x <= line->x)
170 return line->dy > 0;
171
172 return line->dy < 0;
173 }
174 if (!line->dy)
175 {
176 if (y <= line->y)
177 return line->dx < 0;
178
179 return line->dx > 0;
180 }
181
182 dx = (x - line->x);
183 dy = (y - line->y);
184
185 // try to quickly decide by looking at sign bits
186 if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
187 {
188 if ( (line->dy ^ dx) & 0x80000000 )
189 return 1; // (left is negative)
190 return 0;
191 }
192
193 left = FixedMul ( line->dy>>8, dx>>8 );
194 right = FixedMul ( dy>>8 , line->dx>>8 );
195
196 if (right < left)
197 return 0; // front side
198 return 1; // back side
199 }
200
201
202
203 //
204 // P_MakeDivline
205 //
206 void
P_MakeDivline(line_t * li,divline_t * dl)207 P_MakeDivline
208 ( line_t* li,
209 divline_t* dl )
210 {
211 dl->x = li->v1->x;
212 dl->y = li->v1->y;
213 dl->dx = li->dx;
214 dl->dy = li->dy;
215 }
216
217
218
219 //
220 // P_InterceptVector
221 // Returns the fractional intercept point
222 // along the first divline.
223 // This is only called by the addthings
224 // and addlines traversers.
225 //
226 fixed_t
P_InterceptVector(divline_t * v2,divline_t * v1)227 P_InterceptVector
228 ( divline_t* v2,
229 divline_t* v1 )
230 {
231 #if 1
232 fixed_t frac;
233 fixed_t num;
234 fixed_t den;
235
236 den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
237
238 if (den == 0)
239 return 0;
240 // I_Error ("P_InterceptVector: parallel");
241
242 num =
243 FixedMul ( (v1->x - v2->x)>>8 ,v1->dy )
244 +FixedMul ( (v2->y - v1->y)>>8, v1->dx );
245
246 frac = FixedDiv (num , den);
247
248 return frac;
249 #else // UNUSED, float debug.
250 float frac;
251 float num;
252 float den;
253 float v1x;
254 float v1y;
255 float v1dx;
256 float v1dy;
257 float v2x;
258 float v2y;
259 float v2dx;
260 float v2dy;
261
262 v1x = (float)v1->x/FRACUNIT;
263 v1y = (float)v1->y/FRACUNIT;
264 v1dx = (float)v1->dx/FRACUNIT;
265 v1dy = (float)v1->dy/FRACUNIT;
266 v2x = (float)v2->x/FRACUNIT;
267 v2y = (float)v2->y/FRACUNIT;
268 v2dx = (float)v2->dx/FRACUNIT;
269 v2dy = (float)v2->dy/FRACUNIT;
270
271 den = v1dy*v2dx - v1dx*v2dy;
272
273 if (den == 0)
274 return 0; // parallel
275
276 num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx;
277 frac = num / den;
278
279 return frac*FRACUNIT;
280 #endif
281 }
282
283
284 //
285 // P_LineOpening
286 // Sets opentop and openbottom to the window
287 // through a two sided line.
288 // OPTIMIZE: keep this precalculated
289 //
290 fixed_t opentop;
291 fixed_t openbottom;
292 fixed_t openrange;
293 fixed_t lowfloor;
294
295
P_LineOpening(line_t * linedef)296 void P_LineOpening (line_t* linedef)
297 {
298 sector_t* front;
299 sector_t* back;
300
301 if (linedef->sidenum[1] == NO_INDEX) // [crispy] extended nodes
302 {
303 // single sided line
304 openrange = 0;
305 return;
306 }
307
308 front = linedef->frontsector;
309 back = linedef->backsector;
310
311 if (front->ceilingheight < back->ceilingheight)
312 opentop = front->ceilingheight;
313 else
314 opentop = back->ceilingheight;
315
316 if (front->floorheight > back->floorheight)
317 {
318 openbottom = front->floorheight;
319 lowfloor = back->floorheight;
320 }
321 else
322 {
323 openbottom = back->floorheight;
324 lowfloor = front->floorheight;
325 }
326
327 openrange = opentop - openbottom;
328 }
329
330
331 //
332 // THING POSITION SETTING
333 //
334
335
336 //
337 // P_UnsetThingPosition
338 // Unlinks a thing from block map and sectors.
339 // On each position change, BLOCKMAP and other
340 // lookups maintaining lists ot things inside
341 // these structures need to be updated.
342 //
P_UnsetThingPosition(mobj_t * thing)343 void P_UnsetThingPosition (mobj_t* thing)
344 {
345 int blockx;
346 int blocky;
347
348 if ( ! (thing->flags & MF_NOSECTOR) )
349 {
350 // inert things don't need to be in blockmap?
351 // unlink from subsector
352 if (thing->snext)
353 thing->snext->sprev = thing->sprev;
354
355 if (thing->sprev)
356 thing->sprev->snext = thing->snext;
357 else
358 thing->subsector->sector->thinglist = thing->snext;
359 }
360
361 if ( ! (thing->flags & MF_NOBLOCKMAP) )
362 {
363 // inert things don't need to be in blockmap
364 // unlink from block map
365 if (thing->bnext)
366 thing->bnext->bprev = thing->bprev;
367
368 if (thing->bprev)
369 thing->bprev->bnext = thing->bnext;
370 else
371 {
372 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
373 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
374
375 if (blockx>=0 && blockx < bmapwidth
376 && blocky>=0 && blocky <bmapheight)
377 {
378 blocklinks[blocky*bmapwidth+blockx] = thing->bnext;
379 }
380 }
381 }
382 }
383
384
385 //
386 // P_SetThingPosition
387 // Links a thing into both a block and a subsector
388 // based on it's x y.
389 // Sets thing->subsector properly
390 //
391 void
P_SetThingPosition(mobj_t * thing)392 P_SetThingPosition (mobj_t* thing)
393 {
394 subsector_t* ss;
395 sector_t* sec;
396 int blockx;
397 int blocky;
398 mobj_t** link;
399
400
401 // link into subsector
402 ss = R_PointInSubsector (thing->x,thing->y);
403 thing->subsector = ss;
404
405 if ( ! (thing->flags & MF_NOSECTOR) )
406 {
407 // invisible things don't go into the sector links
408 sec = ss->sector;
409
410 thing->sprev = NULL;
411 thing->snext = sec->thinglist;
412
413 if (sec->thinglist)
414 sec->thinglist->sprev = thing;
415
416 sec->thinglist = thing;
417 }
418
419
420 // link into blockmap
421 if ( ! (thing->flags & MF_NOBLOCKMAP) )
422 {
423 // inert things don't need to be in blockmap
424 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
425 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
426
427 if (blockx>=0
428 && blockx < bmapwidth
429 && blocky>=0
430 && blocky < bmapheight)
431 {
432 link = &blocklinks[blocky*bmapwidth+blockx];
433 thing->bprev = NULL;
434 thing->bnext = *link;
435 if (*link)
436 (*link)->bprev = thing;
437
438 *link = thing;
439 }
440 else
441 {
442 // thing is off the map
443 thing->bnext = thing->bprev = NULL;
444 }
445 }
446 }
447
448
449
450 //
451 // BLOCK MAP ITERATORS
452 // For each line/thing in the given mapblock,
453 // call the passed PIT_* function.
454 // If the function returns false,
455 // exit with false without checking anything else.
456 //
457
458
459 //
460 // P_BlockLinesIterator
461 // The validcount flags are used to avoid checking lines
462 // that are marked in multiple mapblocks,
463 // so increment validcount before the first call
464 // to P_BlockLinesIterator, then make one or more calls
465 // to it.
466 //
467 boolean
P_BlockLinesIterator(int x,int y,boolean (* func)(line_t *))468 P_BlockLinesIterator
469 ( int x,
470 int y,
471 boolean(*func)(line_t*) )
472 {
473 int offset;
474 int32_t* list; // [crispy] BLOCKMAP limit
475 line_t* ld;
476
477 if (x<0
478 || y<0
479 || x>=bmapwidth
480 || y>=bmapheight)
481 {
482 return true;
483 }
484
485 offset = y*bmapwidth+x;
486
487 offset = *(blockmap+offset);
488
489 for ( list = blockmaplump+offset ; *list != -1 ; list++)
490 {
491 ld = &lines[*list];
492
493 if (ld->validcount == validcount)
494 continue; // line has already been checked
495
496 ld->validcount = validcount;
497
498 if ( !func(ld) )
499 return false;
500 }
501 return true; // everything was checked
502 }
503
504
505 //
506 // P_BlockThingsIterator
507 //
508 boolean
P_BlockThingsIterator(int x,int y,boolean (* func)(mobj_t *))509 P_BlockThingsIterator
510 ( int x,
511 int y,
512 boolean(*func)(mobj_t*) )
513 {
514 mobj_t* mobj;
515
516 if ( x<0
517 || y<0
518 || x>=bmapwidth
519 || y>=bmapheight)
520 {
521 return true;
522 }
523
524
525 for (mobj = blocklinks[y*bmapwidth+x] ;
526 mobj ;
527 mobj = mobj->bnext)
528 {
529 if (!func( mobj ) )
530 return false;
531 }
532 return true;
533 }
534
535
536
537 //
538 // INTERCEPT ROUTINES
539 //
540 static intercept_t* intercepts; // [crispy] remove INTERCEPTS limit
541 intercept_t* intercept_p;
542
543 // [crispy] remove INTERCEPTS limit
544 // taken from PrBoom+/src/p_maputl.c:422-433
check_intercept(void)545 static void check_intercept(void)
546 {
547 static size_t num_intercepts;
548 const size_t offset = intercept_p - intercepts;
549
550 if (offset >= num_intercepts)
551 {
552 num_intercepts = num_intercepts ? num_intercepts * 2 : MAXINTERCEPTS_ORIGINAL;
553 intercepts = I_Realloc(intercepts, sizeof(*intercepts) * num_intercepts);
554 intercept_p = intercepts + offset;
555 }
556 }
557
558 divline_t trace;
559 boolean earlyout;
560 int ptflags;
561
562 static void InterceptsOverrun(int num_intercepts, intercept_t *intercept);
563
564 // [crispy] show mapthing number in INTERCEPTS overflow warnings
565 extern mobj_t* shootthing;
566
567 //
568 // PIT_AddLineIntercepts.
569 // Looks for lines in the given block
570 // that intercept the given trace
571 // to add to the intercepts list.
572 //
573 // A line is crossed if its endpoints
574 // are on opposite sides of the trace.
575 // Returns true if earlyout and a solid line hit.
576 //
577 boolean
PIT_AddLineIntercepts(line_t * ld)578 PIT_AddLineIntercepts (line_t* ld)
579 {
580 int s1;
581 int s2;
582 fixed_t frac;
583 divline_t dl;
584
585 // avoid precision problems with two routines
586 if ( trace.dx > FRACUNIT*16
587 || trace.dy > FRACUNIT*16
588 || trace.dx < -FRACUNIT*16
589 || trace.dy < -FRACUNIT*16)
590 {
591 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
592 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
593 }
594 else
595 {
596 s1 = P_PointOnLineSide (trace.x, trace.y, ld);
597 s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
598 }
599
600 if (s1 == s2)
601 return true; // line isn't crossed
602
603 // hit the line
604 P_MakeDivline (ld, &dl);
605 frac = P_InterceptVector (&trace, &dl);
606
607 if (frac < 0)
608 return true; // behind source
609
610 // try to early out the check
611 if (earlyout
612 && frac < FRACUNIT
613 && !ld->backsector)
614 {
615 return false; // stop checking
616 }
617
618
619 check_intercept(); // [crispy] remove INTERCEPTS limit
620 intercept_p->frac = frac;
621 intercept_p->isaline = true;
622 intercept_p->d.line = ld;
623 InterceptsOverrun(intercept_p - intercepts, intercept_p);
624 // [crispy] intercepts overflow guard
625 if (intercept_p - intercepts == MAXINTERCEPTS_ORIGINAL + 1)
626 {
627 if (crispy->crosshair & CROSSHAIR_INTERCEPT)
628 return false;
629 else
630 // [crispy] print a warning
631 fprintf(stderr, "PIT_AddLineIntercepts: Triggered INTERCEPTS overflow!\n");
632 }
633 intercept_p++;
634
635 return true; // continue
636 }
637
638
639
640 //
641 // PIT_AddThingIntercepts
642 //
PIT_AddThingIntercepts(mobj_t * thing)643 boolean PIT_AddThingIntercepts (mobj_t* thing)
644 {
645 fixed_t x1;
646 fixed_t y1;
647 fixed_t x2;
648 fixed_t y2;
649
650 int s1;
651 int s2;
652
653 boolean tracepositive;
654
655 divline_t dl;
656
657 fixed_t frac;
658
659 tracepositive = (trace.dx ^ trace.dy)>0;
660
661 // check a corner to corner crossection for hit
662 if (tracepositive)
663 {
664 x1 = thing->x - thing->radius;
665 y1 = thing->y + thing->radius;
666
667 x2 = thing->x + thing->radius;
668 y2 = thing->y - thing->radius;
669 }
670 else
671 {
672 x1 = thing->x - thing->radius;
673 y1 = thing->y - thing->radius;
674
675 x2 = thing->x + thing->radius;
676 y2 = thing->y + thing->radius;
677 }
678
679 s1 = P_PointOnDivlineSide (x1, y1, &trace);
680 s2 = P_PointOnDivlineSide (x2, y2, &trace);
681
682 if (s1 == s2)
683 return true; // line isn't crossed
684
685 dl.x = x1;
686 dl.y = y1;
687 dl.dx = x2-x1;
688 dl.dy = y2-y1;
689
690 frac = P_InterceptVector (&trace, &dl);
691
692 if (frac < 0)
693 return true; // behind source
694
695 check_intercept(); // [crispy] remove INTERCEPTS limit
696 intercept_p->frac = frac;
697 intercept_p->isaline = false;
698 intercept_p->d.thing = thing;
699 InterceptsOverrun(intercept_p - intercepts, intercept_p);
700 // [crispy] intercepts overflow guard
701 if (intercept_p - intercepts == MAXINTERCEPTS_ORIGINAL + 1)
702 {
703 if (crispy->crosshair & CROSSHAIR_INTERCEPT)
704 return false;
705 else
706 // [crispy] print a warning
707 fprintf(stderr, "PIT_AddThingIntercepts: Triggered INTERCEPTS overflow!\n");
708 }
709 intercept_p++;
710
711 return true; // keep going
712 }
713
714
715 //
716 // P_TraverseIntercepts
717 // Returns true if the traverser function returns true
718 // for all lines.
719 //
720 boolean
P_TraverseIntercepts(traverser_t func,fixed_t maxfrac)721 P_TraverseIntercepts
722 ( traverser_t func,
723 fixed_t maxfrac )
724 {
725 int count;
726 fixed_t dist;
727 intercept_t* scan;
728 intercept_t* in;
729
730 count = intercept_p - intercepts;
731
732 in = 0; // shut up compiler warning
733
734 while (count--)
735 {
736 dist = INT_MAX;
737 for (scan = intercepts ; scan<intercept_p ; scan++)
738 {
739 if (scan->frac < dist)
740 {
741 dist = scan->frac;
742 in = scan;
743 }
744 }
745
746 if (dist > maxfrac)
747 return true; // checked everything in range
748
749 #if 0 // UNUSED
750 {
751 // don't check these yet, there may be others inserted
752 in = scan = intercepts;
753 for ( scan = intercepts ; scan<intercept_p ; scan++)
754 if (scan->frac > maxfrac)
755 *in++ = *scan;
756 intercept_p = in;
757 return false;
758 }
759 #endif
760
761 if ( !func (in) )
762 return false; // don't bother going farther
763
764 in->frac = INT_MAX;
765 }
766
767 return true; // everything was traversed
768 }
769
770 extern fixed_t bulletslope;
771
772 // Intercepts Overrun emulation, from PrBoom-plus.
773 // Thanks to Andrey Budko (entryway) for researching this and his
774 // implementation of Intercepts Overrun emulation in PrBoom-plus
775 // which this is based on.
776
777 typedef struct
778 {
779 int len;
780 void *addr;
781 boolean int16_array;
782 } intercepts_overrun_t;
783
784 // Intercepts memory table. This is where various variables are located
785 // in memory in Vanilla Doom. When the intercepts table overflows, we
786 // need to write to them.
787 //
788 // Almost all of the values to overwrite are 32-bit integers, except for
789 // playerstarts, which is effectively an array of 16-bit integers and
790 // must be treated differently.
791
792 static intercepts_overrun_t intercepts_overrun[] =
793 {
794 {4, NULL, false},
795 {4, NULL, /* &earlyout, */ false},
796 {4, NULL, /* &intercept_p, */ false},
797 {4, &lowfloor, false},
798 {4, &openbottom, false},
799 {4, &opentop, false},
800 {4, &openrange, false},
801 {4, NULL, false},
802 {120, NULL, /* &activeplats, */ false},
803 {8, NULL, false},
804 {4, &bulletslope, false},
805 {4, NULL, /* &swingx, */ false},
806 {4, NULL, /* &swingy, */ false},
807 {4, NULL, false},
808 {40, &playerstarts, true},
809 {4, NULL, /* &blocklinks, */ false},
810 {4, &bmapwidth, false},
811 {4, NULL, /* &blockmap, */ false},
812 {4, &bmaporgx, false},
813 {4, &bmaporgy, false},
814 {4, NULL, /* &blockmaplump, */ false},
815 {4, &bmapheight, false},
816 {0, NULL, false},
817 };
818
819 // Overwrite a specific memory location with a value.
820
InterceptsMemoryOverrun(int location,int value)821 static void InterceptsMemoryOverrun(int location, int value)
822 {
823 int i, offset;
824 int index;
825 void *addr;
826
827 i = 0;
828 offset = 0;
829
830 // Search down the array until we find the right entry
831
832 while (intercepts_overrun[i].len != 0)
833 {
834 if (offset + intercepts_overrun[i].len > location)
835 {
836 addr = intercepts_overrun[i].addr;
837
838 // Write the value to the memory location.
839 // 16-bit and 32-bit values are written differently.
840
841 if (addr != NULL)
842 {
843 if (intercepts_overrun[i].int16_array)
844 {
845 index = (location - offset) / 2;
846 ((short *) addr)[index] = value & 0xffff;
847 ((short *) addr)[index + 1] = (value >> 16) & 0xffff;
848 }
849 else
850 {
851 index = (location - offset) / 4;
852 ((int *) addr)[index] = value;
853 }
854 }
855
856 break;
857 }
858
859 offset += intercepts_overrun[i].len;
860 ++i;
861 }
862 }
863
864 // Emulate overruns of the intercepts[] array.
865
InterceptsOverrun(int num_intercepts,intercept_t * intercept)866 static void InterceptsOverrun(int num_intercepts, intercept_t *intercept)
867 {
868 int location;
869
870 if (num_intercepts <= MAXINTERCEPTS_ORIGINAL)
871 {
872 // No overrun
873
874 return;
875 }
876
877 location = (num_intercepts - MAXINTERCEPTS_ORIGINAL - 1) * 12;
878
879 // Overwrite memory that is overwritten in Vanilla Doom, using
880 // the values from the intercept structure.
881 //
882 // Note: the ->d.{thing,line} member should really have its
883 // address translated into the correct address value for
884 // Vanilla Doom.
885
886 InterceptsMemoryOverrun(location, intercept->frac);
887 InterceptsMemoryOverrun(location + 4, intercept->isaline);
888 InterceptsMemoryOverrun(location + 8, (intptr_t) intercept->d.thing);
889 }
890
891
892 //
893 // P_PathTraverse
894 // Traces a line from x1,y1 to x2,y2,
895 // calling the traverser function for each.
896 // Returns true if the traverser function returns true
897 // for all lines.
898 //
899 boolean
P_PathTraverse(fixed_t x1,fixed_t y1,fixed_t x2,fixed_t y2,int flags,boolean (* trav)(intercept_t *))900 P_PathTraverse
901 ( fixed_t x1,
902 fixed_t y1,
903 fixed_t x2,
904 fixed_t y2,
905 int flags,
906 boolean (*trav) (intercept_t *))
907 {
908 fixed_t xt1;
909 fixed_t yt1;
910 fixed_t xt2;
911 fixed_t yt2;
912
913 fixed_t xstep;
914 fixed_t ystep;
915
916 fixed_t partial;
917
918 fixed_t xintercept;
919 fixed_t yintercept;
920
921 int mapx;
922 int mapy;
923
924 int mapxstep;
925 int mapystep;
926
927 int count;
928
929 earlyout = (flags & PT_EARLYOUT) != 0;
930
931 validcount++;
932 intercept_p = intercepts;
933
934 if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
935 x1 += FRACUNIT; // don't side exactly on a line
936
937 if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
938 y1 += FRACUNIT; // don't side exactly on a line
939
940 trace.x = x1;
941 trace.y = y1;
942 trace.dx = x2 - x1;
943 trace.dy = y2 - y1;
944
945 x1 -= bmaporgx;
946 y1 -= bmaporgy;
947 xt1 = x1>>MAPBLOCKSHIFT;
948 yt1 = y1>>MAPBLOCKSHIFT;
949
950 x2 -= bmaporgx;
951 y2 -= bmaporgy;
952 xt2 = x2>>MAPBLOCKSHIFT;
953 yt2 = y2>>MAPBLOCKSHIFT;
954
955 if (xt2 > xt1)
956 {
957 mapxstep = 1;
958 partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
959 ystep = FixedDiv (y2-y1,abs(x2-x1));
960 }
961 else if (xt2 < xt1)
962 {
963 mapxstep = -1;
964 partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
965 ystep = FixedDiv (y2-y1,abs(x2-x1));
966 }
967 else
968 {
969 mapxstep = 0;
970 partial = FRACUNIT;
971 ystep = 256*FRACUNIT;
972 }
973
974 yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep);
975
976
977 if (yt2 > yt1)
978 {
979 mapystep = 1;
980 partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
981 xstep = FixedDiv (x2-x1,abs(y2-y1));
982 }
983 else if (yt2 < yt1)
984 {
985 mapystep = -1;
986 partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
987 xstep = FixedDiv (x2-x1,abs(y2-y1));
988 }
989 else
990 {
991 mapystep = 0;
992 partial = FRACUNIT;
993 xstep = 256*FRACUNIT;
994 }
995 xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
996
997 // Step through map blocks.
998 // Count is present to prevent a round off error
999 // from skipping the break.
1000 mapx = xt1;
1001 mapy = yt1;
1002
1003 for (count = 0 ; count < 64 ; count++)
1004 {
1005 if (flags & PT_ADDLINES)
1006 {
1007 if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts))
1008 return false; // early out
1009 }
1010
1011 if (flags & PT_ADDTHINGS)
1012 {
1013 if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts))
1014 return false; // early out
1015 }
1016
1017 if (mapx == xt2
1018 && mapy == yt2)
1019 {
1020 break;
1021 }
1022
1023 if ( (yintercept >> FRACBITS) == mapy)
1024 {
1025 yintercept += ystep;
1026 mapx += mapxstep;
1027 }
1028 else if ( (xintercept >> FRACBITS) == mapx)
1029 {
1030 xintercept += xstep;
1031 mapy += mapystep;
1032 }
1033
1034 }
1035 // go through the sorted list
1036 return P_TraverseIntercepts ( trav, FRACUNIT );
1037 }
1038
1039
1040
1041