Maze Generator with Recursive Backtracker
The depth-first search algorithm of maze generation is frequently implemented using backtracking. This can be described with a following recursive routine:
- Given a current cell as a parameter,
- Mark the current cell as visited
- While the current cell has any unvisited neighbour cells
- Chose one of the unvisited neighbours
- Remove the wall between the current cell and the chosen cell
- Invoke the routine recursively for a chosen cell which is invoked once for any initial cell in the area.
A disadvantage of this approach is a large depth of recursion – in the worst case, the routine may need to recur on every cell of the area being processed, which may exceed the maximum recursion stack depth in many environments. As a solution, the same bactracking method can be implemented with an explicit stack, which is usually allowed to grow much bigger with no harm.
- Choose the initial cell, mark it as visited and push it to the stack
- While the stack is not empty
- Pop a cell from the stack and make it a current cell
- If the current cell has any neighbours which have not been visited
- Push the current cell to the stack
- Choose one of the unvisited neighbours
- Remove the wall between the current cell and the chosen cell
- Mark the chosen cell as visited and push it to the stack