Algorithm

The maze randomly generates a path through a matrix of four sided cells. Each cell has four boolean variables, numbered so that 0 represents north, 1 east, 2 south, and 3 west. For each cell, a random number chooses one wall to knock down, then moves to the corresponding adjacent cell.

The algorithm iterates recusively through the matrix, starting at (0, 0) and continuing until each cell has been visited once. The following pseudocode outlines the maze generation:

• Create a matrix of rows x columns cells
• Create a stack for visited cells
• Mark the top left corner as visited
• While there are unvisited cells:
  • If there are unvisited adjacent cells:
    • Pick a random direction in which there is an unvisited adjacent cell
    • Knock down the wall in that direction
    • Make that cell the new current cell
    • Push the cell onto the stack
  • Else it is a dead end:
    • Pop cells off the stack until there are unvisited neighboring cells
• Draw the maze, drawing a line if there is a wall