Generating mazes using recursion

What is recursion?

Recursion is a programming concept where a function calls itself. While this sounds like an inifite loop, and if poorly written it can be, the function is designed to stop calling itself once its goal is reached.

function recursive()
{
  if(goal_reached)
    return;

  recursive();
}

Why use recursion?

Recursion can be a useful way to break down certain complex problems into smaller, simpler pieces. It is also useful for iterating through complex data structures such as trees.

The power in recursion comes from its use of the call stack. Due to the recursive calls, the stack becomes a data structure in the algorithm, giving the code a way to keep track of, and get back to where it was. The downside of using the stack in this way is that most call stacks have a finite limit, so it is possible to overflow it if the algorithm recurses too far, so this must be kept in mind.

Using recursion to generate mazes

Maze generation is an excellent candidate for recursion. This complicated algorithm can be broken down into simpler pieces, just focusing on generating one cell at a time, and the call stack can be used to keep track of where the algorithm is in the maze, and how to get back. Here's how it works:

1. Create a data structure to represent the maze. A two dimensional array works well. Each entry in the array represents a cell in the maze, and has properties to represent the state of the cell (whether it's been visited yet or not) and which walls it has.
2. Create a function that evaluates a cell.
   1. In order to evaluate a cell, pick one of the four walls randomly and see if the next cell beyond that wall has been evaluated.
   2. If it has not, then remove the wall and then recall this function to evaluate that cell. This is where the recursion happens, and where we use the call stack to trace our path through the maze.
   3. If the other cell has been evaluated, then move on to the next wall and evaluate its cell neighbor.
   4. Once all four walls have been evaluated, end the function (goal met). This is where we leverage the call stack to unwind our path through the maze.

That's all there is to it. Seems really simple for such a complex problem doesn't it? This is the power of recursion and recursive functions!

Here is the pseudo Javascript code for this algorithm: // Create a two dimensional array and initialize all cells to be unevaluated and have all four walls

let maze = createTwoDimensionalArray(WIDTH, HEIGHT, {evaluated: false, walls: NORTH | SOUTH | EAST | WEST});

// Call evaluateCell on the first cell
// Note that I start with the finish cell and work backwards, this way there is only one path leading to the finish

evaluateCell(WIDTH - 1, HEIGHT - 1);

// Recursive function to evaluate a single cell

function evaluateCell(x, y)
{
  // Mark the cell as evaluated at the start so we don't circle back and get into an infinite loop

  maze[x][y].evaluated = true;

  // Pick a random wall to start evaluating and a random direction to continue the evaluation,
  // this is what makes the maze random

  let wall = pickRandomFromSet([NORTH, SOUTH, EAST, WEST]);
  let direction = pickRandomFromSet([CLOCKWISE, COUNTERCLOCKWISE]);

  // Iterate around each wall of the cell

  for(let i = 0; i < NUMBER_OF_WALLS; i++, wall = getNextWall(wall, direction))
  {
    // Look at the neighbor cell beyond the wall and see if it has been evaluated yet

    let neighbor = getNeighborCell(x, y, wall);
    if(!neighbor.evaluated)
    {
      // If the neighbor cell has not yet been evaluated,
      // then remove the wall between the cells
      // and recursively call this function again to evaluate the neighbor call

      clearWall(x, y, wall);
      evaluateCell(neighbor.x, neighbor.y);
    }
  }
}

Questions and feedback

If you have any questions about using recursion for maze generation, or have any feedback on this article, please contact me. I'll try my best to answer your questions, and I value your feedback!