p_sight.c

//
// Copyright (C) 1993-1996 Id Software, Inc.
// Copyright (C) 2023 Frenkel Smeijers
//
// 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, see <https://www.gnu.org/licenses/>.
//

// P_sight.c

#include "doomdef.h"
#include "p_local.h"

/*
==============================================================================

							P_CheckSight

==============================================================================
*/

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

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


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

static int32_t P_DivlineSide (fixed_t x, fixed_t y, divline_t *node)
{
	fixed_t	dx, dy;
	fixed_t	left, 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 =  (node->dy>>FRACBITS) * (dx>>FRACBITS);
	right = (dy>>FRACBITS) * (node->dx>>FRACBITS);
	
	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
=
==============
*/

static fixed_t P_InterceptVector2 (divline_t *v2, divline_t *v1)
{
	fixed_t	frac, num, 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
=
==============
*/

static boolean P_CrossSubsector (int32_t num)
{
	seg_t			*seg;
	line_t			*line;
	int32_t			s1, s2;
	int32_t			count;
	subsector_t		*sub;
	sector_t		*front, *back;
	fixed_t			opentop, openbottom;
	divline_t		divl;
	vertex_t		*v1, *v2;
	fixed_t			frac, 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->validcount == validcount)
			continue;		// allready checked other side
		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);

		if (s1 == s2)
			continue;			// line isn't crossed
	
		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);

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

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

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

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

		if (openbottom >= opentop)	// quick test for totally closed doors
			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				

	}


	return true;		// passed the subsector ok
}



/*
==============
=
= P_CrossBSPNode
=
= Returns true if strace crosses the given node successfully
=
==============
*/

static boolean P_CrossBSPNode (int32_t bspnum)
{
	node_t	*bsp;
	int32_t	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))
		return true;			// the line doesn't touch the other side
    
// 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
= look from eyes of t1 to any part of t2
=
=====================
*/

boolean P_CheckSight (mobj_t *t1, mobj_t *t2)
{
	int32_t		s1, s2;
	int32_t		pnum, bytenum, bitnum;

//
// check for trivial rejection
//
	s1 = (t1->subsector->sector - sectors);
	s2 = (t2->subsector->sector - sectors);
	pnum = s1*numsectors + s2;
	bytenum = pnum>>3;
	bitnum = 1 << (pnum&7);
	
	if (rejectmatrix[bytenum]&bitnum)
	{
		return false;		// can't possibly be connected
	}

	validcount++;

	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;
	return P_CrossBSPNode (numnodes-1);	// the head node is the last node output
}