/*
			===== IDBSP - id Software's BSP builder for DOOM ====
	DOS port (c) 1994 Ron Rossbach (ej070@cleveland.freenet.edu)

	File: SAVECNCT.C
		Implements the functions which build the REJECT resource.

	Revisions:

		1)	Comment out drawing code, leaving behind empty (NOP) functions to
				preserve the original function calls elsewhere in the code. (v1.0)

		2)	Add "fullreject" command line switch to include "small sectors" (stairs,
				doorways, etc) in the reject calculations.  By default, these sectors
				are ignored. (v1.1)
*/

#include "idbsp.h"

byte				*connections;

int					numblines;
bline_t			*blines;

int					numsectors;
bbox_t			*secboxes;

int					numbchains;
bchain_t		*bchains;

bdivline_t	ends[2], sides[2];
int					end0out, end1out, side0out, side1out;
bbox_t			sweptarea;

/*
===============================================================================
=
= ClearBBox
=
===============================================================================
*/
void ClearBBox(bbox_t *box)
{
	box->xl = box->yl = INT_MAX;
	box->xh = box->yh = INT_MIN;
}

/*
===============================================================================
=
= AddToBBox
=
===============================================================================
*/
void AddToBBox(bbox_t *box, int x, int y)
{
	if (x < box->xl)
		box->xl = x;
	if (x > box->xh)
		box->xh = x;
	if (y < box->yl)
		box->yl = y;
	if (y > box->yh)
		box->yh = y;
}

/*
===============================================================================
=
= BPointOnSide
=
= Returns side 0 (front), 1 (back), or -1 (colinear)
===============================================================================
*/
int	BPointOnSide (bpoint_t *pt, bdivline_t *l)
{
	int		dx,dy;
	int		left, right;

	if (!l->dx)
	{
		if (pt->x < l->x)
			return l->dy > 0;
		return l->dy < 0;
	}
	if (!l->dy)
	{
		if (pt->y < l->y)
			return l->dx < 0;
		return l->dx > 0;
	}

	dx = pt->x - l->x;
	dy = pt->y - l->y;

	left = l->dy * dx;
	right = dy * l->dx;

	if (right < left)
		return 0;		/* front side */
	return 1;			/* back side */
}

/*
===============================================================================
=
=	DrawBBox
=
===============================================================================
*/
void DrawBBox (bbox_t *box)
{
/*
	PSmoveto (box->xl,box->yl);
	PSlineto (box->xh,box->yl);
	PSlineto (box->xh,box->yh);
	PSlineto (box->xl,box->yh);
	PSlineto (box->xl,box->yl);
	PSstroke ();
	NXPing ();
*/
}

/*
===============================================================================
=
=	DrawDivline
=
===============================================================================
*/
void DrawDivline(bdivline_t *li)
{
/*
	PSmoveto (li->x,li->y);
	PSrlineto (li->dx,li->dy);
	PSstroke ();
	NXPing ();
*/
}

/*
===============================================================================
=
=	DrawBChain
=
===============================================================================
*/
void DrawBChain(bchain_t *ch)
{
/*
	int		i;

	PSmoveto (ch->points->x,ch->points->y);
	for (i=1 ; i<ch->numpoints ; i++)
		PSlineto (ch->points[i].x,ch->points[i].y);
	PSstroke ();
	NXPing ();
*/
}

/*
===============================================================================
=
=	DoesChainBlock
=
===============================================================================
*/
boolean DoesChainBlock(bchain_t *chain)
{
/*
	if a solid line can be walked from one side to the other without going out
	an end, the path is blocked
*/
	bpoint_t	*pt;
	int				side, startside;
	int				p;

/* don't check if bounds don't intersect */
	if (sweptarea.xl > chain->bounds.xh || sweptarea.xh < chain->bounds. xl ||
			sweptarea.yl > chain->bounds. yh || sweptarea.yh < chain->bounds. yl)
		return false;

	startside = -1;		/* not started yet */

	for (p=0, pt=chain->points ; p<chain->numpoints ; p++, pt++)
		{
		/* find side for pt */
		if (BPointOnSide (pt, &ends[0]) == end0out)
			{
			startside = -1;	/* off end */
			continue;
			}
		if (BPointOnSide (pt, &ends[1]) == end1out)
			{
			startside = -1;	/* off end */
			continue;
			}
		if (BPointOnSide (pt, &sides[0]) == side0out)
			side = 0;
		else
			if (BPointOnSide (pt, &sides[1]) == side1out)
				side = 1;
			else
				continue;		/* in middle */

	/* point is on one side or the other */
		if (startside == -1 || startside == side)
			{
			startside = side;
			continue;
			}

	/* opposite of startside */
		return true;		/* totally crossed area */
	}

	return false;
}

/*
===============================================================================
=
=	BuildConnections
=
===============================================================================
*/
void BuildConnections(void)
{
	int				blockcount, passcount;
	int				i, j, k, s, bn;
	int				x, y;
	bbox_t		*bbox[2];
	int				walls[4];
	bpoint_t	points[2][2];

/* look for obscured sectors */
	blockcount = passcount = 0;
	bbox[0] = secboxes;
	printf("\n");
	for (i=0 ; i<numsectors-1 ; i++, bbox[0]++)
		{
		printf("connection #%d of %d\r",i,numsectors-1);
		bbox[1] = bbox[0] + 1;
		if ((!fullreject) && (bbox[0]->xh - bbox[0]->xl < 64 ||
													bbox[0]->yh - bbox[0]->yl < 64))
			{	/* don't bother with small sectors (stairs, doorways, etc) */
			continue;
			}
		for (j=i+1 ; j<numsectors ; j++, bbox[1]++)
			{
			if ((!fullreject) && (bbox[1]->xh - bbox[1]->xl < 64 ||
														bbox[1]->yh - bbox[1]->yl < 64))
				{	/* don't bother with small sectors (stairs, doorways, etc) */
				continue;
				}
			if (bbox[1]->xl <= bbox[0]->xh && bbox[1]->xh >= bbox[0]->xl &&
					bbox[1]->yl <= bbox[0]->yh && bbox[1]->yh >= bbox[0]->yl)
				{	/* touching sectors are never blocked */
					passcount++;
					continue;
				}

			sweptarea.xl = bbox[0]->xl < bbox[1]->xl ? bbox[0]->xl : bbox[1]->xl;
			sweptarea.xh = bbox[0]->xh > bbox[1]->xh ? bbox[0]->xh : bbox[1]->xh;
			sweptarea.yl = bbox[0]->yl < bbox[1]->yl ? bbox[0]->yl : bbox[1]->yl;
			sweptarea.yh = bbox[0]->yh > bbox[1]->yh ? bbox[0]->yh : bbox[1]->yh;

/*
 calculate the swept area between the sectors
*/
			for (bn=0 ; bn<2 ; bn++)
				{
				memset (walls,0,sizeof(walls));
				if (bbox[bn]->xl <= bbox[!bn]->xl)
					walls[si_west] = 1;
				if (bbox[bn]->xh >= bbox[!bn]->xh)
					walls[si_east] = 1;
				if (bbox[bn]->yl <= bbox[!bn]->yl)
					walls[si_south] = 1;
				if (bbox[bn]->yh >= bbox[!bn]->yh)
					walls[si_north] = 1;

				for (s=0 ; s<5 ; s++)
					{
					switch (s&3)
						{
						case si_north:
							x = bbox[bn]->xl;
							y = bbox[bn]->yh;
							break;
						case si_east:
							x = bbox[bn]->xh;
							y = bbox[bn]->yh;
							break;
						case si_south:
							x = bbox[bn]->xh;
							y = bbox[bn]->yl;
							break;
						case si_west:
							x = bbox[bn]->xl;
							y = bbox[bn]->yl;
							break;
						}
					if (!walls[(s-1)&3] && walls[s&3])
						{
						points[bn][0].x = x;
						points[bn][0].y = y;
						}
					if (walls[(s-1)&3] && !walls[s&3])
						{
						points[bn][1].x = x;
						points[bn][1].y = y;
						}
					}

				ends[bn].x = points[bn][0].x;
				ends[bn].y = points[bn][0].y;
				ends[bn].dx = points[bn][1].x - points[bn][0].x;
				ends[bn].dy = points[bn][1].y - points[bn][0].y;
				}

			sides[0].x = points[0][0].x;
			sides[0].y = points[0][0].y;
			sides[0].dx = points[1][1].x - points[0][0].x;
			sides[0].dy = points[1][1].y - points[0][0].y;

			sides[1].x = points[0][1].x;
			sides[1].y = points[0][1].y;
			sides[1].dx = points[1][0].x - points[0][1].x;
			sides[1].dy = points[1][0].y - points[0][1].y;

			end0out = !BPointOnSide (&points[1][0], &ends[0]);
			end1out = !BPointOnSide (&points[0][0], &ends[1]);
			side0out = !BPointOnSide (&points[0][1], &sides[0]);
			side1out = !BPointOnSide (&points[0][0], &sides[1]);

/*
 look for a line change that covers the swept area
*/
			for (k=0 ; k<numbchains ; k++)
				{
				if (!DoesChainBlock (&bchains[k]))
					continue;
				blockcount++;
				connections[i*numsectors+j] = connections[j*numsectors+i] = 1;
				goto blocked;
				}

/* nothing definately blocked the path */
			passcount++;

blocked: ;
			}
		}

	printf ("passcount: %i\nblockcount: %i\n",passcount, blockcount);
}

/*
===============================================================================
=
=	BuildBlockingChains
=
===============================================================================
*/
void BuildBlockingChains(void)
{
	boolean		*used;
	int				i, j;
	bpoint_t	*temppoints, *pt_p;
	bline_t		*li1, *li2;
	STORAGE 	*chains_i;
	bchain_t	bch;
	int				cx, cy;

	used = alloca(numblines*sizeof (*used));
	memset(used,0,numblines*sizeof (*used));
	temppoints = alloca(numblines*sizeof (*temppoints));

	chains_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	chains_i->data = (bchain_t *)SafeMalloc(sizeof(bchain_t));
	chains_i->count = 0;
	chains_i->size = sizeof(bchain_t);

	printf("\n");
	li1 = blines;
	for (i=0 ; i<numblines ; i++, li1++)
		{
		printf("bline #%d of %d\r",i,numblines);
		if (used[i])
			continue;
		used[i] = true;

		/* start a new chain */
		pt_p = temppoints;
		pt_p->x = li1->p1.x;
		pt_p->y = li1->p1.y;
		pt_p++;
		pt_p->x = cx = li1->p2.x;
		pt_p->y = cy = li1->p2.y;
		pt_p++;

		ClearBBox(&bch.bounds);
		AddToBBox(&bch.bounds, li1->p1.x, li1->p1.y);
		AddToBBox(&bch.bounds, cx, cy);

		/* look for connected lines */
		do
			{
			li2 = li1+1;
			for (j=i+1 ; j<numblines ; j++,li2++)
				if (!used[j] && li2->p1.x == cx && li2->p1.y == cy)
					break;

			if (j==numblines)
				break;		/* no more lines in chain */

		/* add to chain */
			used[j] = true;
			pt_p->x = cx = li2->p2.x;
			pt_p->y = cy = li2->p2.y;
			pt_p++;
			AddToBBox (&bch.bounds, cx, cy);
			} while (1);

/* save the block chain */
		bch.numpoints = pt_p - temppoints;
		bch.points = (bpoint_t *)SafeMalloc (bch.numpoints*sizeof(*bch.points));
		memcpy (bch.points, temppoints, bch.numpoints*sizeof(*bch.points));

		memcpy((bchain_t *)chains_i->data + chains_i->count, &bch, sizeof(bchain_t));
		chains_i->count += 1;
		chains_i->data = (bchain_t *)SafeRealloc(chains_i->data,
											sizeof(bchain_t) * (chains_i->count + 1));
		}

	numbchains = chains_i->count;
	bchains = chains_i->data;
}

/*
===============================================================================
=
=	BuildBlockingChains
=
===============================================================================
*/
void ProcessConnections (void)
{
	int						i, s, wlcount, count;
	bbox_t				*secbox;
	STORAGE 			*lines;
	worldline_t		*wl;
	mapvertex_t		*vt;
	maplinedef_t	*p;
	mapsidedef_t	*sd;
	bline_t				bline;
	int						sec;
	int 					RonsLines = 0;

	numsectors = secstore_i->count;

	printf("\n numsectors: %d\n",numsectors);
	wlcount = linestore_i->count;

															/* allow rounding to bytes */
	connections = (unsigned char *)SafeMalloc(numsectors*numsectors+8);
	memset (connections, 0, numsectors*numsectors);

	secboxes = secbox = (bbox_t *)SafeMalloc(numsectors*sizeof(bbox_t));
	for (i=0 ; i<numsectors ; i++, secbox++)
		ClearBBox (secbox);

/*
 calculate bounding boxes for all sectors
*/
	count = ldefstore_i->count;
	p = ldefstore_i->data;
	vt = mapvertexstore_i->data;
	printf("\n");
	for (i=0 ; i<count ; i++, p++)
		{
		printf("BBox #%d of %d\r",i,count);
		for (s=0 ; s<1 ; s++)
			{
			if (p->sidenum[s] == -1)
				continue;			/* no back side */
			/* add both points to sector bounding box */
			sd = (mapsidedef_t *)sdefstore_i->data + p->sidenum[s];
			sec = sd->sector;
			AddToBBox (&secboxes[sec], vt[p->v1].x, vt[p->v1].y);
			AddToBBox (&secboxes[sec], vt[p->v2].x, vt[p->v2].y);
			}
		}

/*
 make a list of only the solid lines
*/
	printf("\n");
	wl = linestore_i->data;
	for (i=0; i<wlcount; wl++,i++)
		{
		if (wl->flags & ML_TWOSIDED)
			continue;
		RonsLines++;
		}

	lines = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	lines->data = (bline_t *)SafeCalloc(RonsLines,sizeof(bline));
	lines->count = 0;
	lines->size = sizeof(bline);

	wl = linestore_i->data;
	for ( i=0 ; i<wlcount ; wl++,i++)
		{
		printf("Line #%d of %d\r",i,wlcount);
		if (wl->flags & ML_TWOSIDED)
			continue;			/* don't add two sided lines */
		bline.p1.x = wl->p1.x;
		bline.p1.y = wl->p1.y;
		bline.p2.x = wl->p2.x;
		bline.p2.y = wl->p2.y;
		memcpy((bline_t *)lines->data + lines->count, &bline, sizeof(bline));
		lines->count += 1;
		}

	blines = lines->data;
	numblines = lines->count;

/*
 build blocking chains
*/
  if (trace)
  	printf("\nBuildBlockingChains\n");
	BuildBlockingChains ();

/*
 build connection list
*/
  if (trace)
  	printf("\nBuildConnections\n");
	BuildConnections ();
}

/*
===============================================================================
=
=	OutputConnections
=
===============================================================================
*/
void OutputConnections(void)
{
	int		i;
	int		bytes;
	char	*cons;
	char	*bits;

	cons = connections;
	bytes = (numsectors*numsectors+7)/8;
	bits = (char *)SafeMalloc(bytes);

	for (i=0 ; i<bytes ; i++)
		{
		bits[i] = cons[0] + (cons[1]<<1) + (cons[2]<<2) + (cons[3]<<3) +
							(cons[4]<<4) + (cons[5]<<5) + (cons[6]<<6) + (cons[7]<<7);
		cons +=8;
		}

	addName("reject", bits, bytes);
	printf ("reject: %i\n",bytes);
}