/*- level.c -----------------------------------------------------------------*

 Separated from bsp.c 2000/08/26 by Colin Phipps

 Node builder for DOOM levels (c) 1998 Colin Reed, version 3.0 (dos extended)

 Performance increased 200% over 1.2x

 Many thanks to Mark Harrison for finding a bug in 1.1 which caused some
 texture align problems when a flipped SEG was split.

 Credit to:-

 Raphael Quinet (A very small amount of code has been borrowed from DEU).

 Matt Fell for the doom specs.

 Lee Killough for performance tuning, support for multilevel wads, special
 effects, and wads with lumps besides levels.

 Also, the original idea for some of the techniques where also taken from the
 comment at the bottom of OBJECTS.C in DEU, and the doc by Matt Fell about
 the nodes.

 Use this code for your own editors, but please credit me.

*---------------------------------------------------------------------------*/
/*
 * Modified 2010/08/04 by Christopher Bazley
 */

#include "structs.h"
#include "bsp.h"

enum
{
  BUF_SIZE = 1024
};

/*- Global Vars ------------------------------------------------------------*/

struct Vertex  *vertices;
long            num_verts = 0;

struct LineDef *linedefs;
long            num_lines = 0;

struct SideDef *sidedefs;
long            num_sides = 0;

struct Sector  *sectors;
long            num_sects = 0;

struct SSector *ssectors;
long            num_ssectors = 0;

struct Pseg    *psegs = NULL;
long            num_psegs = 0;

static signed short num_pnodes = 0;
long                num_nodes = 0;

unsigned char  *SectorHits;

long            psx, psy, pex, pey, pdx, pdy;
long            lsx, lsy, lex, ley;

/*- Prototypes -------------------------------------------------------------*/

static void     GetVertexes(void);
static void     GetLinedefs(void);
static void     GetSidedefs(void);
static void     GetSectors(void);

static struct Seg *CreateSegs(void);

/*--------------------------------------------------------------------------*/
/* Find limits from a list of segs, does this by stepping through the segs */
/* and comparing the vertices at both ends. */
/*--------------------------------------------------------------------------*/

void FindLimits(struct Seg * ts, bbox_t box)
{
	int             minx = INT_MAX, miny = INT_MAX, maxx = INT_MIN,
	                maxy = INT_MIN;
	int             fv, tv;

	for (;;) {
		fv = ts->start;
		tv = ts->end;
		/* printf("%d : %d,%d\n",n,vertices[n].x,vertices[n].y); */
		if (vertices[fv].x < minx)
			minx = vertices[fv].x;
		if (vertices[fv].x > maxx)
			maxx = vertices[fv].x;
		if (vertices[fv].y < miny)
			miny = vertices[fv].y;
		if (vertices[fv].y > maxy)
			maxy = vertices[fv].y;
		if (vertices[tv].x < minx)
			minx = vertices[tv].x;
		if (vertices[tv].x > maxx)
			maxx = vertices[tv].x;
		if (vertices[tv].y < miny)
			miny = vertices[tv].y;
		if (vertices[tv].y > maxy)
			maxy = vertices[tv].y;
		if (ts->next == NULL)
			break;
		ts = ts->next;
	}
	/* cph - top, bottom, left, right */
	box[BB_TOP] = maxy; box[BB_BOTTOM] = miny;
	box[BB_LEFT] = minx; box[BB_RIGHT] = maxx;
}

/*--------------------------------------------------------------------------*/

static struct Seg *
add_seg(struct Seg * cs, int n, int fv, int tv,
	struct Seg ** fs, struct SideDef * sd)
{
	struct Seg     *ts = GetMemory(sizeof(struct Seg));	/* get mem for Seg */
	cs = cs ? (cs->next = ts) : (*fs = ts);
	cs->next = NULL;
	cs->start = fv;
	cs->end = tv;
	cs->pdx = (long) (cs->pex = vertices[tv].x)
		- (cs->psx = vertices[fv].x);
	cs->pdy = (long) (cs->pey = vertices[tv].y)
		- (cs->psy = vertices[fv].y);
	cs->ptmp = cs->pdx * cs->psy - cs->psx * cs->pdy;
	cs->len = (long) sqrt((double) cs->pdx * cs->pdx +
			      (double) cs->pdy * cs->pdy);

	if ((cs->sector = sd->sector) == -1)
		fprintf(stderr, "\nWarning: Bad sidedef in linedef %d (Z_CheckHeap error)\n", n);

	cs->angle = ComputeAngle(cs->pdx, cs->pdy);

	if (linedefs[n].tag == 999)
		cs->angle = (cs->angle + (unsigned) (sd->xoff * (65536.0 / 360.0))) & 65535u;

	cs->linedef = n;
	cs->dist = 0;
	return cs;
}

/*- initially creates all segs, one for each line def ----------------------*/

static struct Seg* CreateSegs(void)
{
	struct Seg     *cs = NULL;	/* current Seg */
	struct Seg     *fs = NULL;	/* first Seg in list */
	struct LineDef *l = linedefs;
	int             n;

	Verbose("Creating Segs... ");

	for (n = 0; n < num_lines; n++, l++) {	/* step through linedefs and
		 * get side *//* numbers */
                /* If line is 0 length, don't generate any segs */
                if (!memcmp(&vertices[l->start],&vertices[l->end],sizeof *vertices))
                  continue;
		if (l->sidedef1 != -1)
			(cs = add_seg(cs, n, l->start, l->end, &fs, sidedefs + l->sidedef1))->flip = 0;
		else
			fprintf(stderr,"\nWarning: Linedef %d has no right sidedef\n", n);

		if (l->sidedef2 != -1)
			(cs = add_seg(cs, n, l->end, l->start, &fs, sidedefs + l->sidedef2))->flip = 1;
		else if (l->flags & 4)
			fprintf(stderr,"\nWarning: Linedef %d is 2s but has no left sidedef\n", n);
	}
	Verbose("done.\n");
	return fs;
}

/*- read the vertices from the wad file and place in 'vertices' ------------
    Rewritten by Lee Killough, to speed up performance                       */

static void 
GetVertexes(void)
{
        long            n, used_verts;
	int            *translate;
	struct lumplist *l = FindDir("VERTEXES");
	struct Vertex   *vert, *vert_limit;

	if (!l || !(num_verts = l->dir.length / (sizeof(int16_t) * 2)))
		ProgError("Couldn't find any Vertices");

	vertices = GetMemory(num_verts * sizeof(*vertices));

	seek_lump(l);

	vert_limit = vertices + num_verts;
	for (vert = vertices; vert < vert_limit; vert++)
	{
		if (read_int16(&vert->x) || read_int16(&vert->y))
			read_error(l);
	}

	translate = GetMemory(num_verts * sizeof(*translate));

	for (n = 0; n < num_verts; n++)	/* Unmark all vertices */
		translate[n] = -1;

	for (n = 0; n < num_lines; n++) {	/* Mark all used vertices */
		int             s = linedefs[n].start;
		int             e = linedefs[n].end;
		if (s < 0 || s >= num_verts || e < 0 || e >= num_verts)
			ProgError("Linedef %ld has vertex out of range\n", n);
		translate[s] = translate[e] = 0;
	}
	used_verts = 0;
	for (n = 0; n < num_verts; n++)	/* Sift up all unused vertices */
		if (!translate[n])
			vertices[translate[n] = used_verts++] = vertices[n];

	for (n = 0; n < num_lines; n++) {	/* Renumber vertices */
		int             s = translate[linedefs[n].start];
		int             e = translate[linedefs[n].end];
		if (s < 0 || s >= used_verts || e < 0 || e >= used_verts)
			ProgError("Trouble in GetVertexes: Renumbering\n");
		linedefs[n].start = s;
		linedefs[n].end = e;
	}

	free(translate);

	Verbose("Loaded %ld vertices", num_verts);
	if (num_verts > used_verts)
		Verbose(", but %ld were unused\n(this is normal if the nodes were built before).\n",
		       num_verts - used_verts);
	else
		Verbose(".");
	num_verts = used_verts;
	if (!num_verts)
		ProgError("Couldn't find any used Vertices");
}

/*- write a vertices lump to the output wad file ---------------------------*/

static void PutVertexes(struct lumplist *lump)
{
	struct Vertex       *vertices = lump->data;
	const struct Vertex *vert, *vert_limit;

	vert_limit = vertices + num_verts;
	for (vert = vertices; vert < vert_limit; vert++)
	{
		if (write_int16(&vert->x) || write_int16(&vert->y))
		{
			write_error(lump);
		}
	}
}

/*- read a line definitions lump from the input wad file -------------------*/

static void 
GetLinedefs(void)
{
	struct lumplist *l = FindDir("LINEDEFS");
	struct LineDef  *line, *line_limit;

	if (!l || !(num_lines = l->dir.length / (sizeof(int16_t) * 7)))
		ProgError("Couldn't find any Linedefs");

	linedefs = GetMemory(num_lines * sizeof(*linedefs));

	seek_lump(l);

	line_limit = linedefs + num_lines;
	for (line = linedefs; line < line_limit; line++)
	{
		if (read_uint16(&line->start) ||
		    read_uint16(&line->end) ||
		    read_uint16(&line->flags) ||
		    read_uint16(&line->type) ||
		    read_uint16(&line->tag) ||
		    read_int16(&line->sidedef1) ||
		    read_int16(&line->sidedef2))
			read_error(l);
	}
}

/*- write a line definitions lump to the output wad file -------------------*/

static void PutLinedefs(struct lumplist *lump)
{
	struct LineDef       *linedefs = lump->data;
	const struct LineDef *line, *line_limit;

	line_limit = linedefs + num_lines;
	for (line = linedefs; line < line_limit; line++)
	{
		if (write_uint16(&line->start) ||
		    write_uint16(&line->end) ||
		    write_uint16(&line->flags) ||
		    write_uint16(&line->type) ||
		    write_uint16(&line->tag) ||
		    write_int16(&line->sidedef1) ||
		    write_int16(&line->sidedef2))
		{
			write_error(lump);
		}
	}
}

/*- read a side definitions lump from the input wad file -------------------*/

static void 
GetSidedefs(void)
{
	struct lumplist *l = FindDir("SIDEDEFS");
	struct SideDef  *side, *side_limit;

	if (!l || !(num_sides = l->dir.length / (sizeof(int16_t) * 3 + 24)))
		ProgError("Couldn't find any Sidedefs");

	sidedefs = GetMemory(num_sides * sizeof(*sidedefs));

	seek_lump(l);

	side_limit = sidedefs + num_sides;
	for (side = sidedefs; side < side_limit; side++)
	{
		if (read_int16(&side->xoff) || read_int16(&side->yoff) ||
		    read_chars(side->tex1,sizeof(side->tex1)) != sizeof(side->tex1) ||
		    read_chars(side->tex2,sizeof(side->tex2)) != sizeof(side->tex2) ||
		    read_chars(side->tex3,sizeof(side->tex3)) != sizeof(side->tex3) ||
		    read_int16(&side->sector))
			read_error(l);
	}
}

/*- read a sectors lump from the input wad file ----------------------------*/

static void 
GetSectors(void)
{
	struct lumplist *l = FindDir("SECTORS");
	struct Sector   *sect, *sect_limit;

	if (!l || !(num_sects = l->dir.length / (sizeof(int16_t) * 5 + 16)))
		ProgError("Couldn't find any Sectors");

	sectors = GetMemory(num_sects * sizeof(*sectors));

	seek_lump(l);

	sect_limit = sectors + num_sects;
	for (sect = sectors; sect < sect_limit; sect++)
	{
		if (read_int16(&sect->floorh) ||
		    read_int16(&sect->ceilh) ||
		    read_chars(sect->floort,sizeof(sect->floort)) != sizeof(sect->floort) ||
		    read_chars(sect->ceilt,sizeof(sect->ceilt)) != sizeof(sect->ceilt) ||
		    read_int16(&sect->light) ||
		    read_int16(&sect->special) ||
		    read_int16(&sect->tag))
			read_error(l);
	}
}

/*- write a segments lump to the output wad file ---------------------------*/

static void PutSegs(struct lumplist *lump)
{
	struct Pseg *psegs = lump->data;
	const struct Pseg *pseg, *pseg_limit;

	pseg_limit = psegs + num_psegs;
	for (pseg = psegs; pseg < pseg_limit; pseg++)
	{
		if (write_int16(&pseg->start) ||
		    write_int16(&pseg->end) ||
		    write_uint16(&pseg->angle) ||
		    write_int16(&pseg->linedef) ||
		    write_int16(&pseg->flip) ||
		    write_uint16(&pseg->dist))
		{
			write_error(lump);
		}
	}
}

/*- write a sub-sectors lump to the output wad file ------------------------*/

static void PutSSectors(struct lumplist *lump)
{
	struct SSector *ssectors = lump->data;
	const struct SSector *ssect, *ssect_limit;

	ssect_limit = ssectors + num_ssectors;
	for (ssect = ssectors; ssect < ssect_limit; ssect++)
	{
		if (write_uint16(&ssect->num) || write_uint16(&ssect->first))
		{
			write_error(lump);
		}
	}
}

/*- write a blank reject lump to the output wad file -----------------------*/

static void PutReject(struct lumplist *lump)
{
	char buffer[BUF_SIZE];
	size_t nwrote, rem;

	memset(buffer, '\0', sizeof(buffer));
	for (rem = (size_t)((num_sects * num_sects + 7) / 8); rem > 0; rem -= nwrote)
	{
		/* Write as much of the remaining data as will fit into the buffer */
		size_t nbytes = rem > sizeof(buffer) ? sizeof(buffer) : rem;
		nwrote = write_chars(buffer, nbytes);
		if (nwrote != nbytes)
		{
			write_error(lump);
		}
	}
}

/*--------------------------------------------------------------------------*/
/* Converts the nodes from a btree into the array format for inclusion in 
 * the .wad. Frees the btree as it goes */

static signed short ReverseNodes(struct lumplist *lump, struct Node * tn)
{
	unsigned int i;

	tn->chright = tn->nextr ? ReverseNodes(lump, tn->nextr) :
		tn->chright | 0x8000;

	tn->chleft = tn->nextl ? ReverseNodes(lump, tn->nextl) :
		tn->chleft | 0x8000;

	if (write_int16(&tn->x) || /* starting point*/
	    write_int16(&tn->y) ||
	    write_int16(&tn->dx) || /* offset to ending point*/
	    write_int16(&tn->dy))
	{
		write_error(lump);
	}

	/* bounding rectangle 1*/
	for (i = 0; i < NELEMS(tn->rightbox); i++)
	{
		if (write_int16(&tn->rightbox[i]))
			write_error(lump);
	}

	/* bounding rectangle 2*/
	for (i = 0; i < NELEMS(tn->leftbox); i++)
	{
		if (write_int16(&tn->leftbox[i]))
			write_error(lump);
	}

	/* Node or SSector (if high bit is set)*/
	if (write_int16(&tn->chright) ||
	    write_int16(&tn->chleft))
	{
		write_error(lump);
	}

	/* Free the node, it's written now */
	memset(tn,0,sizeof *tn);
	free(tn);
	return num_pnodes++;
}

/*- write a given node list to the wad file and destroy them ---------------*/

static void PutNodes(struct lumplist *lump)
{
	num_pnodes = 0;
	ReverseNodes(lump, lump->data);
}

/* Height of nodes */
static unsigned 
height(const struct Node * tn)
{
	if (tn) {
		unsigned        l = height(tn->nextl), r = height(tn->nextr);
		return l > r ? l + 1 : r + 1;
	}
	return 1;
}

/*
 * DoLevel -
 * 
 * Process a level, building NODES, etc
 */

void 
DoLevel(void)
{
	struct Seg     *tsegs;
	static struct Node *nodelist;
	static bbox_t mapbound;

	num_ssectors = 0;
	num_psegs = 0;
	num_nodes = 0;

	GetLinedefs();		/* Get and convert linedefs first */
	GetVertexes();		/* vertices here. */
	GetSidedefs();
	GetSectors();

	Fortify_CheckAllMemory();

	tsegs = CreateSegs();	/* Initially create segs */

	Fortify_CheckAllMemory();

	FindLimits(tsegs,mapbound);	/* Find limits of vertices */

	Verbose("Map goes from (%d,%d) to (%d,%d)\n", 
		mapbound[BB_TOP   ],mapbound[BB_LEFT  ],
		mapbound[BB_BOTTOM],mapbound[BB_RIGHT ]);

	SectorHits = GetMemory(num_sects);

	nodelist = CreateNode(tsegs,mapbound);	/* recursively create nodes */

	Fortify_CheckAllMemory();

	Verbose(
#ifdef NO_BACKSPACE
	        "\n"
#endif /* NO_BACKSPACE */
	        "%lu NODES created, with %lu SSECTORS.\n", num_nodes, num_ssectors);

	Verbose("Found %lu used vertices\n", num_verts);

	Verbose("Heights of left and right subtrees = (%u,%u)\n",
	       height(nodelist->nextl), height(nodelist->nextr));

	add_lump("SEGS", PutSegs, psegs);
	add_lump("SSECTORS", PutSSectors, ssectors);
	add_lump("VERTEXES", PutVertexes, vertices);
	add_lump("LINEDEFS", PutLinedefs, linedefs);

	/* Replace any existing REJECT lump unless -noreject was specified. */
	if (!noreject || !FindDir("REJECT"))
		add_lump("REJECT", PutReject, NULL);

	/* When called back later, CreateBlockmap needs 'vertices',
	   'linedefs' and 'mapbound' to still exist */
	add_lump("BLOCKMAP", CreateBlockmap, mapbound);

	/* When called back later, PutNodes frees 'nodelist' */
	add_lump("NODES", PutNodes, nodelist);

	/* Can use default copy-from-input action for sectors and
	   sidedefs because we never modify them */

	free(SectorHits);
}				/* if (lump->islevel) */

/*
 * LevelFinished -
 *
 * Free resources allocated to process a level
 */

void LevelFinished(void)
{
	free(sectors);
	free(sidedefs);
	free(vertices);
	free(linedefs);
	free(ssectors);
	free(psegs);
}

/*- end of file ------------------------------------------------------------*/
