diff options
Diffstat (limited to 'src/strife/p_maputl.c')
| -rw-r--r-- | src/strife/p_maputl.c | 1009 |
1 files changed, 0 insertions, 1009 deletions
diff --git a/src/strife/p_maputl.c b/src/strife/p_maputl.c deleted file mode 100644 index 4ab5d1d5..00000000 --- a/src/strife/p_maputl.c +++ /dev/null @@ -1,1009 +0,0 @@ -// 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 ); -} - - - |