/* maze.c : a simple maze drawing program */

/* RELEASED WITHOUT COPYRIGHT AND WITHOUT WARRANTY BY JONATHAN MAYO, 2002.
 * THIS SOURCE CODE IS PUBLIC DOMAIN. 
 */

/*
 * +-+---+---------+---------------------+---+-----------+---------+---------+
 * | |   |         |                     |   |           |         |         |
 * | | | | ------+ | --+---------------+ | | | +---+ ----+ | ----+ | +-----+ |
 * | | | |       |     |               | | |   |   |     | |     | | |     | |
 * | | | +---+---+-+-- | +-----+---+ | | | +---+ | +---+ | +-+-+ +-+ | +-- | |
 * |   | |   |     |   | |     |   | | | | |     |     | |   | |       |   | |
 * +---+ | | | +-+ | +-+ | +---+ | | | | | +-----+ | | | +-- | +-+-+---+---+ |
 * |   |   |   | | | |     |     | | | | |       | | | |         | |       | |
 * | | +---+---+ | | +-+ +-+ +---+ | | | +-----+ | | | +---+---+ | | --+-- | |
 * | | |       |   |   | |   |   | | | |       | | | |     |   |   |   |   | |
 *   | | --+-+ | +-+-+ +-+ +-+ --+ +-+ | ------+ | | +-----+ | +---+-+ | +-+  
 * | | |   | |   |   |   | |           |         | | |     | | |     | | |   |
 * | | +-+ | +---+ | +-- | | ------+---+ --------+-+ | +-+ | | | +-+ | | | | |
 * | |   |   |     | |     |       |   |             | | |   |   | | | | | | |
 * | +-+ +-+ | +---+ | +---+ +-----+ | +-- +---+ +---+ | +---+---+ | | | +-+ |
 * | | |   |   |     | |   | |       | |   |   | |     | |         |   | |   |
 * | | | +-+---+ ----+ | | | | --+---+ +---+ | | | +-+-+ | +-----+ +---+ | --+
 * | | | |     |     | | | | |   |     |   | | | | | |     |     |       |   |
 * | | | | --+ +---- +-+ | +-+-- | ----+ | | | +-+ | | ----+---- +-------+-- |
 * |   |     |           |       |       |   |     |                         |
 * +---+-----+-----------+-------+-------+---+-----+-------------------------+
 *
 *
 * usage:
 *      ./maze 75x20
 * 
 * produces a maze 75 x 20. rounds numbers up to the next odd number. (mazes
 * have to be an odd dimention to make room for the path walls)
 */

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

/* use getpid() if we have it */
#ifdef __unix
# include <unistd.h>
#else
# define	getpid()		0
#endif

/* make the inline macro if we have it */
#if __STDC_VERSION__ > 199901L /* any C99 or better compiler */
/* inline is fine in C99, we do nothing */
#elif __GNUC__ /* older GCC or -ansi */
# define	inline			__inline__
#else	/* old ANSI C89 or worse */
# define	inline			/* */
#endif


#define		CELL_WALL		'O'
#define		CELL_FLOOR		' '

struct maze
{
	unsigned w;
	unsigned h;
	unsigned char *m;
};

inline static unsigned char *mazeAddr(struct maze *maze, int x, int y)
{
	return &maze->m[maze->w*y+x];
}

void mazeInit(struct maze *maze, int w, int h)
{
	int i;
	maze->w=(w|1)+2;
	maze->h=(h|1)+2;
	maze->m=malloc(maze->w * maze->h *sizeof *maze->m);
	for(i=0;i<maze->h*maze->w;i++) {
		maze->m[i]=CELL_WALL;
	}
	for(i=0;i<maze->w;i++) {
		*mazeAddr(maze,i,0)=CELL_FLOOR;
		*mazeAddr(maze,i,maze->h-1)=CELL_FLOOR;
	}
	for(i=1;i<maze->h-1;i++) {
		*mazeAddr(maze,0,i)=CELL_FLOOR;
		*mazeAddr(maze,maze->w-1,i)=CELL_FLOOR;
	}
}

static void mazeDraw(struct maze *maze, int x, int y, int xdir, int ydir)
{
	*mazeAddr(maze,x,y)=CELL_FLOOR;
	x+=xdir;
	y+=ydir;
	*mazeAddr(maze,x,y)=CELL_FLOOR;
	x+=xdir;
	y+=ydir;
	*mazeAddr(maze,x,y)=CELL_FLOOR;
}

static void mazeNextPt(struct maze *maze, int *xdir, int *ydir)
{
	int v;
	v= (*xdir ? (*xdir)+2 : (*ydir)+3)%4;
	*xdir= v%2 ? 0 : 1-v;
	*ydir= v%2 ? 2-v : 0;
}

static void mazeRandPt(struct maze *maze, int *xdir, int *ydir)
{
	int v=rand()%4;	
	*xdir= v%2 ? 0 : 1-v;
	*ydir= v%2 ? 2-v : 0;
}

static int mazeTestPt(struct maze *maze, int x, int y)
{
	return *mazeAddr(maze,x,y)==CELL_WALL;
}

static void mazeFillR(struct maze *maze, int x, int y, int xdir, int ydir)
{
	int i;
	mazeRandPt(maze,&xdir,&ydir);
	for(i=0;i<4;i++) {
		int tx, ty;
		tx=x+xdir*2;
		ty=y+ydir*2;
		if(tx>0 && tx<maze->w-1 && ty>0 && ty<maze->h-1) {
			if(mazeTestPt(maze,tx,ty)) {
				mazeDraw(maze,x,y,xdir,ydir);	
				mazeFillR(maze,tx,ty,xdir,ydir);	
			}
		}
		mazeNextPt(maze,&xdir,&ydir);
	}
}

void mazeFill(struct maze *maze)
{
	*mazeAddr(maze,2,2)=CELL_FLOOR;
	mazeFillR(maze,2,2,+1,0);
}

void mazeExit(struct maze *maze)
{
	mazeDraw(maze,0,maze->h/2,1,0);	
	mazeDraw(maze,maze->w-1,maze->h/2,-1,0);	
}

void mazeFilter(struct maze *maze)
{
	int x;
	int y;
	for(y=1;y<maze->h-1;y++) {
		for(x=1;x<maze->w-1;x++) {
			unsigned char *cell;

			cell=mazeAddr(maze,x,y);
			if(*cell!=CELL_FLOOR) {
				const char tab[16] = "+|||-+++-+++-+++";
									/*aaaaaaaaAAAAAAAA        c
									 *bbbbBBBBbbbbBBBB      a + b
									 *ccCCccCCccCCccCC        d
									 *dDdDdDdDdDdDdDdD
									 */
				unsigned a;
				a=	(*mazeAddr(maze,x-1,y)!=CELL_FLOOR)<<3 |
					(*mazeAddr(maze,x+1,y)!=CELL_FLOOR)<<2 |
					(*mazeAddr(maze,x,y-1)!=CELL_FLOOR)<<1 |
					(*mazeAddr(maze,x,y+1)!=CELL_FLOOR);
				*cell=tab[a];	
			}	
		}
	}
}

void mazeShow(struct maze *maze)
{
	int y;
	for(y=1;y<maze->h-1;y++) {
		printf("%.*s\n",(int)maze->w-2,mazeAddr(maze,1,y));
	}
}

void mazeFree(struct maze *maze)
{
	free(maze->m);
}

void mazeGo(int w, int h)
{
	struct maze maze;
	mazeInit(&maze,w,h);	/* initialize the maze */
	mazeFill(&maze);		/* draw the actual maze */
	mazeExit(&maze);		/* place exits */
	mazeFilter(&maze);		/* filter the maze to have +|- instead of O */
	mazeShow(&maze);		/* show the maze to stdout */
	mazeFree(&maze);		/* release the maze data */
}

int main(int argc, char **argv)
{
	int argi;
	srand( time(NULL)+getpid());

	if(argc==1) 
		mazeGo(79,20);
	for(argi=1;argi<argc;argi++) {	
		int w;
		int h;
		char *endptr;
		char *endptr2;
		w=strtol(argv[argi],&endptr,10);
		if(!endptr)
			continue;
		h=strtol(endptr+1,&endptr2,10);
		if(!endptr2)
			continue;
	}
	return 0;
}