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!gnbcortesi@informix.com (David Cortesi) (12/14/90)
In article <1990Dec13.190759.9297@craycos.com> scott@craycos.com (Scott Bolte) writes: > > 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,"_.":" |"];} Well, when I tried it on a NeXT it said, quote: [crickhollow 71] cc maze.c -o maze [crickhollow 72] maze 10 _._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._ Bus error And no way am I gonna try to debug *that* thing...
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"
boutell@freezer.it.udel.edu (Tom Boutell) (12/16/90)
Believe it or not I *can* explain that behavior on the part of maze. The reason is that the code uses the space in which the user's input is stored by scanf to store a string without allocating it!! Really sick and clever stuff, but not universally portable. (Works OK here.) -- THE TECHNOLOGY HOUSE: An idea whose time has come! My girlfriend is a pseudo- aardvark. She is quite insistent on this point. And remember- when all else fails- and no one else can help- boutell@freezer.it.udel.edu
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
colas@avahi.inria.fr (Colas Nahaboo) (12/17/90)
In article <1990Dec14.001604.20990@informix.com>, cortesi@informix.com (David Cortesi) writes: > Well, when I tried it on a NeXT it said, quote: > [crickhollow 71] cc maze.c -o maze > [crickhollow 72] maze > 10 > ._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._ > Bus error It does this with gcc (which is) in ANSI mode. (gcc is cc on NeXT) Do a (g)cc -traditional > And no way am I gonna try to debug *that* thing... Seems that you need to debug gcc, easier isn't it? :-) -- Colas Nahaboo, Bull Research France -- Koala Project -- GWM X11 Window Manager Internet: colas@mirsa.inria.fr, Phone: (33) 93.65.77.70, Fax: (33) 93 65 77 66 INRIA Sophia, 2004, rte des Lucioles, B.P.109 - 06561 Valbonne Cedex, FRANCE
gordon@aix02.aix.rpi.edu (Gordon E. Greene) (12/18/90)
Perhaps a clarification is required about my posting. I received several messages about it. My contention that a non-tree maze is not solvable by trailing hand refers to mazes that don't have both the entry and exit on the outside. My starting point for this was an old book of mazes I once had. Many of the mazes had both entry and exit inside the maze. Some of them were not planar: that is they had corridors that passed over and under each other. It wouldn't be so tough to encode these mazes by labelling all the intersections, putting the maze into some graph representation, and then doing a path search through it from the start node to the end node. I think you'll agree that this would take a lot of the challenge out of doing mazes though. Breadth-first and depth-first searches would both find a path through, and variations to find the best (whatever best means) path could be implemented too. Sorry for any confusion that may have arisen from my incomplete description. -- --------- 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
alter@ttidca.TTI.COM (Steve Alter) (12/18/90)
In article <6WH^XJ_@rpi.edu> gordon@itsgw.rpi.edu (Gordon E. Greene) writes: } 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.... } } gordon@rpi.edu USERF023@RPITSMTS USERF023@mts.rpi.edu The right-hand-on-the-wall algorithm, in its simple form, won't be able to solve all mazes with loops in them (i.e. a maze that is not uniquely connected) but a simple modification to the algorithm can fix that. Just remember every room you've visited, and as you're walking around, if you see that you're about to step into an already visited room, then just pretend that there's a wall in front of you and continue to apply the right-hand rule. After that, you can forget about that piece of phantom wall, because the rooms on both sides of it have been visited. Related topic: I remember a program that generates a 2-level maze, in which passages can cross over each other, and to some extend, two passages can even run in vertical parallel because the upper one is painted narrower than the lower. The generator paints such a maze by growing all branches simultaneously, and the graphic effect is really strange! Rather than solving it, the program let's you mouse through it with no help. Anybody else heard of such a sadistic piece of code? -- Steve Alter <alter@ttidca.tti.com> {philabs,psivax,pyramid,quad1,rdlvax,retix,rutgers}!ttidca!alter Citicorp/TTI, Santa Monica CA (213) 450-9111 x2541
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
tel@adimail.UUCP (Terry Monks) (12/18/90)
> In article <1990Dec13.190759.9297@craycos.com> scott@craycos.com (Scott Bolte) writes: > > > >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,"_.":" |"];} > works fine on a Sun Sparcstation... -- Terry Monks Automata Design Inc (703) 472-9400
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
sartin@hplabsz.HPL.HP.COM (Rob Sartin) (12/19/90)
Actually, most of you already have a good program for maze solution (as opposed to generation), it's called pathalias. Just enter all the rooms as having links of cost 1 to the rooms they connect to and then run pathalias with the "entrance" node. Voila, you get a minimum length path to every room. It'll solve non-planar mazes, too. Rob
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).
gombo@tharr.UUCP (Alun Jones) (12/19/90)
Someone recently put up the obfuscated c code maze generator.
(Or rather, they put up a clear version of it.)
I'm going to respond with a program that takes the output from that maze
generator, and solves the maze.
In fact, if you feed it ANY SIZE maze - even MULTIPLY CONNECTED, it will find
a best route through it. (In this context, through means from the hole in top
left, to the hole in bottom right.)
I think it's quite cute, but it's not really good enough for the obfuscated
c code contest - unless there's a category for 'Best program using output
from a previous winner'.
Oh, and one more thing - there doesn't yet exist a clear version of this
program - I debug it in this state. You're welcome to distribute it - I'm
not proud. :-) Call it pd, call it whatever you will - just don't call it
copyright.
---------------------------Code begins after this line.---------------
#define _ define
#_ B switch(getchar()){D
#_ D case
#_ E >>1
#_ F(x)free((char *)x)
#_ H ;for(
#_ I (e&2?-1:1)
#_ J e&1?0:
#_ K (P("\n"),
#_ P(a)j=write(1,a,1)
#_ Q(a,b,c)P(a+((b)>>4&1)+((c)&2))
#_ S struct
#_ V =p->p
#_ W while(
#_ X(a)(S a *)malloc(sizeof(S a))
#_ Y (Q("## .",Z
#_ Z M[g
char *malloc();void free();
main(){int M[5000],C=0,R=0,g,e,j;S d{int p;S d*l;}*p,*n;S q{S d*g;S q*n;}*q,*o,
*r H;getchar()!='\n';C++)H e=(C>>=1);e--;)M[e]=!(M[e+C]=13);M[!(Z=C]=15)]=8;W!R
){B-1:R=g-1;break;D'|':Z-1]&=~1;Z]&=~4;}B'_':Z]&=~8;D' ':Z+C]=13|(Z]>>2);g++;}}
o=q=X(q);(p=X(d))->p=0;W(g V)!=R){Z]|=32 H e=~0;++e<4;)if(1<<e&Z])if(
M[(n=X(d))->p V+(J I)+C*(~J-I)]&32)F(n);else{n->l=p;o->g=n;o=o->n=X(q);}p=
(r=q)->g;q=q->n;F(r);}Z V]|=16;W g)Z=(p=p->l)->p]|=16;M[R+C]=16 H g=e=0;e<R;
e+=C){H;!e||Y]&Z-1],Z]E)),(g++<e+C||K 0));(Q(" .",Z-1],0)))H g=e;Y],(Z]&Z+C]&
(Z]&Z-1])E)E),(g++<e+C||K g--,0)));Y-1]&Z+C-1],Z-1]>>2)));}return j;}
------------------------------Code ends above this line.-----------------
Oh, one thing - it doubles the width and height (in characters) it gets,
and uses # to mark the walls, . to mark the path from entry to exit.
There is another version for lineprinters that overprints on the original maze
but I shan't post that.
--
Alun Jones - Unix Development Engineer - Welcom Software Technology Int'l.
My views are nothing whatsoever to do with the company I work for.
(That may be boring, but I feel safer for it.)
<-- tharr *free* public access to Usenet in the UK 0234 261804 -->ndjc@hobbit.UUCP (Nick Crossley) (12/20/90)
In article <21945@ttidca.TTI.COM> alter@ttidca.TTI.COM (Steve Alter) writes: >I remember a program that generates a 2-level maze, in which passages >can cross over each other, and to some extend, two passages can even >run in vertical parallel because the upper one is painted narrower than >the lower. The generator paints such a maze by growing all branches >simultaneously, and the graphic effect is really strange! Rather than >solving it, the program let's you mouse through it with no help. >Anybody else heard of such a sadistic piece of code? There is a standard demo/game on the Macintosh that does this. It provides several different 'difficulty' settings, and the more difficult mazes do have two layers. It was one of the first bits of software from Apple available for the Mac after its launch, together with games such as the Alice 'chess' game. I have no idea who wrote the maze program, but it might be the one you are thinking of. -- <<< standard disclaimers >>> Nick Crossley, ICL NA, 9801 Muirlands, Irvine, CA 92718-2521, USA 714-458-7282 uunet!ccicpg!ndjc / ndjc@ccicpg.UUCP
gordon@itsgw.rpi.edu (Gordon E. Greene) (12/20/90)
In article <21945@ttidca.TTI.COM> alter@ttidca.TTI.COM (Steve Alter) writes: >The right-hand-on-the-wall algorithm, in its simple form, won't be able >to solve all mazes with loops in them (i.e. a maze that is not uniquely >connected) but a simple modification to the algorithm can fix that. >Just remember every room you've visited, and as you're walking around, >if you see that you're about to step into an already visited room, then >just pretend that there's a wall in front of you and continue to apply >the right-hand rule. After that, you can forget about that piece of >phantom wall, because the rooms on both sides of it have been visited. > I'm not sure I see how this keeps you from getting stuck in loops unless you switch hands when you've gone around once. >Related topic: > >I remember a program that generates a 2-level maze, in which passages >can cross over each other, and to some extend, two passages can even >run in vertical parallel because the upper one is painted narrower than >the lower. The generator paints such a maze by growing all branches >simultaneously, and the graphic effect is really strange! Rather than >solving it, the program let's you mouse through it with no help. >Anybody else heard of such a sadistic piece of code? > I believe I have such a program for the Mac someplace. I will look for it if there is any interest. It will take a while as I will be away for the weekend and then I may have some problems getting access to a mac since I don't own one and RPI shuts down a lot of the micro facilities over break. -- --------- You can never have too many ferrets. ----------- gordon@rpi.edu USERF023@RPITSMTS USERF023@mts.rpi.edu
mcneely@ncrcae.Columbia.NCR.COM (Alan McNeely) (12/21/90)
>In article <21945@ttidca.TTI.COM> alter@ttidca.TTI.COM (Steve Alter) writes: >>The right-hand-on-the-wall algorithm, in its simple form, won't be able >>connected) but a simple modification to the algorithm can fix that. >>Just remember every room you've visited, and as you're walking around, >>if you see that you're about to step into an already visited room, then >>just pretend that there's a wall in front of you and continue to apply >>the right-hand rule. After that, you can forget about that piece of >>phantom wall, because the rooms on both sides of it have been visited. >> Actually I think you have to remember the wall. Example: ----- ! ! ! ! ! ______! ! ! FINISH ! ------ -- ! ! ! ! START From Start, algorithm goes right, creates imaginary wall coming back down toward the 4-way, and goes back around the inside of the loop. If we don't remember the imaginary wall we'll be trapped on the loop indefinitely. Right? Alan McNeely mcneely@bigb.columbia.ncr.com
nicholso@pioneer.arc.nasa.gov (Melvin H. Nicholson -- YBH) (12/21/90)
Steve Alter writes: >The right-hand-on-the-wall algorithm, in its simple form, won't be able >connected) but a simple modification to the algorithm can fix that. >Just remember every room you've visited, and as you're walking around, >if you see that you're about to step into an already visited room, then >just pretend that there's a wall in front of you and continue to apply >the right-hand rule. After that, you can forget about that piece of >phantom wall, because the rooms on both sides of it have been visited. > Alan McNeely writes: >Actually I think you have to remember the wall. Example: > ----- > ! ! > ! ! ! > ______! ! ! >FINISH ! > ------ -- > ! ! > ! ! > START > >From Start, algorithm goes right, creates imaginary wall coming back >down toward the 4-way, and goes back around the inside of the loop. >If we don't remember the imaginary wall we'll be trapped on the loop >indefinitely. Right? > >Alan McNeely >mcneely@bigb.columbia.ncr.com This algorythim has an even bigger problem, whether the wall is remembered or not. If "in front of" means "blocking entrance to the square" then whenever the "mouse" leaves moves from A toward C through B, where C is previously traversed and A has two (non-imagined) parallel walls, the "mouse" will be forced to move back toward A. Since A has now been previously traveled a new wall is imagined, keeping the "mouse" in B moving toward C (and then back to A, ad infinitum) What did you mean by "in front of" ???? Mel Nicholson Psycholinguistics Research Associates (PLRA)
cosell@bbn.com (Bernie Cosell) (12/21/90)
gordon@itsgw.rpi.edu (Gordon E. Greene) writes: }In article <21945@ttidca.TTI.COM> alter@ttidca.TTI.COM (Steve Alter) writes: }>The right-hand-on-the-wall algorithm, in its simple form, won't be able }>to solve all mazes with loops in them (i.e. a maze that is not uniquely }>connected) but a simple modification to the algorithm can fix that. }>Just remember every room you've visited, and as you're walking around, }>if you see that you're about to step into an already visited room, then }>just pretend that there's a wall in front of you and continue to apply }>the right-hand rule. After that, you can forget about that piece of }>phantom wall, because the rooms on both sides of it have been visited. }> }I'm not sure I see how this keeps you from getting stuck in loops unless you }switch hands when you've gone around once. You missed the part "just remember every room you've visited" --- he's just magically converted the algorithm from being a simple finite-state one to being order (N^2) Once you've scaled the automaton to include enough memory to, in essence, map the whole maze, there are lots of algorithms that become available. Finding a *finite*state* algorithm for an arbitrary maze is very difficult. The best I've seen is Manny Blum's algorithm: it will solve an arbitrary planar maze with a finite-state-automaton with *two* markers. That is, the automaton has a few new operations [besides "move left", "move right", etc] which are "drop a marker" and "pick up a marker". and a new input condiion: there is a marker in teh cell you're in. /Bernie\
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 >
john@newave.UUCP (John A. Weeks III) (12/27/90)
In article <Z5K^*R&@rpi.edu> gordon@itsgw.rpi.edu (Gordon E. Greene) writes: > In article <21945@ttidca.TTI.COM> alter@ttidca.TTI.COM (Steve Alter) writes: > > I remember a program that generates a 2-level maze [...] > > Anybody else heard of such a sadistic piece of code? > I believe I have such a program for the Mac someplace. It is called "The Amazing Maze", and it was on one of the demo disks supplied to dealers with the original 128K Macintosh. It runs on the Mac+, but not on the Mac II line. I would enjoy getting a Mac II version of a Maze program that uses color. -john- -- =============================================================================== John A. Weeks III (612) 942-6969 john@newave.mn.org NeWave Communications ...uunet!rosevax!tcnet!wd0gol!newave!john ===============================================================================
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>