1 // Emacs style mode select -*- C++ -*-
2 //-----------------------------------------------------------------------------
3 //
4 // $Id:$
5 //
6 // Copyright (C) 1993-1996 by id Software, Inc.
7 //
8 // This source is available for distribution and/or modification
9 // only under the terms of the DOOM Source Code License as
10 // published by id Software. All rights reserved.
11 //
12 // The source is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License
15 // for more details.
16 //
17 // $Log:$
18 //
19 // DESCRIPTION:
20 // Movement/collision utility functions,
21 // as used by function in p_map.c.
22 // BLOCKMAP Iterator functions,
23 // and some PIT_* functions to use for iteration.
24 //
25 //-----------------------------------------------------------------------------
26
27
28
29 #include <stdlib.h>
30
31
32 #include "m_bbox.h"
33
34 #include "doomdef.h"
35 #include "doomstat.h"
36 #include "p_local.h"
37 #include "p_3dmidtex.h"
38
39 // State.
40 #include "r_state.h"
41 #include "templates.h"
42 #include "po_man.h"
43
44 static AActor *RoughBlockCheck (AActor *mo, int index, void *);
45
46
47 //==========================================================================
48 //
49 // P_AproxDistance
50 //
51 // Gives an estimation of distance (not exact)
52 //
53 //==========================================================================
54
P_AproxDistance(fixed_t dx,fixed_t dy)55 fixed_t P_AproxDistance (fixed_t dx, fixed_t dy)
56 {
57 dx = abs(dx);
58 dy = abs(dy);
59 return (dx < dy) ? dx+dy-(dx>>1) : dx+dy-(dy>>1);
60 }
61
62 //==========================================================================
63 //
64 // P_InterceptVector
65 //
66 // Returns the fractional intercept point along the first divline.
67 //
68 //==========================================================================
69
P_InterceptVector(const divline_t * v2,const divline_t * v1)70 fixed_t P_InterceptVector (const divline_t *v2, const divline_t *v1)
71 {
72 #if 0 // [RH] Use 64 bit ints, so long divlines don't overflow
73
74 SQWORD den = ( ((SQWORD)v1->dy*v2->dx - (SQWORD)v1->dx*v2->dy) >> FRACBITS );
75 if (den == 0)
76 return 0; // parallel
77 SQWORD num = ((SQWORD)(v1->x - v2->x)*v1->dy + (SQWORD)(v2->y - v1->y)*v1->dx);
78 return (fixed_t)(num / den);
79
80 #elif 0 // This is the original Doom version
81
82 fixed_t frac;
83 fixed_t num;
84 fixed_t den;
85
86 den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
87
88 if (den == 0)
89 return 0;
90 // I_Error ("P_InterceptVector: parallel");
91
92 num =
93 FixedMul ( (v1->x - v2->x)>>8 ,v1->dy )
94 +FixedMul ( (v2->y - v1->y)>>8, v1->dx );
95
96 frac = FixedDiv (num , den);
97
98 return frac;
99
100 #else // optimized version of the float debug version. A lot faster on modern systens.
101
102
103 double frac;
104 double num;
105 double den;
106
107 // There's no need to divide by FRACUNIT here.
108 // At the end both num and den will contain a factor
109 // 1/(FRACUNIT*FRACUNIT) so they'll cancel each other out.
110 double v1x = (double)v1->x;
111 double v1y = (double)v1->y;
112 double v1dx = (double)v1->dx;
113 double v1dy = (double)v1->dy;
114 double v2x = (double)v2->x;
115 double v2y = (double)v2->y;
116 double v2dx = (double)v2->dx;
117 double v2dy = (double)v2->dy;
118
119 den = v1dy*v2dx - v1dx*v2dy;
120
121 if (den == 0)
122 return 0; // parallel
123
124 num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx;
125 frac = num / den;
126
127 return FLOAT2FIXED(frac);
128 #endif
129 }
130
131
132 //==========================================================================
133 //
134 // P_LineOpening
135 //
136 // Sets opentop and openbottom to the window
137 // through a two sided line.
138 //
139 //==========================================================================
140
P_LineOpening(FLineOpening & open,AActor * actor,const line_t * linedef,fixed_t x,fixed_t y,fixed_t refx,fixed_t refy,int flags)141 void P_LineOpening (FLineOpening &open, AActor *actor, const line_t *linedef,
142 fixed_t x, fixed_t y, fixed_t refx, fixed_t refy, int flags)
143 {
144 if (!(flags & FFCF_ONLY3DFLOORS))
145 {
146 sector_t *front, *back;
147 fixed_t fc, ff, bc, bf;
148
149 if (linedef->sidedef[1] == NULL)
150 {
151 // single sided line
152 open.range = 0;
153 return;
154 }
155
156 front = linedef->frontsector;
157 back = linedef->backsector;
158
159 fc = front->ceilingplane.ZatPoint (x, y);
160 ff = front->floorplane.ZatPoint (x, y);
161 bc = back->ceilingplane.ZatPoint (x, y);
162 bf = back->floorplane.ZatPoint (x, y);
163
164 /*Printf ("]]]]]] %d %d\n", ff, bf);*/
165
166 open.topsec = fc < bc? front : back;
167 open.ceilingpic = open.topsec->GetTexture(sector_t::ceiling);
168 open.top = fc < bc ? fc : bc;
169
170 bool usefront;
171
172 // [RH] fudge a bit for actors that are moving across lines
173 // bordering a slope/non-slope that meet on the floor. Note
174 // that imprecisions in the plane equation mean there is a
175 // good chance that even if a slope and non-slope look like
176 // they line up, they won't be perfectly aligned.
177 if (refx == FIXED_MIN ||
178 abs (ff-bf) > 256)
179 {
180 usefront = (ff > bf);
181 }
182 else
183 {
184 if ((front->floorplane.a | front->floorplane.b) == 0)
185 usefront = true;
186 else if ((back->floorplane.a | front->floorplane.b) == 0)
187 usefront = false;
188 else
189 usefront = !P_PointOnLineSide (refx, refy, linedef);
190 }
191
192 if (usefront)
193 {
194 open.bottom = ff;
195 open.bottomsec = front;
196 open.floorpic = front->GetTexture(sector_t::floor);
197 open.floorterrain = front->GetTerrain(sector_t::floor);
198 open.lowfloor = bf;
199 }
200 else
201 {
202 open.bottom = bf;
203 open.bottomsec = back;
204 open.floorpic = back->GetTexture(sector_t::floor);
205 open.floorterrain = back->GetTerrain(sector_t::floor);
206 open.lowfloor = ff;
207 }
208 }
209 else
210 { // Dummy stuff to have some sort of opening for the 3D checks to modify
211 open.topsec = NULL;
212 open.ceilingpic.SetInvalid();
213 open.top = FIXED_MAX;
214 open.bottomsec = NULL;
215 open.floorpic.SetInvalid();
216 open.floorterrain = -1;
217 open.bottom = FIXED_MIN;
218 open.lowfloor = FIXED_MAX;
219 }
220
221 // Check 3D floors
222 if (actor != NULL)
223 {
224 P_LineOpening_XFloors(open, actor, linedef, x, y, refx, refy, !!(flags & FFCF_3DRESTRICT));
225 }
226
227 if (actor != NULL && linedef->frontsector != NULL && linedef->backsector != NULL &&
228 linedef->flags & ML_3DMIDTEX)
229 {
230 open.touchmidtex = P_LineOpening_3dMidtex(actor, linedef, open, !!(flags & FFCF_3DRESTRICT));
231 }
232 else
233 {
234 open.abovemidtex = open.touchmidtex = false;
235 }
236
237 open.range = open.top - open.bottom;
238 }
239
240
241 //
242 // THING POSITION SETTING
243 //
244
245 //==========================================================================
246 //
247 // P_UnsetThingPosition
248 // Unlinks a thing from block map and sectors.
249 // On each position change, BLOCKMAP and other
250 // lookups maintaining lists of things inside
251 // these structures need to be updated.
252 //
253 //==========================================================================
254
UnlinkFromWorld()255 void AActor::UnlinkFromWorld ()
256 {
257 sector_list = NULL;
258 if (!(flags & MF_NOSECTOR))
259 {
260 // invisible things don't need to be in sector list
261 // unlink from subsector
262
263 // killough 8/11/98: simpler scheme using pointers-to-pointers for prev
264 // pointers, allows head node pointers to be treated like everything else
265 AActor **prev = sprev;
266 AActor *next = snext;
267
268 if (prev != NULL) // prev will be NULL if this actor gets deleted due to cleaning up from a broken savegame
269 {
270 if ((*prev = next)) // unlink from sector list
271 next->sprev = prev;
272 snext = NULL;
273 sprev = (AActor **)(size_t)0xBeefCafe; // Woo! Bug-catching value!
274
275 // phares 3/14/98
276 //
277 // Save the sector list pointed to by touching_sectorlist.
278 // In P_SetThingPosition, we'll keep any nodes that represent
279 // sectors the Thing still touches. We'll add new ones then, and
280 // delete any nodes for sectors the Thing has vacated. Then we'll
281 // put it back into touching_sectorlist. It's done this way to
282 // avoid a lot of deleting/creating for nodes, when most of the
283 // time you just get back what you deleted anyway.
284 //
285 // If this Thing is being removed entirely, then the calling
286 // routine will clear out the nodes in sector_list.
287
288 sector_list = touching_sectorlist;
289 touching_sectorlist = NULL; //to be restored by P_SetThingPosition
290 }
291 }
292
293 if (!(flags & MF_NOBLOCKMAP))
294 {
295 // [RH] Unlink from all blocks this actor uses
296 FBlockNode *block = this->BlockNode;
297
298 while (block != NULL)
299 {
300 if (block->NextActor != NULL)
301 {
302 block->NextActor->PrevActor = block->PrevActor;
303 }
304 *(block->PrevActor) = block->NextActor;
305 FBlockNode *next = block->NextBlock;
306 block->Release ();
307 block = next;
308 }
309 BlockNode = NULL;
310 }
311 }
312
313
314 //==========================================================================
315 //
316 // P_SetThingPosition
317 // Links a thing into both a block and a subsector based on it's x y.
318 // Sets thing->sector properly
319 //
320 //==========================================================================
321
LinkToWorld(bool buggy)322 void AActor::LinkToWorld (bool buggy)
323 {
324 // link into subsector
325 sector_t *sec;
326
327 if (!buggy || numgamenodes == 0)
328 {
329 sec = P_PointInSector (X(), Y());
330 }
331 else
332 {
333 sec = LinkToWorldForMapThing ();
334 }
335
336 LinkToWorld (sec);
337 }
338
LinkToWorld(sector_t * sec)339 void AActor::LinkToWorld (sector_t *sec)
340 {
341 if (sec == NULL)
342 {
343 LinkToWorld ();
344 return;
345 }
346 Sector = sec;
347 subsector = R_PointInSubsector(X(), Y()); // this is from the rendering nodes, not the gameplay nodes!
348
349 if ( !(flags & MF_NOSECTOR) )
350 {
351 // invisible things don't go into the sector links
352 // killough 8/11/98: simpler scheme using pointer-to-pointer prev
353 // pointers, allows head nodes to be treated like everything else
354
355 AActor **link = &sec->thinglist;
356 AActor *next = *link;
357 if ((snext = next))
358 next->sprev = &snext;
359 sprev = link;
360 *link = this;
361
362 // phares 3/16/98
363 //
364 // If sector_list isn't NULL, it has a collection of sector
365 // nodes that were just removed from this Thing.
366
367 // Collect the sectors the object will live in by looking at
368 // the existing sector_list and adding new nodes and deleting
369 // obsolete ones.
370
371 // When a node is deleted, its sector links (the links starting
372 // at sector_t->touching_thinglist) are broken. When a node is
373 // added, new sector links are created.
374 P_CreateSecNodeList (this, X(), Y());
375 touching_sectorlist = sector_list; // Attach to thing
376 sector_list = NULL; // clear for next time
377 }
378
379
380 // link into blockmap (inert things don't need to be in the blockmap)
381 if ( !(flags & MF_NOBLOCKMAP) )
382 {
383 int x1 = GetSafeBlockX(X() - radius - bmaporgx);
384 int x2 = GetSafeBlockX(X() + radius - bmaporgx);
385 int y1 = GetSafeBlockY(Y() - radius - bmaporgy);
386 int y2 = GetSafeBlockY(Y() + radius - bmaporgy);
387
388 if (x1 >= bmapwidth || x2 < 0 || y1 >= bmapheight || y2 < 0)
389 { // thing is off the map
390 BlockNode = NULL;
391 }
392 else
393 { // [RH] Link into every block this actor touches, not just the center one
394 FBlockNode **alink = &this->BlockNode;
395 x1 = MAX (0, x1);
396 y1 = MAX (0, y1);
397 x2 = MIN (bmapwidth - 1, x2);
398 y2 = MIN (bmapheight - 1, y2);
399 for (int y = y1; y <= y2; ++y)
400 {
401 for (int x = x1; x <= x2; ++x)
402 {
403 FBlockNode **link = &blocklinks[y*bmapwidth + x];
404 FBlockNode *node = FBlockNode::Create (this, x, y);
405
406 // Link in to block
407 if ((node->NextActor = *link) != NULL)
408 {
409 (*link)->PrevActor = &node->NextActor;
410 }
411 node->PrevActor = link;
412 *link = node;
413
414 // Link in to actor
415 node->PrevBlock = alink;
416 node->NextBlock = NULL;
417 (*alink) = node;
418 alink = &node->NextBlock;
419 }
420 }
421 }
422 }
423 }
424
425 //==========================================================================
426 //
427 // [RH] LinkToWorldForMapThing
428 //
429 // Emulate buggy PointOnLineSide and fix actors that lie on
430 // lines to compensate for some IWAD maps.
431 //
432 //==========================================================================
433
R_PointOnSideSlow(fixed_t x,fixed_t y,node_t * node)434 static int R_PointOnSideSlow (fixed_t x, fixed_t y, node_t *node)
435 {
436 // [RH] This might have been faster than two multiplies and an
437 // add on a 386/486, but it certainly isn't on anything newer than that.
438 fixed_t dx;
439 fixed_t dy;
440 double left;
441 double right;
442
443 if (!node->dx)
444 {
445 if (x <= node->x)
446 return node->dy > 0;
447
448 return node->dy < 0;
449 }
450 if (!node->dy)
451 {
452 if (y <= node->y)
453 return node->dx < 0;
454
455 return node->dx > 0;
456 }
457
458 dx = (x - node->x);
459 dy = (y - node->y);
460
461 // Try to quickly decide by looking at sign bits.
462 if ( (node->dy ^ node->dx ^ dx ^ dy)&0x80000000 )
463 {
464 if ( (node->dy ^ dx) & 0x80000000 )
465 {
466 // (left is negative)
467 return 1;
468 }
469 return 0;
470 }
471
472 // we must use doubles here because the fixed point code will produce errors due to loss of precision for extremely short linedefs.
473 left = (double)node->dy * (double)dx;
474 right = (double)dy * (double)node->dx;
475
476 if (right < left)
477 {
478 // front side
479 return 0;
480 }
481 // back side
482 return 1;
483 }
484
LinkToWorldForMapThing()485 sector_t *AActor::LinkToWorldForMapThing ()
486 {
487 node_t *node = gamenodes + numgamenodes - 1;
488
489 do
490 {
491 // Use original buggy point-on-side test when spawning
492 // things at level load so that the map spots in the
493 // emerald key room of Hexen MAP01 are spawned on the
494 // window ledge instead of the blocking floor in front
495 // of it. Why do I consider it buggy? Because a point
496 // that lies directly on a line should always be
497 // considered as "in front" of the line. The orientation
498 // of the line should be irrelevant.
499 node = (node_t *)node->children[R_PointOnSideSlow (X(), Y(), node)];
500 }
501 while (!((size_t)node & 1));
502
503 subsector_t *ssec = (subsector_t *)((BYTE *)node - 1);
504
505 if (flags4 & MF4_FIXMAPTHINGPOS)
506 {
507 // If the thing is exactly on a line, move it into the subsector
508 // slightly in order to resolve clipping issues in the renderer.
509 // This check needs to use the blockmap, because an actor on a
510 // one-sided line might go into a subsector behind the line, so
511 // the line would not be included as one of its subsector's segs.
512
513 int blockx = GetSafeBlockX(X() - bmaporgx);
514 int blocky = GetSafeBlockY(Y() - bmaporgy);
515
516 if ((unsigned int)blockx < (unsigned int)bmapwidth &&
517 (unsigned int)blocky < (unsigned int)bmapheight)
518 {
519 int *list;
520
521 for (list = blockmaplump + blockmap[blocky*bmapwidth + blockx] + 1; *list != -1; ++list)
522 {
523 line_t *ldef = &lines[*list];
524
525 if (ldef->frontsector == ldef->backsector)
526 { // Skip two-sided lines inside a single sector
527 continue;
528 }
529 if (ldef->backsector != NULL)
530 {
531 if (ldef->frontsector->floorplane == ldef->backsector->floorplane &&
532 ldef->frontsector->ceilingplane == ldef->backsector->ceilingplane)
533 { // Skip two-sided lines without any height difference on either side
534 continue;
535 }
536 }
537
538 // Not inside the line's bounding box
539 if (X() + radius <= ldef->bbox[BOXLEFT]
540 || X() - radius >= ldef->bbox[BOXRIGHT]
541 || Y() + radius <= ldef->bbox[BOXBOTTOM]
542 || Y() - radius >= ldef->bbox[BOXTOP] )
543 continue;
544
545 // Get the exact distance to the line
546 divline_t dll, dlv;
547 fixed_t linelen = (fixed_t)sqrt((double)ldef->dx*ldef->dx + (double)ldef->dy*ldef->dy);
548
549 P_MakeDivline (ldef, &dll);
550
551 dlv.x = X();
552 dlv.y = Y();
553 dlv.dx = FixedDiv(dll.dy, linelen);
554 dlv.dy = -FixedDiv(dll.dx, linelen);
555
556 fixed_t distance = abs(P_InterceptVector(&dlv, &dll));
557
558 if (distance < radius)
559 {
560 DPrintf ("%s at (%d,%d) lies on %s line %td, distance = %f\n",
561 this->GetClass()->TypeName.GetChars(), X()>>FRACBITS, Y()>>FRACBITS,
562 ldef->dx == 0? "vertical" : ldef->dy == 0? "horizontal" : "diagonal",
563 ldef-lines, FIXED2FLOAT(distance));
564 angle_t finean = R_PointToAngle2 (0, 0, ldef->dx, ldef->dy);
565 if (ldef->backsector != NULL && ldef->backsector == ssec->sector)
566 {
567 finean += ANGLE_90;
568 }
569 else
570 {
571 finean -= ANGLE_90;
572 }
573 finean >>= ANGLETOFINESHIFT;
574
575 // Get the distance we have to move the object away from the wall
576 distance = radius - distance;
577 SetXY(X() + FixedMul(distance, finecosine[finean]), Y() + FixedMul(distance, finesine[finean]));
578 return P_PointInSector (X(), Y());
579 }
580 }
581 }
582 }
583
584 return ssec->sector;
585 }
586
SetOrigin(fixed_t ix,fixed_t iy,fixed_t iz,bool moving)587 void AActor::SetOrigin (fixed_t ix, fixed_t iy, fixed_t iz, bool moving)
588 {
589 UnlinkFromWorld ();
590 SetXYZ(ix, iy, iz);
591 if (moving) SetMovement(ix - X(), iy - Y(), iz - Z());
592 LinkToWorld ();
593 floorz = Sector->floorplane.ZatPoint (ix, iy);
594 ceilingz = Sector->ceilingplane.ZatPoint (ix, iy);
595 P_FindFloorCeiling(this, FFCF_ONLYSPAWNPOS);
596 }
597
598 FBlockNode *FBlockNode::FreeBlocks = NULL;
599
Create(AActor * who,int x,int y)600 FBlockNode *FBlockNode::Create (AActor *who, int x, int y)
601 {
602 FBlockNode *block;
603
604 if (FreeBlocks != NULL)
605 {
606 block = FreeBlocks;
607 FreeBlocks = block->NextBlock;
608 }
609 else
610 {
611 block = new FBlockNode;
612 }
613 block->BlockIndex = x + y*bmapwidth;
614 block->Me = who;
615 block->NextActor = NULL;
616 block->PrevActor = NULL;
617 block->PrevBlock = NULL;
618 block->NextBlock = NULL;
619 return block;
620 }
621
Release()622 void FBlockNode::Release ()
623 {
624 NextBlock = FreeBlocks;
625 FreeBlocks = this;
626 }
627
628 //
629 // BLOCK MAP ITERATORS
630 // For each line/thing in the given mapblock,
631 // call the passed PIT_* function.
632 // If the function returns false,
633 // exit with false without checking anything else.
634 //
635
636
637 //===========================================================================
638 //
639 // FBlockLinesIterator
640 //
641 //===========================================================================
642 extern polyblock_t **PolyBlockMap;
643
FBlockLinesIterator(int _minx,int _miny,int _maxx,int _maxy,bool keepvalidcount)644 FBlockLinesIterator::FBlockLinesIterator(int _minx, int _miny, int _maxx, int _maxy, bool keepvalidcount)
645 {
646 if (!keepvalidcount) validcount++;
647 minx = _minx;
648 maxx = _maxx;
649 miny = _miny;
650 maxy = _maxy;
651 Reset();
652 }
653
FBlockLinesIterator(const FBoundingBox & box)654 FBlockLinesIterator::FBlockLinesIterator(const FBoundingBox &box)
655 {
656 validcount++;
657 maxy = GetSafeBlockY(box.Top() - bmaporgy);
658 miny = GetSafeBlockY(box.Bottom() - bmaporgy);
659 maxx = GetSafeBlockX(box.Right() - bmaporgx);
660 minx = GetSafeBlockX(box.Left() - bmaporgx);
661 Reset();
662 }
663
664
665 //===========================================================================
666 //
667 // FBlockLinesIterator :: StartBlock
668 //
669 //===========================================================================
670
StartBlock(int x,int y)671 void FBlockLinesIterator::StartBlock(int x, int y)
672 {
673 curx = x;
674 cury = y;
675 if (x >= 0 && y >= 0 && x < bmapwidth && y <bmapheight)
676 {
677 int offset = y*bmapwidth + x;
678 polyLink = PolyBlockMap? PolyBlockMap[offset] : NULL;
679 polyIndex = 0;
680
681 // There is an extra entry at the beginning of every block.
682 // Apparently, id had originally intended for it to be used
683 // to keep track of things, but the final code does not do that.
684 list = blockmaplump + *(blockmap + offset) + 1;
685 }
686 else
687 {
688 // invalid block
689 list = NULL;
690 polyLink = NULL;
691 }
692 }
693
694 //===========================================================================
695 //
696 // FBlockLinesIterator :: Next
697 //
698 //===========================================================================
699
Next()700 line_t *FBlockLinesIterator::Next()
701 {
702 while (true)
703 {
704 while (polyLink != NULL)
705 {
706 if (polyLink->polyobj)
707 {
708 if (polyIndex == 0)
709 {
710 if (polyLink->polyobj->validcount == validcount)
711 {
712 polyLink = polyLink->next;
713 continue;
714 }
715 polyLink->polyobj->validcount = validcount;
716 }
717
718 line_t *ld = polyLink->polyobj->Linedefs[polyIndex];
719
720 if (++polyIndex >= (int)polyLink->polyobj->Linedefs.Size())
721 {
722 polyLink = polyLink->next;
723 polyIndex = 0;
724 }
725
726 if (ld->validcount == validcount)
727 {
728 continue;
729 }
730 else
731 {
732 ld->validcount = validcount;
733 return ld;
734 }
735 }
736 else polyLink = polyLink->next;
737 }
738
739 if (list != NULL)
740 {
741 while (*list != -1)
742 {
743 line_t *ld = &lines[*list];
744
745 list++;
746 if (ld->validcount != validcount)
747 {
748 ld->validcount = validcount;
749 return ld;
750 }
751 }
752 }
753
754 if (++curx > maxx)
755 {
756 curx = minx;
757 if (++cury > maxy) return NULL;
758 }
759 StartBlock(curx, cury);
760 }
761 }
762
763 //===========================================================================
764 //
765 // FBlockThingsIterator :: FBlockThingsIterator
766 //
767 //===========================================================================
768
FBlockThingsIterator()769 FBlockThingsIterator::FBlockThingsIterator()
770 : DynHash(0)
771 {
772 minx = maxx = 0;
773 miny = maxy = 0;
774 ClearHash();
775 block = NULL;
776 }
777
FBlockThingsIterator(int _minx,int _miny,int _maxx,int _maxy)778 FBlockThingsIterator::FBlockThingsIterator(int _minx, int _miny, int _maxx, int _maxy)
779 : DynHash(0)
780 {
781 minx = _minx;
782 maxx = _maxx;
783 miny = _miny;
784 maxy = _maxy;
785 ClearHash();
786 Reset();
787 }
788
FBlockThingsIterator(const FBoundingBox & box)789 FBlockThingsIterator::FBlockThingsIterator(const FBoundingBox &box)
790 : DynHash(0)
791 {
792 maxy = GetSafeBlockY(box.Top() - bmaporgy);
793 miny = GetSafeBlockY(box.Bottom() - bmaporgy);
794 maxx = GetSafeBlockX(box.Right() - bmaporgx);
795 minx = GetSafeBlockX(box.Left() - bmaporgx);
796 ClearHash();
797 Reset();
798 }
799
800 //===========================================================================
801 //
802 // FBlockThingsIterator :: ClearHash
803 //
804 //===========================================================================
805
ClearHash()806 void FBlockThingsIterator::ClearHash()
807 {
808 clearbuf(Buckets, countof(Buckets), -1);
809 NumFixedHash = 0;
810 DynHash.Clear();
811 }
812
813 //===========================================================================
814 //
815 // FBlockThingsIterator :: StartBlock
816 //
817 //===========================================================================
818
StartBlock(int x,int y)819 void FBlockThingsIterator::StartBlock(int x, int y)
820 {
821 curx = x;
822 cury = y;
823 if (x >= 0 && y >= 0 && x < bmapwidth && y <bmapheight)
824 {
825 block = blocklinks[y*bmapwidth + x];
826 }
827 else
828 {
829 // invalid block
830 block = NULL;
831 }
832 }
833
834 //===========================================================================
835 //
836 // FBlockThingsIterator :: SwitchBlock
837 //
838 //===========================================================================
839
SwitchBlock(int x,int y)840 void FBlockThingsIterator::SwitchBlock(int x, int y)
841 {
842 minx = maxx = x;
843 miny = maxy = y;
844 StartBlock(x, y);
845 }
846
847 //===========================================================================
848 //
849 // FBlockThingsIterator :: Next
850 //
851 //===========================================================================
852
Next(bool centeronly)853 AActor *FBlockThingsIterator::Next(bool centeronly)
854 {
855 for (;;)
856 {
857 while (block != NULL)
858 {
859 AActor *me = block->Me;
860 FBlockNode *mynode = block;
861 HashEntry *entry;
862 int i;
863
864 block = block->NextActor;
865 // Don't recheck things that were already checked
866 if (mynode->NextBlock == NULL && mynode->PrevBlock == &me->BlockNode)
867 { // This actor doesn't span blocks, so we know it can only ever be checked once.
868 return me;
869 }
870 if (centeronly)
871 {
872 // Block boundaries for compatibility mode
873 fixed_t blockleft = (curx << MAPBLOCKSHIFT) + bmaporgx;
874 fixed_t blockright = blockleft + MAPBLOCKSIZE;
875 fixed_t blockbottom = (cury << MAPBLOCKSHIFT) + bmaporgy;
876 fixed_t blocktop = blockbottom + MAPBLOCKSIZE;
877
878 // only return actors with the center in this block
879 if (me->X() >= blockleft && me->X() < blockright &&
880 me->Y() >= blockbottom && me->Y() < blocktop)
881 {
882 return me;
883 }
884 }
885 else
886 {
887 size_t hash = ((size_t)me >> 3) % countof(Buckets);
888 for (i = Buckets[hash]; i >= 0; )
889 {
890 entry = GetHashEntry(i);
891 if (entry->Actor == me)
892 { // I've already been checked. Skip to the next actor.
893 break;
894 }
895 i = entry->Next;
896 }
897 if (i < 0)
898 { // Add me to the hash table and return me.
899 if (NumFixedHash < (int)countof(FixedHash))
900 {
901 entry = &FixedHash[NumFixedHash];
902 entry->Next = Buckets[hash];
903 Buckets[hash] = NumFixedHash++;
904 }
905 else
906 {
907 if (DynHash.Size() == 0)
908 {
909 DynHash.Grow(50);
910 }
911 i = DynHash.Reserve(1);
912 entry = &DynHash[i];
913 entry->Next = Buckets[hash];
914 Buckets[hash] = i + countof(FixedHash);
915 }
916 entry->Actor = me;
917 return me;
918 }
919 }
920 }
921
922 if (++curx > maxx)
923 {
924 curx = minx;
925 if (++cury > maxy) return NULL;
926 }
927 StartBlock(curx, cury);
928 }
929 }
930
931
932 //===========================================================================
933 //
934 // FPathTraverse :: Intercepts
935 //
936 //===========================================================================
937
938 TArray<intercept_t> FPathTraverse::intercepts(128);
939
940
941 //===========================================================================
942 //
943 // FPathTraverse :: AddLineIntercepts.
944 // Looks for lines in the given block
945 // that intercept the given trace
946 // to add to the intercepts list.
947 //
948 // A line is crossed if its endpoints
949 // are on opposite sides of the trace.
950 //
951 //===========================================================================
952
AddLineIntercepts(int bx,int by)953 void FPathTraverse::AddLineIntercepts(int bx, int by)
954 {
955 FBlockLinesIterator it(bx, by, bx, by, true);
956 line_t *ld;
957
958 while ((ld = it.Next()))
959 {
960 int s1;
961 int s2;
962 fixed_t frac;
963 divline_t dl;
964
965 // avoid precision problems with two routines
966 if ( trace.dx > FRACUNIT*16
967 || trace.dy > FRACUNIT*16
968 || trace.dx < -FRACUNIT*16
969 || trace.dy < -FRACUNIT*16)
970 {
971 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
972 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
973 }
974 else
975 {
976 s1 = P_PointOnLineSide (trace.x, trace.y, ld);
977 s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
978 }
979
980 if (s1 == s2) continue; // line isn't crossed
981
982 // hit the line
983 P_MakeDivline (ld, &dl);
984 frac = P_InterceptVector (&trace, &dl);
985
986 if (frac < 0 || frac > FRACUNIT) continue; // behind source or beyond end point
987
988 intercept_t newintercept;
989
990 newintercept.frac = frac;
991 newintercept.isaline = true;
992 newintercept.done = false;
993 newintercept.d.line = ld;
994 intercepts.Push (newintercept);
995 }
996 }
997
998
999 //===========================================================================
1000 //
1001 // FPathTraverse :: AddThingIntercepts
1002 //
1003 //===========================================================================
1004
AddThingIntercepts(int bx,int by,FBlockThingsIterator & it,bool compatible)1005 void FPathTraverse::AddThingIntercepts (int bx, int by, FBlockThingsIterator &it, bool compatible)
1006 {
1007 AActor *thing;
1008
1009 it.SwitchBlock(bx, by);
1010 while ((thing = it.Next(compatible)))
1011 {
1012 int numfronts = 0;
1013 divline_t line;
1014 int i;
1015
1016
1017 if (!compatible)
1018 {
1019 // [RH] Don't check a corner to corner crossection for hit.
1020 // Instead, check against the actual bounding box (but not if compatibility optioned.)
1021
1022 // There's probably a smarter way to determine which two sides
1023 // of the thing face the trace than by trying all four sides...
1024 for (i = 0; i < 4; ++i)
1025 {
1026 switch (i)
1027 {
1028 case 0: // Top edge
1029 line.x = thing->X() + thing->radius;
1030 line.y = thing->Y() + thing->radius;
1031 line.dx = -thing->radius * 2;
1032 line.dy = 0;
1033 break;
1034
1035 case 1: // Right edge
1036 line.x = thing->X() + thing->radius;
1037 line.y = thing->Y() - thing->radius;
1038 line.dx = 0;
1039 line.dy = thing->radius * 2;
1040 break;
1041
1042 case 2: // Bottom edge
1043 line.x = thing->X() - thing->radius;
1044 line.y = thing->Y() - thing->radius;
1045 line.dx = thing->radius * 2;
1046 line.dy = 0;
1047 break;
1048
1049 case 3: // Left edge
1050 line.x = thing->X() - thing->radius;
1051 line.y = thing->Y() + thing->radius;
1052 line.dx = 0;
1053 line.dy = thing->radius * -2;
1054 break;
1055 }
1056 // Check if this side is facing the trace origin
1057 if (P_PointOnDivlineSidePrecise (trace.x, trace.y, &line) == 0)
1058 {
1059 numfronts++;
1060
1061 // If it is, see if the trace crosses it
1062 if (P_PointOnDivlineSidePrecise (line.x, line.y, &trace) !=
1063 P_PointOnDivlineSidePrecise (line.x + line.dx, line.y + line.dy, &trace))
1064 {
1065 // It's a hit
1066 fixed_t frac = P_InterceptVector (&trace, &line);
1067 if (frac < 0)
1068 { // behind source
1069 continue;
1070 }
1071
1072 intercept_t newintercept;
1073 newintercept.frac = frac;
1074 newintercept.isaline = false;
1075 newintercept.done = false;
1076 newintercept.d.thing = thing;
1077 intercepts.Push (newintercept);
1078 continue;
1079 }
1080 }
1081 }
1082
1083 // If none of the sides was facing the trace, then the trace
1084 // must have started inside the box, so add it as an intercept.
1085 if (numfronts == 0)
1086 {
1087 intercept_t newintercept;
1088 newintercept.frac = 0;
1089 newintercept.isaline = false;
1090 newintercept.done = false;
1091 newintercept.d.thing = thing;
1092 intercepts.Push (newintercept);
1093 }
1094 }
1095 else
1096 {
1097 // Old code for compatibility purposes
1098 fixed_t x1, y1, x2, y2;
1099 int s1, s2;
1100 divline_t dl;
1101 fixed_t frac;
1102
1103 bool tracepositive = (trace.dx ^ trace.dy)>0;
1104
1105 // check a corner to corner crossection for hit
1106 if (tracepositive)
1107 {
1108 x1 = thing->X() - thing->radius;
1109 y1 = thing->Y() + thing->radius;
1110
1111 x2 = thing->X() + thing->radius;
1112 y2 = thing->Y() - thing->radius;
1113 }
1114 else
1115 {
1116 x1 = thing->X() - thing->radius;
1117 y1 = thing->Y() - thing->radius;
1118
1119 x2 = thing->X() + thing->radius;
1120 y2 = thing->Y() + thing->radius;
1121 }
1122
1123 s1 = P_PointOnDivlineSide (x1, y1, &trace);
1124 s2 = P_PointOnDivlineSide (x2, y2, &trace);
1125
1126 if (s1 != s2)
1127 {
1128 dl.x = x1;
1129 dl.y = y1;
1130 dl.dx = x2-x1;
1131 dl.dy = y2-y1;
1132
1133 frac = P_InterceptVector (&trace, &dl);
1134
1135 if (frac >= 0)
1136 {
1137 intercept_t newintercept;
1138 newintercept.frac = frac;
1139 newintercept.isaline = false;
1140 newintercept.done = false;
1141 newintercept.d.thing = thing;
1142 intercepts.Push (newintercept);
1143 }
1144 }
1145 }
1146 }
1147 }
1148
1149
1150 //===========================================================================
1151 //
1152 // FPathTraverse :: Next
1153 //
1154 //===========================================================================
1155
Next()1156 intercept_t *FPathTraverse::Next()
1157 {
1158 intercept_t *in = NULL;
1159
1160 fixed_t dist = FIXED_MAX;
1161 for (unsigned scanpos = intercept_index; scanpos < intercepts.Size (); scanpos++)
1162 {
1163 intercept_t *scan = &intercepts[scanpos];
1164 if (scan->frac < dist && !scan->done)
1165 {
1166 dist = scan->frac;
1167 in = scan;
1168 }
1169 }
1170
1171 if (dist > FRACUNIT || in == NULL) return NULL; // checked everything in range
1172 in->done = true;
1173 return in;
1174 }
1175
1176 //===========================================================================
1177 //
1178 // FPathTraverse
1179 // Traces a line from x1,y1 to x2,y2,
1180 //
1181 //===========================================================================
1182
FPathTraverse(fixed_t x1,fixed_t y1,fixed_t x2,fixed_t y2,int flags)1183 FPathTraverse::FPathTraverse (fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2, int flags)
1184 {
1185 fixed_t xt1, xt2;
1186 fixed_t yt1, yt2;
1187 long long _x1, _x2, _y1, _y2;
1188
1189 fixed_t xstep;
1190 fixed_t ystep;
1191
1192 fixed_t partialx, partialy;
1193
1194 fixed_t xintercept;
1195 fixed_t yintercept;
1196
1197 int mapx;
1198 int mapy;
1199
1200 int mapxstep;
1201 int mapystep;
1202
1203 int count;
1204
1205 validcount++;
1206 intercept_index = intercepts.Size();
1207
1208 if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
1209 x1 += FRACUNIT; // don't side exactly on a line
1210
1211 if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
1212 y1 += FRACUNIT; // don't side exactly on a line
1213
1214 trace.x = x1;
1215 trace.y = y1;
1216 if (flags & PT_DELTA)
1217 {
1218 trace.dx = x2;
1219 trace.dy = y2;
1220 }
1221 else
1222 {
1223 trace.dx = x2 - x1;
1224 trace.dy = y2 - y1;
1225 }
1226
1227 _x1 = (long long)x1 - bmaporgx;
1228 _y1 = (long long)y1 - bmaporgy;
1229 x1 -= bmaporgx;
1230 y1 -= bmaporgy;
1231 xt1 = int(_x1 >> MAPBLOCKSHIFT);
1232 yt1 = int(_y1 >> MAPBLOCKSHIFT);
1233
1234 if (flags & PT_DELTA)
1235 {
1236 _x2 = _x1 + x2;
1237 _y2 = _y1 + y2;
1238 xt2 = int(_x2 >> MAPBLOCKSHIFT);
1239 yt2 = int(_y2 >> MAPBLOCKSHIFT);
1240 x2 = (int)_x2;
1241 y2 = (int)_y2;
1242 }
1243 else
1244 {
1245 _x2 = (long long)x2 - bmaporgx;
1246 _y2 = (long long)y2 - bmaporgy;
1247 x2 -= bmaporgx;
1248 y2 -= bmaporgy;
1249 xt2 = int(_x2 >> MAPBLOCKSHIFT);
1250 yt2 = int(_y2 >> MAPBLOCKSHIFT);
1251 }
1252
1253 if (xt2 > xt1)
1254 {
1255 mapxstep = 1;
1256 partialx = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
1257 ystep = FixedDiv (y2-y1,abs(x2-x1));
1258 }
1259 else if (xt2 < xt1)
1260 {
1261 mapxstep = -1;
1262 partialx = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
1263 ystep = FixedDiv (y2-y1,abs(x2-x1));
1264 }
1265 else
1266 {
1267 mapxstep = 0;
1268 partialx = FRACUNIT;
1269 ystep = 256*FRACUNIT;
1270 }
1271 yintercept = int(_y1>>MAPBTOFRAC) + FixedMul (partialx, ystep);
1272
1273
1274 if (yt2 > yt1)
1275 {
1276 mapystep = 1;
1277 partialy = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
1278 xstep = FixedDiv (x2-x1,abs(y2-y1));
1279 }
1280 else if (yt2 < yt1)
1281 {
1282 mapystep = -1;
1283 partialy = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
1284 xstep = FixedDiv (x2-x1,abs(y2-y1));
1285 }
1286 else
1287 {
1288 mapystep = 0;
1289 partialy = FRACUNIT;
1290 xstep = 256*FRACUNIT;
1291 }
1292 xintercept = int(_x1>>MAPBTOFRAC) + FixedMul (partialy, xstep);
1293
1294 // [RH] Fix for traces that pass only through blockmap corners. In that case,
1295 // xintercept and yintercept can both be set ahead of mapx and mapy, so the
1296 // for loop would never advance anywhere.
1297
1298 if (abs(xstep) == FRACUNIT && abs(ystep) == FRACUNIT)
1299 {
1300 if (ystep < 0)
1301 {
1302 partialx = FRACUNIT - partialx;
1303 }
1304 if (xstep < 0)
1305 {
1306 partialy = FRACUNIT - partialy;
1307 }
1308 if (partialx == partialy)
1309 {
1310 xintercept = xt1 << FRACBITS;
1311 yintercept = yt1 << FRACBITS;
1312 }
1313 }
1314
1315 // Step through map blocks.
1316 // Count is present to prevent a round off error
1317 // from skipping the break statement.
1318 mapx = xt1;
1319 mapy = yt1;
1320
1321 bool compatible = (flags & PT_COMPATIBLE) && (i_compatflags & COMPATF_HITSCAN);
1322
1323 // we want to use one list of checked actors for the entire operation
1324 FBlockThingsIterator btit;
1325 for (count = 0 ; count < 100 ; count++)
1326 {
1327 if (flags & PT_ADDLINES)
1328 {
1329 AddLineIntercepts(mapx, mapy);
1330 }
1331
1332 if (flags & PT_ADDTHINGS)
1333 {
1334 AddThingIntercepts(mapx, mapy, btit, compatible);
1335 }
1336
1337 if (mapx == xt2 && mapy == yt2)
1338 {
1339 break;
1340 }
1341
1342 // [RH] Handle corner cases properly instead of pretending they don't exist.
1343 switch ((((yintercept >> FRACBITS) == mapy) << 1) | ((xintercept >> FRACBITS) == mapx))
1344 {
1345 case 0: // neither xintercept nor yintercept match!
1346 count = 100; // Stop traversing, because somebody screwed up.
1347 break;
1348
1349 case 1: // xintercept matches
1350 xintercept += xstep;
1351 mapy += mapystep;
1352 break;
1353
1354 case 2: // yintercept matches
1355 yintercept += ystep;
1356 mapx += mapxstep;
1357 break;
1358
1359 case 3: // xintercept and yintercept both match
1360 // The trace is exiting a block through its corner. Not only does the block
1361 // being entered need to be checked (which will happen when this loop
1362 // continues), but the other two blocks adjacent to the corner also need to
1363 // be checked.
1364 if (!compatible)
1365 {
1366 if (flags & PT_ADDLINES)
1367 {
1368 AddLineIntercepts(mapx + mapxstep, mapy);
1369 AddLineIntercepts(mapx, mapy + mapystep);
1370 }
1371
1372 if (flags & PT_ADDTHINGS)
1373 {
1374 AddThingIntercepts(mapx + mapxstep, mapy, btit, false);
1375 AddThingIntercepts(mapx, mapy + mapystep, btit, false);
1376 }
1377 xintercept += xstep;
1378 yintercept += ystep;
1379 mapx += mapxstep;
1380 mapy += mapystep;
1381 }
1382 else
1383 {
1384 count = 100; // Doom originally did not handle this case so do the same in compatibility mode.
1385 }
1386 break;
1387 }
1388 }
1389 }
1390
~FPathTraverse()1391 FPathTraverse::~FPathTraverse()
1392 {
1393 intercepts.Resize(intercept_index);
1394 }
1395
1396
1397 //===========================================================================
1398 //
1399 // P_RoughMonsterSearch
1400 //
1401 // Searches though the surrounding mapblocks for monsters/players
1402 // distance is in MAPBLOCKUNITS
1403 //===========================================================================
1404
P_RoughMonsterSearch(AActor * mo,int distance,bool onlyseekable)1405 AActor *P_RoughMonsterSearch (AActor *mo, int distance, bool onlyseekable)
1406 {
1407 return P_BlockmapSearch (mo, distance, RoughBlockCheck, (void *)onlyseekable);
1408 }
1409
P_BlockmapSearch(AActor * mo,int distance,AActor * (* check)(AActor *,int,void *),void * params)1410 AActor *P_BlockmapSearch (AActor *mo, int distance, AActor *(*check)(AActor*, int, void *), void *params)
1411 {
1412 int blockX;
1413 int blockY;
1414 int startX, startY;
1415 int blockIndex;
1416 int firstStop;
1417 int secondStop;
1418 int thirdStop;
1419 int finalStop;
1420 int count;
1421 AActor *target;
1422
1423 startX = GetSafeBlockX(mo->X()-bmaporgx);
1424 startY = GetSafeBlockY(mo->Y()-bmaporgy);
1425 validcount++;
1426
1427 if (startX >= 0 && startX < bmapwidth && startY >= 0 && startY < bmapheight)
1428 {
1429 if ( (target = check (mo, startY*bmapwidth+startX, params)) )
1430 { // found a target right away
1431 return target;
1432 }
1433 }
1434 for (count = 1; count <= distance; count++)
1435 {
1436 blockX = clamp (startX-count, 0, bmapwidth-1);
1437 blockY = clamp (startY-count, 0, bmapheight-1);
1438
1439 blockIndex = blockY*bmapwidth+blockX;
1440 firstStop = startX+count;
1441 if (firstStop < 0)
1442 {
1443 continue;
1444 }
1445 if (firstStop >= bmapwidth)
1446 {
1447 firstStop = bmapwidth-1;
1448 }
1449 secondStop = startY+count;
1450 if (secondStop < 0)
1451 {
1452 continue;
1453 }
1454 if (secondStop >= bmapheight)
1455 {
1456 secondStop = bmapheight-1;
1457 }
1458 thirdStop = secondStop*bmapwidth+blockX;
1459 secondStop = secondStop*bmapwidth+firstStop;
1460 firstStop += blockY*bmapwidth;
1461 finalStop = blockIndex;
1462
1463 // Trace the first block section (along the top)
1464 for (; blockIndex <= firstStop; blockIndex++)
1465 {
1466 if ( (target = check (mo, blockIndex, params)) )
1467 {
1468 return target;
1469 }
1470 }
1471 // Trace the second block section (right edge)
1472 for (blockIndex--; blockIndex <= secondStop; blockIndex += bmapwidth)
1473 {
1474 if ( (target = check (mo, blockIndex, params)) )
1475 {
1476 return target;
1477 }
1478 }
1479 // Trace the third block section (bottom edge)
1480 for (blockIndex -= bmapwidth; blockIndex >= thirdStop; blockIndex--)
1481 {
1482 if ( (target = check (mo, blockIndex, params)) )
1483 {
1484 return target;
1485 }
1486 }
1487 // Trace the final block section (left edge)
1488 for (blockIndex++; blockIndex > finalStop; blockIndex -= bmapwidth)
1489 {
1490 if ( (target = check (mo, blockIndex, params)) )
1491 {
1492 return target;
1493 }
1494 }
1495 }
1496 return NULL;
1497 }
1498
1499 //===========================================================================
1500 //
1501 // RoughBlockCheck
1502 //
1503 //===========================================================================
1504
RoughBlockCheck(AActor * mo,int index,void * param)1505 static AActor *RoughBlockCheck (AActor *mo, int index, void *param)
1506 {
1507 bool onlyseekable = param != NULL;
1508 FBlockNode *link;
1509
1510 for (link = blocklinks[index]; link != NULL; link = link->NextActor)
1511 {
1512 if (link->Me != mo)
1513 {
1514 if (onlyseekable && !mo->CanSeek(link->Me))
1515 {
1516 continue;
1517 }
1518 if (mo->IsOkayToAttack (link->Me))
1519 {
1520 return link->Me;
1521 }
1522 }
1523 }
1524 return NULL;
1525 }
1526
1527 //===========================================================================
1528 //
1529 // P_VanillaPointOnLineSide
1530 // P_PointOnLineSide() from the initial Doom source code release
1531 //
1532 //===========================================================================
1533
P_VanillaPointOnLineSide(fixed_t x,fixed_t y,const line_t * line)1534 int P_VanillaPointOnLineSide(fixed_t x, fixed_t y, const line_t* line)
1535 {
1536 fixed_t dx;
1537 fixed_t dy;
1538 fixed_t left;
1539 fixed_t right;
1540
1541 if (!line->dx)
1542 {
1543 if (x <= line->v1->x)
1544 return line->dy > 0;
1545
1546 return line->dy < 0;
1547 }
1548 if (!line->dy)
1549 {
1550 if (y <= line->v1->y)
1551 return line->dx < 0;
1552
1553 return line->dx > 0;
1554 }
1555
1556 dx = (x - line->v1->x);
1557 dy = (y - line->v1->y);
1558
1559 left = FixedMul ( line->dy>>FRACBITS , dx );
1560 right = FixedMul ( dy , line->dx>>FRACBITS );
1561
1562 if (right < left)
1563 return 0; // front side
1564 return 1; // back side
1565 }
1566
1567 //===========================================================================
1568 //
1569 // P_VanillaPointOnDivlineSide
1570 // P_PointOnDivlineSide() from the initial Doom source code release
1571 //
1572 //===========================================================================
1573
P_VanillaPointOnDivlineSide(fixed_t x,fixed_t y,const divline_t * line)1574 int P_VanillaPointOnDivlineSide(fixed_t x, fixed_t y, const divline_t* line)
1575 {
1576 fixed_t dx;
1577 fixed_t dy;
1578 fixed_t left;
1579 fixed_t right;
1580
1581 if (!line->dx)
1582 {
1583 if (x <= line->x)
1584 return line->dy > 0;
1585
1586 return line->dy < 0;
1587 }
1588 if (!line->dy)
1589 {
1590 if (y <= line->y)
1591 return line->dx < 0;
1592
1593 return line->dx > 0;
1594 }
1595
1596 dx = (x - line->x);
1597 dy = (y - line->y);
1598
1599 // try to quickly decide by looking at sign bits
1600 if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
1601 {
1602 if ( (line->dy ^ dx) & 0x80000000 )
1603 return 1; // (left is negative)
1604 return 0;
1605 }
1606
1607 left = FixedMul ( line->dy>>8, dx>>8 );
1608 right = FixedMul ( dy>>8 , line->dx>>8 );
1609
1610 if (right < left)
1611 return 0; // front side
1612 return 1; // back side
1613 }
1614
1615