Depth First Search (DFS) Maze Generator is a randomized version of the depth-first search traversal algorithm. Implemented with a stack, this approach is one of the simplest ways to generate a maze.

Let's first have a look on the DFS traversal algorithm: One starts at any cell and explores as far as possible along each branch before backtracking.

To generate a maze, we just have to randomize the traversal: meaning we pick a random but unvisited neighbor to continue our traversal. When we hit a dead end (cell with no unvisited neighbors), we 'backtrack' to the most recent cell in the stack.

Steps

  • Choose a starting cell in the field and add it to the stack.
  • While there is cell to be handled in the stack:
  • 1. Pop cell from the top of the stack.
  • 2. Connect and visit all available neighbours from: bottom, left, right, top and unvisited.
  • 3. Randomly select the one to be on the top and Push those neighbours on the stack.

Pseudo-Code

Maze DFS(int width, int height, Cell startCell)
{
  Maze maze(width, height);
  Stack pathStack(startCell);

  // While there is node to be handled in the stack
  while (!pathStack.empty())
  {
    // Handle the cell at the top of the stack:
    // Get available neighbours from bottom, left, right, top and unvisited
    Cell cell = pathStack.pop();
    auto neighbours = GetAvailableNeighbours(maze, cell);

    // If there is avaible node to process (loop to backtrack - 'pop' otherwise)
    if (!neighbours.empty())
    {
      // Randomly select a node to be processed
      auto randIdx = Random() % neighbours.size();

      // For each available node: connect to the cell, mark it as visited
      // and push it into the stack.
      for (auto i = 0; i < neighbours.size(); ++i)
      {
        cell->Connect(Cell::Visite(neighbours[i]));

        // Only the choosen item should be add to the top following a DFS strategy
        if (i != randIdx) pathStack.push(neighbours[i]);
      }

      // Add the choosen node as the next one to be processed
      pathStack.push(neighbours[randIdx]);
    }
  }

  return maze;
} 

Mazes generated have a low branching factor and contain many long corridors, because the algorithm explores as far as possible along each branch before 'backtracking' (using previous cell on the stack).

The River characteristic means that when creating the Maze, the algorithm will look for and clear out nearby cells: It flows into the Maze like water. DFS Mazes tend to have a main River, resulting in a large amount of short dead ends.

All of this makes depth-first a good algorithm for generating mazes in video games.
In mazes generated by that algorithm, it will typically be relatively easy to find the way to the root since most paths lead to or from there, but it is hard to find the way out.