From: bre@os.is (Bjarni R. Einarsson)
Newsgroups: alt.sources,comp.lang.c
Subject: MAZE GENERATOR
Keywords: Maze,source
Date: 23 Jul 92 11:27:14 GMT
Followup-To: alt.sources
Organization: Orkustofnun


Hi!  I have seen quite a few requests for random MAZE ganerators,
and i thought it might be an interestin challenge to write one.
Another reason I wrote it is that I could not get this to work:

char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);
--            E;             J[              E]             =T
[E   ]=  E)   printf("._");  for(;(A-=Z=!Z)  ||  (printf("\n|"
)    ,   A    =              39              ,C             --
)    ;   Z    ||    printf   (M   ))M[Z]=Z[A-(E   =A[J-Z])&&!C
&    A   ==             T[                                  A]     
|6<<27<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];}

For some reason all this does on my computer is print a pattern 
like this:
 
._._._._._.
| | | | | |
| | | | | |
|_._._._._|   Which isn't much of a maze to me..
              Anyway, I am getting a bit sidetracked.
Here is my maze program, it can make a random maze up to 100x100 characters
in size and it always POSSIBLE, but often hard to finish.  I am not pleased 
with everything, feel free to modify and replace whatever needs it.

If anybody loves it to pieces mail would be welcome.. Also I would kinda like
to keep copies of any major changes to the code.
  ______________________________________________   ___________________
 /                                              \ /                   \
( "Shee, you guys are so unhip its a wonder your O Bjarni R. Einarsson )
(  bums don't fall off!" -- Zaphod Beeblebrox    O  - - bre@os.is - -  )
 \______________________________________________/ \___________________/

Here it comes:
---- cut here and so on -----
/*
           Random Maze Generator
                   -- Bjarni R. Einarsson  BRE@OS.IS

Basic idea:

MAIN
{
   Setup;
   makeMaze(BEGX,BEGY,int) {
      push ;
      while (STACK IS NOT EMPTY) {
         while (CAN NOT WALK) { Random_pop } ;
         SelectDirection ;
         DrawCorridor { drawToArray, push } ;
     }
   }
   DrawMaze ;
}
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define bpush(n) if (stackp < 6000) stack[stackp++] = n 
#define bpop     (stackp ? stack[--stackp] : -1)

int mz[100][100] ;
int stack[6000],stackp = 0 ;
int xs,ys ;

int brand(int m)
{
	return (rand()%m);
}
int OKspot(int x, int y, int col)
{
	int i = 0 ;
	if ((x > xs) || (x < 0) || (y < 0) || (y > ys))	return 6 ;
	if (mz[x+1][y] > 15) i++ ; 
	if (mz[x-1][y] > 15) i++ ; 
	if (mz[x][y+1] > 15) i++ ; 
	if (mz[x][y-1] > 15) i++ ; 
	return i ;
}
int OKdirs(int x, int y, int col)
{
	int i = 4;
	if ((x <= 0 ) || (OKspot(x-1,y,col) > 1)) --i ;
	if ((y <= 0 ) || (OKspot(x,y-1,col) > 1)) --i ;
	if ((x >= xs) || (OKspot(x+1,y,col) > 1)) --i ;
	if ((y >= ys) || (OKspot(x,y+1,col) > 1)) --i ;
	return i ;
}
void getRandom(int *x, int *y)
{
	int i ;
	i = brand(stackp/2) ;
	*y = stack[i*2] ;
	*x = stack[i*2+1] ;
	stack[i*2]   = stack[stackp-2] ; 
	stack[i*2+1] = stack[stackp-1] ;
	stackp -= 2 ; 
}
void MAKEMAZE(int begx, int begy, int col)
{
	int x,y,xx,yy,i,j ;
	x = begx ;
	y = begy ;
	bpush(y) ;
	bpush(x) ;
	mz[x][y] = col ;
	while  (1) {
		if ((!OKdirs(x,y,col)) || (brand(100) == 1)) {
				while (!OKdirs(x,y,col-1)) {
				if (!stackp) return ;
				getRandom(&x,&y) ;
			}
			col++ ;
		}
		yy = 0 ;
		xx = 0 ;
		while (xx+yy == 0) {
			xx = brand(3)-1 ;
			if (!xx) yy = brand(3)-1 ;
		}
		j = brand(3)+1 ;
		while ((j-- > 0) && (OKspot(x+xx,y+yy,col) <= 1 )) {
			x += xx ;
			y += yy ; 
			mz[x][y] = col ;
			bpush(y) ;
			bpush(x) ;
		}
	}
}
void SETUP()
{
	int i,j ;
	srand(time(NULL)) ;
	for (i = 0; i < 100; i++)
		for (j = 0; j < 100; j++) mz[i][j] = 0 ;
}
void DRAWMAZE()
{
	int i,j ;
	for (i = 0; i < xs+3; i++) printf("#") ;
	printf("\n") ;
	for (i = 0; i <= ys; i++) {
		printf((i != 0) ? "#" : "|") ;
		for (j = 0; j <= xs; j++)
			printf(mz[j][i] ? " " : "#") ;
		printf((i != ys) ? "#" : "|") ;
		printf("\n") ;
	}
	for (i = 0; i < xs+3; i++) printf("#") ;
	printf("\n") ;
}

void main(int ac, char *args[])
{
	xs = 75 ;
	ys = 20 ;
	if (ac > 1) xs = atoi(args[1]) ;
	if (ac > 2) ys = atoi(args[2]) ;
	if (xs > 99) xs = 99 ;
	if (xs < 10) xs = 10 ;
	if (ys > 99) ys = 99 ;
	if (ys < 6) ys = 6 ;
	SETUP() ;
	MAKEMAZE(0,0,16) ;
	mz[0][0] = mz[xs][ys] = 16 ;
	DRAWMAZE() ;
}

/*
There are some unused variables, but they do not matter and do
not get in the way, so I didn't remove them.

Does anyone have a better maze generator I can look at?
*/