13 = Gives an estimation of distance (not exact)
18 fixed_t P_AproxDistance (fixed_t dx, fixed_t dy)
37 int P_PointOnLineSide (fixed_t x, fixed_t y, line_t *line)
55 dx = (x - line->v1->x);
56 dy = (y - line->v1->y);
58 left = FixedMul ( line->dy>>FRACBITS , dx );
59 right = FixedMul ( dy , line->dx>>FRACBITS );
62 return 0; // front side
63 return 1; // back side
72 = Considers the line to be infinite
73 = Returns side 0 or 1, -1 if box crosses the line
77 int P_BoxOnLineSide (fixed_t *tmbox, line_t *ld)
81 switch (ld->slopetype)
84 p1 = tmbox[BOXTOP] > ld->v1->y;
85 p2 = tmbox[BOXBOTTOM] > ld->v1->y;
93 p1 = tmbox[BOXRIGHT] < ld->v1->x;
94 p2 = tmbox[BOXLEFT] < ld->v1->x;
102 p1 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXTOP], ld);
103 p2 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld);
106 p1 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXTOP], ld);
107 p2 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld);
119 = P_PointOnDivlineSide
125 int P_PointOnDivlineSide (fixed_t x, fixed_t y, divline_t *line)
146 // try to quickly decide by looking at sign bits
147 if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
149 if ( (line->dy ^ dx) & 0x80000000 )
150 return 1; // (left is negative)
154 left = FixedMul ( line->dy>>8, dx>>8 );
155 right = FixedMul ( dy>>8 , line->dx>>8 );
158 return 0; // front side
159 return 1; // back side
172 void P_MakeDivline (line_t *li, divline_t *dl)
186 = Returns the fractional intercept point along the first divline
188 = This is only called by the addthings and addlines traversers
192 fixed_t P_InterceptVector (divline_t *v2, divline_t *v1)
195 fixed_t frac, num, den;
197 den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);
200 // I_Error ("P_InterceptVector: parallel");
201 num = FixedMul ( (v1->x - v2->x)>>8 ,v1->dy) +
202 FixedMul ( (v2->y - v1->y)>>8 , v1->dx);
203 frac = FixedDiv (num , den);
207 float frac, num, den, v1x,v1y,v1dx,v1dy,v2x,v2y,v2dx,v2dy;
209 v1x = (float)v1->x/FRACUNIT;
210 v1y = (float)v1->y/FRACUNIT;
211 v1dx = (float)v1->dx/FRACUNIT;
212 v1dy = (float)v1->dy/FRACUNIT;
213 v2x = (float)v2->x/FRACUNIT;
214 v2y = (float)v2->y/FRACUNIT;
215 v2dx = (float)v2->dx/FRACUNIT;
216 v2dy = (float)v2->dy/FRACUNIT;
218 den = v1dy*v2dx - v1dx*v2dy;
220 return 0; // parallel
221 num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx;
224 return frac*FRACUNIT;
233 = Sets opentop and openbottom to the window through a two sided line
234 = OPTIMIZE: keep this precalculated
238 fixed_t opentop, openbottom, openrange;
241 void P_LineOpening (line_t *linedef)
243 sector_t *front, *back;
245 if (linedef->sidenum[1] == -1)
246 { // single sided line
251 front = linedef->frontsector;
252 back = linedef->backsector;
254 if (front->ceilingheight < back->ceilingheight)
255 opentop = front->ceilingheight;
257 opentop = back->ceilingheight;
258 if (front->floorheight > back->floorheight)
260 openbottom = front->floorheight;
261 lowfloor = back->floorheight;
265 openbottom = back->floorheight;
266 lowfloor = front->floorheight;
269 openrange = opentop - openbottom;
273 ===============================================================================
275 THING POSITION SETTING
277 ===============================================================================
283 = P_UnsetThingPosition
285 = Unlinks a thing from block map and sectors
290 void P_UnsetThingPosition (mobj_t *thing)
294 if ( ! (thing->flags & MF_NOSECTOR) )
295 { // inert things don't need to be in blockmap
296 // unlink from subsector
298 thing->snext->sprev = thing->sprev;
300 thing->sprev->snext = thing->snext;
302 thing->subsector->sector->thinglist = thing->snext;
305 if ( ! (thing->flags & MF_NOBLOCKMAP) )
306 { // inert things don't need to be in blockmap
307 // unlink from block map
309 thing->bnext->bprev = thing->bprev;
311 thing->bprev->bnext = thing->bnext;
314 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
315 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
316 if (blockx>=0 && blockx < bmapwidth
317 && blocky>=0 && blocky <bmapheight)
318 blocklinks[blocky*bmapwidth+blockx] = thing->bnext;
329 = Links a thing into both a block and a subsector based on it's x y
330 = Sets thing->subsector properly
335 void P_SetThingPosition (mobj_t *thing)
343 // link into subsector
345 ss = R_PointInSubsector (thing->x,thing->y);
346 thing->subsector = ss;
347 if ( ! (thing->flags & MF_NOSECTOR) )
348 { // invisible things don't go into the sector links
352 thing->snext = sec->thinglist;
354 sec->thinglist->sprev = thing;
355 sec->thinglist = thing;
359 // link into blockmap
361 if ( ! (thing->flags & MF_NOBLOCKMAP) )
362 { // inert things don't need to be in blockmap
363 blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT;
364 blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT;
365 if (blockx>=0 && blockx < bmapwidth && blocky>=0 && blocky <bmapheight)
367 link = &blocklinks[blocky*bmapwidth+blockx];
369 thing->bnext = *link;
371 (*link)->bprev = thing;
375 { // thing is off the map
376 thing->bnext = thing->bprev = NULL;
384 ===============================================================================
388 For each line/thing in the given mapblock, call the passed function.
389 If the function returns false, exit with false without checking anything else.
391 ===============================================================================
397 = P_BlockLinesIterator
399 = The validcount flags are used to avoid checking lines
400 = that are marked in multiple mapblocks, so increment validcount before
401 = the first call to P_BlockLinesIterator, then make one or more calls to it
405 boolean P_BlockLinesIterator (int x, int y, boolean(*func)(line_t*) )
411 if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
413 offset = y*bmapwidth+x;
415 offset = *(blockmap+offset);
417 for ( list = blockmaplump+offset ; *list != -1 ; list++)
420 if (ld->validcount == validcount)
421 continue; // line has already been checked
422 ld->validcount = validcount;
428 return true; // everything was checked
435 = P_BlockThingsIterator
440 boolean P_BlockThingsIterator (int x, int y, boolean(*func)(mobj_t*) )
444 if (x<0 || y<0 || x>=bmapwidth || y>=bmapheight)
447 for (mobj = blocklinks[y*bmapwidth+x] ; mobj ; mobj = mobj->bnext)
455 ===============================================================================
459 ===============================================================================
462 intercept_t intercepts[MAXINTERCEPTS], *intercept_p;
471 = PIT_AddLineIntercepts
473 = Looks for lines in the given block that intercept the given trace
474 = to add to the intercepts list
475 = A line is crossed if its endpoints are on opposite sides of the trace
476 = Returns true if earlyout and a solid line hit
480 boolean PIT_AddLineIntercepts (line_t *ld)
486 // avoid precision problems with two routines
487 if ( trace.dx > FRACUNIT*16 || trace.dy > FRACUNIT*16
488 || trace.dx < -FRACUNIT*16 || trace.dy < -FRACUNIT*16)
490 s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace);
491 s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace);
495 s1 = P_PointOnLineSide (trace.x, trace.y, ld);
496 s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld);
499 return true; // line isn't crossed
504 P_MakeDivline (ld, &dl);
505 frac = P_InterceptVector (&trace, &dl);
507 return true; // behind source
509 // try to early out the check
510 if (earlyout && frac < FRACUNIT && !ld->backsector)
511 return false; // stop checking
513 intercept_p->frac = frac;
514 intercept_p->isaline = true;
515 intercept_p->d.line = ld;
518 return true; // continue
526 = PIT_AddThingIntercepts
531 boolean PIT_AddThingIntercepts (mobj_t *thing)
533 fixed_t x1,y1, x2,y2;
535 boolean tracepositive;
539 tracepositive = (trace.dx ^ trace.dy)>0;
541 // check a corner to corner crossection for hit
545 x1 = thing->x - thing->radius;
546 y1 = thing->y + thing->radius;
548 x2 = thing->x + thing->radius;
549 y2 = thing->y - thing->radius;
553 x1 = thing->x - thing->radius;
554 y1 = thing->y - thing->radius;
556 x2 = thing->x + thing->radius;
557 y2 = thing->y + thing->radius;
559 s1 = P_PointOnDivlineSide (x1, y1, &trace);
560 s2 = P_PointOnDivlineSide (x2, y2, &trace);
562 return true; // line isn't crossed
568 frac = P_InterceptVector (&trace, &dl);
570 return true; // behind source
571 intercept_p->frac = frac;
572 intercept_p->isaline = false;
573 intercept_p->d.thing = thing;
576 return true; // keep going
583 = P_TraverseIntercepts
585 = Returns true if the traverser function returns true for all lines
589 boolean P_TraverseIntercepts ( traverser_t func, fixed_t maxfrac )
593 intercept_t *scan, *in;
595 count = intercept_p - intercepts;
596 in = 0; // shut up compiler warning
601 for (scan = intercepts ; scan<intercept_p ; scan++)
602 if (scan->frac < dist)
609 return true; // checked everything in range
611 { // don't check these yet, ther may be others inserted
612 in = scan = intercepts;
613 for ( scan = intercepts ; scan<intercept_p ; scan++)
614 if (scan->frac > maxfrac)
622 return false; // don't bother going farther
626 return true; // everything was traversed
636 = Traces a line from x1,y1 to x2,y2, calling the traverser function for each
637 = Returns true if the traverser function returns true for all lines
641 boolean P_PathTraverse (fixed_t x1, fixed_t y1, fixed_t x2, fixed_t y2,
642 int flags, boolean (*trav) (intercept_t *))
644 fixed_t xt1,yt1,xt2,yt2;
647 fixed_t xintercept, yintercept;
648 int mapx, mapy, mapxstep, mapystep;
651 earlyout = flags & PT_EARLYOUT;
654 intercept_p = intercepts;
656 if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0)
657 x1 += FRACUNIT; // don't side exactly on a line
658 if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
659 y1 += FRACUNIT; // don't side exactly on a line
667 xt1 = x1>>MAPBLOCKSHIFT;
668 yt1 = y1>>MAPBLOCKSHIFT;
672 xt2 = x2>>MAPBLOCKSHIFT;
673 yt2 = y2>>MAPBLOCKSHIFT;
678 partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1));
679 ystep = FixedDiv (y2-y1,abs(x2-x1));
684 partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1);
685 ystep = FixedDiv (y2-y1,abs(x2-x1));
691 ystep = 256*FRACUNIT;
693 yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep);
699 partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1));
700 xstep = FixedDiv (x2-x1,abs(y2-y1));
705 partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1);
706 xstep = FixedDiv (x2-x1,abs(y2-y1));
712 xstep = 256*FRACUNIT;
714 xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep);
718 // step through map blocks
719 // Count is present to prevent a round off error from skipping the break
723 for (count = 0 ; count < 64 ; count++)
725 if (flags & PT_ADDLINES)
727 if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts))
728 return false; // early out
730 if (flags & PT_ADDTHINGS)
732 if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts))
733 return false; // early out
736 if (mapx == xt2 && mapy == yt2)
739 if ( (yintercept >> FRACBITS) == mapy)
744 else if ( (xintercept >> FRACBITS) == mapx)
754 // go through the sorted list
756 return P_TraverseIntercepts ( trav, FRACUNIT );