random maze generator
Al Dunbar
userAKDU at ualtamts.BITNET
Fri Sep 15 00:47:32 AEST 1989
In article <757 at eplrx7.UUCP>, leipold at 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
More information about the Comp.lang.c
mailing list