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!gnb
mdchaney@bronze.ucs.indiana.edu (M Darrin Chaney) (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. > >Any useful info would be appreciated. Martin (and other gamers)- I have included at the bottom of this message a small recursive program/routine that will generate random mazes. It should run on an Ultrix/Unix platform with no modifications, or on a VMS platform with the "random/srandom" functions renamed to "rand/srand" (or, better yet, write the functions for VMS to use the built-in mth$random). Here is how it works. The maze is stored as a large array, in this case 500x500. You enter the maze size with command line options. Each piece of the array represents a cell. Each cell has four walls, numbered clockwise from 0 to 3. The wall is represented by its corresponding bit. If the bit is on, then the wall exists. Otherwise, the wall doesn't exist, and one can travel in that direction to the next cell. Keep in mind, then, that an unoccupied cell has a value of 15 decimal, or 1111 binary. To generate the maze, we must think recursively. First, we start at the upper left-hand corner (1,1). We'll call our maze generating function make_maze, and it will be called with 2 arguments, which are an x,y coordinate pair. So, to start the maze, we'll use make_maze(1,1). The first thing the function does is to pick a random permutation. For the four directions, taken one at a time, there are 4*3*2*1, 24, ways that they could be taken. So, we pick a number from 0 to 23. Then, we go through each of the four ways in that order. At each one, we test whether or not we can go that direction. If so, we call make_maze with that coordinate pair. If not, we simply try the next direction. The maze generating loop is only 16 lines. I included another piece of code that picks a suitable exit. As a matter of fact, the exit it picks is the edge cell that is farthest from the beginning (through the maze, that is). The version at the bottom will display its maze with the VT100 graphics set, which is available on almost all emulators. The picture isn't perfect, as I needed 4 little pieces that weren't there, but I think you'll get the picture. If you'd like, I also have a ReGIS version which draws the maze, then solves it, all graphically, and slow enough to watch how it works. I can make no guarantees that it works perfectly on a VT240, but it should for mazes down to 50x30 or so. If you'd like that version, just drop some email. If you have any questions, just write. Cheers- Darrin M Darrin Chaney mdchaney@bronze.ucs.indiana.edu mdchaney@rose.ucs.indiana.edu mdchaney@iubacs ------------------------------------------------------------------------------- /* M Darrin Chaney Command line options: -x : set nummber of columns -y : set number of rows -r : specify seed for random number generator make_maze -x 20 -y 20 -r 4 */ #include <stdio.h> #include <math.h> #include <time.h> #define MAXX 500 #define MAXY 500 int deltax[4]={0,1,0,-1}; int deltay[4]={-1,0,1,0}; unsigned char maze[MAXX+1][MAXY+1]; int perms[24][4]={{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1}, {1,0,2,3},{1,0,3,2},{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0}, {2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},{2,3,0,1},{2,3,1,0}, {3,0,1,2},{3,0,2,1},{3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0}}; /* pieces array is just for the VT100 graphics viewer */ char pieces[16]={32,32,32,109,32,120,108,116, 32,106,113,118,107,117,119,110}; int maxx=21,maxy=21; int max_level=0,max_level_x,max_level_y; int srandom(); int random(); main(argc,argv) int argc; char *argv[]; { int i,j,k,x,y; char line[202]; int ran,gran=0,dir; for (i=1 ; i<argc ; i++) { if (*argv[i]=='-') { switch (*(argv[i]+1)) { case 'x': maxx=atoi(argv[++i])+1; break; case 'y': maxy=atoi(argv[++i])+1; break; case 'r': ran=atoi(argv[++i]); gran=1; break; default: fprintf(stderr,"Unknown flag: %s\n",argv[i]); break; } } else { fprintf(stderr,"Unknown flag: %s\n",argv[i]); } } if (gran==1) srandom(ran); else srandom(time(0)); for (x=0 ; x<maxx+1 ; x++) for (y=0 ; y<maxy+1 ; y++) if ((x==0) || (x==maxx) || (y==0) || (y==maxy)) maze[x][y]=0; else maze[x][y]=15; make_maze(1,1,0,2); /* The rest of this is just for the viewer */ for (y=0 ; y<maxy+1 ; y++) { maze[0][y]=2; maze[maxx][y]=8; } for (x=1 ; x<maxx ; x++) { maze[x][0]=4; maze[x][maxy]=1; } maze[0][0]=maze[maxx][0]=maze[maxx][maxy]=maze[0][maxy]=0; for (y=0 ; y<maxy ; y++) { for (i=0,x=0 ; x<maxx ; x++,i++) { line[i]=0; if (maze[x][y] & 2) line[i] += 1; if (maze[x][y] & 4) line[i] += 8; if (maze[x+1][y+1] & 1) line[i] += 2; if (maze[x+1][y+1] & 8) line[i] += 4; line[i]=pieces[line[i]]; } line[i]=0; printf("\033(0%s\033(B\n",&line[0]); } } make_maze(x,y,level,dir) int x,y,level,dir; { int i,j,k; int direction,perm_num; if ((level>max_level) && ((x==1) || (y==1) || (x==maxx-1) || (y==maxy-1))) { max_level=level; max_level_x=x; max_level_y=y; } perm_num = random() % 24; for (k=0 ; k<4 ; k++) { direction=perms[perm_num][k]; i=x+deltax[direction]; j=y+deltay[direction]; if (maze[i][j]==15) { maze[x][y] -= (1 << direction); maze[i][j] -= (1 << (direction ^ 2)); make_maze(i,j,level+1,direction); } } } fatal_error(str) char *str; { fprintf(stderr,"Error: %s\n",str); exit(0); } ------------------------------------------------------------------------------- mdchaney@iubacs mdchaney@bronze.ucs.indiana.edu mdchaney@rose.ucs.indiana.edu
zane@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
pinkas@st860.intel.com (Israel Pinkas) (12/18/90)
In article <1990Dec15.093542.2725@pegasus.com> tleylan@pegasus.com (Tom Leylan) writes: > 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 ? Yep, that's the problem. The BSD version of rand() returns a number between 0 and 2^31-1, whereas the System V and DOS versions return a number between 0 and 2^15-1. Since the return value is compared against 6<<27, the test always fails on DOS and SysV machines. Change the 27 on the last line to 11 and you should get better results. > 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. I believe that it is from the 1989 contest. -Israel Pinkas -- -------------------------------------- Disclaimer: The above are my personal opinions, and in no way represent the opinions of Intel Corporation. In no way should the above be taken to be a statement of Intel. UUCP: {amdcad,decwrl,hplabs,oliveb,pur-ee,qantel}!intelca!mipos3!st860!pinkas ARPA: pinkas%st860.intel.com@relay.cs.net CSNET: pinkas@st860.intel.com
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
tleylan@pegasus.com (Tom Leylan) (12/25/90)
In article <PINKAS.90Dec17174817@st860.intel.com> pinkas@st860.intel.com (Israel Pinkas) writes: > >Yep, that's the problem. The BSD version of rand() returns a number >between 0 and 2^31-1, whereas the System V and DOS versions return a number >between 0 and 2^15-1. Since the return value is compared against 6<<27, >the test always fails on DOS and SysV machines. > >Change the 27 on the last line to 11 and you should get better results. Many thanks to everyone who pointed me in the direction of the elusive 11 that was, as you all know, the problem. Now to turn this into some sort of dumb little maze game... tom >
merlyn@digibd.com (Brian Westley (Merlyn LeRoy)) (12/31/90)
>> 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. >I believe that it is from the 1989 contest. Didn't win, though. (I'd've picked it over some of the others). For the curious, it's by John Tromp (tromp@piring.cwi.nl) (He won for his Tetris program in 1990) Didn't notice that the maze layout also spelled "maze" --- Merlyn LeRoy 4-time IOCCC winner
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (12/31/90)
merlyn@digibd.com (Brian Westley (Merlyn LeRoy)) writes: >>> 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. >>I believe that it is from the 1989 contest. >Didn't win, though. (I'd've picked it over some of the others). >For the curious, it's by John Tromp (tromp@piring.cwi.nl) >(He won for his Tetris program in 1990) >Didn't notice that the maze layout also spelled "maze" Yeah, that's fairly subtle; needs squinting. I wonder if it would have won if the judges had picked up on it. My all time favorite IOCCC entry was the one that was in the shape of a locomotive. >Merlyn LeRoy >4-time IOCCC winner Was this from code deliberately designed to win, or just day to day stuff of yours in some big project that your coworkers sent in in your name? ;-) Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>