#ifndef lint
static char sccsid[] = "%W% (mg@ukc) %G%";
#endif  lint
#include "colour.h"
#include <stdio.h>

#define min(x,y)	((x)>(y)?(y):(x))
#define Cell(x,y)	(cell[(x) + xdimtimes[y]])
int *	xdimtimes;

/* convert x,y,z coordinates to screen coords */
#define convx(x,y,z) (SCREENWIDTH/2 + (x) * SCREENDIST / (y))
#define convy(x,y,z) (SCREENHEIGHT/2 + (z) * SCREENDIST / (y))

#define SCREENHEIGHT	512
#define SCREENWIDTH	768
#define SCREENDIST	512

/* limits for the line clipper */
int minx = 1;
int miny = 1;
int maxx = SCREENWIDTH-2;
int maxy = SCREENHEIGHT-2;

#define NORTH	0
#define EAST	1
#define SOUTH	2
#define WEST	3

char *	word[]={ "north", "east", "south", "west" };

#define WALLWIDTH	512
#define WALLHEIGHT	384
#define WALLEDGECOLOUR	PINK
#define WALLFACECOLOUR	GREY
#define EMPTYCOLOUR	BLACK
#define FILLTOCOLOUR	WHITE
#define SKYCOLOUR	LT_BLUE
#define FLOORCOLOUR	GREEN

#define IDBITS	48
#define ID1	16
#define ID2	32
#define GOAL	64

#define LINES	WHITE
#define INSIDE	RED

char *cell;
char *alloc();
long random();

int xdim = 8;
int ydim = 8;
int mazesize;	/* == xdim * ydim */

int man_x, man_y, man_z, man_facing;

char face[] = { 1,  2,  4,  8,  1,  2,  4,  8 };
int    dx[] = { 0,  1,  0, -1,  0,  1,  0, -1 };
int    dy[] = { 1,  0, -1,  0,  1,  0, -1,  0 };
int max_forward [8];

char ch;

main(argc, argv)
char **argv;
{
	register int i,j;
	if (argc > 1) ydim = xdim = atoi(argv[1]);
	if (argc > 2) ydim = atoi(argv[2]);
	mazesize = xdim * ydim;
	cell = alloc(mazesize);
	xdimtimes = (int *) alloc( ydim * sizeof(int) );
	if ( cell == NULL || xdimtimes == NULL ) {
		fputs("maze: Out of memory.\n", stderr);
		exit(1);
	}
	for(i=j=0; i<ydim; i++) {
		xdimtimes[i] = j;
		j += xdim;
	}
	max_forward[0] = max_forward[4] = ydim-1;
	max_forward[1] = max_forward[5] = xdim-1;
	max_forward[3] = max_forward[6] = 0;
	max_forward[2] = max_forward[7] = 0;
	designmaze();
	init();
	set_up_problem();
	showplan();
	walkman();
	finish();
}

designmaze()
{
	register int x,y;
	register int move;
	register int connectedcells;
	register int newx, newy;

	bzero(cell, mazesize);

	srandom(getpid()+30000*getppid());
	cell[0] = ID1;
	cell[mazesize-1] = ID2;
	connectedcells = 2;
	while (connectedcells < mazesize/2) {
		for (x = xdim-1; x>=0; x--) {
			for (y = ydim-1; y>=0; y--) {
				if (Cell(x,y) != 0) {
					move = (int) random() & 3;
					if ( (newx = x + dx[move]) >= 0 && newx < xdim
					   &&(newy = y + dy[move]) >= 0 && newy < ydim
					   && Cell(newx,newy) == 0 ) {
						Cell(x,y) |= face[move];
						/* Cell(newx,newy) == 0 */
						Cell(newx,newy) = face[move^2] | (Cell(x,y) & IDBITS);
						connectedcells++;
	}	}	}	}	}
	while (connectedcells < mazesize) {
		for (x = xdim-1; x>=0; x--) {
			for (y = ydim-1; y>=0; y--) {
				if (Cell(x,y) == 0) {
					move = (int) random() & 3;
					if ( (newx = x + dx[move]) >= 0 && newx < xdim
					   &&(newy = y + dy[move]) >= 0 && newy < ydim
					   && Cell(newx,newy) != 0 ) {
						/* Cell(x,y) == 0 */
						Cell(x,y) = face[move] | ( Cell(newx,newy) & IDBITS );
						Cell(newx,newy) |= face[move^2];
						connectedcells++;
	}	}	}	}	}
	/* find two adjacent cells which belong to different halves */
	do {
		x = (abs((int) random()) % (xdim-2)) + 1;
		y = (abs((int) random()) % (ydim-2)) + 1;
		move = (int) random() & 3;
	} while ( ( Cell(x,y) & IDBITS ) == ( Cell( (newx = x+dx[move]), (newy = y+dy[move]) ) & IDBITS ) );
	/* and join them */
	Cell(x,y) |= face[move];
	Cell(newx,newy) |= face[move^2];
}

showplan()
{
	register int x, y;
	register int xscale, yscale;

	clear();
	colour(WHITE);
	xscale = (SCREENWIDTH-1) / xdim;
	yscale = (SCREENHEIGHT-1) / ydim;
	moveto(0,0); lineto(xscale * xdim,0);
	for (y=0; y<ydim; y++) {
		moveto(0,y*yscale); lineby(0,yscale);
		for (x=0; x<xdim; x++) {
			moveto ( x * xscale, (y+1) * yscale );
			if ( (Cell(x,y) & face[NORTH]) == 0 )
				lineby ( xscale, 0 );
			else	moveby ( xscale, 0 );
			if ( (Cell(x,y) & face[EAST]) == 0 )
				lineby ( 0, -yscale);
	}	}
	/*NOTREACHED*/
	update();
	message("You are at %d %d facing %s.", man_x+1, man_y+1, word[man_facing]);
}

set_up_problem()
{
	man_x = xdim/2;
	man_y = 0;
	man_z = 0;
	man_facing = (int) random() & 1; /* NORTH or EAST */
	man_facing = NORTH;
	cell[mazesize-1] |= GOAL;
}

showview()
{
	register int dist_ahead, dist_right;
	register int max_ahead, max_left, max_right;
	char curr_cell;

	max_ahead = max_forward[man_facing] - man_x * dx[man_facing] - man_y * dy[man_facing];
	max_left  = max_forward[man_facing+3] - man_x * dx[man_facing+3] - man_y * dy[man_facing+3];
	max_right = max_forward[man_facing+1] - man_x * dx[man_facing+1] - man_y * dy[man_facing+1];

	clear();
	colour(FILLTOCOLOUR);
	moveto(minx-1,miny-1); lineto(minx-1,maxy+1), lineto(maxx+1,maxy+1); lineto(maxx+1,miny-1);lineto(minx-1,miny-1);
	moveto(minx, (miny+maxy)/2); lineto(maxx, (miny+maxy)/2);
	colour(FLOORCOLOUR); moveto((minx+maxx)/2, miny); fill(FILLTOCOLOUR);
	colour(SKYCOLOUR); moveto((minx+maxx)/2, maxy); fill(FILLTOCOLOUR);
	moveto(minx, (miny+maxy)/2); lineto(maxx, (miny+maxy)/2);
	for (dist_ahead = max_ahead; dist_ahead >= 0; dist_ahead-- ) {
		for (dist_right = -min(max_left, dist_ahead+1); dist_right < 0; dist_right++) showcell(dist_ahead, dist_right);
		for (dist_right = min(max_right, dist_ahead+1); dist_right >= 0; dist_right--) showcell(dist_ahead, dist_right);
	}
}

showcell(dist_ahead, dist_right)
register int dist_ahead, dist_right;
{
	register int curr_x, curr_y;
	register char curr_cell;

	curr_x = man_x + dist_ahead * dx[man_facing] + dist_right * dx[man_facing+1];
	curr_y = man_y + dist_ahead * dy[man_facing] + dist_right * dy[man_facing+1];
	curr_cell = Cell(curr_x,curr_y);
	/* facing wall */
	if ((curr_cell & face[man_facing]) == 0)
		drawwall( dist_right*WALLWIDTH - WALLWIDTH/2, (dist_ahead+1)*WALLWIDTH,
			  dist_right*WALLWIDTH + WALLWIDTH/2, (dist_ahead+1)*WALLWIDTH );
	if ( abs(dist_right) <= dist_ahead) {
		/* left hand wall */
		if (dist_ahead == 0) {
			if ((curr_cell & face[man_facing+3]) == 0)
				drawwall( dist_right * WALLWIDTH - WALLWIDTH / 2, WALLWIDTH/2,
					  dist_right * WALLWIDTH - WALLWIDTH / 2, WALLWIDTH );
		} else {
			if ((dist_right <= 0) && ((curr_cell & face[man_facing+3]) == 0))
				drawwall( dist_right * WALLWIDTH - WALLWIDTH / 2, dist_ahead * WALLWIDTH,
					  dist_right * WALLWIDTH - WALLWIDTH / 2, (dist_ahead + 1) * WALLWIDTH );
		}
		/* right hand wall */
		if (dist_ahead == 0) {
			if ((curr_cell & face[man_facing+1]) == 0)
				drawwall( dist_right * WALLWIDTH + WALLWIDTH / 2, WALLWIDTH/2,
					  dist_right * WALLWIDTH + WALLWIDTH / 2, WALLWIDTH );
		} else {
			if ((dist_right >= 0) && ((curr_cell & face[man_facing+1]) == 0))
				drawwall( dist_right * WALLWIDTH + WALLWIDTH / 2, dist_ahead * WALLWIDTH,
					  dist_right * WALLWIDTH + WALLWIDTH / 2, (dist_ahead + 1) * WALLWIDTH );
		}
	}
	/* do special floor */
}

drawwall(x1, y1, x2, y2)
register int x1, x2, y1, y2;
{
	int bx1, tx1, by1, ty1;	/* bottom and top of pillars at (x1,y1) in screen coordinates */
	int bx2, tx2, by2, ty2;
	int fillx1, filly1;
	int fillx2, filly2;

	bx1 = convx(x1,y1,-man_z - WALLHEIGHT/2); bx2 = convx(x2,y2,-man_z - WALLHEIGHT/2);
	by1 = convy(x1,y1,-man_z - WALLHEIGHT/2); by2 = convy(x2,y2,-man_z - WALLHEIGHT/2);
	tx1 = convx(x1,y1,-man_z + WALLHEIGHT/2); tx2 = convx(x2,y2,-man_z + WALLHEIGHT/2);
	ty1 = convy(x1,y1,-man_z + WALLHEIGHT/2); ty2 = convy(x2,y2,-man_z + WALLHEIGHT/2);
	colour(FILLTOCOLOUR);
	moveto(bx1,by1); /* bottom left */
	clippedlineto(tx1,ty1); /* to top left */
	clippedlineto(tx2,ty2); /* to top right */
	clippedlineto(bx2,by2); /* to bottom right */
	clippedlineto(bx1,by1); /* to bottom left */

	/* Find a point to fill from by clipping the horizontal midline of the wall face */
	/* if some of this fell in the window, fill from one of the points */
	/* this does not cater for walls which overlap the bottom/top edges of the window */

	fillx1 = (bx1+tx1)/2; filly1 = (by1+ty1)/2;	/* centrepoint of left vertical */
	fillx2 = (bx2+tx2)/2; filly2 = (by2+ty2)/2;	/* centrepoint of right vertical */
	if (clip ( &fillx1, &filly1, &fillx2, &filly2 ) == 0 ) { /* if clip fails, whole midline is outside window */
		if (abs(fillx2-fillx1) > 1) {
			moveto ( (fillx1+fillx2)/2, (filly1+filly2)/2 );
			colour(EMPTYCOLOUR);
			fill(FILLTOCOLOUR);
			colour(WALLFACECOLOUR);
			fill(FILLTOCOLOUR);
		}
		colour(WALLEDGECOLOUR);
		moveto(bx1,by1); /* bottom left */
		clippedlineto(tx1,ty1); /* to top left */
		clippedlineto(tx2,ty2); /* to top right */
		clippedlineto(bx2,by2); /* to bottom right */
		clippedlineto(bx1,by1); /* to bottom left */
	}
}

moveto3D(x,y,z)
register int x,y,z;
{
	moveto( SCREENWIDTH/2 + x * SCREENDIST / y, SCREENHEIGHT/2 + z * SCREENDIST / y );
}

lineto3D(x,y,z)
register int x,y,z;
{
	clippedlineto( SCREENWIDTH/2 + x * SCREENDIST / y, SCREENHEIGHT/2 + z * SCREENDIST / y );
}

walkman()
{
	for(;;) {
		showview();
		update();
loop:		read(0,&ch,1);
		switch(ch) {
		case 'h':
			man_facing = (man_facing - 1) & 3;
			break;
		case 'l':
			man_facing = (man_facing + 1) & 3;
			break;
		case 'j':
			man_facing = man_facing ^ 2;
			break;
		case 'k':
			if (Cell(man_x,man_y) & face[man_facing]) {
				/* there is a gap ahead */
				man_x += dx[man_facing];
				man_y += dy[man_facing];
				if (Cell(man_x,man_y) & GOAL) {
					finish();
					exit(0);
				}
			} else {
				message("You just blundered into the wall.");
				goto loop;
			}
			break;
		case '\033': /* ESC */
			finish();
			exit(0);
			break;
		case 'u':
			man_z += 100;
			break;
		case 'd':
			man_z -= 100;
			break;
		case 'p':
			showplan();
			break;
		default:
			goto loop;
		}
	}
}