The Binary Tree Algorithm
Explore the Binary Tree algorithm for maze generation in this lesson. Learn how to create simple random mazes by deciding to carve passages north or east for each cell in a grid. Understand the algorithm's logic through examples and constraints, and gain practical insights into implementing it effectively.
We'll cover the following...
The Binary Tree algorithm for mazes
The Binary Tree algorithm is, quite possibly, the simplest algorithm around for generating a maze. As its name suggests, it merely requires us to choose between two possible options at each step. For each cell in the grid, we decide whether to carve a passage north or east. By the time we’ve done so for every cell, we have a maze!
This process of looking at cells is called visiting them. Visiting them in some order is walking the grid. Some walks might be random, choosing directions arbitrarily from step to step, like the ones we’ll see in this course. Others are more predictable. For Binary Tree, it turns out that we can do it either way. The algorithm really doesn’t care what order we use to visit the cells. Let's see how it's done below.