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

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.

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