1 // Emacs style mode select -*- C++ -*-
2 //-----------------------------------------------------------------------------
6 // Copyright (C) 1993-1996 by id Software, Inc.
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.
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
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.
25 //-----------------------------------------------------------------------------
28 rcsid[] = "$Id: p_maputl.c,v 1.5 1997/02/03 22:45:11 b1 Exp $";
42 // Gives an estimation of distance (not exact)
88 dx = (x - line->v1->x);
89 dy = (y - line->v1->y);
91 left = FixedMul ( line->dy>>FRACBITS , dx );
92 right = FixedMul ( dy , line->dx>>FRACBITS );
95 return 0; // front side
96 return 1; // back side
103 // Considers the line to be infinite
104 // Returns side 0 or 1, -1 if box crosses the line.
114 switch (ld->slopetype)
117 p1 = tmbox[BOXTOP] > ld->v1->y;
118 p2 = tmbox[BOXBOTTOM] > ld->v1->y;
127 p1 = tmbox[BOXRIGHT] < ld->v1->x;
128 p2 = tmbox[BOXLEFT] < ld->v1->x;
137 p1 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXTOP], ld);
138 p2 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld);
142 p1 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXTOP], ld);
143 p2 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld);
157 // P_PointOnDivlineSide
189 // try to quickly decide by looking at sign bits
190 if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
192 if ( (line->dy ^ dx) & 0x80000000 )
193 return 1; // (left is negative)
197 left = FixedMul ( line->dy>>8, dx>>8 );
198 right = FixedMul ( dy>>8 , line->dx>>8 );
201 return 0; // front side
202 return 1; // back side
225 // Returns the fractional intercept point
226 // along the first divline.
227 // This is only called by the addthings
228 // and addlines traversers.
239 den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
243 // I_Error ("P_InterceptVector: parallel");
246 FixedMul ( (v1->x - v2->x)>>8 ,v1->dy )
247 +FixedMul ( (v2->y - v1->y)>>8, v1->dx );
249 frac = FixedDiv (num , den);
257 // Sets opentop and openbottom to the window
258 // through a two sided line.
259 // OPTIMIZE: keep this precalculated
267 void P_LineOpening (line_t* linedef)
272 if (linedef->sidenum[1] == -1)
279 front = linedef->frontsector;
280 back = linedef->backsector;
282 if (front->ceilingheight < back->ceilingheight)
283 opentop = front->ceilingheight;
285 opentop = back->ceilingheight;
287 if (front->floorheight > back->floorheight)
289 openbottom = front->floorheight;
290 lowfloor = back->floorheight;
294 openbottom = back->floorheight;
295 lowfloor = front->floorheight;
298 openrange = opentop - openbottom;
303 // THING POSITION SETTING
308 // P_UnsetThingPosition
309 // Unlinks a thing from block map and sectors.
310 // On each position change, BLOCKMAP and other
311 // lookups maintaining lists ot things inside
312 // these structures need to be updated.
314 void P_UnsetThingPosition (mobj_t* thing)
319 if ( ! (thing->flags & MF_NOSECTOR) )
321 // inert things don't need to be in blockmap?
322 // unlink from subsector
324 thing->snext->sprev = thing->sprev;
327 thing->sprev->snext = thing->snext;
329 thing->subsector->sector->thinglist = thing->snext;
332 if ( ! (thing->flags & MF_NOBLOCKMAP) )
334 // inert things don't need to be in blockmap
335 // unlink from block map
337 thing->bnext->bprev = thing->bprev;
340 thing->bprev->bnext = thing->bnext;
343 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
344 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
346 if (blockx>=0 && blockx < bmapwidth
347 && blocky>=0 && blocky <bmapheight)
349 blocklinks[blocky*bmapwidth+blockx] = thing->bnext;
357 // P_SetThingPosition
358 // Links a thing into both a block and a subsector
359 // based on it's x y.
360 // Sets thing->subsector properly
363 P_SetThingPosition (mobj_t* thing)
372 // link into subsector
373 ss = R_PointInSubsector (thing->x,thing->y);
374 thing->subsector = ss;
376 if ( ! (thing->flags & MF_NOSECTOR) )
378 // invisible things don't go into the sector links
382 thing->snext = sec->thinglist;
385 sec->thinglist->sprev = thing;
387 sec->thinglist = thing;
391 // link into blockmap
392 if ( ! (thing->flags & MF_NOBLOCKMAP) )
394 // inert things don't need to be in blockmap
395 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
396 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
399 && blockx < bmapwidth
401 && blocky < bmapheight)
403 link = &blocklinks[blocky*bmapwidth+blockx];
405 thing->bnext = *link;
407 (*link)->bprev = thing;
413 // thing is off the map
414 thing->bnext = thing->bprev = NULL;
422 // BLOCK MAP ITERATORS
423 // For each line/thing in the given mapblock,
424 // call the passed PIT_* function.
425 // If the function returns false,
426 // exit with false without checking anything else.
431 // P_BlockLinesIterator
432 // The validcount flags are used to avoid checking lines
433 // that are marked in multiple mapblocks,
434 // so increment validcount before the first call
435 // to P_BlockLinesIterator, then make one or more calls
442 boolean(*func)(line_t*) )
456 offset = y*bmapwidth+x;
458 offset = *(blockmap+offset);
460 for ( list = blockmaplump+offset ; *list != -1 ; list++)
464 if (ld->validcount == validcount)
465 continue; // line has already been checked
467 ld->validcount = validcount;
472 return true; // everything was checked
477 // P_BlockThingsIterator
480 P_BlockThingsIterator
483 boolean(*func)(mobj_t*) )
496 for (mobj = blocklinks[y*bmapwidth+x] ;
509 // INTERCEPT ROUTINES
511 intercept_t intercepts[MAXINTERCEPTS];
512 intercept_t* intercept_p;
519 // PIT_AddLineIntercepts.
520 // Looks for lines in the given block
521 // that intercept the given trace
522 // to add to the intercepts list.
524 // A line is crossed if its endpoints
525 // are on opposite sides of the trace.
526 // Returns true if earlyout and a solid line hit.
529 PIT_AddLineIntercepts (line_t* ld)
536 // avoid precision problems with two routines
537 if ( trace.dx > FRACUNIT*16
538 || trace.dy > FRACUNIT*16
539 || trace.dx < -FRACUNIT*16
540 || trace.dy < -FRACUNIT*16)
542 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
543 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
547 s1 = P_PointOnLineSide (trace.x, trace.y, ld);
548 s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
552 return true; // line isn't crossed
555 P_MakeDivline (ld, &dl);
556 frac = P_InterceptVector (&trace, &dl);
559 return true; // behind source
561 // try to early out the check
566 return false; // stop checking
570 intercept_p->frac = frac;
571 intercept_p->isaline = true;
572 intercept_p->d.line = ld;
575 return true; // continue
581 // PIT_AddThingIntercepts
583 boolean PIT_AddThingIntercepts (mobj_t* thing)
593 boolean tracepositive;
599 tracepositive = (trace.dx ^ trace.dy)>0;
601 // check a corner to corner crossection for hit
604 x1 = thing->x - thing->radius;
605 y1 = thing->y + thing->radius;
607 x2 = thing->x + thing->radius;
608 y2 = thing->y - thing->radius;
612 x1 = thing->x - thing->radius;
613 y1 = thing->y - thing->radius;
615 x2 = thing->x + thing->radius;
616 y2 = thing->y + thing->radius;
619 s1 = P_PointOnDivlineSide (x1, y1, &trace);
620 s2 = P_PointOnDivlineSide (x2, y2, &trace);
623 return true; // line isn't crossed
630 frac = P_InterceptVector (&trace, &dl);
633 return true; // behind source
635 intercept_p->frac = frac;
636 intercept_p->isaline = false;
637 intercept_p->d.thing = thing;
640 return true; // keep going
645 // P_TraverseIntercepts
646 // Returns true if the traverser function returns true
659 count = intercept_p - intercepts;
661 for (in=(intercept_t*)0 ; count-- ; )
664 for (scan = intercepts ; scan<intercept_p ; scan++)
666 if (scan->frac < dist)
674 return true; // checked everything in range
677 return false; // don't bother going farther
682 return true; // everything was traversed
690 // Traces a line from x1,y1 to x2,y2,
691 // calling the traverser function for each.
692 // Returns true if the traverser function returns true
702 boolean (*trav) (intercept_t *))
725 earlyout = flags & PT_EARLYOUT;
728 intercept_p = intercepts;
730 if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
731 x1 += FRACUNIT; // don't side exactly on a line
733 if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
734 y1 += FRACUNIT; // don't side exactly on a line
743 xt1 = x1>>MAPBLOCKSHIFT;
744 yt1 = y1>>MAPBLOCKSHIFT;
748 xt2 = x2>>MAPBLOCKSHIFT;
749 yt2 = y2>>MAPBLOCKSHIFT;
754 partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
755 ystep = FixedDiv (y2-y1,abs(x2-x1));
760 partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
761 ystep = FixedDiv (y2-y1,abs(x2-x1));
767 ystep = 256*FRACUNIT;
770 yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep);
776 partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
777 xstep = FixedDiv (x2-x1,abs(y2-y1));
782 partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
783 xstep = FixedDiv (x2-x1,abs(y2-y1));
789 xstep = 256*FRACUNIT;
791 xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
793 // Step through map blocks.
794 // Count is present to prevent a round off error
795 // from skipping the break.
799 for (count = 0 ; count < 64 ; count++)
801 if (flags & PT_ADDLINES)
803 if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts))
804 return false; // early out
807 if (flags & PT_ADDTHINGS)
809 if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts))
810 return false; // early out
819 if ( (yintercept >> FRACBITS) == mapy)
824 else if ( (xintercept >> FRACBITS) == mapx)
831 // go through the sorted list
832 return P_TraverseIntercepts ( trav, FRACUNIT );