diff options
Diffstat (limited to 'src/doom/p_maputl.c')
| -rw-r--r-- | src/doom/p_maputl.c | 1009 |
1 files changed, 1009 insertions, 0 deletions
diff --git a/src/doom/p_maputl.c b/src/doom/p_maputl.c new file mode 100644 index 00000000..4ab5d1d5 --- /dev/null +++ b/src/doom/p_maputl.c @@ -0,0 +1,1009 @@ +// Emacs style mode select -*- C++ -*- +//----------------------------------------------------------------------------- +// +// Copyright(C) 1993-1996 Id Software, Inc. +// Copyright(C) 2005 Simon Howard +// Copyright(C) 2005, 2006 Andrey Budko +// +// This program is free software; you can redistribute it and/or +// modify it under the terms of the GNU General Public License +// as published by the Free Software Foundation; either version 2 +// of the License, or (at your option) any later version. +// +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA +// 02111-1307, USA. +// +// DESCRIPTION: +// Movement/collision utility functions, +// as used by function in p_map.c. +// BLOCKMAP Iterator functions, +// and some PIT_* functions to use for iteration. +// +//----------------------------------------------------------------------------- + + + +#include <stdlib.h> + + +#include "m_bbox.h" + +#include "doomdef.h" +#include "doomstat.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 = 0; + int p2 = 0; + + 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; + +static void InterceptsOverrun(int num_intercepts, intercept_t *intercept); + +// +// 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; + InterceptsOverrun(intercept_p - intercepts, intercept_p); + 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; + InterceptsOverrun(intercept_p - intercepts, intercept_p); + 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 = INT_MAX; + 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 = INT_MAX; + } + + return true; // everything was traversed +} + +extern fixed_t bulletslope; + +// Intercepts Overrun emulation, from PrBoom-plus. +// Thanks to Andrey Budko (entryway) for researching this and his +// implementation of Intercepts Overrun emulation in PrBoom-plus +// which this is based on. + +typedef struct +{ + int len; + void *addr; + boolean int16_array; +} intercepts_overrun_t; + +// Intercepts memory table. This is where various variables are located +// in memory in Vanilla Doom. When the intercepts table overflows, we +// need to write to them. +// +// Almost all of the values to overwrite are 32-bit integers, except for +// playerstarts, which is effectively an array of 16-bit integers and +// must be treated differently. + +static intercepts_overrun_t intercepts_overrun[] = +{ + {4, NULL, false}, + {4, NULL, /* &earlyout, */ false}, + {4, NULL, /* &intercept_p, */ false}, + {4, &lowfloor, false}, + {4, &openbottom, false}, + {4, &opentop, false}, + {4, &openrange, false}, + {4, NULL, false}, + {120, NULL, /* &activeplats, */ false}, + {8, NULL, false}, + {4, &bulletslope, false}, + {4, NULL, /* &swingx, */ false}, + {4, NULL, /* &swingy, */ false}, + {4, NULL, false}, + {40, &playerstarts, true}, + {4, NULL, /* &blocklinks, */ false}, + {4, &bmapwidth, false}, + {4, NULL, /* &blockmap, */ false}, + {4, &bmaporgx, false}, + {4, &bmaporgy, false}, + {4, NULL, /* &blockmaplump, */ false}, + {4, &bmapheight, false}, + {0, NULL, false}, +}; + +// Overwrite a specific memory location with a value. + +static void InterceptsMemoryOverrun(int location, int value) +{ + int i, offset; + int index; + void *addr; + + i = 0; + offset = 0; + + // Search down the array until we find the right entry + + while (intercepts_overrun[i].len != 0) + { + if (offset + intercepts_overrun[i].len > location) + { + addr = intercepts_overrun[i].addr; + + // Write the value to the memory location. + // 16-bit and 32-bit values are written differently. + + if (addr != NULL) + { + if (intercepts_overrun[i].int16_array) + { + index = (location - offset) / 2; + ((short *) addr)[index] = value & 0xffff; + ((short *) addr)[index + 1] = (value >> 16) & 0xffff; + } + else + { + index = (location - offset) / 4; + ((int *) addr)[index] = value; + } + } + + break; + } + + offset += intercepts_overrun[i].len; + ++i; + } +} + +// Emulate overruns of the intercepts[] array. + +static void InterceptsOverrun(int num_intercepts, intercept_t *intercept) +{ + int location; + + if (num_intercepts <= MAXINTERCEPTS_ORIGINAL) + { + // No overrun + + return; + } + + location = (num_intercepts - MAXINTERCEPTS_ORIGINAL - 1) * 12; + + // Overwrite memory that is overwritten in Vanilla Doom, using + // the values from the intercept structure. + // + // Note: the ->d.{thing,line} member should really have its + // address translated into the correct address value for + // Vanilla Doom. + + InterceptsMemoryOverrun(location, intercept->frac); + InterceptsMemoryOverrun(location + 4, intercept->isaline); + InterceptsMemoryOverrun(location + 8, (int) intercept->d.thing); +} + + +// +// 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 ); +} + + + |