50 views

Skip to first unread message

Apr 2, 1992, 5:27:19 PM4/2/92

to

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 ~~~~~~~~~~

Apr 3, 1992, 2:26:28 PM4/3/92

to

In article <1992Apr2...@vaxb.acs.unt.edu> ot...@vaxb.acs.unt.edu

writes:

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.

Apr 10, 1992, 10:43:26 PM4/10/92

to

It should be trivial to deduce the algorithm, but if you can't a really bad

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

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu