# Random Maze

Taking a short break from the adventure game posts to show how to create simple random mazes in BB4W.  This algorithm was described to me by Clive Fraser, and thanks to Amy for showing me her implementation of it.

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