p_sight.c

// Emacs style mode select   -*- C++ -*-
//-----------------------------------------------------------------------------
//
// Copyright(C) 1993-1997 Id Software, Inc.
// Copyright(C) 1997 Midway Home Entertainment, Inc
// Copyright(C) 2007-2012 Samuel Villarreal
//
// 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:
//    LineOfSight/Visibility checks, uses REJECT Lookup Table.
//
//-----------------------------------------------------------------------------

#include "doomdef.h"
#include "m_fixed.h"
#include "i_system.h"
#include "p_local.h"
#include "doomstat.h"

//
// P_CheckSight
//
fixed_t     sightzstart;        // eye z of looker
fixed_t     topslope;
fixed_t     bottomslope;        // slopes to top and bottom of target

divline_t   strace;             // from t1 to t2
fixed_t     t2x;
fixed_t     t2y;

int         sightcounts[2];


//
// P_DivlineSide
// Returns side 0 (front), 1 (back), or 2 (on).
//

int P_DivlineSide(fixed_t x, fixed_t y, divline_t* node) {
    fixed_t    dx;
    fixed_t    dy;
    fixed_t    left;
    fixed_t    right;

    if(!node->dx) {
        if(x==node->x) {
            return 2;
        }

        if(x <= node->x) {
            return node->dy > 0;
        }

        return node->dy < 0;
    }

    if(!node->dy) {
        if(x==node->y) {
            return 2;
        }

        if(y <= node->y) {
            return node->dx < 0;
        }

        return node->dx > 0;
    }

    dx = (x - node->x);
    dy = (y - node->y);

    left =  F2INT(node->dy) * F2INT(dx);
    right = F2INT(dy) * F2INT(node->dx);

    if(right < left) {
        return 0;    // front side
    }

    if(left == right) {
        return 2;
    }

    return 1;        // back side
}


//
// P_InterceptVector2
// Returns the fractional intercept point
// along the first divline.
// This is only called by the addthings and addlines traversers.
//

fixed_t P_InterceptVector2(divline_t* v2, divline_t* v1) {
    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;
    }

    num = FixedMul((v1->x - v2->x)>>8 ,v1->dy) +
          FixedMul((v2->y - v1->y)>>8 , v1->dx);

    frac = FixedDiv(num , den);

    return frac;
}

//
// P_CrossSubsector
// Returns true if strace crosses the given subsector successfully.
//

dboolean P_CrossSubsector(int num) {
    seg_t*          seg;
    line_t*         line;
    int             s1;
    int             s2;
    int             count;
    subsector_t*    sub;
    sector_t*       front;
    sector_t*       back;
    fixed_t         opentop;
    fixed_t         openbottom;
    divline_t       divl;
    vertex_t*       v1;
    vertex_t*       v2;
    fixed_t         frac;
    fixed_t         slope;

#ifdef RANGECHECK
    if(num>=numsubsectors)
        I_Error("P_CrossSubsector: ss %i with numss = %i",
                num,
                numsubsectors);
#endif

    sub = &subsectors[num];

    // check lines
    count = sub->numlines;
    seg = &segs[sub->firstline];

    for(; count; seg++, count--) {
        line = seg->linedef;
        if(!line) { //miniseg!
            continue;
        }

        // allready checked other side?
        if(line->validcount == validcount) {
            continue;
        }

        line->validcount = validcount;

        v1 = line->v1;
        v2 = line->v2;
        s1 = P_DivlineSide(v1->x,v1->y, &strace);
        s2 = P_DivlineSide(v2->x, v2->y, &strace);

        // line isn't crossed?
        if(s1 == s2) {
            continue;
        }

        divl.x = v1->x;
        divl.y = v1->y;
        divl.dx = v2->x - v1->x;
        divl.dy = v2->y - v1->y;
        s1 = P_DivlineSide(strace.x, strace.y, &divl);
        s2 = P_DivlineSide(t2x, t2y, &divl);

        // line isn't crossed?
        if(s1 == s2) {
            continue;
        }

        // stop because it is not two sided anyway
        // might do this after updating validcount?
        if(!(line->flags & ML_TWOSIDED)) {
            return false;
        }

        // crosses a two sided line
        front = seg->frontsector;
        back = seg->backsector;

        // no wall to block sight with?
        if(front->floorheight == back->floorheight
                && front->ceilingheight == back->ceilingheight) {
            continue;
        }

        // possible occluder
        // because of ceiling height differences
        if(front->ceilingheight < back->ceilingheight) {
            opentop = front->ceilingheight;
        }
        else {
            opentop = back->ceilingheight;
        }

        // because of ceiling height differences
        if(front->floorheight > back->floorheight) {
            openbottom = front->floorheight;
        }
        else {
            openbottom = back->floorheight;
        }

        // quick test for totally closed doors
        if(openbottom >= opentop) {
            return false;    // stop
        }

        frac = P_InterceptVector2(&strace, &divl);

        if(front->floorheight != back->floorheight) {
            slope = FixedDiv(openbottom - sightzstart , frac);
            if(slope > bottomslope) {
                bottomslope = slope;
            }
        }

        if(front->ceilingheight != back->ceilingheight) {
            slope = FixedDiv(opentop - sightzstart , frac);
            if(slope < topslope) {
                topslope = slope;
            }
        }

        if(topslope <= bottomslope) {
            return false;    // stop
        }
    }

    // passed the subsector ok
    return true;
}



//
// P_CrossBSPNode
// Returns true if strace crosses the given node successfully.
//

dboolean P_CrossBSPNode(int bspnum) {
    node_t* bsp;
    int     side;

    if(bspnum & NF_SUBSECTOR) {
        if(bspnum == -1) {
            return P_CrossSubsector(0);
        }
        else {
            return P_CrossSubsector(bspnum&(~NF_SUBSECTOR));
        }
    }

    bsp = &nodes[bspnum];

    // decide which side the start point is on
    side = P_DivlineSide(strace.x, strace.y, (divline_t *)bsp);
    if(side == 2) {
        side = 0;    // an "on" should cross both sides
    }

    // cross the starting side
    if(!P_CrossBSPNode(bsp->children[side])) {
        return false;
    }

    // the partition plane is crossed here
    if(side == P_DivlineSide(t2x, t2y,(divline_t *)bsp)) {
        // the line doesn't touch the other side
        return true;
    }

    // cross the ending side
    return P_CrossBSPNode(bsp->children[side^1]);
}


//
// P_CheckSight
// Returns true if a straight line between t1 and t2 is unobstructed.
// Uses REJECT.
//

dboolean P_CheckSight(mobj_t* t1, mobj_t* t2) {
    int     s1;
    int     s2;
    int     pnum;
    int     bytenum;
    int     bitnum;

    // First check for trivial rejection.

    // Determine subsector entries in REJECT table.
    s1 = (t1->subsector->sector - sectors);
    s2 = (t2->subsector->sector - sectors);
    pnum = s1*numsectors + s2;
    bytenum = pnum>>3;
    bitnum = 1 << (pnum&7);

    // Check in REJECT table.
    if(rejectmatrix[bytenum]&bitnum) {
        sightcounts[0]++;

        // can't possibly be connected
        return false;
    }

    // An unobstructed LOS is possible.
    // Now look from eyes of t1 to any part of t2.
    sightcounts[1]++;

    D_IncValidCount();

    sightzstart = t1->z + t1->height - (t1->height>>2);
    topslope = (t2->z+t2->height) - sightzstart;
    bottomslope = (t2->z) - sightzstart;

    strace.x = t1->x;
    strace.y = t1->y;
    t2x = t2->x;
    t2y = t2->y;
    strace.dx = t2->x - t1->x;
    strace.dy = t2->y - t1->y;

    // the head node is the last node output
    return P_CrossBSPNode(numnodes-1);
}

//
// P_ScanSights
// Optimal mobj sight checking that check sights
// in main tick loop rather from multiple
// mobj action routines
//

void P_ScanSights(void) {
    mobj_t* mobj;

    for(mobj = mobjhead.next; mobj != &mobjhead; mobj = mobj->next) {
        // must be killable
        if(!(mobj->flags & MF_COUNTKILL)) {
            continue;
        }

        // must have longer tics
        if(mobj->tics == 1) {
            continue;
        }

        mobj->flags &= ~MF_SEETARGET;

        // must have a target
        if(!mobj->target) {
            continue;
        }

        if(!P_CheckSight(mobj, mobj->target)) {
            continue;
        }

        mobj->flags |= MF_SEETARGET;
    }
}