Generate a 2D Maze Recursively

''#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