martins@syacus.acus.oz (Martin Schwenke) (12/13/90)
I am interested in software or algorithms for generating mazes with unique solutions. I am also, but less, interested in maze solving algorithms, and programs. Any useful info would be appreciated. peace & happiness, martin -- :: Martin Schwenke ::::::::: martins@syacus.acus.oz.au ::::::: +61 2 887 6791 :: ) _ _ peace & happiness _ ) _ __ _ ) Australian Centre ) / / / / __ _ _/ o _ ( ' / /_| / / / ( ' / o for / ( / / ( (_( / ' ( ( / > `_) ( / |(__ (__( `_) ( UNISYS Software (
scott@mcs-server.gac.edu (Scott Hess) (12/13/90)
In article <1215@syacus.acus.oz> martins@syacus.acus.oz (Martin Schwenke) writes:
I am interested in software or algorithms for generating mazes with
unique solutions. I am also, but less, interested in maze solving
algorithms, and programs.
A nice solution I found to this is the following algorithm (adapted from
a particularily ugly BASIC program . . .):
Your maze is made up of a bunch of cells in a 2d array. Each looks
something like:
O?
?X
Where O is open, ? are uncertain, and X is a wall. So, you need two
bits per cell to represent this.
To start out, set all the cells to be closed (both ? are X).
Pick a random cell (this can be anywhere, just choose somewhere).
loop
From the current cell, do a random walk. This means, pick a random
direction. Look in that direction to see if you can move there.
If so, open a path to there (either in your cell [right/down],
or the appropriate neighbor [up/left]).
Assume an implicit wall on the right hand side.
until you run into a wall.
Now, you need to find a new place to start. So, what you do is
begin scanning the array in some fashion (say, left to right, top
to bottom - reading fashion) for closed cells. Once you find one,
open a path to a neighbor, and then random walk . . .
Do this over and over until all cells are accounted for (as found
by running over the starting scan block again).
While this isn't the most complex solution, it generated very acceptable
mazes for my purposes (I was to write a maze-solver. What good's
a solver without a generator :-]. To add to the fun, it was in
text mode on a PC, so I wrote a virtual window for it . . . :-)
--
scott hess scott@gac.edu
Independent NeXT Developer GAC Undergrad
<I still speak for nobody>
"Tried anarchy, once. Found it had too many constraints . . ."
"Buy `Sweat 'n wit '2 Live Crew'`, a new weight loss program by
Richard Simmons . . ."scott@craycos.com (Scott Bolte) (12/14/90)
> I am interested in software or algorithms for generating mazes .... Believe it or not the following C code can generate unique mazes of arbitrary size. Extract the code and compile it. When you run it just give a number, after you run it, not on the command line. I do not know where it came from but I have had it for at least a year. 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,"_.":" |"];} Scott -- ___________________________________________________________________________ Scott Bolte scott@craycos.com +1 719 540 4186 Cray Computer Corporation, 1110 Bayfield Drive, Colorado Springs, CO 80906
gnb@bby.oz.au (Gregory N. Bond) (12/14/90)
>>>>> On 13 Dec 90 01:19:40 GMT, martins@syacus.acus.oz (Martin Schwenke) said:
Martin> I am interested in software or algorithms for generating mazes with
Martin> unique solutions. I am also, but less, interested in maze solving
Martin> algorithms, and programs.
OK, build it by induction.
1) Select a start square. This is a uniquely connected maze.
Induct:
2) Given a uniquely connected maze of n squares, we can make a
uniquely connected maze of n+1 squares by adding a new square
adjacent to the existing maze and connecting it by removing wall
only.
3) Choose arbitary start and end squares. Guaranteed only 1 way
through between any two squares.
However, this generates "choppy" mazes, with very few long runs. Much
better looking mazes can be generated by slightly changing the
algorithm so that at point 2) instead of adding just one square, you
add a "corridor" that is straight say 80% of the time, and turns
randomly 20% of the time, and join that on to the existing maze at
only one point. The length of the coridor can be limited (say, the
length of the short size fo the maze) or run untill it gets boxed in
by existing maze elements.
I experemented a lot with maze generation many years ago on a 64k Z80
system. With fairly compact encoding (4 cells/byte) and a 60K TPA, I
was producing mazes approx 150 x 2000. If I could read 8inch 1.2MB
CP/M disks, I'd send you the programs, but they don't fit in the Sun
tapedrive slot...
As for solving.....
With any uniquely connected maze it is possible to solve it by the
"right hand rule" - stick your right hand on the wall and keep
walking, always turning right at every opportunity. The sunview maze
screenblanker does that. (I once hacked it to leave a grey trail
where it had visited - most interesting graphical view of the
algorithm at work).
Greg.
--
Gregory Bond, Burdett Buckeridge & Young Ltd, Melbourne, Australia
Internet: gnb@melba.bby.oz.au non-MX: gnb%melba.bby.oz@uunet.uu.net
Uucp: {uunet,pyramid,ubc-cs,ukc,mcvax,prlb2,nttlab...}!munnari!melba.bby.oz!gnbzane@ddsw1.MCS.COM (Sameer Parekh) (12/15/90)
I read of an alogrithim somewhere that makes constantly changing mazes. You have 2 dimensional matrix of square tiles. They look like this: ________ | / | |/ /| |_____/_| (Something like that) They tiles face in any direction. Then every time the maze changes, you can rotate the tiles. -- zane@ddsw1.MCS.COM
tleylan@pegasus.com (Tom Leylan) (12/15/90)
In article <1990Dec13.190759.9297@craycos.com> scott@craycos.com (Scott Bolte) writes: > >> I am interested in software or algorithms for generating mazes .... > > Believe it or not the following C code can generate unique > mazes of arbitrary size. Extract the code and compile it. When > you run it just give a number, after you run it, not on the > command line. > > I do not know where it came from but I have had it for at least > a year. > <code previously posted> Scott... it looked so cute that I tried it but no maze. It printed a repeated pattern though. Made me suspect that the RAND() function might be operating differently. I'm using Microsoft C and it returns a random value between 1 and 32767. Does this appear to conflict with anything ? BTW, if I was forced to guess it's origins it "looks" like an entry in the obfuscated code contest that someone holds each year. tom
pphillip@cs.ubc.ca (Peter Phillips) (12/15/90)
In article <1215@syacus.acus.oz> martins@syacus.acus.oz (Martin Schwenke) writes: > >I am interested in software or algorithms for generating mazes with >unique solutions. I am also, but less, interested in maze solving >algorithms, and programs. One method is to think of a maze as a spanning tree for a connected graph. Take any graph, assign random weights to each arc. Apply some minimal spanning tree algorithm. A drawing of the resulting tree will be maze. It helps if you know of some way of embedding the graph in a plane. All this works out simply if your starting graph is a grid. This method has a few advantages. First, you aren't stuck with using a grid. You could use this to make a maze out of a map of countries or some other familiar graph. Second, you can create different effects by varying how you choose your weights without worrying about screwing up the algorithm. Third, it runs in time close to order n. (n = number of nodes). I wrote some code to do this once as an application of Kruskal's minimal spanning tree algorithm (a rather nifty little algorithm). I've still got code to do this in C lying around somewhere. Hmm, you could work this in reverse. Create a program which takes an arbitrary tree and turns it into a grid maze. You could use this to turn a UNIX file system tree into a maze, as if it isn't already. :-) -- Peter Phillips, pphillip@cs.ubc.ca | "It's worse than that ... He has {alberta,uunet}!ubc-cs!pphillip | no brain." -- McCoy, "Spock's Brain"
scott@craycos.com (Scott Bolte) (12/17/90)
In article <1990Dec15.093542.2725@pegasus.com> tleylan@pegasus.com (Tom Leylan) writes: > ... I'm using Microsoft C and it returns a random >value between 1 and 32767. Does this appear to conflict with anything ? I do not see how that would cause a problem. Why don't you try the following unrolled code... It is not nearly as obscure as the original code, which several people have confirmed came from the obfuscated code contest. #define HALF_LINE 40 char M[3], A, even, E = HALF_LINE, J[HALF_LINE], T[HALF_LINE]; main(argc,argv) char *argv[]; { int lines; char wall; srand(getpid()); if( argc > 1) lines = atoi(argv[1]); else (void) scanf("%d" , &lines); A = 1; /* * Top line */ for (*J = A ; --E; J[E] = T[E] = E) printf("._"); while( 1) { /* * even toggles between 0 and 1. */ even = !even; A -= even; if ( A == 0 ){ printf("\n|"); A = HALF_LINE - 1 ; if( lines-- == 0) exit(0); } E = A[J - even]; /* * default settings. */ if( even ) M[1] = '|'; else M[0] = ' '; if( A != E ) { if( lines != 0) /* * rule for the middle lines. */ wall = (0x30000000 < rand()); else /* * rule for the bottom line. */ wall = (A== T[A] | (0x30000000 < rand())) || !even; if( wall ) { T[E] = T[A]; J[T[E]] = E; T[A] = A - even; J[T[A]] = A; if( even ) M[1] = '.'; else M[0] = '_'; } } else /* * Very last printout. */ if ( !lines && !even ) M[0] = '_'; if( !even ) printf(M); } } Scott -- ___________________________________________________________________________ Scott Bolte scott@craycos.com +1 719 540 4186 Cray Computer Corporation, 1110 Bayfield Drive, Colorado Springs, CO 80906
gordon@itsgw.rpi.edu (Gordon E. Greene) (12/17/90)
In article <1990Dec15.122555.20420@cs.ubc.ca> pphillip@cs.ubc.ca (Peter Phillips) writes: >One method is to think of a maze as a spanning tree for a connected >graph. Take any graph, assign random weights to each arc. Apply some >minimal spanning tree algorithm. A drawing of the resulting tree will >be maze. It helps if you know of some way of embedding the graph in a >plane. All this works out simply if your starting graph is a grid. Even more general than this is to observe that any maze (in a plane) is a conected planar graph. If one started the algorithm with a random connected planar graph and then just drew it, one would have a maze. This method can give mazes with loop corridors in them. The tree algorithms give only simple mazes (right hand on the wall to get out). A more general planar graph can give mazes which the trailing hand method won't solve. In addition, if one pays a lot of attention to the algorithm for drawing the graph, corridors could be curved, join at rooms, whatever. To actually draw a planar graph, one could sort the graph into polygons. One could then determine which edges lie inside which polygons, and then deform the polygons to allow for rooms, curved hallways, and so on. -- --------- You can never have too many ferrets. ----------- gordon@rpi.edu USERF023@RPITSMTS USERF023@mts.rpi.edu
zane@ddsw1.MCS.COM (Sameer Parekh) (12/18/90)
In article <1990Dec16.181459.10786@craycos.com> scott@craycos.com (Scott Bolte) writes: > I do not see how that would cause a problem. Why don't you try > the following unrolled code... It is not nearly as obscure as > the original code, which several people have confirmed came > from the obfuscated code contest. I thought the patterning of the code was neat. Did you notice that it looked like a maze? (Yet I compiled it, but I just got straight lines, not a maze) -- zane@ddsw1.MCS.COM
sls@beaner.cs.wisc.edu (Steve Scott) (12/19/90)
In article <1990Dec18.035646.7316@ddsw1.MCS.COM> zane@ddsw1.MCS.COM (Sameer Parekh) writes: > > I thought the patterning of the code was neat. Did you notice >that it looked like a maze? (Yet I compiled it, but I just got >straight lines, not a maze) > >-- >zane@ddsw1.MCS.COM > *Looks* like a maze? Look again. It *spells* maze. --Steve
gessel@masada.cs.swarthmore.edu (Daniel Mark Gessel) (12/19/90)
>*Looks* like a maze? Look again. It *spells* maze. >--Steve I saw this posting and notice, squint your eyes. Dan -- Daniel Mark Gessel Independent Software Consultant Internet: gessel@cs.swarthmore.edu and Developer I do not represent Swarthmore College (thank God).
zane@ddsw1.MCS.COM (Sameer Parekh) (12/22/90)
In article <1990Dec18.171931.968@spool.cs.wisc.edu> sls@beaner.cs.wisc.edu (Steve Scott) writes: >In article <1990Dec18.035646.7316@ddsw1.MCS.COM> zane@ddsw1.MCS.COM (Sameer Parekh) writes: >> >> I thought the patterning of the code was neat. Did you notice >>that it looked like a maze? (Yet I compiled it, but I just got >>straight lines, not a maze) >> >>-- >>zane@ddsw1.MCS.COM >> > >*Looks* like a maze? Look again. It *spells* maze. > >--Steve Oh yeah! I didn't notice. That is IMMENSE! And it compiles too! But how do you work it? I just got straight lines. . . -- zane@ddsw1.MCS.COM