doom

p_maputl.c (12042B)

---

 #include <stdlib.h>
 
 #include "m_bbox.h"
 #include "doomdef.h"
 #include "p_local.h"
 #include "r_state.h"
 
 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);
 }
 
 
 
 
 
 
 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;		
     return 1;			
 }
 
 
 
 
 
 
 
 
 int
 P_BoxOnLineSide(fixed_t* tmbox, line_t* ld)
 {
     int	 p1, 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:
 			p1 = p2 = 0;
     }
     if (p1 == p2)
 		return p1;
     return -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);
 	
     
     if ( (line->dy ^ line->dx ^ dx ^ dy)&0x80000000 )
     {
 	if ( (line->dy ^ dx) & 0x80000000 )
 	    return 1;		
 	return 0;
     }
 	
     left = FixedMul ( line->dy>>8, dx>>8 );
     right = FixedMul ( dy>>8 , line->dx>>8 );
 	
     if (right < left)
 	return 0;		
     return 1;			
 }
 
 
 
 
 
 
 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;
 }
 
 
 
 
 
 
 
 
 
 
 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;
     
     
     num =
 	FixedMul ( (v1->x - v2->x)>>8 ,v1->dy )
 	+FixedMul ( (v2->y - v1->y)>>8, v1->dx );
 
     frac = FixedDiv (num , den);
 
     return frac;
 #else	
     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;	
     
     num = (v1x - v2x)*v1dy + (v2y - v1y)*v1dx;
     frac = num / den;
 
     return frac*FRACUNIT;
 #endif
 }
 
 
 
 
 
 
 
 
 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)
     {
 	
 	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;
 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 void P_UnsetThingPosition (mobj_t* thing)
 {
     int		blockx;
     int		blocky;
 
     if ( ! (thing->flags & MF_NOSECTOR) )
     {
 	
 	
 	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) )
     {
 	
 	
 	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;
 	    }
 	}
     }
 }
 
 
 
 
 
 
 
 
 void
 P_SetThingPosition (mobj_t* thing)
 {
     subsector_t*	ss;
     sector_t*		sec;
     int			blockx;
     int			blocky;
     mobj_t**		link;
 
     
     
     ss = R_PointInSubsector (thing->x,thing->y);
     thing->subsector = ss;
     
     if ( ! (thing->flags & MF_NOSECTOR) )
     {
 	
 	sec = ss->sector;
 	
 	thing->sprev = NULL;
 	thing->snext = sec->thinglist;
 
 	if (sec->thinglist)
 	    sec->thinglist->sprev = thing;
 
 	sec->thinglist = thing;
     }
 
     
     
     if ( ! (thing->flags & MF_NOBLOCKMAP) )
     {
 	
 	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->bnext = thing->bprev = NULL;
 	}
     }
 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 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; 	
 
 	ld->validcount = validcount;
 		
 	if ( !func(ld) )
 	    return false;
     }
     return true;	
 }
 
 
 
 
 
 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_t	intercepts[INT_MAXERCEPTS];
 intercept_t*	intercept_p;
 
 divline_t 	trace;
 boolean 	earlyout;
 int		ptflags;
 
 
 
 
 
 
 
 
 
 
 
 boolean
 PIT_AddLineIntercepts (line_t* ld)
 {
     int			s1;
     int			s2;
     fixed_t		frac;
     divline_t		dl;
 	
     
     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;	
     
     
     P_MakeDivline (ld, &dl);
     frac = P_InterceptVector (&trace, &dl);
 
     if (frac < 0)
 	return true;	
 	
     
     if (earlyout
 	&& frac < FRACUNIT
 	&& !ld->backsector)
     {
 	return false;	
     }
     
 	
     intercept_p->frac = frac;
     intercept_p->isaline = true;
     intercept_p->d.line = ld;
     intercept_p++;
 
     return true;	
 }
 
 
 
 
 
 
 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;
 		
     
     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;		
 	
     dl.x = x1;
     dl.y = y1;
     dl.dx = x2-x1;
     dl.dy = y2-y1;
     
     frac = P_InterceptVector (&trace, &dl);
 
     if (frac < 0)
 	return true;		
 
     intercept_p->frac = frac;
     intercept_p->isaline = false;
     intercept_p->d.thing = thing;
     intercept_p++;
 
     return true;		
 }
 
 
 
 
 
 
 
 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;			
 	
     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;	
 
 #if 0  
     {
 	
 	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;	
 
 	in->frac = INT_MAX;
     }
 	
     return true;		
 }
 
 
 
 
 
 
 
 
 
 
 
 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;	
     
     if ( ((y1-bmaporgy)&(MAPBLOCKSIZE-1)) == 0)
 	y1 += FRACUNIT;	
 
     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);
     
     
     
     
     mapx = xt1;
     mapy = yt1;
 	
     for (count = 0 ; count < 64 ; count++)
     {
 	if (flags & PT_ADDLINES)
 	{
 	    if (!P_BlockLinesIterator (mapx, mapy,PIT_AddLineIntercepts))
 		return false;	
 	}
 	
 	if (flags & PT_ADDTHINGS)
 	{
 	    if (!P_BlockThingsIterator (mapx, mapy,PIT_AddThingIntercepts))
 		return false;	
 	}
 		
 	if (mapx == xt2
 	    && mapy == yt2)
 	{
 	    break;
 	}
 	
 	if ( (yintercept >> FRACBITS) == mapy)
 	{
 	    yintercept += ystep;
 	    mapx += mapxstep;
 	}
 	else if ( (xintercept >> FRACBITS) == mapx)
 	{
 	    xintercept += xstep;
 	    mapy += mapystep;
 	}
 		
     }
     
     return P_TraverseIntercepts ( trav, FRACUNIT );
 }