WANTED: maze-generating algorithm
ot...@vaxb.acs.unt.edu
I'm looking for an algorithm that, when given a rectangular area to fill,
fills it with a randomly generated maze with a single solution. I saw such a
thing once, done in basic, so I know it's possible. :-) I would love it if
the algorithm generalizes for an N-dimension maze, but 2 dimensions would be
satisfactory.
If you don't have an actual algorithm description, but have source code (any
HLL) for a program that does it, I would appreciate that too. If it's
commented adequately, I can probably glean the algorithm from it.
Followups are directed to comp.programming.
Thanks in advance.
______ _ _ /\
/ __ /__________ _____ M. Otto //// /__\
/ / / //_ __ __// _ / ot...@vaxb.acs.unt.edu _ _ //// // \\
/ /_/ / / / / / / // / A virtual prisoner of the VAX \\\X/// / \ / \
/_____/ /_/ /_/ /____/ at The University of North Texas \XXX/ / ~ ~ \
Denton, USA ~~~~~~~~~~
Charlie Gibbs
writes:
> I'm looking for an algorithm that, when given a rectangular area to fill,
>fills it with a randomly generated maze with a single solution. I saw such a
>thing once, done in basic, so I know it's possible. :-) I would love it if
>the algorithm generalizes for an N-dimension maze, but 2 dimensions would be
>satisfactory.
>
> If you don't have an actual algorithm description, but have source code (any
>HLL) for a program that does it, I would appreciate that too. If it's
>commented adequately, I can probably glean the algorithm from it.
From the depths of a musty old 9-track tape, I dug this up:
100 ' NAME: AMAZING***
105 '
110 ' BY: Jack Hauber and S. J. Garland on 12/13/72
115 '
120 ' DESCRIPTION: Constructs a maze of any size the user wishes (up
125 ' to 25 rows by 23 columns). Each maze is unique and guaranteed
130 ' to have only one solution.
135 '
140 ' INSTRUCTIONS: Type "RUN" for complete instructions.
145 '
150 ' CATEGORY: DEMONS***
155 '
160 ' LANGUAGE: BASIC
165 '
170 ' INDEX LINE:
175 ' |Constructs unique, 1 solution |maze
180 '
185 '
220 RANDOMIZE
230 PRINT "THIS PROGRAM WILL PRINT A DIFFERENT MAZE EACH TIME IT IS"
240 PRINT "RUN. THERE WILL BE A UNIQUE PATH THROUGH THE MAZE. YOU"
250 PRINT "CAN CHOOSE ANY DIMENSIONS FOR THE MAZE UP TO 25 SQUARES"
260 PRINT "LONG AND 23 SQUARES WIDE."
270 PRINT
280 PRINT "WHAT ARE YOUR LENGTH AND WIDTH (E. G. 13,10)";
290 INPUT R9, C9
300 DIM W(25,23), V(25,23)
310 LET N9 = R9*C9
320 MAT W = ZER(R9,C9) 'KEEPS TRACK OF SQUARES VISITED
330 MAT V = ZER(R9,C9) 'AND THEIR RIGHT, BOTTOM WALLS
340 LET B = 0 'FLAG NO EXIT TO BOTTOM YET
350 REM FIND SQUARE IN WHICH TO START
360 LET F = INT(RND*C9+1)
370 PRINT 'PRINT TOP BORDER
380 FOR C = 1 TO C9
390 IF C = F THEN 420
400 PRINT ":--";
410 GOTO 430
420 PRINT ": ";
430 NEXT C
440 PRINT ":"
450 LET R = 1 'START IN FIRST ROW
460 LET C = F 'AND COLUMN UNDER HOLE IN BORDER
470 LET N = 1 'COUNT OF SQUARES VISITED
480 LET W(R,C) = N
490 '
500 ' A CORRIDOR IS CONSTRUCTED BY MOVING IN A RANDOM DIRECTION FROM
510 ' THE CURRENT SQUARE TO SOME SQUARE THAT HAS NOT BEEN VISITED
520 ' YET AND ERASING THE WALL BETWEEN THE TWO SQUARES. IF NO SUCH
530 ' MOVE IS POSSIBLE, A SIDE CORRIDOR IS STARTED IN SOME SQUARE
540 ' ALREADY VISITED WHICH IS ADJACENT TO AN UNVISITED SQUARE. ONLY
550 ' ONE EXIT TO THE BOTTOM OF THE MAZE IS ALLOWED.
560 '
570 REM MAKE LIST OF UNBLOCKED DIRECTIONS
580 LET D = 0
590 REM CAN WE GO LEFT
600 IF C = 1 THEN 640 'NO, ON BORDER
610 IF W(R,C-1) > 0 THEN 640 'NO, SQUARE USED ALREADY
620 LET D = D+1 'YES, ADD "LEFT" TO LIST
630 LET D(D) = 1
640 REM CAN WE GO RIGHT
650 IF C = C9 THEN 690 'NO, ON BORDER
660 IF W(R,C+1) > 0 THEN 690 'NO, SQUARE USED ALREADY
670 LET D = D+1 'YES, ADD "RIGHT" TO LIST
680 LET D(D) = 2
690 REM CAN WE GO UP
700 IF R = 1 THEN 740 'NO, ON BORDER
710 IF W(R-1,C) > 0 THEN 740 'NO, SQUARE USED ALREADY
720 LET D = D+1 'YES, ADD "UP" TO LIST
730 LET D(D) = 3
740 REM CAN WE GO DOWN
750 IF R < R9 THEN 780 'MAYBE, NOT ON BORDER
760 IF B = 1 THEN 810 'NO, ALREADY HAVE EXIT TO BOTTOM
770 GOTO 790 'YES, ALLOW EXIT TO BOTTOM
780 IF W(R+1,C) > 0 THEN 810 'NO, SQUARE USED ALREADY
790 LET D = D+1 'YES, ADD "DOWN" TO LIST
800 LET D(D) = 4
810 REM CHOOSE DIRECTION
820 IF D = 0 THEN 1090 'ALL DIRECTIONS BLOCKED
830 LET X = INT(D*RND+1) 'PICK RANDOM DIRECTION
840 ON D(X) GOTO 850,890,930,970
850 REM GO LEFT
860 LET C = C-1
870 LET V(R,C) = 2 'NEW SQUARE HAS ONLY BOTTOM WALL
880 GOTO 1030
890 REM GO RIGHT
900 LET V(R,C) = V(R,C) + 2 'ERASE RIGHT WALL OF THIS SQUARE
910 LET C = C+1
920 GOTO 1030
930 REM GO UP
940 LET R = R-1
950 LET V(R,C) = 1 'NEW SQUARE HAS ONLY RIGHT WALL
960 GOTO 1030
970 REM GO DOWN
980 LET V(R,C) = V(R,C) + 1 'ERASE BOTTOM WALL OF THIS SQUARE
990 LET R = R+1
1000 IF R <= R9 THEN 1030 'STILL IN MAZE
1010 LET B = 1 'FLAG EXIT TO BOTTOM
1020 GOTO 1140 'AND GO VISIT OTHER SQUARES
1030 REM MARK SQUARE AS USED
1040 LET N = N+1
1050 LET W(R,C) = N
1060 IF N < N9 THEN 570
1070 REM DONE
1080 GOTO 1180
1090 REM RESTART IN USED SQUARE ADJACENT TO UNUSED SQUARE
1100 LET C = C+1
1110 IF C <= C9 THEN 1160
1120 LET R = R+1
1130 IF R <= R9 THEN 1150
1140 LET R = 1
1150 LET C = 1
1160 IF W(R,C) > 0 THEN 570
1170 GOTO 1100
1180 REM PRINT OUT MAZE
1190 FOR R = 1 TO R9
1200 PRINT "I";
1210 FOR C = 1 TO C9
1220 IF V(R,C) < 2 THEN 1250
1230 PRINT " ";
1240 GOTO 1260
1250 PRINT " I";
1260 NEXT C
1270 PRINT
1280 FOR C = 1 TO C9
1290 IF MOD(V(R,C),2) = 0 THEN 1320
1300 PRINT ": ";
1310 GOTO 1330
1320 PRINT ":--";
1330 NEXT C
1340 PRINT ":"
1350 NEXT R
1360 END
A friend once hacked this code so that it could produce larger
mazes by printing multiple sheets (on his TTY35RO :-) that he could
tape together, but you could probably figure it out from here.
Enjoy...
Charli...@mindlink.bc.ca
I'm trying to develop a photographic memory.
Peter da Silva
one is in David Ahl's 101 computer games. If you can't find it, look around
and dig a new maze everywhere you haven't been yet.
--
/F{findfont exch scalefont setfont}def /S{moveto show}def /T{/Times-Roman F}def
6 T (Have you hugged your wolf today?)468 20 S 9 T (Taronga Park BBS)24 35 S 10
/Courier F(`-_-')488 40 S ( 'U` )488 30 S 6 T (+1 713 568 0480 2400/n/8/1)24 27
S (+1 713 568 1032 Trailblazer)24 20 S 12 T (Peter da Silva)24 45 S showpage