Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!usc!ucsd!ogccse!blake!uw-beaver!ubc-cs!alberta!uqv-mts!Al_Dunbar
From: userAKDU@ualtamts.BITNET (Al Dunbar)
Newsgroups: comp.lang.c
Subject: Re: random maze generator
Message-ID: <341@ualtamts.BITNET>
Date: 14 Sep 89 14:47:32 GMT
References: <481@mindlink.UUCP> <757@eplrx7.UUCP>
Organization: University of Alberta (MTS)
Lines: 35

In article <757@eplrx7.UUCP>, leipold@eplrx7.UUCP (leipold) writes:
>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.  ...
>
>--Walt L.
>
>---------------
 
A  theoretical question: is this algorithm complete, or is there
at least one maze that it is unable to generate,  regardless  of
the  contrariness  of  the random number function? The algorithm
says:
 
"To make a maze out of an array of closed cells:
 
1) divide it into two adjacent sub- arrays separated by a
common wall chosen at random;
 
2) make each sub- array into a maze;
 
3) connect the two mazes by removing one of the segments of
the wall separating them."
 
Any  maze  produced this way will be spanned in one direction by
one straight wall containing only a single  break.  Using  trial
and  error,  I have as yet been unable to devise a maze that did
not have this property, but somehow it doesn't seem likely to be
impossible. Can anyone prove this either way?
 
/Al Dunbar