Maze Generation

Research

This Wikipedia article on maze generation algorithms was a great help.

1. Choose the initial cell, mark it as visited and push it to the stack
2. While the stack is not empty
   1. Pop a cell from the stack and make it a current cell
   2. If the current cell has any neighbours which have not been visited
      1. Push the current cell to the stack
      2. Choose one of the unvisited neighbours
      3. Remove the wall between the current cell and the chosen cell
      4. Mark the chosen cell as visited and push it to the stack

Implementation

Note: The current cell is shown in green with the cells in the stack shown in grey.

When the algorithm is backtracking, the cell is shown in pink.

Stack

One important feature of this algorithm is the use of a stack.

You can think of a stack like a pile of plates ready to be washed up - as you are given a plate you place it down on top of the previous, this is known as a ‘push’. When you go to wash one up you take it from the top of the pile, known as a ‘pop’. This is a last-in, first-out system.

In JavaScript/TypeScript, we can use an array for this structure. It helpfully has the methods push and pop that can be used exactly as needed.

The loop

When we visit a cell, we push it into the stack. We look at the neighbouring cells, that have not yet been visited, picking one at random, this becomes the next cell. We remove the wall between the current and the next. The next becomes our current cell. Repeat.

However, there comes a time when the current cell has no unvisited neighbours, we have no next cell to go to - we’ve reached a dead-end. This is where backtracking and the stack come into play.

We ‘pop’ an item from the stack and see if it has any unvisited neighbours. If it does, make this the current and carry on. If not, keep popping from the stack, checking for unvisited neighbours, until our stack becomes empty.

When the stack is empty we’re done!