Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!haven!udel!eplrx7!leipold
From: leipold@eplrx7.UUCP (leipold)
Newsgroups: comp.lang.c
Subject: Re: random maze generator
Message-ID: <757@eplrx7.UUCP>
Date: 7 Sep 89 18:46:18 GMT
References: <481@mindlink.UUCP>
Reply-To: leipold@eplrx7.UUCP (Walt Leipold)
Organization: E.I. du Pont de Nemours & Co.
Lines: 131

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@dupont.com)
--