'=========================================================================== ' Subject: MAZE GENERATING SUB Date: 06-23-98 (22:35) ' Author: Charles Shampine Code: QB, QBasic, PDS ' Origin: Shampine@imcnet.net Packet: ALGOR.ABC '=========================================================================== ' 'Maze generating SUB by Charles Shampine - 1998 ' This SUB will randomly create a maze of any size and store it in a '2-dimensional array called maze%(x,y), providing the following criteria 'are met: '1. The dimensions for both axes MUST be >= 7. The sides do not have to be ' equal, but they must not be grossly different either! You'll have to ' experiment with the dimensions to see what the SUB is (and isn't) ' capable of. '2. BOTH dimensions must be ODD!!! '3. The amount of space DIMmed must be large enough to hold maze. ' Example: If your maze is to be 51*51, the array must be DIMmed ' to at least (50,50). The maximum dimensional size of the maze is limited ' only by the amount allotted in the DIM SHARED statement. For ' demonstrational purposes, I have DIMmed the array to a memory-hogging ' 180*180 in case you want to see a maze that big. ' ' Obviously, the greater the dimensions the longer it will takes to create 'the maze. The maze generated has a START and a FINISH and is always 'solvable. ' If the SUB makes an unusually high number of attempts to create a map, or 'you find that the START and FINISH are too close together, your dimensions 'are probably too different! ' 'I hope you find this SUB useful! 'Please feel free to modify, use, and redistribute! ' 'maxrow% - Vertical dimension of maze, must be odd. 'maxcol% - Horizontal dimension of maze, must be odd. '************************************************************************** DECLARE SUB MazeGen () DIM SHARED maze%(180, 180) 'That's (0-180, 0-180) folks, a total of 181*181. 'SET THIS TO THE MINIMUM THAT YOU REQUIRE!!! 'We used SHARED in our DIM because we want maze% 'array useable by all subs and procedures. COMMON SHARED maxcol%, maxrow% COMMON SHARED startx%, starty%, finishx%, finishy% 'The 2 preceding COMMON SHARED statements allow the program to retain the 'values of the included variables so that they can be used by any SUB or 'procedure. maxcol% = 79: maxrow% = 79 'These variables MUST be set before the call 'to the SUB. Remember, dimensions must be odd 'for clean output. MazeGen 'This command calls the SUB!!! '************************************************************************** showmaze: 'A sample display routine. 'This routine will not display the entire maze if one of it's 'dimensions is greater than what the screen mode supports. ' 'The data format for array maze%(x,y) is as follows: ' 0- indicates an open space. ' 1- indicates a wall. ' 2- STARTING point, only one of these. ' 3- FINISHING point, only one of these. ' 'following data statement contains color info. DATA 0,8,10,13 SCREEN 7: FOR x% = 0 TO maxcol% - 1: FOR y% = 0 TO maxrow% - 1 pnt% = maze%(x%, y%): RESTORE showmaze FOR z% = 1 TO pnt% + 1: READ col%: NEXT z% 'gets color info. PSET (x%, y%), col%: NEXT y%, x% COLOR 7: LOCATE 1, 34: PRINT "MazeGen": COLOR 6 LOCATE 3, 28: PRINT "A random maze": LOCATE 5, 29 PRINT "generator by": LOCATE 7, 25: PRINT "Charles Shampine" LOCATE 9, 37: PRINT "1998": RESTORE showmaze: FOR z% = 0 TO 2: READ col% NEXT: LOCATE 13, 30: COLOR col%: PRINT "START": PSET (278, 99), col% RESTORE showmaze: FOR z% = 0 TO 3: READ col%: NEXT LOCATE 15, 29: COLOR col%: PRINT "FINISH": PSET (278, 115), col% mazegame: 'A very simple game using the maze our SUB created. 'PLEASE NOTE- Routine gets maze data from the screen rather than 'the maze%(x,y) array. COLOR 7: LOCATE 22, 26: PRINT "Use ARROW keys": LOCATE 23, 29 PRINT "to navigate": penx% = startx%: peny% = starty% PSET (penx%, peny%), 14 DO: : DO: LOOP UNTIL INKEY$ = "" DO: PSET (penx%, peny%), 1: PSET (penx%, peny%), 14: ky$ = INKEY$ LOOP UNTIL ky$ <> "": openx% = penx%: openy% = peny% IF LEN(ky$) = 2 THEN 'arrow keys IF RIGHT$(ky$, 1) = "K" AND penx% > 0 THEN penx% = penx% - 1 IF RIGHT$(ky$, 1) = "M" AND penx% < maxcol% THEN penx% = penx% + 1 IF RIGHT$(ky$, 1) = "H" AND peny% > 0 THEN peny% = peny% - 1 IF RIGHT$(ky$, 1) = "P" AND peny% < maxrow% THEN peny% = peny% + 1 END IF chck% = POINT(penx%, peny%) IF chck% = 0 OR chck% = 1 OR chck% = 13 THEN PSET (penx%, peny%), 14: PSET (openx%, openy%), 7: PSET (startx%, starty%), 10 END IF IF chck% = 7 OR chck% = 10 THEN PSET (penx%, peny%), 14: PSET (openx%, openy%), 1 END IF IF chck% = 8 THEN penx% = openx%: peny% = openy% IF chck% = 13 THEN LOCATE 22, 26: PRINT " MAZE SOLVED! " LOCATE 23, 26: PRINT "PRESS ANY KEY!" DO: LOOP UNTIL INKEY$ = "" DO: LOOP UNTIL INKEY$ <> "": RUN END IF LOOP SUB MazeGen RESTORE: KEY OFF: RANDOMIZE TIMER DIM d%(3, 1): d%(0, 0) = 0: d%(0, 1) = 2: d%(1, 0) = -2: d%(1, 1) = 0 d%(2, 0) = 0: d%(2, 1) = -2: d%(3, 0) = 2: d%(3, 1) = 0: tries% = 0 n0% = 0: n1% = 1: n2% = 2: n3% = 3: n4% = 4: n5% = 5: n6% = 6 32101 tt% = maxcol% + maxrow%: cr# = ((tt% - 17) + 50) / 100 cr1# = ABS(maxcol% - maxrow%) * .6: tt% = tt% - cr1# limit% = INT(tt% * cr#): tries% = tries% + 1 'the following line is optional... LOCATE 1, 1: PRINT "# of attempts to create specified maze:"; tries% FOR x% = n0% TO maxcol% - n1%: FOR y% = n0% TO maxrow% - n1% maze%(x%, y%) = n6%: NEXT y%, x% 32102 finishx% = INT(RND * maxcol% - n1%) + n1%: finishy% = INT(RND * maxrow% - n1%) + n1% IF finishx% / n2% = INT(finishx% / n2%) OR finishy% / n2% = INT(finishy% / n2%) THEN 32102 startx% = n0%: starty% = n0%: xpos% = finishx%: ypos% = finishy% maze%(xpos%, ypos%) = n0% 32103 rr% = INT(RND(n1%) * n4%): x% = rr% 32104 ny% = ypos% + d%(rr%, n0%): nx% = xpos% + d%(rr%, n1%) IF ny% = finishy% AND nx% = finishx% THEN 32103 IF ny% < n1% OR ny% >= maxrow% - n1% OR nx% < n1% OR nx% >= maxcol% - n1% THEN 32105 IF maze%(nx%, ny%) = n6% THEN cnt% = cnt% + n1%: maze%(nx%, ny%) = rr% + n1% maze%((xpos% + d%(rr%, n1%) / n2%), (ypos% + d%(rr%, n0%) / n2%)) = n0% ypos% = ny%: xpos% = nx%: GOTO 32103 END IF 32105 rr% = INT(RND(n1%) * n4%): IF rr% <> x% THEN GOTO 32104 rr% = maze%(xpos%, ypos%) - n1%: IF rr% < n0% THEN 32105 maze%(xpos%, ypos%) = n0%: cnt% = cnt% - n1%: oy% = ypos%: ox% = xpos% ypos% = ypos% - d%(rr%, n0%): xpos% = xpos% - d%(rr%, n1%) IF ypos% = finishy% AND xpos% = finishx% THEN 32106 IF cnt% >= limit% AND flag% = n0% THEN starty% = oy%: startx% = ox%: flag% = n1% GOTO 32104 32106 IF startx% = n0% AND starty% = n0% THEN 32101 FOR y% = n1% TO maxrow% - n2%: FOR x% = n1% TO maxcol% - n2% IF maze%(x%, y%) = n6% THEN cnt% = n0%: FOR cy% = y% - n1% TO y% + n1% FOR cx% = x% - n1% TO x% + n1% IF maze%(cx%, cy%) <> n6% THEN cnt% = cnt% + n1% NEXT cx%, cy% IF cnt% > n0% THEN 32107 maze%(x%, y%) = n5% END IF 32107 NEXT x%, y% FOR y% = n1% TO maxrow% - n1%: FOR x% = n1% TO maxcol% - n1% IF maze%(x%, y%) = n5% THEN 32108 rr% = INT(RND(n1%) * n4%): rx% = x% + d%(rr%, n1%) ry% = y% + d%(rr%, n0%): IF rx% < n1% OR ry% < n1% THEN 32108 IF rx% > maxcol% - n1% OR ry% > maxrow% - n1% THEN 32108 IF maze%(rx%, ry%) = n0% THEN IF (rx% = finishx% AND ry% = finishy%) OR (rx% = startx% AND ry% = starty%) THEN 32109 maze%(x%, y%) = n0% maze%(x% + d%(rr%, n1%) / n2%, y% + d%(rr%, n0%) / n2%) = n0% END IF END IF 32109 NEXT x%, y%: FOR y% = n1% TO maxrow% - n1% FOR x% = n1% TO maxcol% - n1%: IF maze%(x%, y%) = n5% THEN 32107 NEXT x%, y%: maze%(finishx%, finishy%) = n3%: maze%(startx%, starty%) = n2% FOR x% = n0% TO maxcol% - n1%: FOR y% = n0% TO maxrow% - n1% pnt% = maze%(x%, y%): IF pnt% = n6% THEN maze%(x%, y%) = n1% NEXT y%, x%: EXIT SUB END SUB