/* maze.c
   Generates Perfect 2D Mazes 
   Written by Ben Lamb - February 1999
*/ 

#include <stdio.h>

/* Global variables - why not */
int isValid(int s);
int vertAbove(int s);
int vertBelow(int s);
int horzLeft(int s);
int horzRight(int s);

int a[7000];
int n, t, x, y;

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

	int s, z, srnd = 123;
	x = 39;   /* Adjust the size of your maze here */ 
	y = 24; 
	t = 2*x*y+x+y;

  if (argc > 1)  srnd = atoi(argv[1]);
  srand(srnd); 
	/* initialise maze */
	for(n=0; n<t; n++)
		a[n] = 0;

	/* generate outer wall */
	for(n=0; n < x; n++)
		a[n] = 1;
	for(n=0; n < x; n++)
		a[t-n-1] = 1;
	for(n=x; n < t; n+=(2*x+1))
		a[n] = 1;
	for(n=2*x; n < t; n+=(2*x+1))
		a[n] = 1;

	/* generate the maze itself 
	   choose walls at random but obey two rules:
		one end of the wall must touch an existing wall
		the other end must not touch anything
	*/
	for(n=0; n < 200000; n++) {
		s = rand()%t;
		if(a[s] == 0)
			if(isValid(s))
				a[s] = 1;
	}

	/* output maze */
	for(n=0; n < x; n++)
		if(a[n]) { printf("._"); } else { printf("  "); }
	printf("\n");

	for(z=1; z < y+1; z++) {
		for(n=0; n < x; n++) {
			if(a[z*(2*x+1)+n-(x+1)]) { printf("|"); } else { printf("."); }
			if(a[(2*x+1)*z+n]) { printf("_"); } else { printf(" "); }
		}
		if(a[z*(2*x+1)-1]) { printf("|"); }
		printf("\n");
	}
	printf("\n");
}

int isValid(int s) {
	/* horizontal or vertical segment? */
	if((s%(2*x+1))>(x-1)) {
		/* vertical seg */
		if(vertAbove(s) == 1 && vertBelow(s) == 0 || vertAbove(s) == 0 && vertBelow(s) == 1)
			return 1;
	} else {
                /* horizontal seg */
		if(horzLeft(s) == 1 && horzRight(s) == 0 || horzLeft(s) == 0 && horzRight(s) == 1)
                        return 1;
	}
	return 0;
}

int vertAbove(s) {
	int c = 0;
	if(s%(2*x+1) != 2*x && a[s-x] == 1) c++; // right side
	if(s%(2*x+1) != x && a[s-x-1] == 1) c++; // left side
	if(s > 2*x && a[s-2*x-1] == 1) c++; // above
	if(c > 0) { return 1; } else { return 0; }
}

int vertBelow(s) {
	int c = 0;
        if(s%(2*x+1) != 2*x && a[s+x] == 1) c++;
        if(s%(2*x+1) != x && a[s+x+1] == 1) c++;
	if(s < (t-2*x-1) && a[s+2*x+1] == 1) c++;
	if(c > 0) { return 1; } else { return 0; }
}

int horzLeft(s) {
	int c = 0;
	if(s>0 && a[s-1] == 1) c++;
	if(a[s-x-1] == 1) c++;
	if(a[s+x] == 1) c++;
	if(c > 0) { return 1; } else { return 0; }
}

int horzRight(s) {
	int c = 0;
        if(s < t && a[s+1] == 1) c++;
        if(a[s+x+1] == 1) c++;
        if(a[s-x] == 1) c++;
	if(c > 0) { return 1; } else { return 0; }
}