1
2 /* P_maputl.c */
3
4 #include "doomdef.h"
5 #include "p_local.h"
6
7
8 /*
9 ===================
10 =
11 = P_AproxDistance
12 =
13 = Gives an estimation of distance (not exact)
14 =
15 ===================
16 */
17
P_AproxDistance(fixed_t dx,fixed_t dy)18 fixed_t P_AproxDistance (fixed_t dx, fixed_t dy)
19 {
20 dx = abs(dx);
21 dy = abs(dy);
22 if (dx < dy)
23 return dx+dy-(dx>>1);
24 return dx+dy-(dy>>1);
25 }
26
27
28 /*
29 ==================
30 =
31 = P_PointOnLineSide
32 =
33 = Returns 0 or 1
34 ==================
35 */
36
P_PointOnLineSide(fixed_t x,fixed_t y,line_t * line)37 int P_PointOnLineSide (fixed_t x, fixed_t y, line_t *line)
38 {
39 fixed_t dx,dy;
40 fixed_t left, right;
41
42 if (!line->dx)
43 {
44 if (x <= line->v1->x)
45 return line->dy > 0;
46 return line->dy < 0;
47 }
48 if (!line->dy)
49 {
50 if (y <= line->v1->y)
51 return line->dx < 0;
52 return line->dx > 0;
53 }
54
55 dx = (x - line->v1->x);
56 dy = (y - line->v1->y);
57
58 left = FixedMul ( line->dy>>FRACBITS , dx );
59 right = FixedMul ( dy , line->dx>>FRACBITS );
60
61 if (right < left)
62 return 0; /* front side */
63 return 1; /* back side */
64 }
65
66
67 /*
68 =================
69 =
70 = P_BoxOnLineSide
71 =
72 = Considers the line to be infinite
73 = Returns side 0 or 1, -1 if box crosses the line
74 =================
75 */
76
P_BoxOnLineSide(fixed_t * tmbox,line_t * ld)77 int P_BoxOnLineSide (fixed_t *tmbox, line_t *ld)
78 {
79 /* changed from int p1 */
80 int p1=0;
81 /* changed from int p2 */
82 int p2=0;
83
84 switch (ld->slopetype)
85 {
86 case ST_HORIZONTAL:
87 p1 = tmbox[BOXTOP] > ld->v1->y;
88 p2 = tmbox[BOXBOTTOM] > ld->v1->y;
89 if (ld->dx < 0)
90 {
91 p1 ^= 1;
92 p2 ^= 1;
93 }
94 break;
95 case ST_VERTICAL:
96 p1 = tmbox[BOXRIGHT] < ld->v1->x;
97 p2 = tmbox[BOXLEFT] < ld->v1->x;
98 if (ld->dy < 0)
99 {
100 p1 ^= 1;
101 p2 ^= 1;
102 }
103 break;
104 case ST_POSITIVE:
105 p1 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXTOP], ld);
106 p2 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld);
107 break;
108 case ST_NEGATIVE:
109 p1 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXTOP], ld);
110 p2 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld);
111 break;
112 }
113
114 if (p1 == p2)
115 return p1;
116 return -1;
117 }
118
119 /*
120 ==================
121 =
122 = P_PointOnDivlineSide
123 =
124 = Returns 0 or 1
125 ==================
126 */
127
P_PointOnDivlineSide(fixed_t x,fixed_t y,divline_t * line)128 int P_PointOnDivlineSide (fixed_t x, fixed_t y, divline_t *line)
129 {
130 fixed_t dx,dy;
131 fixed_t left, right;
132
133 if (!line->dx)
134 {
135 if (x <= line->x)
136 return line->dy > 0;
137 return line->dy < 0;
138 }
139 if (!line->dy)
140 {
141 if (y <= line->y)
142 return line->dx < 0;
143 return line->dx > 0;
144 }
145
146 dx = (x - line->x);
147 dy = (y - line->y);
148
149 /* try to quickly decide by looking at sign bits */
150 if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
151 {
152 if ( (line->dy ^ dx) & 0x80000000 )
153 return 1; /* (left is negative) */
154 return 0;
155 }
156
157 left = FixedMul ( line->dy>>8, dx>>8 );
158 right = FixedMul ( dy>>8 , line->dx>>8 );
159
160 if (right < left)
161 return 0; /* front side */
162 return 1; /* back side */
163 }
164
165
166
167 /*
168 ==============
169 =
170 = P_MakeDivline
171 =
172 ==============
173 */
174
P_MakeDivline(line_t * li,divline_t * dl)175 void P_MakeDivline (line_t *li, divline_t *dl)
176 {
177 dl->x = li->v1->x;
178 dl->y = li->v1->y;
179 dl->dx = li->dx;
180 dl->dy = li->dy;
181 }
182
183
184 /*
185 ===============
186 =
187 = P_InterceptVector
188 =
189 = Returns the fractional intercept point along the first divline
190 =
191 = This is only called by the addthings and addlines traversers
192 ===============
193 */
194
P_InterceptVector(divline_t * v2,divline_t * v1)195 fixed_t P_InterceptVector (divline_t *v2, divline_t *v1)
196 {
197 #if 1
198 fixed_t frac, num, den;
199
200 den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
201 if (den == 0)
202 return 0;
203 /* I_Error ("P_InterceptVector: parallel"); */
204 num = FixedMul ( (v1->x - v2->x)>>8 ,v1->dy) +
205 FixedMul ( (v2->y - v1->y)>>8 , v1->dx);
206 frac = FixedDiv (num , den);
207
208 return frac;
209 #else
210 float frac, num, den, v1x,v1y,v1dx,v1dy,v2x,v2y,v2dx,v2dy;
211
212 v1x = (float)v1->x/FRACUNIT;
213 v1y = (float)v1->y/FRACUNIT;
214 v1dx = (float)v1->dx/FRACUNIT;
215 v1dy = (float)v1->dy/FRACUNIT;
216 v2x = (float)v2->x/FRACUNIT;
217 v2y = (float)v2->y/FRACUNIT;
218 v2dx = (float)v2->dx/FRACUNIT;
219 v2dy = (float)v2->dy/FRACUNIT;
220
221 den = v1dy*v2dx - v1dx*v2dy;
222 if (den == 0)
223 return 0; /* parallel */
224 num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx;
225 frac = num / den;
226
227 return frac*FRACUNIT;
228 #endif
229 }
230
231 /*
232 ==================
233 =
234 = P_LineOpening
235 =
236 = Sets opentop and openbottom to the window through a two sided line
237 = OPTIMIZE: keep this precalculated
238 ==================
239 */
240
241 fixed_t opentop, openbottom, openrange;
242 fixed_t lowfloor;
243
P_LineOpening(line_t * linedef)244 void P_LineOpening (line_t *linedef)
245 {
246 sector_t *front, *back;
247
248 if (linedef->sidenum[1] == -1)
249 { /* single sided line */
250 openrange = 0;
251 return;
252 }
253
254 front = linedef->frontsector;
255 back = linedef->backsector;
256
257 if (front->ceilingheight < back->ceilingheight)
258 opentop = front->ceilingheight;
259 else
260 opentop = back->ceilingheight;
261 if (front->floorheight > back->floorheight)
262 {
263 openbottom = front->floorheight;
264 lowfloor = back->floorheight;
265 }
266 else
267 {
268 openbottom = back->floorheight;
269 lowfloor = front->floorheight;
270 }
271
272 openrange = opentop - openbottom;
273 }
274
275 /*
276 ===============================================================================
277
278 THING POSITION SETTING
279
280 ===============================================================================
281 */
282
283 /*
284 ===================
285 =
286 = P_UnsetThingPosition
287 =
288 = Unlinks a thing from block map and sectors
289 =
290 ===================
291 */
292
P_UnsetThingPosition(mobj_t * thing)293 void P_UnsetThingPosition (mobj_t *thing)
294 {
295 int blockx, blocky;
296
297 if ( ! (thing->flags & MF_NOSECTOR) )
298 { /* inert things don't need to be in blockmap */
299 /* unlink from subsector */
300 if (thing->snext)
301 thing->snext->sprev = thing->sprev;
302 if (thing->sprev)
303 thing->sprev->snext = thing->snext;
304 else
305 thing->subsector->sector->thinglist = thing->snext;
306 }
307
308 if ( ! (thing->flags & MF_NOBLOCKMAP) )
309 { /* inert things don't need to be in blockmap */
310 /* unlink from block map */
311 if (thing->bnext)
312 thing->bnext->bprev = thing->bprev;
313 if (thing->bprev)
314 thing->bprev->bnext = thing->bnext;
315 else
316 {
317 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
318 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
319 if (blockx>=0 && blockx < bmapwidth
320 && blocky>=0 && blocky <bmapheight)
321 blocklinks[blocky*bmapwidth+blockx] = thing->bnext;
322 }
323 }
324 }
325
326
327 /*
328 ===================
329 =
330 = P_SetThingPosition
331 =
332 = Links a thing into both a block and a subsector based on it's x y
333 = Sets thing->subsector properly
334 =
335 ===================
336 */
337
P_SetThingPosition(mobj_t * thing)338 void P_SetThingPosition (mobj_t *thing)
339 {
340 subsector_t *ss;
341 sector_t *sec;
342 int blockx, blocky;
343 mobj_t **link;
344
345 /*
346 * link into subsector
347 */
348 ss = R_PointInSubsector (thing->x,thing->y);
349 thing->subsector = ss;
350 if ( ! (thing->flags & MF_NOSECTOR) )
351 { /* invisible things don't go into the sector links */
352 sec = ss->sector;
353
354 thing->sprev = NULL;
355 thing->snext = sec->thinglist;
356 if (sec->thinglist)
357 sec->thinglist->sprev = thing;
358 sec->thinglist = thing;
359 }
360
361 /*
362 * link into blockmap
363 */
364 if ( ! (thing->flags & MF_NOBLOCKMAP) )
365 { /* inert things don't need to be in blockmap */
366 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
367 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
368 if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky <bmapheight)
369 {
370 link = &blocklinks[blocky*bmapwidth+blockx];
371 thing->bprev = NULL;
372 thing->bnext = *link;
373 if (*link)
374 (*link)->bprev = thing;
375 *link = thing;
376 }
377 else
378 { /* thing is off the map */
379 thing->bnext = thing->bprev = NULL;
380 }
381 }
382 }
383
384
385
386 /*
387 ===============================================================================
388
389 BLOCK MAP ITERATORS
390
391 For each line/thing in the given mapblock, call the passed function.
392 If the function returns false, exit with false without checking anything else.
393
394 ===============================================================================
395 */
396
397 /*
398 ==================
399 =
400 = P_BlockLinesIterator
401 =
402 = The validcount flags are used to avoid checking lines
403 = that are marked in multiple mapblocks, so increment validcount before
404 = the first call to P_BlockLinesIterator, then make one or more calls to it
405 ===================
406 */
407
P_BlockLinesIterator(int x,int y,boolean (* func)(line_t *))408 boolean P_BlockLinesIterator (int x, int y, boolean(*func)(line_t*) )
409 {
410 int offset;
411 short *list;
412 line_t *ld;
413
414 if (x<0
415 || y<0
416 || x>=bmapwidth
417 || y>=bmapheight)
418 return true;
419 offset = y*bmapwidth+x;
420
421 offset = *(blockmap+offset);
422
423 for ( list = blockmaplump+offset ; *list != -1 ; list++)
424 {
425 ld = &lines[*list];
426 if (ld->validcount == validcount)
427 continue; /* line has already been checked */
428 ld->validcount = validcount;
429
430 if ( !func(ld) )
431 return false;
432 }
433
434 return true; /* everything was checked */
435 }
436
437
438 /*
439 ==================
440 =
441 = P_BlockThingsIterator
442 =
443 ==================
444 */
445
P_BlockThingsIterator(int x,int y,boolean (* func)(mobj_t *))446 boolean P_BlockThingsIterator (int x, int y, boolean(*func)(mobj_t*) )
447 {
448 mobj_t *mobj;
449
450 if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
451 return true;
452
453 for (mobj = blocklinks[y*bmapwidth+x] ; mobj ; mobj = mobj->bnext)
454 if (!func( mobj ) )
455 return false;
456
457 return true;
458 }
459
460 /*
461 ===============================================================================
462
463 INTERCEPT ROUTINES
464
465 ===============================================================================
466 */
467
468 intercept_t intercepts[MAXINTERCEPTS], *intercept_p;
469
470 divline_t trace;
471 boolean earlyout;
472 int ptflags;
473
474 /*
475 ==================
476 =
477 = PIT_AddLineIntercepts
478 =
479 = Looks for lines in the given block that intercept the given trace
480 = to add to the intercepts list
481 = A line is crossed if its endpoints are on opposite sides of the trace
482 = Returns true if earlyout and a solid line hit
483 ==================
484 */
485
PIT_AddLineIntercepts(line_t * ld)486 boolean PIT_AddLineIntercepts (line_t *ld)
487 {
488 int s1, s2;
489 fixed_t frac;
490 divline_t dl;
491
492 /* avoid precision problems with two routines */
493 if ( trace.dx > FRACUNIT*16 || trace.dy > FRACUNIT*16
494 || trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16)
495 {
496 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
497 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
498 }
499 else
500 {
501 s1 = P_PointOnLineSide (trace.x, trace.y, ld);
502 s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
503 }
504 if (s1 == s2)
505 return true; /* line isn't crossed */
506
507 /*
508 * hit the line
509 */
510 P_MakeDivline (ld, &dl);
511 frac = P_InterceptVector (&trace, &dl);
512 if (frac < 0)
513 return true; /* behind source */
514
515 /* try to early out the check */
516 if (earlyout && frac < FRACUNIT && !ld->backsector)
517 return false; /* stop checking */
518
519 intercept_p->frac = frac;
520 intercept_p->isaline = true;
521 intercept_p->d.line = ld;
522 intercept_p++;
523
524 return true; /* continue */
525 }
526
527
528
529 /*
530 ==================
531 =
532 = PIT_AddThingIntercepts
533 =
534 ==================
535 */
536
PIT_AddThingIntercepts(mobj_t * thing)537 boolean PIT_AddThingIntercepts (mobj_t *thing)
538 {
539 fixed_t x1,y1, x2,y2;
540 int s1, s2;
541 boolean tracepositive;
542 divline_t dl;
543 fixed_t frac;
544
545 tracepositive = (trace.dx ^ trace.dy)>0;
546
547 /* check a corner to corner crossection for hit */
548
549 if (tracepositive)
550 {
551 x1 = thing->x - thing->radius;
552 y1 = thing->y + thing->radius;
553
554 x2 = thing->x + thing->radius;
555 y2 = thing->y - thing->radius;
556 }
557 else
558 {
559 x1 = thing->x - thing->radius;
560 y1 = thing->y - thing->radius;
561
562 x2 = thing->x + thing->radius;
563 y2 = thing->y + thing->radius;
564 }
565 s1 = P_PointOnDivlineSide (x1, y1, &trace);
566 s2 = P_PointOnDivlineSide (x2, y2, &trace);
567 if (s1 == s2)
568 return true; /* line isn't crossed */
569
570 dl.x = x1;
571 dl.y = y1;
572 dl.dx = x2-x1;
573 dl.dy = y2-y1;
574 frac = P_InterceptVector (&trace, &dl);
575 if (frac < 0)
576 return true; /* behind source */
577 intercept_p->frac = frac;
578 intercept_p->isaline = false;
579 intercept_p->d.thing = thing;
580 intercept_p++;
581
582 return true; /* keep going */
583 }
584
585 #ifdef GL_HERETIC
PIT_AddThingInterceptsForCorona(mobj_t * thing)586 boolean PIT_AddThingInterceptsForCorona (mobj_t* thing) {
587 fixed_t x1;
588 fixed_t y1;
589 fixed_t x2;
590 fixed_t y2;
591
592 int s1;
593 int s2;
594
595 boolean tracepositive;
596
597 divline_t dl;
598
599 fixed_t frac;
600
601 tracepositive = (trace.dx ^ trace.dy)>0;
602
603 /* check a corner to corner crossection for hit */
604 if (tracepositive)
605 {
606 x1 = thing->x - thing->radius/2;
607 y1 = thing->y + thing->radius/2;
608
609 x2 = thing->x + thing->radius/2;
610 y2 = thing->y - thing->radius/2;
611 }
612 else
613 {
614 x1 = thing->x - thing->radius/2;
615 y1 = thing->y - thing->radius/2;
616
617 x2 = thing->x + thing->radius/2;
618 y2 = thing->y + thing->radius/2;
619 }
620
621 s1 = P_PointOnDivlineSide (x1, y1, &trace);
622 s2 = P_PointOnDivlineSide (x2, y2, &trace);
623
624 if (s1 == s2)
625 return true; /* line isn't crossed */
626
627 dl.x = x1;
628 dl.y = y1;
629 dl.dx = x2-x1;
630 dl.dy = y2-y1;
631
632 frac = P_InterceptVector (&trace, &dl);
633
634 if (frac < 0)
635 return true; /* behind source */
636
637 intercept_p->frac = frac;
638 intercept_p->isaline = false;
639 intercept_p->d.thing = thing;
640 intercept_p++;
641
642 return true; /* keep going */
643 }
644 #endif /* GL_HERETIC */
645
646 /*
647 ====================
648 =
649 = P_TraverseIntercepts
650 =
651 = Returns true if the traverser function returns true for all lines
652 ====================
653 */
654
P_TraverseIntercepts(traverser_t func,fixed_t maxfrac)655 boolean P_TraverseIntercepts ( traverser_t func, fixed_t maxfrac )
656 {
657 int count;
658 fixed_t dist;
659 intercept_t *scan, *in;
660
661 count = intercept_p - intercepts;
662 in = 0; /* shut up compiler warning */
663
664 while (count--)
665 {
666 dist = MAXINT;
667 for (scan = intercepts ; scan<intercept_p ; scan++)
668 if (scan->frac < dist)
669 {
670 dist = scan->frac;
671 in = scan;
672 }
673
674 if (dist > maxfrac)
675 return true; /* checked everything in range */
676 #if 0
677 { /* don't check these yet, ther may be others inserted */
678 in = scan = intercepts;
679 for ( scan = intercepts ; scan<intercept_p ; scan++)
680 if (scan->frac > maxfrac)
681 *in++ = *scan;
682 intercept_p = in;
683 return false;
684 }
685 #endif
686
687 if ( !func (in) )
688 return false; /* don't bother going farther */
689 in->frac = MAXINT;
690 }
691
692 return true; /* everything was traversed */
693 }
694
695
696
697 /*
698 ==================
699 =
700 = P_PathTraverse
701 =
702 = Traces a line from x1,y1 to x2,y2, calling the traverser function for each
703 = Returns true if the traverser function returns true for all lines
704 ==================
705 */
706
P_PathTraverse(fixed_t x1,fixed_t y1,fixed_t x2,fixed_t y2,int flags,boolean (* trav)(intercept_t *))707 boolean P_PathTraverse (fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2,
708 int flags, boolean (*trav) (intercept_t *))
709 {
710 fixed_t xt1,yt1,xt2,yt2;
711 fixed_t xstep,ystep;
712 fixed_t partial;
713 fixed_t xintercept, yintercept;
714 int mapx, mapy, mapxstep, mapystep;
715 int count;
716
717 earlyout = flags & PT_EARLYOUT;
718
719 validcount++;
720 intercept_p = intercepts;
721
722 if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
723 x1 += FRACUNIT; /* don't side exactly on a line */
724 if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
725 y1 += FRACUNIT; /* don't side exactly on a line */
726 trace.x = x1;
727 trace.y = y1;
728 trace.dx = x2 - x1;
729 trace.dy = y2 - y1;
730
731 x1 -= bmaporgx;
732 y1 -= bmaporgy;
733 xt1 = x1>>MAPBLOCKSHIFT;
734 yt1 = y1>>MAPBLOCKSHIFT;
735
736 x2 -= bmaporgx;
737 y2 -= bmaporgy;
738 xt2 = x2>>MAPBLOCKSHIFT;
739 yt2 = y2>>MAPBLOCKSHIFT;
740
741 if (xt2 > xt1)
742 {
743 mapxstep = 1;
744 partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
745 ystep = FixedDiv (y2-y1,abs(x2-x1));
746 }
747 else if (xt2 < xt1)
748 {
749 mapxstep = -1;
750 partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
751 ystep = FixedDiv (y2-y1,abs(x2-x1));
752 }
753 else
754 {
755 mapxstep = 0;
756 partial = FRACUNIT;
757 ystep = 256*FRACUNIT;
758 }
759 yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep);
760
761
762 if (yt2 > yt1)
763 {
764 mapystep = 1;
765 partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
766 xstep = FixedDiv (x2-x1,abs(y2-y1));
767 }
768 else if (yt2 < yt1)
769 {
770 mapystep = -1;
771 partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
772 xstep = FixedDiv (x2-x1,abs(y2-y1));
773 }
774 else
775 {
776 mapystep = 0;
777 partial = FRACUNIT;
778 xstep = 256*FRACUNIT;
779 }
780 xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
781
782
783 /*
784 * step through map blocks
785 * Count is present to prevent a round off error from skipping the break
786 */
787 mapx = xt1;
788 mapy = yt1;
789
790 for (count = 0 ; count < 64 ; count++)
791 {
792 if (flags & PT_ADDLINES)
793 {
794 if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts))
795 return false; /* early out */
796 }
797 if (flags & PT_ADDTHINGS)
798 {
799 if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts))
800 return false; /* early out */
801 }
802
803 #ifdef GL_HERETIC
804 if (flags & PT_ADDTHINGS2)
805 {
806 if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingInterceptsForCorona))
807 return false; /* early out */
808 }
809 #endif
810
811 if (mapx == xt2 && mapy == yt2)
812 break;
813
814 if ( (yintercept >> FRACBITS) == mapy)
815 {
816 yintercept += ystep;
817 mapx += mapxstep;
818 }
819 else if ( (xintercept >> FRACBITS) == mapx)
820 {
821 xintercept += xstep;
822 mapy += mapystep;
823 }
824
825 }
826
827
828 /*
829 * go through the sorted list
830 */
831 return P_TraverseIntercepts ( trav, FRACUNIT );
832 }
833
834
835
836