Amiga ACS 1998 #2/amigaacscoverdisc1998-021998.iso/games/doom/source/linuxdoom-1.10/p_maputl.c

C/C++ Source or Header | 1997-12-22 | 16KB | 884 lines

// Emacs style mode select   -*- C++ -*-
//-----------------------------------------------------------------------------
//
// $Id:$
//
// 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:$
//
// 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,v 1.5 1997/02/03 22:45:11 b1 Exp $";


#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 );
}