Binary Tree Maze Generator is one of the very rareful algorithms with the ability to generate a perfect maze without keeping any state at all: it is an exact memoryless Maze generation algorithm with no limit to the size of Maze you can create. It can build the entire maze by looking at each cell independently. This is the most straightforward and fastest algorithm possible.

Mazes generated are real Binary Tree Data Structure (cf. following images) while having a very biased texture (cf. Texture section).

As its name suggests, it merely requires you to choose between two possible options at each step: For each cell in the grid, toss a coin to decide whether to carve a passage north or west.

Steps

  • For each existing cell in the grid:
  • 1. Get if they exist, north or west neighbors.
  • 2. Toss a coin to connect with one of them.
  • It is already done!

Pseudo-Code

Maze BinaryTree(int width, int height)
{
  // For each existing cell in the grid, randomly carve a passage either north or west
  Maze maze(width, height);
  for (auto y = 0; y < height; ++y)
    for (auto x = 0; x < width; ++x)
    {
      // Get available neighbours (nort + west)
      if (x > 0) neighbours.push_back(maze[x - 1][y]);
      if (y > 0) neighbours.push_back(maze[x][y - 1]);

      // No possible connection
      if (neighbours.empty())
        continue;

      // Randomly connect whether south or east
      auto tossCoin = Random() % neighbours.size();
      mazeMatrix[x][y]->Connect(neighbours[tossCoin]);
    }

  return maze;
} 

Binary tree Mazes are different from standard perfect Mazes; since about half the cell types can never exist in them. For example, there will never be a crossroads, and all dead ends have passages pointing down or right, and never up or left.

The Maze tends to have a strong diagonal bias from upper left to lower right, where the Maze is much easier to navigate from the lower right to the upper left. You will always be able to travel up or left, but never both. Then, leading to the top left corner, you can always deterministically travel diagonally up and left without hitting any barriers to reach the root.

Last but not least, two of the four sides of the maze will be spanned by a single corridor due to its directional construction.