Maze Generator

I really like this site. at the moment.  Maze Generator from xefer.com is as good as they come.  You can create any size maze (within reason) and then let the computer solve it.  The algorithm uses a depth first tree search to test each path in the maze.  Here you can see the grey path has been 'visited' and rejected.  The current path being investigated is shown in blue.  For really large mazes you will want to leave the app running in a spare tab as the animation takes up most of the run time.

Maze in Microsoft's Edge browser

Settings allow you to alter the width, height and size of each cell.  You can also change the anfractuosity of the maze.  Yes, I had to look 'anfractuosity' up.  It means twisty-ness.

+1 geek experience point awarded to xefer.com. Do go and check out their other projects which include a game of life simulator among other stuff.

Bored already?   Can't wait for the next superdecade games post?  You could either check out our website, have a game of Have Spell Will Travel, or check out all our posts about random maze algorithms.

Uh oh, Slime!

You find yourself trapped in a maze that is flooding with horrid #green #slime.  You had better bash those cursor keys and get out quickly!

Uh oh, Slime! is a simple maze game that uses the random maze generator.  Source code is provided below for your hacking fun.

5 levels of difficulty, so even your gran can play.

RUN!

You can download the source code and Windows Executable here, or find the The BBC BASIC Source code below:

     REM daft maze game
     REM Timothy Goliath Street
     REM superdecadegames.com
     REM ---------------------------
     REM VERSION HISTORY
     REM ---------------------------
     VERSION$ = "1.0.0.1"
     REM 2015-05-03

     MODE 10 : OFF :   OSCLI "escape off"
     PROC_preventResize

     REM find difficulty level
     CASE FN_showIntro OF
       WHEN "1"
         MAZE_WIDTH% = 15
         MAZE_HEIGHT% = 12
         CELL_WIDTH% = 96

       WHEN "2"
         MAZE_WIDTH% = 30
         MAZE_HEIGHT% = 24
         CELL_WIDTH% = 48

       WHEN "3"
         MAZE_WIDTH% = 60
         MAZE_HEIGHT% = 48
         CELL_WIDTH% = 24

       WHEN "4"
         MAZE_WIDTH% = 90
         MAZE_HEIGHT% = 72
         CELL_WIDTH% = 18

       WHEN "5"
         MAZE_WIDTH% = 120
         MAZE_HEIGHT% = 96
         CELL_WIDTH% = 12

     ENDCASE

     REM number of passes used by maze generator
     MAZE_COUNTER_LIMIT% = MAZE_WIDTH% * MAZE_HEIGHT% * 90

     REM set up a maze array
     DIM Maze%( MAZE_WIDTH%-1, MAZE_HEIGHT%-1 )

     _entrance% = 0 : REM position of the entrance

     DIM player{ x%, y% }

     delay% = 8
     SLIME_CHANCE% = 3

     wins% = 0
     losses% = 0

     REPEAT

       PROC_createMaze( Maze%(), _entrance% )

       REM player starts at the entrance
       player.x% = _entrance% : player.y% = 1
       dead% = FALSE : REM flag controls whether player is dead
       won% = FALSE : REM flag controls whether player has reached end
       numSteps% = 0 : REM the number of steps gone by

       REPEAT UNTIL INKEY(1) =-1

       REPEAT
         PROC_drawMaze( Maze%() )
         PROC_drawPlayer( player.x%, player.y% )

         TIME = 0
         g% = INKEY(delay%)
         WAIT delay% - TIME
         numSteps% += 1

         REM short delay before slime grows
         IF numSteps% > 20 THEN
           PROC_growSlime( Maze%() )
         ENDIF

         CASE g% OF
           WHEN 139 : REM up
             IF FN_canMove( Maze%(), player.x%, player.y%+1 ) THEN
               player.y% += 1
             ENDIF

           WHEN 136 : REM left
             IF FN_canMove( Maze%(), player.x%-1, player.y% ) THEN
               player.x% -= 1
             ENDIF

           WHEN 137 : REM right
             IF FN_canMove( Maze%(), player.x%+1, player.y% ) THEN
               player.x% += 1
             ENDIF

           WHEN 138 : REM down
             IF FN_canMove( Maze%(), player.x%, player.y%-1 ) THEN
               player.y% -= 1
             ENDIF

         ENDCASE

         REM check for death
         IF Maze%(player.x%, player.y%) = 2 THEN
           dead% = TRUE
         ENDIF
         REM check for victory
         IF player.y% = MAZE_HEIGHT%-1 THEN
           won% = TRUE
         ENDIF


       UNTIL dead% OR won%

       IF dead% losses% += 1 : PROC_showDead
       IF won% wins%+=1 : PROC_showWon

       PROC_clearMaze( Maze%() )
     UNTIL FALSE
     END



     DEFPROC_showDead
     LOCAL g
     OSCLI "refresh on":OSCLI "refresh"
     COLOUR 1, 0,0,0 : COLOUR 129 : CLS
     COLOUR 3, 0, 240, 0: COLOUR 3

     OSCLI "font Courier New, 44b"
     PRINTTAB(7,1) "OH NO! ":PRINTTAB(1,2)"THE SLIME GOT YOU!"
     OSCLI "font Courier New, 24"
     PRINTTAB(9)"wins: "STR$(wins%)" losses: "STR$(losses%)
     COLOUR 3, 200,200,200: COLOUR 3
     OSCLI "font Courier New, 18"
     PRINT '"  Press any key to start, or <SPACE> to reset."
     REPEAT UNTIL INKEY(1) = -1

     g = GET
     IF g= 32 RUN
     WAIT 100
     ENDPROC


     DEFPROC_showWon
     LOCAL g
     OSCLI "refresh on":OSCLI "refresh"
     COLOUR 1, 0,0,0 : COLOUR 129 : CLS
     COLOUR 3, 0, 240, 0: COLOUR 3

     OSCLI "font Courier New, 44b"
     PRINTTAB(2,1) "EXCELLENT!":PRINTTAB(3,2)"YOU ESCAPED!"
     OSCLI "font Courier New, 24"
     PRINTTAB(9)"wins: "STR$(wins%)" losses: "STR$(losses%)

     COLOUR 3, 200,200,200: COLOUR 3
     OSCLI "font Courier New, 18"
     PRINT '"  Press any key to start, or <SPACE> to reset."
     REPEAT UNTIL INKEY(1) = -1

     g = GET
     IF g= 32 RUN
     WAIT 100
     ENDPROC



     DEFFN_canMove( m%(), x%, y% )
     REM check for a path or slime
     IF m%(x%,y%) = 1 OR m%(x%,y%) = 2 THEN
       =TRUE
     ELSE
       =FALSE
     ENDIF


     DEFFN_showIntro
     LOCAL g$
     OSCLI "refresh on":OSCLI "refresh"
     COLOUR 1, 0,0,0 : COLOUR 129 : CLS
     COLOUR 2, 200,200,200: COLOUR 2
     OSCLI "font Courier New, 18"
     PRINTTAB(7,1)"Superdecade Games proudly presents..."
     OSCLI "font Courier New, 60b"
     COLOUR 3, 0, 240, 0: COLOUR 3
     PRINTTAB(1,1)"UH OH, SLIME!"
     COLOUR 2, 200,200,200: COLOUR 2

     OSCLI "font Courier New, 18"
     PRINT "       Use the cursor keys to escape from"
     PRINT "       the maze before the slime gets you." '
     OSCLI "font Courier New, 24b"
     PRINT "         (1) Don't hurt me!"
     PRINT "         (2) Novice"
     PRINT "         (3) Tricky"
     PRINT "         (4) Expert"
     PRINT "         (5) Impossible?"
     OSCLI "font Courier New, 18"
     PRINT'"          www.superdecade.blogspot.com"

     REPEAT
       g$ = GET$
     UNTIL g$ = "1" OR g$="2" OR g$="3" OR g$="4" OR g$="5"

     = g$


     DEFPROC_createMaze( m%(), RETURN _entrance% )
     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
     IF FN_placeExit( m%(), MAZE_HEIGHT%-1, MAZE_HEIGHT%-2, -1)

     REM place an exit on the bottom row
     _entrance% = FN_placeExit( m%(), 0, 1, 1 )

     REM make one slime at entrance
     m%(_entrance%, 0 ) = 2
     ENDPROC


     DEFFN_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
     REM returns the x position of the entrance/exit found
     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
     = x%



     DEFPROC_drawMaze( m%() )
     REM show the maze
     REM 0 - wall
     REM 1 - path
     REM 2 - slime
     LOCAL x%, y%
     COLOUR 2, 180,180,180: COLOUR 130 : CLS
     COLOUR 1, 100,100,100 : GCOL 0, 1
     COLOUR 3, 0,240,0 : GCOL 0, 3
     :
     OSCLI "refresh off"
     FOR x% = 0 TO MAZE_WIDTH%-1
       FOR y% = 0 TO MAZE_HEIGHT% -1
         IF m%(x%,y%)= 0 THEN
           GCOL 0, 1
           RECTANGLE FILL x%*CELL_WIDTH%,  y%*CELL_WIDTH%, CELL_WIDTH%, CELL_WIDTH%
         ENDIF
         IF m%(x%,y%)= 2 THEN
           GCOL 0, 3
           RECTANGLE FILL x%*CELL_WIDTH%,  y%*CELL_WIDTH%, CELL_WIDTH%, CELL_WIDTH%
         ENDIF

       NEXT
     NEXT
     OSCLI "refresh"
     ENDPROC


     DEFPROC_growSlime( m%() )
     REM if there is a path next to some slime, then there is a chance
     REM that slime will grow there
     LOCAL slime%()
     DIM slime%( MAZE_WIDTH%-1, MAZE_HEIGHT%-1)
     REM check for each clear space next to a slime
     FOR x% = 0 TO MAZE_WIDTH%-1
       FOR y% = 0 TO MAZE_HEIGHT% -1
         IF m%(x%,y%) = 2 THEN
           REM found slime, check next door
           IF x%-1 >= 0 THEN
             IF m%(x%-1,y%) = 1 THEN
               IF RND(SLIME_CHANCE%) = SLIME_CHANCE% slime%(x%-1,y%) = 2
             ENDIF
           ENDIF
           IF x%+1 <= MAZE_WIDTH%-1 THEN
             IF m%(x%+1,y%) = 1 THEN
               IF RND(SLIME_CHANCE%) = SLIME_CHANCE% slime%(x%+1,y%) = 2
             ENDIF
           ENDIF
           IF y%-1 >= 0 THEN
             IF m%(x%,y%-1) = 1 THEN
               IF RND(SLIME_CHANCE%) = SLIME_CHANCE%  slime%(x%,y%-1) = 2
             ENDIF
           ENDIF
           IF y%+1 <= MAZE_HEIGHT%-1 THEN
             IF m%(x%,y%+1) = 1 THEN
               IF RND(SLIME_CHANCE%) = SLIME_CHANCE%  slime%(x%,y%+1) = 2
             ENDIF
           ENDIF

         ENDIF
       NEXT
     NEXT
     FOR x% = 0 TO MAZE_WIDTH%-1
       FOR y% = 0 TO MAZE_HEIGHT% -1
         IF slime%(x%,y%) = 2 m%(x%,y%) = 2
       NEXT
     NEXT

     ENDPROC


     DEFPROC_drawPlayer( x%, y% )
     REM show player's position as a red circle
     OSCLI "refresh off"
     COLOUR 2, 250,0,0 : GCOL 0, 2
     CIRCLE FILL x%*CELL_WIDTH%+CELL_WIDTH% DIV 2,  y%*CELL_WIDTH%+CELL_WIDTH% DIV 2, CELL_WIDTH% DIV 2
     OSCLI "refresh"
     ENDPROC


     DEFPROC_clearMaze( m%() )
     REM remove all data from the maze array
     LOCAL x%, y%
     FOR x% = 0 TO MAZE_WIDTH%-1
       FOR y% = 0 TO MAZE_HEIGHT% -1
         m%(x%, y%) = 0
       NEXT
     NEXT
     ENDPROC


     DEF PROC_preventResize
     REM prevent user resizing window
     PRIVATE ws%
     SYS "GetWindowLong", @hwnd%, -16 TO ws%
     REM prevent user maximising window
     SYS "SetWindowLong", @hwnd%, -16, ws% AND NOT &50000
     ENDPROC


#programming #randommaze #slime

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