The algorithm creates a random maze on screen and garantees a complete path from start to finish.
In pseudocode it works as follows:
START WITH A GRID CONTAIN NOTHING BUT WALLS
TAKE A RANDOM START POINT AND CHANGE TO A PATH
REPEATEDLY
CHOOSE A RANDOM POSITION
IF THE POSITION HAS ONLY ONE CONNECTED PATH
CHANGE IT TO A PATH
 |
| A random maze with start and end points. |
Source code follows:
REM Random Maze
REM Timothy Goliath Street
REM 2014/12/18
MODE 10 : OFF
REM setup the maze grid
MAZE_WIDTH% = 60
MAZE_HEIGHT% = 48
CELL_WIDTH% = 24
MAZE_COUNTER_LIMIT% = MAZE_WIDTH% * MAZE_HEIGHT% * 30
DIM Maze%( MAZE_WIDTH%-1, MAZE_HEIGHT%-1 )
REPEAT
PRINT "Creating a maze..."
PROC_createMaze( Maze%() )
PROC_drawMaze( Maze%() )
REPEAT
MOUSE xclick%, yclick%, click%
UNTIL click% >0
PROC_clearMaze( Maze%() )
UNTIL FALSE
END
DEFPROC_createMaze( m%() )
LOCAL x%, y%
LOCAL mazeCounter%
REM create one empty space
REM somewhere in the grid
x% = RND(MAZE_WIDTH%-2)
y% = RND(MAZE_HEIGHT%-2)
m%(x%,y%) = 1 : REM set to path
REPEAT
x% = RND(MAZE_WIDTH%-2)
y% = RND(MAZE_HEIGHT%-2)
REM look around this space and
REM create a path if it links
REM to only one other space
IF m%(x%,y%+1)+m%(x%,y%-1)+m%(x%-1,y%)+m%(x%+1, y%) = 1 THEN
m%(x%,y%) = 1 : REM set to path
ENDIF
REM increment the maze pointer
mazeCounter% += 1
UNTIL mazeCounter% = MAZE_COUNTER_LIMIT%
REM place an exit on the top row
PROC_placeExit( m%(), MAZE_HEIGHT%-1, MAZE_HEIGHT%-2, -1)
REM place an exit on the bottom row
PROC_placeExit( m%(), 0, 1, 1 )
ENDPROC
DEFPROC_placeExit( m%(), placeRow%, checkRow%, dir% )
REM looks through the row for the first opportunity to
REM place an exit that joins up with existing path
REM dir -1 = check from right hand side
REM dir 1 = check from left hand side
LOCAL x%
LOCAL found%
IF dir% = -1 THEN x% = MAZE_WIDTH%-1
WHILE NOTfound% AND x%<MAZE_WIDTH% AND x%>-1
IF m%(x%, checkRow% ) = 1 THEN
found% = TRUE
m%(x%, placeRow%) = 1 : REM place exit
ELSE
x% += dir%
ENDIF
ENDWHILE
ENDPROC
DEFPROC_drawMaze( m%() )
LOCAL x%, y%
COLOUR 2, 0, 45, 178 : COLOUR 130 : CLS
COLOUR 1, 0, 255, 30 : GCOL 0, 1
OSCLI "refresh off"
FOR x% = 0 TO MAZE_WIDTH%-1
FOR y% = 0 TO MAZE_HEIGHT% -1
IF m%(x%,y%)= 0 THEN
RECTANGLE FILL x%*CELL_WIDTH%, y%*CELL_WIDTH%, CELL_WIDTH%, CELL_WIDTH%
ENDIF
NEXT
NEXT
OSCLI "refresh"
ENDPROC
DEFPROC_clearMaze( m%() )
LOCAL x%, y%
FOR x% = 0 TO MAZE_WIDTH%-1
FOR y% = 0 TO MAZE_HEIGHT% -1
m%(x%, y%) = 0
NEXT
NEXT
ENDPROC
The second program works similarly, however there is some additonal code for producing chambers within the maze. Students might like to take this code to produce the start an adventure game, or a pac-man-esque game.
 |
| Random maze with chambers. |
Source code follows:
REM Random Maze 02
REM Timothy Goliath Street
REM 2014/12/18
MODE 10 : OFF
REM setup the maze grid
MAZE_WIDTH% = 60
MAZE_HEIGHT% = 48
CELL_WIDTH% = 24
MAZE_COUNTER_LIMIT% = MAZE_WIDTH% * MAZE_HEIGHT% * 30
DIM Maze%( MAZE_WIDTH%-1, MAZE_HEIGHT%-1 )
REPEAT
PRINT "Creating a maze..."
PROC_createMaze( Maze%() )
PROC_drawMaze( Maze%() )
REPEAT
MOUSE xclick%, yclick%, click%
UNTIL click% >0
PROC_clearMaze( Maze%() )
UNTIL FALSE
END
DEFPROC_createMaze( m%() )
LOCAL x%, y%
LOCAL mazeCounter%
LOCAL roomCounter%, numRooms%
REM create one empty space
REM somewhere in the grid
x% = RND(MAZE_WIDTH%-2)
y% = RND(MAZE_HEIGHT%-2)
m%(x%,y%) = 1 : REM set to path
REPEAT
x% = RND(MAZE_WIDTH%-2)
y% = RND(MAZE_HEIGHT%-2)
REM look around this space and
REM create a path if it links
REM to only one other space
IF m%(x%,y%+1)+m%(x%,y%-1)+m%(x%-1,y%)+m%(x%+1, y%) = 1 THEN
m%(x%,y%) = 1 : REM set to path
ENDIF
REM increment the maze pointer
mazeCounter% += 1
UNTIL mazeCounter% = MAZE_COUNTER_LIMIT%
REM place some rooms
numRooms% = RND(MAZE_WIDTH%) + RND(MAZE_HEIGHT%)
WHILE roomCounter% < numRooms%
x% = RND(MAZE_WIDTH%-2)
y% = RND(MAZE_HEIGHT%-2)
IF m%(x%,y%+1)+m%(x%,y%-1)+m%(x%-1,y%)+m%(x%+1, y%) > 3 THEN
m%(x%,y%) = 1 : REM set to path
roomCounter% += 1
ENDIF
ENDWHILE
REM place an exit on the top row
PROC_placeExit( m%(), MAZE_HEIGHT%-1, MAZE_HEIGHT%-2, -1)
REM place an exit on the bottom row
PROC_placeExit( m%(), 0, 1, 1 )
ENDPROC
DEFPROC_placeExit( m%(), placeRow%, checkRow%, dir% )
REM looks through the row for the first opportunity to
REM place an exit that joins up with existing path
REM dir -1 = check from right hand side
REM dir 1 = check from left hand side
LOCAL x%
LOCAL found%
IF dir% = -1 THEN x% = MAZE_WIDTH%-1
WHILE NOTfound% AND x%<MAZE_WIDTH% AND x%>-1
IF m%(x%, checkRow% ) = 1 THEN
found% = TRUE
m%(x%, placeRow%) = 1 : REM place exit
ELSE
x% += dir%
ENDIF
ENDWHILE
ENDPROC
DEFPROC_drawMaze( m%() )
LOCAL x%, y%
COLOUR 2, 0, 45, 178 : COLOUR 130 : CLS
COLOUR 1, 0, 255, 30 : GCOL 0, 1
OSCLI "refresh off"
FOR x% = 0 TO MAZE_WIDTH%-1
FOR y% = 0 TO MAZE_HEIGHT% -1
IF m%(x%,y%)= 0 THEN
RECTANGLE FILL x%*CELL_WIDTH%, y%*CELL_WIDTH%, CELL_WIDTH%, CELL_WIDTH%
ENDIF
NEXT
NEXT
OSCLI "refresh"
ENDPROC
DEFPROC_clearMaze( m%() )
LOCAL x%, y%
FOR x% = 0 TO MAZE_WIDTH%-1
FOR y% = 0 TO MAZE_HEIGHT% -1
m%(x%, y%) = 0
NEXT
NEXT
ENDPROC