p_maputl.c

The source code of Doom legacy for windows

// Emacs style mode select   -*- C++ -*- 
//-----------------------------------------------------------------------------
//
// $Id: p_maputl.c,v 1.11 2001/03/13 22:14:19 stroggonmeth Exp $
//
// Copyright (C) 1993-1996 by id Software, Inc.
// Portions Copyright (C) 1998-2000 by DooM Legacy Team.
//
// 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.
//
//
// $Log: p_maputl.c,v $
// Revision 1.11  2001/03/13 22:14:19  stroggonmeth
// Long time no commit. 3D floors, FraggleScript, portals, ect.
//
// Revision 1.10  2001/01/25 22:15:43  bpereira
// added heretic support
//
// Revision 1.9  2000/11/02 19:49:35  bpereira
// no message
//
// Revision 1.8  2000/11/02 17:50:08  stroggonmeth
// Big 3Dfloors & FraggleScript commit!!
//
// Revision 1.7  2000/08/31 14:30:55  bpereira
// no message
//
// Revision 1.6  2000/08/11 19:10:13  metzgermeister
// *** empty log message ***
//
// Revision 1.5  2000/04/15 22:12:57  stroggonmeth
// Minor bug fixes
//
// Revision 1.4  2000/04/08 17:29:25  stroggonmeth
// no message
//
// Revision 1.3  2000/04/04 00:32:47  stroggonmeth
// Initial Boom compatability plus few misc changes all around.
//
// Revision 1.2  2000/02/27 00:42:10  hurdler
// fix CR+LF problem
//
// Revision 1.1.1.1  2000/02/22 20:32:32  hurdler
// Initial import into CVS (v1.29 pr3)
//
//
// 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 "p_local.h"
#include "r_main.h"
#include "p_maputl.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;
      default :
        I_Error("P_BoxOnLineSide: unknow slopetype %d\n",ld->slopetype);
        return -1;
    }

    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,num,den;
    float       v1x,v1y,v1dx,v1dy;
    float       v2x,v2y,v2dx,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;
    extern mobj_t* tmthing;

    if (linedef->sidenum[1] == -1)
    {
        // single sided line
        openrange = 0;
        return;
    }

    front = linedef->frontsector;
    back = linedef->backsector;
#ifdef PARANOIA
    if(!front)
        I_Error("lindef without front");
    if(!back)
        I_Error("lindef without back");
#endif

    if(tmthing)
    {
      wallportal_t*  wpr;
      fixed_t        thingbot, thingtop;

      thingbot = tmthing->z;
      thingtop = thingbot + tmthing->height;

      for(wpr = linedef->wallportals; wpr; wpr = wpr->next)
        if(thingtop <= *wpr->topheight && thingtop >= *wpr->bottomheight)
          break;

      if(wpr)
      {
        opentop = *wpr->topheight;
        lowfloor = front->floorheight < back->floorheight ? front->floorheight : back->floorheight;
        if(*wpr->bottomheight < lowfloor)
        {
          openbottom = lowfloor;
          lowfloor = *wpr->bottomheight;
        }
        else
          openbottom = *wpr->bottomheight;
      }
      else
      {
        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;
        }
      }

      //SoM: 3/27/2000: Check for fake floors in the sector.
      if(front->ffloors || back->ffloors)
      {
        ffloor_t*      rover;

        fixed_t    lowestceiling = opentop;
        fixed_t    highestfloor = openbottom;
        fixed_t    lowestfloor = lowfloor;
        fixed_t    delta1;
        fixed_t    delta2;

        if(!tmthing)
          goto no_thing;

        thingtop = tmthing->z + tmthing->height;

        // Check for frontsector's fake floors
        if(front->ffloors)
          for(rover = front->ffloors; rover; rover = rover->next)
          {
            if(!(rover->flags & FF_SOLID)) continue;

            delta1 = abs(tmthing->z - ((*rover->bottomheight + *rover->topheight) / 2));
            delta2 = abs(thingtop - ((*rover->bottomheight + *rover->topheight) / 2));
            if(*rover->bottomheight < lowestceiling && delta1 >= delta2)
              lowestceiling = *rover->bottomheight;

            if(*rover->topheight > highestfloor && delta1 < delta2)
              highestfloor = *rover->topheight;
            else if(*rover->topheight > lowestfloor && delta1 < delta2)
              lowestfloor = *rover->topheight;
          }

        // Check for backsectors fake floors
        if(back->ffloors)
          for(rover = back->ffloors; rover; rover = rover->next)
          {
            if(!(rover->flags & FF_SOLID))
              continue;

            delta1 = abs(tmthing->z - ((*rover->bottomheight + *rover->topheight) / 2));
            delta2 = abs(thingtop - ((*rover->bottomheight + *rover->topheight) / 2));
            if(*rover->bottomheight < lowestceiling && delta1 >= delta2)
              lowestceiling = *rover->bottomheight;

            if(*rover->topheight > highestfloor && delta1 < delta2)
              highestfloor = *rover->topheight;
            else if(*rover->topheight > lowestfloor && delta1 < delta2)
              lowestfloor = *rover->topheight;
          }

        if(highestfloor > openbottom)
          openbottom = highestfloor;

        if(lowestceiling < opentop)
          opentop = lowestceiling;

        if(lowestfloor > lowfloor)
          lowfloor = lowestfloor;
      }
      openrange = opentop - openbottom;
      return;
    }

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

    no_thing:

    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;
#ifdef PARANOIA
        thing->sprev = NULL;
        thing->snext = NULL;
#endif
        //SoM: 4/7/2000
        //
        // Save the sector list pointed to by touching_sectorlist.
        // In P_SetThingPosition, we'll keep any nodes that represent
        // sectors the Thing still touches. We'll add new ones then, and
        // delete any nodes for sectors the Thing has vacated. Then we'll
        // put it back into touching_sectorlist. It's done this way to
        // avoid a lot of deleting/creating for nodes, when most of the
        // time you just get back what you deleted anyway.
        //
        // If this Thing is being removed entirely, then the calling
        // routine will clear out the nodes in sector_list.

        sector_list = thing->touching_sectorlist;
        thing->touching_sectorlist = NULL; //to be restored by P_SetThingPosition
    }

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