Generate a 2D Maze Recursively

Reverend Jim 0 Tallied Votes 594 Views Share

This code generates an ascii maze of up to size 30x30. If you try to generate a larger maze then you will likely run out of stack space. There is no way to increase the size of the stack in vbscript.

Each cell in the maze is represented by a string of five characters such as "11110". The first four chars represent whether a wall is present ("1") or absent ("0") in the four directions "UDLR". The fifth char represents whether a cell has been visited ("1") or not ("0"). Each cell maintains its awareness of the four walls bounding it. When you move from one cell to the next, each cell must have its corresponding wall cleared. So from the point of view of the cell you are movng from, you must set its corresponding wall char to "0" as well as the wall in the next cell, which would be the cell in the opposite direction. For example, if you are moving right one cell you must clear the "R" wall ("11100") in the current cell, and the opposite, or "L" wall ("11010") in the cell you are moving to.

We keep visiting cells in random directions until we end up in a cell that has no "next" cell, either because we are at the edge of the maze, or all neighbouring cells have already been visited. Each time we visit a new cell we push down one more level in the recursion. At a dead end we pop out (backtrack) until we find a direction that hasn't been explored yet.

''#region Header                                                                        '
''                                                                                      '
''  Name:                                                                               '
''                                                                                      '
''      Maze.vbs                                                                        '
''                                                                                      '
''  Description:                                                                        '
''                                                                                      '
''      Generates a maze of size (0:MAXROW, 0:MAXCOL)                                   '
''                                                                                      '
''  Notes:                                                                              '
''                                                                                      '
''      Each element in the maze has five indicators, initially "11110" indicating      '
''      as follows:                                                                     '
''                                                                                      '
''          If there is a wall up, down, left, or right then the corresponding char     '
''          is set to "1", otherwise "0". The rightmost char is set to "1" if that      '
''          has been visited, otherwise "0".                                            '
''                                                                                      '
''      The maze is "walked" recursively in random directions. When a particular walk   '
''      reaches the point where it cannot proceed in any direction, the traversal Is    '
''      popped back a level until it reaches a level where it can proceed in an untried '
''      direction. When we pop back out of all levels we have visited every possible    '
''      cell and we can then print the maze.                                            '
''                                                                                      '
''  2018-03-16  rj  original code                                                       '
''                                                                                      '
''#endregion                                                                            '

'Get the maze dimensions from the command line. The maze does not have to be square.

If Wscript.Arguments.Count <> 2 Then
    Wscript.Echo "Maze numrows numcols"
    Wscript.Echo ""
    Wscript.Echo "   Where numrows and numcols are in the range [3,30]"
    Wscript.Quit 
End If

MAXROW = Wscript.Arguments(0)
MAXCOL = Wscript.Arguments(1)

If Not Validate(MAXROW,MAXCOL,3,30) Then
    Wscript.Echo "numrows and numcols must be integers in the range 3-30"
    Wscript.Quit 
End If    

'Use ExecuteGlobal to dimension because vbScript does not allow variables at run time

ExecuteGlobal "Dim maze(" & MAXROW & "," & MAXCOL & ")"
InitializeMaze

'Direction constants

Const C_UP    = "U"
Const C_DOWN  = "D"
Const C_LEFT  = "L"
Const C_RIGHT = "R"

' Visit all the cells starting at a random cell

Visit Random(0,MAXROW),Random(0,MAXCOL)

PrintMaze

''Wander through the maze recursively, removing walls as we go                          '
Sub Visit (ByVal row, ByVal col)

    Dim nrow        'next row in a random direction                         '
    Dim ncol        'next column in a random direction                      '
    Dim dir         'for iterating through all possible directions randomly '

    'Mark the current cell as having been visited

    SetVisited row, col

    ' Visit neighbors in all directions in random order

    For Each dir In RandomDirections()

        ' Get coordinates of the neighbor in the next random direction

        nrow = NextRow(row,dir)
        ncol = NextCol(col,dir)

        'Visit an unvisited neighbor, removing the separating walls. Note that each
        'cell has its own wall so to remove the wall between two adjacent cells we
        'must remove the corresponding wall in both cells.

        if Not Visited(nrow,ncol) Then
            RemoveWall row , col , dir 
            RemoveWall nrow, ncol, Opposite(dir)
            Visit nrow, ncol
        End If
        
    Next

End Sub

''Output the maze                                                                       '
Sub PrintMaze ()

    Dim row, col, line

    For row = 0 To MAXROW

        For Each line In Array("top","middle")
            For col = 0 To MAXCOL
                If line = "top" Then
                    Output "+"
                    Output IIF(hasWall(row,col,C_UP), "---" , "   ")
                    If col = MAXCOL Then Output "+"
                Else
                    Output IIF(hasWall(row,col,C_LEFT), "|" , " ")
                    Output "   "
                    If col = MAXCOL Then Output IIF(hasWall(row,col,C_RIGHT), "|" , " ")
                End If
            Next
            Output vbcrlf
        Next
        
    Next
    
    'Print the bottom row

    For col = 0 To MAXCOL
        Output "+---"
    Next
    Output "+" & VbCrLf

End Sub

''Given a direction, get its opposite                                                   '
Function Opposite(ByVal dir)

    Select Case dir
        Case C_UP    : Opposite = C_DOWN
        Case C_DOWN  : Opposite = C_UP
        Case C_LEFT  : Opposite = C_RIGHT
        Case C_RIGHT : Opposite = C_LEFT
    End Select

End Function

''Build a array of the four directions in random order.                                 '
Function RandomDirections ()

    Dim dirstr      'Random directions separated by a blank as "U L D R "
    Dim dir         'A randomly generated direction                     '
    
    dirstr = ""

    Do While Len(dirstr) < 8
        dir = Array(C_UP,C_DOWN,C_LEFT,C_RIGHT)(Random(0,3))
        If instr(dirstr,dir) = 0 Then
            dirstr = dirstr & dir & " "
        End If
    Loop
    
    'Convert "X X X X " to "X" "X" "X" "X"

    RandomDirections = Split(Trim(dirstr))

End Function

''Get column of the neighbor in a given a direction or -1 if outside the maze           '
Function NextCol (ByVal col, ByVal dir)

    if dir = C_LEFT  Then col = col - 1
    If dir = C_RIGHT Then col = col + 1
    NextCol = IIF(InMaze(0,col),col,-1)

End Function

''Get row of the neighbor in a given a direction or -1 if outside the maze              '
Function NextRow(ByVal row, ByVal dir)

    If dir = C_UP   Then row = row - 1
    if dir = C_DOWN Then row = row + 1
    NextRow = IIF(InMaze(row,0),row,-1)

End Function

''Mark a cell as visited.                                                               '
Sub setVisited(ByVal row, ByVal col)

    Dim cell: cell = getCell(row,col)
    If cell = "" Then Exit Sub
    setCell row, col, Left(cell,4) & "1"

End Sub

''Get the visited state of a cell. Return "1" if visited or outside maze, otherwise "0" '
Function Visited (ByVal row, ByVal col)

    Dim cell: cell = getCell(row,col)

    If cell = "" Then
        Visited = True
    Else
        Visited = Right(getCell(row,col),1) = "1"
    End If

End Function

''Remove a cell's wall in a given direction.                                            '
Sub RemoveWall (ByVal row, ByVal col, ByVal dir)

    Dim  cell, newCell

    cell = getCell(row,col)
    If cell = "" Then Exit Sub
    
    newCell = IIF(dir = C_UP   , "0", Mid(cell,1,1)) _
            & IIF(dir = C_DOWN , "0", Mid(cell,2,1)) _
            & IIF(dir = C_LEFT , "0", Mid(cell,3,1)) _
            & IIF(dir = C_RIGHT, "0", Mid(cell,4,1)) _
            & IIF(Visited(row,col),"1","0")

    setCell row, col, newCell
    
End Sub

''Return True if a cell has a wall in the given direction or if we are outside maze     '
Function hasWall (ByVal row, ByVal col, ByVal dir)

    Dim cell: cell = getCell(row,col)

    Select Case True
        Case cell = ""     : hasWall = True
        Case dir = C_UP    : hasWall = Mid(cell,1,1) = "1"
        Case dir = C_DOWN  : hasWall = Mid(cell,2,1) = "1"
        Case dir = C_LEFT  : hasWall = Mid(cell,3,1) = "1"
        Case dir = C_RIGHT : hasWall = Mid(cell,4,1) = "1"
    End Select

End Function

''Set the cell at maze(row,col) to a given value                                        '
Sub setCell (ByVal row, ByVal col, ByVal cell)
    If InMaze(row,col) Then maze(row,col) = cell
End Sub

''Get the cell at maze(row,col) if it exists. Return "" if outside maze                 '
Function getCell (ByVal row, ByVal col)
    If InMaze(row,col) Then
        getCell = maze(row,col)
    Else
        getCell = ""
    End If
End Function

''Return True if the given coordinates are in the maze                                  '
Function InMaze (ByVal row, ByVal col)
    InMaze = row >= 0 And row <= MAXROW And col >= 0 And col <= MAXCOL
End Function

''Initialize all cells to show all walls and not visited ("11110")                      '
Sub InitializeMaze ()

    Dim row, col

    For row = 0 To MAXROW
        For col = 0 To MAXCOL
            maze(row,col) = "11110"
        Next
    Next

End Sub

''Generate a random number in the range [lower,upper]                                   '
Function Random (ByVal lower , ByVal upper)
    Randomize: Random = Int((upper - lower + 1) * Rnd + lower)
End Function

''StdOut output                                                                         '
Sub Output (ByVal str)
    WScript.StdOut.Write(str)
End Sub

''Ternary function                                                                      '
Function IIF (cond, tval, fval)
    If cond Then IIF = tval: Else IIF = fval: End If
End Function

''Validate the inputs                                                                   '
Function Validate (ByRef MAXROW, ByRef MAXCOL, min, max)

    Validate = False
    
    If Not isNumeric(MAXROW) Then Exit Function
    If Not isNumeric(MAXCOL) Then Exit Function
    
    MAXROW = cInt(MAXROW)
    MAXCOL = cInt(MAXCOL)
    
    If MAXROW < min Or MAXROW > max Then Exit Function
    If MAXCOL < min Or MAXCOL > max Then Exit Function
    
    MAXROW = MAXROW - 1
    MAXCOL = MAXCOL - 1
    
    Validate = True
    
End Function
JamesCherrill 4,733 Most Valuable Poster Team Colleague Featured Poster

I also did a random maze program (Java) a while back, and was very happy to discover Kruskal's algorithm. It generates random perfect (exactly one solution) mazes very efficiently, and works for mazes with any kind of geometry. Well worth a quick Google.

Reverend Jim 4,678 Hi, I'm Jim, one of DaniWeb's moderators. Moderator Featured Poster

If anyone is wondering, "why vbscript?", the answer is

  1. everyone running Windows has access to it (included with Windows)
  2. the code is (I hope) simple and easy to follow (no obtuse language constructs)

For example, while lambda expressions may be concise, I find them anything but clear, especially to non-experts. A more lengthy (but clearer) programming construct can always be made more concise (but less clear) but that obfuscates the algorithm and I am coding here for educational/illustrative purposes rather than compactness or efficiency. That's mostly a result of my background as a maintenance programmer. Code efficiency was secondary to being able to quickly understand a piece of unfamiliar code.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.