/* evolve a maze level */

#include <u.h>
#include <libc.h>
#include <draw.h>

/* Maze states */
enum {
	U 		= 1,
	R 		= 1<<1,
	B		= 1<<2,
	L		= 1<<3,
	E 		= 1<<4,
	T 		= 1<<5,
	M 		= 1<<6,
};


enum {
	MX = 6,
	MY = 6,
};

typedef struct {
	Point 		t;	/* theseus */
	Point 		m;	/* minotaur */
	Point		e;	/* exit */
	uint 		b[MX][MY];
	uint 		i;
	uint		s;	/* score */
} Level;

Level l;


uint maxmoves = 30;
char moves[1024];

void
start(void)
{
	l.s = 0;
	l.e = Pt(0, 0);
	/* choose which side the exit is on, clockwise rotation */
	switch(nrand(4)) {
	case 0:	/* top */
		l.e = Pt(nrand(MX), 0);
		break;
	case 1:	/* right */
		l.e = Pt(MX-1, nrand(MY));
		break;
	case 2: /* bottom */
		l.e = Pt(nrand(MX), MY-1);
		break;
	case 3: /* left */
		l.e = Pt(0, nrand(MY));
		break;
	}

	/* find a place for theseus, not on the exit, please */
	l.t = Pt(nrand(MX), nrand(MY));
	while(eqpt(l.t, l.e))
		l.t = Pt(nrand(MX), nrand(MY));

	/* the minotaur should not share the same initial square as theseus */
	l.m = Pt(nrand(MX), nrand(MY));
	while(eqpt(l.t, l.m))
		l.m = Pt(nrand(MX), nrand(MY));
}

void
addwall(Point p)
{
	if((l.b[p.x][p.y] & (0xF)) == 0xF)
		return;

	switch(nrand(4)) {
	case 0: /* top */
		l.b[p.x][p.y] |= U;
		if(p.y != 0)
			l.b[p.x][p.y-1] |= B;
		break;
	case 1:
		l.b[p.x][p.y] |= R; 
		if(p.x != MX-1)
			l.b[p.x+1][p.y] |= L;
		break;
	case 2:
		l.b[p.x][p.y] |= B; 
		if(p.y != MY-1)
			l.b[p.x][p.y+1] |= U;
		break;
	case 3:
		l.b[p.x][p.y] |= L; 
		if(p.x != 0)
			l.b[p.x-1][p.y] |= R;
		break;
	}
}

void
remwall(Point p)
{
	int i;

	if(l.b[p.x][p.y] == 0)
		return;

	do {
		i = nrand(4);
	} while(l.b[p.x][p.y] & (1<<i));

	switch(i) {
	case 0: /* top */
		l.b[p.x][p.y] &= ~U;
		if(p.y != 0)
			l.b[p.x][p.y-1] &= ~B;
		break;
	case 1:
		l.b[p.x][p.y] &= ~R; 
		if(p.x != MX-1)
			l.b[p.x+1][p.y] &= ~L;
		break;
	case 2:
		l.b[p.x][p.y] &= ~B; 
		if(p.y != MY-1)
			l.b[p.x][p.y+1] &= ~U;
		break;
	case 3:
		l.b[p.x][p.y] &= ~L; 
		if(p.x != 0)
			l.b[p.x-1][p.y] &= ~R;
		break;
	}
}

/* 
 * randomly decide to create or remove a wall 
 */
void
evolve(void)
{
	int i;
	Point p;


	/* choose a square to modify */
	p = Pt(nrand(MX), nrand(MY));

	if((l.b[p.x][p.y] & (0xF)) == 0) {
		addwall(p);
	} else if((l.b[p.x][p.y] & (0xF)) == 0xF) {
		remwall(p);
	} else {
		if(nrand(2)) {
			remwall(p);
		} else {
			addwall(p);
		}
	}

	/* clean up any erroneous walls */
	for(i = 0; i < MX; i++) {
		l.b[i][0] 		&= ~U;
		l.b[i][MY-1] 	&= ~B;
		l.b[0][i] 		&= ~L;
		l.b[MX-1][i]	&= ~R;
	}

	if((l.b[p.x][p.y] & (0xF)) == 0xF)
		remwall(p);
}

void
movem(Level *lvl)
{
	Point m, t, o;
	int moves = 0;

	m = lvl->m;
	t = lvl->t;

	while(moves < 2) {
		o = m;

		/* first move horizontally, then vertically */
		if((t.x > m.x) && !(lvl->b[m.x][m.y] & R))
			m.x++; 
		else if((t.x < m.x) && !(lvl->b[m.x][m.y] & L))
			m.x--;
		else if((t.y > m.y) && !(lvl->b[m.x][m.y] & B))
			m.y++;
		else if((t.y < m.y) && !(lvl->b[m.x][m.y] & U))
			m.y--;

		moves++;
		lvl->m = m;

		if(eqpt(m, o)) {
			return;
		}

		if(eqpt(m, t))
			break;
	}
}

int
solve(Level lvl) 
{
	Level m;

	if(lvl.s > maxmoves)
		return 0;

	movem(&lvl);
	if(eqpt(lvl.t, lvl.m))
		return 0;

	if(eqpt(lvl.t, lvl.e)) {
		l.s = lvl.s;
		return 1;
	}

	m = lvl;
	m.s++;

	if((m.t.y != 0) && !(m.b[m.t.x][m.t.y] & U)) {
		m.t.y--;
		moves[m.s] = 'U';
		if(solve(m))
			return 1;
	}
	if((m.t.x != MX-1) && !(m.b[m.t.x][m.t.y] & R)) {
		m.t.x++;
		moves[m.s] = 'R';
		if(solve(m))
			return 1;
	}
	if((m.t.y != MY-1) && !(m.b[m.t.x][m.t.y] & B)) {
		m.t.y++;
		moves[m.s] = 'B';
		if(solve(m))
			return 1;
	}
	if((m.t.x != 0) && !(m.b[m.t.x][m.t.y] & L)) {
		m.t.x--;
		moves[m.s] = 'L';
		if(solve(m))
			return 1;
	}

	return 0;
}

void 
printout(void)
{
	int x, y;
	uint b;

	print("/* score: %ud */\n", l.s);
	print("/* solution: ");
	for(x = 0; x <= l.s; x++) 
		print("%c", moves[x]);
	print(" */\n");

	print("{\n");
	for(y = 0; y < MY; y++) {
		print("\t");
		for(x = 0; x < MX; x++) {
			b = l.b[x][y];
			print("0");
			if(eqpt(l.e, Pt(x, y)))
				print("+E");
			if(eqpt(l.m, Pt(x, y)))
				print("+M");
			if(eqpt(l.t, Pt(x, y)))
				print("+T");

			if(b & U)
				print("+U");
			if(b & R)
				print("+R");
			if(b & L)
				print("+L");
			if(b & B)
				print("+B");
			print(",\t\t");
		}
		print("\n");
	}
	print("},\n");
}

void
main(int argc, char *argv[])
{
	int tries = 1000;

	if(argc == 2)
		maxmoves = (uint)atoi(argv[1]);
	else if(argc > 2) {
		print("usage: %s [maxmoves] -- default is %d\n", argv[0], maxmoves);
		exits("usage");
	}
	if(maxmoves > 1024)
		maxmoves = 1024;

	srand(time(0));

	start();

	while(tries--) {
		evolve();
		if(solve(l)) {
			printout();
			tries = 1000;
		}
		start();
	}
}