/* saveconnect.m */

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

	used = alloca(numblines * sizeof(*used));
	memset(used, 0, numblines * sizeof(*used));
	temppoints = alloca(numblines * sizeof(*temppoints));
/*
   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;
}


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