75x50 Maze generated by a binary tree algorithm.

Flooding starting on root cell: enhance how uniform is its structure

The binary tree generated representing its data structure topology.

Binary Tree Maze Generator is one of the very rare algorithms with the ability to generate a perfect maze without keeping any state at all: it is an exact memory-less 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).

A smaller maze generated, on which you may already see a binary tree.

Lets turn it by 45 to help the visualization.

Decomposing it within a path tree makes it fully clear.

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!

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 deterministic 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.

1. Because this algorithm doesn’t consider the state of any cells, it can be started anywhere. For conveniencce let's start on top-left corner.

2. Toissing the coint within the Nort boundary force us to connect all cells with the West neigbor (Impossible to carve North). This is one of the side-effects mentioned within the Texture section.

3. Next row, :
a. First cell can only be connected North (No West neighbor)
b. Second cell toss North
c. Third cell toss West
d. Coin will be tossed for the 4th cell.

4. By finishing iteration on each cells: Maze is done!