diff options
Diffstat (limited to 'src/p_maputl.c')
| -rw-r--r-- | src/p_maputl.c | 886 |
1 files changed, 886 insertions, 0 deletions
diff --git a/src/p_maputl.c b/src/p_maputl.c new file mode 100644 index 00000000..dc27cc00 --- /dev/null +++ b/src/p_maputl.c @@ -0,0 +1,886 @@ +// Emacs style mode select -*- C++ -*- +//----------------------------------------------------------------------------- +// +// $Id: p_maputl.c 4 2005-07-23 16:19:41Z fraggle $ +// +// Copyright (C) 1993-1996 by id Software, Inc. +// +// This source is available for distribution and/or modification +// only under the terms of the DOOM Source Code License as +// published by id Software. All rights reserved. +// +// The source is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// FITNESS FOR A PARTICULAR PURPOSE. See the DOOM Source Code License +// for more details. +// +// $Log$ +// Revision 1.1 2005/07/23 16:20:03 fraggle +// Initial revision +// +// +// DESCRIPTION: +// Movement/collision utility functions, +// as used by function in p_map.c. +// BLOCKMAP Iterator functions, +// and some PIT_* functions to use for iteration. +// +//----------------------------------------------------------------------------- + +static const char +rcsid[] = "$Id: p_maputl.c 4 2005-07-23 16:19:41Z fraggle $"; + + +#include <stdlib.h> + + +#include "m_bbox.h" + +#include "doomdef.h" +#include "p_local.h" + + +// State. +#include "r_state.h" + +// +// P_AproxDistance +// Gives an estimation of distance (not exact) +// + +fixed_t +P_AproxDistance +( fixed_t dx, + fixed_t dy ) +{ + dx = abs(dx); + dy = abs(dy); + if (dx < dy) + return dx+dy-(dx>>1); + return dx+dy-(dy>>1); +} + + +// +// P_PointOnLineSide +// Returns 0 or 1 +// +int +P_PointOnLineSide +( fixed_t x, + fixed_t y, + line_t* line ) +{ + fixed_t dx; + fixed_t dy; + fixed_t left; + fixed_t right; + + if (!line->dx) + { + if (x <= line->v1->x) + return line->dy > 0; + + return line->dy < 0; + } + if (!line->dy) + { + if (y <= line->v1->y) + return line->dx < 0; + + return line->dx > 0; + } + + dx = (x - line->v1->x); + dy = (y - line->v1->y); + + left = FixedMul ( line->dy>>FRACBITS , dx ); + right = FixedMul ( dy , line->dx>>FRACBITS ); + + if (right < left) + return 0; // front side + return 1; // back side +} + + + +// +// P_BoxOnLineSide +// Considers the line to be infinite +// Returns side 0 or 1, -1 if box crosses the line. +// +int +P_BoxOnLineSide +( fixed_t* tmbox, + line_t* ld ) +{ + int p1; + int p2; + + switch (ld->slopetype) + { + case ST_HORIZONTAL: + p1 = tmbox[BOXTOP] > ld->v1->y; + p2 = tmbox[BOXBOTTOM] > ld->v1->y; + if (ld->dx < 0) + { + p1 ^= 1; + p2 ^= 1; + } + break; + + case ST_VERTICAL: + p1 = tmbox[BOXRIGHT] < ld->v1->x; + p2 = tmbox[BOXLEFT] < ld->v1->x; + if (ld->dy < 0) + { + p1 ^= 1; + p2 ^= 1; + } + break; + + case ST_POSITIVE: + p1 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXTOP], ld); + p2 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXBOTTOM], ld); + break; + + case ST_NEGATIVE: + p1 = P_PointOnLineSide (tmbox[BOXRIGHT], tmbox[BOXTOP], ld); + p2 = P_PointOnLineSide (tmbox[BOXLEFT], tmbox[BOXBOTTOM], ld); + break; + } + + if (p1 == p2) + return p1; + return -1; +} + + +// +// P_PointOnDivlineSide +// Returns 0 or 1. +// +int +P_PointOnDivlineSide +( fixed_t x, + fixed_t y, + divline_t* line ) +{ + fixed_t dx; + fixed_t dy; + fixed_t left; + fixed_t right; + + if (!line->dx) + { + if (x <= line->x) + return line->dy > 0; + + return line->dy < 0; + } + if (!line->dy) + { + if (y <= line->y) + return line->dx < 0; + + return line->dx > 0; + } + + dx = (x - line->x); + dy = (y - line->y); + + // try to quickly decide by looking at sign bits + if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 ) + { + if ( (line->dy ^ dx) & 0x80000000 ) + return 1; // (left is negative) + return 0; + } + + left = FixedMul ( line->dy>>8, dx>>8 ); + right = FixedMul ( dy>>8 , line->dx>>8 ); + + if (right < left) + return 0; // front side + return 1; // back side +} + + + +// +// P_MakeDivline +// +void +P_MakeDivline +( line_t* li, + divline_t* dl ) +{ + dl->x = li->v1->x; + dl->y = li->v1->y; + dl->dx = li->dx; + dl->dy = li->dy; +} + + + +// +// P_InterceptVector +// Returns the fractional intercept point +// along the first divline. +// This is only called by the addthings +// and addlines traversers. +// +fixed_t +P_InterceptVector +( divline_t* v2, + divline_t* v1 ) +{ +#if 1 + fixed_t frac; + fixed_t num; + fixed_t den; + + den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy); + + if (den == 0) + return 0; + // I_Error ("P_InterceptVector: parallel"); + + num = + FixedMul ( (v1->x - v2->x)>>8 ,v1->dy ) + +FixedMul ( (v2->y - v1->y)>>8, v1->dx ); + + frac = FixedDiv (num , den); + + return frac; +#else // UNUSED, float debug. + float frac; + float num; + float den; + float v1x; + float v1y; + float v1dx; + float v1dy; + float v2x; + float v2y; + float v2dx; + float v2dy; + + v1x = (float)v1->x/FRACUNIT; + v1y = (float)v1->y/FRACUNIT; + v1dx = (float)v1->dx/FRACUNIT; + v1dy = (float)v1->dy/FRACUNIT; + v2x = (float)v2->x/FRACUNIT; + v2y = (float)v2->y/FRACUNIT; + v2dx = (float)v2->dx/FRACUNIT; + v2dy = (float)v2->dy/FRACUNIT; + + den = v1dy*v2dx - v1dx*v2dy; + + if (den == 0) + return 0; // parallel + + num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx; + frac = num / den; + + return frac*FRACUNIT; +#endif +} + + +// +// P_LineOpening +// Sets opentop and openbottom to the window +// through a two sided line. +// OPTIMIZE: keep this precalculated +// +fixed_t opentop; +fixed_t openbottom; +fixed_t openrange; +fixed_t lowfloor; + + +void P_LineOpening (line_t* linedef) +{ + sector_t* front; + sector_t* back; + + if (linedef->sidenum[1] == -1) + { + // single sided line + openrange = 0; + return; + } + + front = linedef->frontsector; + back = linedef->backsector; + + if (front->ceilingheight < back->ceilingheight) + opentop = front->ceilingheight; + else + opentop = back->ceilingheight; + + if (front->floorheight > back->floorheight) + { + openbottom = front->floorheight; + lowfloor = back->floorheight; + } + else + { + openbottom = back->floorheight; + lowfloor = front->floorheight; + } + + openrange = opentop - openbottom; +} + + +// +// THING POSITION SETTING +// + + +// +// P_UnsetThingPosition +// Unlinks a thing from block map and sectors. +// On each position change, BLOCKMAP and other +// lookups maintaining lists ot things inside +// these structures need to be updated. +// +void P_UnsetThingPosition (mobj_t* thing) +{ + int blockx; + int blocky; + + if ( ! (thing->flags & MF_NOSECTOR) ) + { + // inert things don't need to be in blockmap? + // unlink from subsector + if (thing->snext) + thing->snext->sprev = thing->sprev; + + if (thing->sprev) + thing->sprev->snext = thing->snext; + else + thing->subsector->sector->thinglist = thing->snext; + } + + if ( ! (thing->flags & MF_NOBLOCKMAP) ) + { + // inert things don't need to be in blockmap + // unlink from block map + if (thing->bnext) + thing->bnext->bprev = thing->bprev; + + if (thing->bprev) + thing->bprev->bnext = thing->bnext; + else + { + blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT; + blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT; + + if (blockx>=0 && blockx < bmapwidth + && blocky>=0 && blocky <bmapheight) + { + blocklinks[blocky*bmapwidth+blockx] = thing->bnext; + } + } + } +} + + +// +// P_SetThingPosition +// Links a thing into both a block and a subsector +// based on it's x y. +// Sets thing->subsector properly +// +void +P_SetThingPosition (mobj_t* thing) +{ + subsector_t* ss; + sector_t* sec; + int blockx; + int blocky; + mobj_t** link; + + + // link into subsector + ss = R_PointInSubsector (thing->x,thing->y); + thing->subsector = ss; + + if ( ! (thing->flags & MF_NOSECTOR) ) + { + // invisible things don't go into the sector links + sec = ss->sector; + + thing->sprev = NULL; + thing->snext = sec->thinglist; + + if (sec->thinglist) + sec->thinglist->sprev = thing; + + sec->thinglist = thing; + } + + + // link into blockmap + if ( ! (thing->flags & MF_NOBLOCKMAP) ) + { + // inert things don't need to be in blockmap + blockx = (thing->x - bmaporgx)>>MAPBLOCKSHIFT; + blocky = (thing->y - bmaporgy)>>MAPBLOCKSHIFT; + + if (blockx>=0 + && blockx < bmapwidth + && blocky>=0 + && blocky < bmapheight) + { + link = &blocklinks[blocky*bmapwidth+blockx]; + thing->bprev = NULL; + thing->bnext = *link; + if (*link) + (*link)->bprev = thing; + + *link = thing; + } + else + { + // thing is off the map + thing->bnext = thing->bprev = NULL; + } + } +} + + + +// +// BLOCK MAP ITERATORS +// For each line/thing in the given mapblock, +// call the passed PIT_* function. +// If the function returns false, +// exit with false without checking anything else. +// + + +// +// P_BlockLinesIterator +// The validcount flags are used to avoid checking lines +// that are marked in multiple mapblocks, +// so increment validcount before the first call +// to P_BlockLinesIterator, then make one or more calls +// to it. +// +boolean +P_BlockLinesIterator +( int x, + int y, + boolean(*func)(line_t*) ) +{ + int offset; + short* list; + line_t* ld; + + if (x<0 + || y<0 + || x>=bmapwidth + || y>=bmapheight) + { + return true; + } + + offset = y*bmapwidth+x; + + offset = *(blockmap+offset); + + for ( list = blockmaplump+offset ; *list != -1 ; list++) + { + ld = &lines[*list]; + + if (ld->validcount == validcount) + continue; // line has already been checked + + ld->validcount = validcount; + + if ( !func(ld) ) + return false; + } + return true; // everything was checked +} + + +// +// P_BlockThingsIterator +// +boolean +P_BlockThingsIterator +( int x, + int y, + boolean(*func)(mobj_t*) ) +{ + mobj_t* mobj; + + if ( x<0 + || y<0 + || x>=bmapwidth + || y>=bmapheight) + { + return true; + } + + + for (mobj = blocklinks[y*bmapwidth+x] ; + mobj ; + mobj = mobj->bnext) + { + if (!func( mobj ) ) + return false; + } + return true; +} + + + +// +// INTERCEPT ROUTINES +// +intercept_t intercepts[MAXINTERCEPTS]; +intercept_t* intercept_p; + +divline_t trace; +boolean earlyout; +int ptflags; + +// +// PIT_AddLineIntercepts. +// Looks for lines in the given block +// that intercept the given trace +// to add to the intercepts list. +// +// A line is crossed if its endpoints +// are on opposite sides of the trace. +// Returns true if earlyout and a solid line hit. +// +boolean +PIT_AddLineIntercepts (line_t* ld) +{ + int s1; + int s2; + fixed_t frac; + divline_t dl; + + // avoid precision problems with two routines + if ( trace.dx > FRACUNIT*16 + || trace.dy > FRACUNIT*16 + || trace.dx < -FRACUNIT*16 + || trace.dy < -FRACUNIT*16) + { + s1 = P_PointOnDivlineSide (ld->v1->x, ld->v1->y, &trace); + s2 = P_PointOnDivlineSide (ld->v2->x, ld->v2->y, &trace); + } + else + { + s1 = P_PointOnLineSide (trace.x, trace.y, ld); + s2 = P_PointOnLineSide (trace.x+trace.dx, trace.y+trace.dy, ld); + } + + if (s1 == s2) + return true; // line isn't crossed + + // hit the line + P_MakeDivline (ld, &dl); + frac = P_InterceptVector (&trace, &dl); + + if (frac < 0) + return true; // behind source + + // try to early out the check + if (earlyout + && frac < FRACUNIT + && !ld->backsector) + { + return false; // stop checking + } + + + intercept_p->frac = frac; + intercept_p->isaline = true; + intercept_p->d.line = ld; + intercept_p++; + + return true; // continue +} + + + +// +// PIT_AddThingIntercepts +// +boolean PIT_AddThingIntercepts (mobj_t* thing) +{ + fixed_t x1; + fixed_t y1; + fixed_t x2; + fixed_t y2; + + int s1; + int s2; + + boolean tracepositive; + + divline_t dl; + + fixed_t frac; + + tracepositive = (trace.dx ^ trace.dy)>0; + + // check a corner to corner crossection for hit + if (tracepositive) + { + x1 = thing->x - thing->radius; + y1 = thing->y + thing->radius; + + x2 = thing->x + thing->radius; + y2 = thing->y - thing->radius; + } + else + { + x1 = thing->x - thing->radius; + y1 = thing->y - thing->radius; + + x2 = thing->x + thing->radius; + y2 = thing->y + thing->radius; + } + + s1 = P_PointOnDivlineSide (x1, y1, &trace); + s2 = P_PointOnDivlineSide (x2, y2, &trace); + + if (s1 == s2) + return true; // line isn't crossed + + dl.x = x1; + dl.y = y1; + dl.dx = x2-x1; + dl.dy = y2-y1; + + frac = P_InterceptVector (&trace, &dl); + + if (frac < 0) + return true; // behind source + + intercept_p->frac = frac; + intercept_p->isaline = false; + intercept_p->d.thing = thing; + intercept_p++; + + return true; // keep going +} + + +// +// P_TraverseIntercepts +// Returns true if the traverser function returns true +// for all lines. +// +boolean +P_TraverseIntercepts +( traverser_t func, + fixed_t maxfrac ) +{ + int count; + fixed_t dist; + intercept_t* scan; + intercept_t* in; + + count = intercept_p - intercepts; + + in = 0; // shut up compiler warning + + while (count--) + { + dist = MAXINT; + for (scan = intercepts ; scan<intercept_p ; scan++) + { + if (scan->frac < dist) + { + dist = scan->frac; + in = scan; + } + } + + if (dist > maxfrac) + return true; // checked everything in range + +#if 0 // UNUSED + { + // don't check these yet, there may be others inserted + in = scan = intercepts; + for ( scan = intercepts ; scan<intercept_p ; scan++) + if (scan->frac > maxfrac) + *in++ = *scan; + intercept_p = in; + return false; + } +#endif + + if ( !func (in) ) + return false; // don't bother going farther + + in->frac = MAXINT; + } + + return true; // everything was traversed +} + + + + +// +// P_PathTraverse +// Traces a line from x1,y1 to x2,y2, +// calling the traverser function for each. +// Returns true if the traverser function returns true +// for all lines. +// +boolean +P_PathTraverse +( fixed_t x1, + fixed_t y1, + fixed_t x2, + fixed_t y2, + int flags, + boolean (*trav) (intercept_t *)) +{ + fixed_t xt1; + fixed_t yt1; + fixed_t xt2; + fixed_t yt2; + + fixed_t xstep; + fixed_t ystep; + + fixed_t partial; + + fixed_t xintercept; + fixed_t yintercept; + + int mapx; + int mapy; + + int mapxstep; + int mapystep; + + int count; + + earlyout = flags & PT_EARLYOUT; + + validcount++; + intercept_p = intercepts; + + if ( ((x1-bmaporgx)&(MAPBLOCKSIZE-1)) == 0) + x1 += FRACUNIT; // don't side exactly on a line + + if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0) + y1 += FRACUNIT; // don't side exactly on a line + + trace.x = x1; + trace.y = y1; + trace.dx = x2 - x1; + trace.dy = y2 - y1; + + x1 -= bmaporgx; + y1 -= bmaporgy; + xt1 = x1>>MAPBLOCKSHIFT; + yt1 = y1>>MAPBLOCKSHIFT; + + x2 -= bmaporgx; + y2 -= bmaporgy; + xt2 = x2>>MAPBLOCKSHIFT; + yt2 = y2>>MAPBLOCKSHIFT; + + if (xt2 > xt1) + { + mapxstep = 1; + partial = FRACUNIT - ((x1>>MAPBTOFRAC)&(FRACUNIT-1)); + ystep = FixedDiv (y2-y1,abs(x2-x1)); + } + else if (xt2 < xt1) + { + mapxstep = -1; + partial = (x1>>MAPBTOFRAC)&(FRACUNIT-1); + ystep = FixedDiv (y2-y1,abs(x2-x1)); + } + else + { + mapxstep = 0; + partial = FRACUNIT; + ystep = 256*FRACUNIT; + } + + yintercept = (y1>>MAPBTOFRAC) + FixedMul (partial, ystep); + + + if (yt2 > yt1) + { + mapystep = 1; + partial = FRACUNIT - ((y1>>MAPBTOFRAC)&(FRACUNIT-1)); + xstep = FixedDiv (x2-x1,abs(y2-y1)); + } + else if (yt2 < yt1) + { + mapystep = -1; + partial = (y1>>MAPBTOFRAC)&(FRACUNIT-1); + xstep = FixedDiv (x2-x1,abs(y2-y1)); + } + else + { + mapystep = 0; + partial = FRACUNIT; + xstep = 256*FRACUNIT; + } + xintercept = (x1>>MAPBTOFRAC) + FixedMul (partial, xstep); + + // Step through map blocks. + // Count is present to prevent a round off error + // from skipping the break. + mapx = xt1; + mapy = yt1; + + for (count = 0 ; count < 64 ; count++) + { + if (flags & PT_ADDLINES) + { + if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts)) + return false; // early out + } + + if (flags & PT_ADDTHINGS) + { + if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts)) + return false; // early out + } + + if (mapx == xt2 + && mapy == yt2) + { + break; + } + + if ( (yintercept >> FRACBITS) == mapy) + { + yintercept += ystep; + mapx += mapxstep; + } + else if ( (xintercept >> FRACBITS) == mapx) + { + xintercept += xstep; + mapy += mapystep; + } + + } + // go through the sorted list + return P_TraverseIntercepts ( trav, FRACUNIT ); +} + + + |