/* $Id: mapgen.c,v 1.14 2008/06/20 22:10:36 minh Exp minh $ */

/*
 * Copyright (c) 2008 Nhat Minh Lê
 *
 * Permission to use, copy, modify, and/or distribute this software
 * for any purpose with or without fee is hereby granted, provided
 * that the above copyright notice and this permission notice appear
 * in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
 * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#if 1
#define W 10
#define H 6

#define XS 6
#define YS 4
#else
#define W 21
#define H 21

#define XS 11
#define YS 11
#endif

#define MW (W*(XS+1)+1)
#define MH (H*(YS+1)+1)

enum { WNONE = 1, WDOOR, WSOLID, NWTYPE };
enum { TSTART = 1, TEND };

struct cell {
	/* can be made unsigned char */
	int wall[4];	/* W,S,E,N */
	int type;
};

unsigned long seed;

static char map[MW][MH];
static struct cell cmap[W][H];

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) < (b) ? (b) : (a))

/* using the RNG provided by the C standard for the sake of having
   portable seeds that always generate the same map */
static int rnd(int n)
{
	seed = (seed * 1103515245UL + 12345UL) / 65536UL % 32768UL;
	return n == 0 ? 0 : seed % n;
}

static struct cell *neighbor(int x, int y, int i, int *qxptr, int *qyptr)
{
	struct cell *q;
	int qx, qy;

	switch (i) {
	case 0:	q = x == 0 ? NULL : &cmap[qx = x-1][qy = y]; break;
	case 1:	q = y == H-1 ? NULL : &cmap[qx = x][qy = y+1]; break;
	case 2:	q = x == W-1 ? NULL : &cmap[qx = x+1][qy = y]; break;
	case 3:	q = y == 0 ? NULL : &cmap[qx = x][qy = y-1];
	}

	if (q != NULL) {
		if (qxptr != NULL)
			*qxptr = qx;
		if (qyptr != NULL)
			*qyptr = qy;
	}
	return q;
}

static void setrwall(int x, int y, int ri, int n)
{
	int i;

	switch (ri) {
	case 0: i = 2; break;
	case 1: i = 3; break;
	case 2: i = 0; break;
	case 3: i = 1;
	}

	cmap[x][y].wall[i] = n;
}

static void dig(int x, int y)
{
	struct cell *p, *q;
	int i, qx, qy;
	int notend;

#if 0
	printf("%d %d\n", x, y);
#endif

	notend = 0;
	p = &cmap[x][y];
	while (p->wall[0] == 0 || p->wall[1] == 0 ||
	       p->wall[2] == 0 || p->wall[3] == 0) {
		while (p->wall[i = rnd(4)] != 0)
			continue;
		q = neighbor(x, y, i, &qx, &qy);
		if (q == NULL || q->wall[0] != 0 || q->wall[1] != 0 ||
		    q->wall[2] != 0 || q->wall[3] != 0) {
			p->wall[i] = WSOLID;
			if (q != NULL)
				setrwall(qx, qy, i, p->wall[i]);
		} else {
			p->wall[i] = rnd(WSOLID-1) + 1;
			setrwall(qx, qy, i, p->wall[i]);
			dig(qx, qy);
			notend = 1;
		}
	}
	if (!notend)
		p->type = TEND;
}

static void fillrect(int mx, int my, int mw, int mh, char c)
{
	int i, j, m, n;

	for (i = mx, m = mx+mw; i < m; ++i)
		for (j = my, n = my+mh; j < n; ++j)
			map[i][j] = c;
}

/* this function is called on each cell of the generation map from top
   to bottom and from left to right (column-first); this is important
   because we may perform fix up for the left and top edges whereas it
   is unecessary for the right and bottom edges */
static void draw(int x, int y)
{
	struct cell *p;
	int i, j, m, n, u, v;
	int mx, my;
	int xo, yo, w, h;

	p = &cmap[x][y];

	mx = x * (XS+1) + 1;
	my = y * (YS+1) + 1;

	w = rnd(XS) + 1;
	h = rnd(YS) + 1;
	xo = rnd(XS - w);
	yo = rnd(YS - h);

#if 0
	printf("%d %d : %d %d\n", x, y, mx+1, my+1);
	map[mx+1][my+1] = '.';
#endif

#if 0
	fillrect(mx, my, XS, YS, '/');
#endif
	fillrect(mx + xo, my + yo, w, h, ' ');
	switch (p->type) {
	case TSTART:	map[mx+xo][my+yo] = 'S'; break;
	case TEND:	map[mx+xo][my+yo] = 'E';
	}

#if 0
	map[mx][my] = x + '0';
	map[mx+1][my] = y + '0';
#endif

#if 0
	map[mx][my] = p->wall[0] == WSOLID ? '_' : 'W';
	map[mx+1][my] = p->wall[1] == WSOLID ? '_' : 'S';
	map[mx][my+1] = p->wall[2] == WSOLID ? '_' : 'E';
	map[mx+1][my+1] = p->wall[3] == WSOLID ? '_' : 'N';
#endif

	switch (p->wall[0]) {
	case WNONE:
		for (i = mx, n = i + xo; i < n; ++i)
			for (j = my + yo, m = j + h; j < m; ++j)
				map[i][j] = ' ';
		for (j = my, m = my + YS; j < m && map[mx-1][j] != ' '; ++j)
			continue;
		for (v = j; v < m && map[mx-1][v] == ' '; ++v)
			continue;
		for (j = MIN(my+yo, j), m = MAX(my+yo+h, v) - 1; j <= m; ++j)
			map[mx-1][j] = ' ';
		break;
	case WDOOR:
		v = my + yo + rnd(h);
		for (i = mx, n = i + xo; i < n; ++i)
			map[i][v] = ' ';
		for (j = my, m = my + YS; j < m && map[mx-1][j] != ' '; ++j)
			continue;
		if (j == v)
			map[mx-1][j] = 'D';
		else
			for (m = MAX(j, v), j = MIN(j, v); j <= m; ++j)
				map[mx-1][j] = ' ';
	}

	switch (p->wall[1]) {
	case WNONE:
		for (m = my + YS, j = m - YS + yo + h; j <= m; ++j)
			for (i = mx + xo, n = i + w; i < n; ++i)
				map[i][j] = ' ';
		break;
	case WDOOR:
		i = mx + xo + rnd(w);
		for (m = my + YS, j = m - YS + yo + h; j <= m; ++j)
			map[i][j] = ' ';
	}

	switch (p->wall[2]) {
	case WNONE:
		for (n = mx + XS, i = n - XS + xo + w; i <= n; ++i)
			for (j = my + yo, m = j + h; j < m; ++j)
				map[i][j] = ' ';
		break;
	case WDOOR:
		i = my + yo + rnd(h);
		for (m = mx + XS, j = m - XS + xo + w; j <= m; ++j)
			map[j][i] = ' ';
	}

	switch (p->wall[3]) {
	case WNONE:
		for (j = my, m = j + yo; j < m; ++j)
			for (i = mx + xo, n = i + w; i < n; ++i)
				map[i][j] = ' ';
		for (i = mx, n = mx + XS; i < n && map[i][my-1] != ' '; ++i)
			continue;
		for (u = i; u < n && map[u][my-1] == ' '; ++u)
			continue;
		for (i = MIN(mx+xo, i), n = MAX(mx+xo+w, u) - 1; i <= n; ++i)
			map[i][my-1] = ' ';
		break;
	case WDOOR:
		u = mx + xo + rnd(w);
		for (j = my, m = j + yo; j < m; ++j)
			map[u][j] = ' ';
		for (i = mx, n = mx + XS; i < n && map[i][my-1] != ' '; ++i)
			continue;
		if (i == u)
			map[i][my-1] = 'D';
		else
			for (n = MAX(i, u), i = MIN(i, u); i <= n; ++i)
				map[i][my-1] = ' ';
	}
}

static void display(void)
{
	int i, j;

	for (i = 0; i < W; ++i)
		for (j = 0; j < H; ++j)
			draw(i, j);

	for (i = 0; i < MH; ++i){
		for (j = 0; j < MW; ++j)
			putchar(map[j][i]);
		putchar('\n');
	}
}

int main(int argc, char *argv[])
{
	int i, j;

	seed = argc > 1 ? strtoul(argv[1], NULL, 0) : time(NULL);
	printf("seed: %lu\n", seed);

	for (i = 0; i < W; ++i)
		for (j = 0; j < H; ++j) {
			cmap[i][j].wall[0] = cmap[i][j].wall[1] =
			    cmap[i][j].wall[2] = cmap[i][j].wall[3] = 0;
			cmap[i][j].type = 0;
		}

	i = rnd(W), j = rnd(H);
	cmap[i][j].type = TSTART;
	dig(i, j);

	for (i = 0; i < MW; ++i)
		for (j = 0; j < MH; ++j)
			map[i][j] = '#';

	display();

	return 0;
}