Growing Tree Algorithm Maze Generator

The Growing Tree algorithm is interesting, because it can emulate the behavior of several other algorithms, depending on how the next cell is chosen during generation. The implementation on this page uses a breadth-first, queue-like approach.

A perfect maze is a maze in which there is exactly one path from any point in the maze to any other point. That means you can't end up going around in circles, but you will often encounter dead ends, forcing you to turn around and go back.

The maze maps generated here includes a default version without any start and finish positions, so you can decide those for yourself: there will be a solution from any point in the maze to any other point. If you want inspiration, you can enable a suggested start and finish position - and even see the solution between the two.

About the Growing Tree Algorithm

The Growing Tree algorithm is a flexible and powerful method for generating perfect mazes. The algorithm is interesting because it can emulate the behavior of several other maze generation algorithms, such as Prim's algorithm, recursive backtracking, and recursive division, depending on how you select the next cell to process.

How the Growing Tree Algorithm Works

Step 1: Initialization

• Start with a grid of unvisited cells.
• Choose a random starting cell and add it to a list.

Step 2: Maze Generation Loop

• While the cell list is not empty:
  • Select a cell from the list based on a specific strategy (explained below).
  • Carve a passage from the selected cell to one of its unvisited neighbors (chosen randomly).
  • Add the neighbor to the list since it's now part of the maze.
  • If the selected cell has no unvisited neighbors, remove it from the list.

Step 3: Termination

• The algorithm finishes when there are no more cells in the list, meaning the entire maze has been carved.

Cell Selection Strategies (Flexibility of the Algorithm)

The defining feature of the Growing Tree algorithm is how you choose which cell to process next. This choice dramatically affects the maze's appearance:

Newest Cell (Stack-like Behavior) – Recursive Backtracker:

• Always select the most recently added cell.
• Produces long, twisty corridors with many dead ends (like a depth-first search maze).
• Mazes tend to have long passages and are easy to solve.

Random Cell (Randomized Prim's Algorithm):

• Pick a random cell from the list each time.
• Creates a more evenly distributed maze with complex, tangled paths.
• Fewer long corridors and more branching.

Oldest Cell (Queue-like Behavior):

• Always choose the oldest cell in the list.
• Generates mazes with a more uniform spread, like a breadth-first search pattern.
• Short, bushy passageways with dense connections.
• (This is the version implemented here)

Hybrid Approaches:

Combine strategies for varied maze characteristics. For example:

• 90% newest, 10% random: Looks mostly like a recursive backtracker maze, but with occasional branches that break up long corridors.
• 50% newest, 50% oldest: Balances long corridors with bushy growth.