random maze generator
leipold
leipold at eplrx7.UUCP
Fri Sep 8 04:46:18 AEST 1989
smarison writes:
> Does anyone have any good random maze generators written in C? I'm
> writing a program and need to generate a random maze but I have no
> idea how to do it.
The following code generates a spanning tree maze, which by definition
has only one solution. It cops out and uses a simple 'printer-plot'
output format -- the original I wrote for the Macintosh included
Mac graphics and a little 'snake' which crawled through the maze to
solve it...
--Walt L.
---------------
#include <math.h>
#include <stdio.h>
#include <strings.h>
#define MAXROW 12
#define MAXCOL 18
#define WALLUP 1
#define WALLDOWN 0
#define min(a,b) (a)<=(b) ? (a) : (b)
#define max(a,b) (a)>=(b) ? (a) : (b)
int right[MAXCOL][MAXROW],
down [MAXCOL][MAXROW];
main () /* generate spanning tree maze */
{
int row,col;
NewMaze(&col,&row);
MakeMaze(1,1,col,row);
BreakDown(0,1,1,1);
BreakDown(col,row,col+1,row);
ShowMaze(1,1,col,row);
}
NewMaze(xmax,ymax)
int *xmax,*ymax;
{
int i,j;
*xmax = MAXCOL-1; *ymax = MAXROW-1;
for (i=0; i<=*xmax; i+=1)
for (j=0; j<=*ymax; j+=1) {
right[i][j]=WALLUP;
down [i][j]=WALLUP;
}
for (i=0; i<=*xmax; i+=1)
right[i][0]=WALLDOWN;
for (j=0; j<=*ymax; j+=1)
down[0][j]=WALLDOWN;
}
MakeMaze(xa,ya,xb,yb)
int xa,ya,xb,yb;
{
int x0,x1,x2,x3,y0,y1,y2,y3;
int RandBetween();
x1=min(xa,xb); y1=min(ya,yb);
x2=max(xa,xb); y2=max(ya,yb);
if (x1==x2 && y1==y2)
return;
else if ((x2-x1)+(y2-y1) == 1)
BreakDown(x1,y1,x2,y2);
else if (x2-x1 > y2-y1) {
x3 = RandBetween(x1,x2-1);
MakeMaze(x1,y1,x3,y2);
MakeMaze(x3+1,y1,x2,y2);
y0 = RandBetween(y1,y2);
BreakDown(x3,y0,x3+1,y0);
}
else {
y3 = RandBetween(y1,y2-1);
MakeMaze(x1,y1,x2,y3);
MakeMaze(x1,y3+1,x2,y2);
x0 = RandBetween(x1,x2);
BreakDown(x0,y3,x0,y3+1);
}
}
ShowMaze(x1,y1,x2,y2)
int x1,y1,x2,y2;
{
int i,j;
char rt[256],dn[256];
for (j=y1-1; j<=y2; j+=1) {
strcpy(rt,"\0");
strcpy(dn,"\0");
for (i=x1-1; i<=x2; i+=1) {
strcat(rt,(right[i][j] == WALLUP) ? " 00" : " ");
strcat(dn,(down [i][j] == WALLUP) ? "0000" : " 00");
}
printf("%s\n",rt);
printf("%s\n",dn);
}
}
BreakDown(x1,y1,x2,y2)
int x1,y1,x2,y2;
{
if (x1 == x2)
down[x1][y1] = WALLDOWN;
else if (y1 == y2)
right[x1][y1] = WALLDOWN;
}
int RandBetween(n1,n2)
int n1,n2;
{
return n1 + (abs(random()) % (n2-n1+1));
/* assumes 'random' returns 15-bit random number */
}
--
"As long as you've lit one candle, Walt Leipold
you're allowed to curse the darkness." (leipolw%esvax at dupont.com)
--
More information about the Comp.lang.c
mailing list