/* saveconnect.m */

#ifdef _STEVE_FIX_
#include <malloc.h>
#endif

#include "idbsp.h"

typedef struct
{
	int		x,y;
} bpoint_t;

typedef struct
{
	int		xl, xh, yl, yh;
} bbox_t;

typedef struct
{
	bpoint_t	p1, p2;
} bline_t;

typedef struct
{
	int			numpoints;
	bbox_t		bounds;
	bpoint_t	*points;
} bchain_t;

typedef struct
{
	int		x,y;
	int		dx,dy;
} bdivline_t;


/* [numsec][numsec] array */
byte		*connections;

int			numblines;
bline_t	*blines;

int			numsectors;
bbox_t		*secboxes;

int			numbchains;
bchain_t	*bchains;

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

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 */
}


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 ();
*/
}

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

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 ();
*/
}


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


/*
====================
=
= 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 0
if (p>0)
{
	PSmoveto ((pt-1)->x, (pt-1)->y);
	PSlineto (pt->x,pt->y);
	PSstroke ();
	NXPing ();
}
#endif

		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
=
====================
*/

enum {si_north, si_east, si_south, si_west};

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 (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 (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;
/*
				if (draw)
				{
				EraseWindow ();
				DrawBBox (bbox[0]);
				DrawBBox (bbox[1]);
				DrawDivline (&ends[0]);
				DrawDivline (&ends[1]);
				DrawDivline (&sides[0]);
				DrawDivline (&sides[1]);
				DrawBChain (&bchains[k]);
				}
*/
				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;
/*	id			chains_i; */
	STORAGE *chains_i;
	bchain_t	bch;
	int			cx, cy;

#ifdef _STEVE_FIX_
  used = malloc (numblines*sizeof (*used));
	memset (used,0,numblines*sizeof (*used));
	temppoints = malloc (numblines*sizeof (*temppoints));
#else
  used = alloca (numblines*sizeof (*used));
	memset (used,0,numblines*sizeof (*used));
	temppoints = alloca (numblines*sizeof (*temppoints));
#endif

/*
	chains_i = [[Storage alloc]
					initCount:		0
					elementSize:	sizeof(bchain_t)
					description:	NULL];
*/
	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 *)malloc (bch.numpoints*sizeof(*bch.points));
		memcpy (bch.points, temppoints, bch.numpoints*sizeof(*bch.points));
/*		[chains_i addElement: &bch]; */
		memcpy((bchain_t *)chains_i->data + chains_i->count, &bch, sizeof(bchain_t));
		chains_i->count += 1;
		chains_i->data = (bchain_t *)realloc(chains_i->data,
											sizeof(bchain_t) * (chains_i->count + 1));
/*DrawBChain (&bch); */
	}

/*
	numbchains = [chains_i count];
	bchains = [chains_i elementAt:0];
*/
	numbchains = chains_i->count;
	bchains = chains_i->data;

#ifdef _STEVE_FIX_
  free(used);
  free(temppoints);
#endif
}


/*
====================
=
= ProcessConnections
=
====================
*/

void ProcessConnections (void)
{
	int					i, s, wlcount, count;
	bbox_t				*secbox;
/*	id					lines; */
	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];
	wlcount = [linestore_i count];
*/

	numsectors = secstore_i->count;
	wlcount = linestore_i->count;

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

	secboxes = secbox = (bbox_t *)malloc (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 elementAt:0];
	vt = [mapvertexstore_i elementAt:0];
*/

	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 elementAt: p->sidenum[s]]; */
			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
*/
/*
	lines = [[Storage alloc]
					initCount:		0
					elementSize:	sizeof(bline)
					description:	NULL];
*/
/*
	lines = SafeMalloc(sizeof(STORAGE));
	lines->data = SafeMalloc(sizeof(bline));
	lines->count = 0;
	lines->size = sizeof(bline);
*/

/*	wl = [linestore_i elementAt: 0]; */
	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;
/*		[lines addElement: &bline]; */
		memcpy((bline_t *)lines->data + lines->count, &bline, sizeof(bline));
		lines->count += 1;
/*
		lines->data = (bline_t *)realloc(lines->data,
									sizeof(bline_t) + (lines->count + 1));
*/
	}

/*
	blines = [lines elementAt: 0];
	numblines = [lines count];
*/

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

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

/*
 build connection list
*/
	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 *)malloc(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;
	}

/*	[wad_i addName: "reject" data:bits size:bytes]; */
	addName("reject", bits, bytes);
	printf ("reject: %i\n",bytes);
}