Recursive Division

The Recursive Division algorithm explained and illustrated

The Recursive Division algorithm is unique among the algorithms we’ve looked at for two reasons. First, it treats the maze as a fractal—a shape whose component parts are all identical (or nearly so) to the whole. Second, instead of carving passages like the other algorithms have done, this one begins with a wide open space and adds walls until a maze is produced. Algorithms of this nature are called wall adders (as opposed to passage carvers).

It works by dividing the grid into two subgrids, adding a wall between them and a single passage linking them. The algorithm is then repeated on each side, recursively, until the passages are the desired size.

Let’s walk through it. (It is recommended to keep the slides side-by-side when reading the steps).

1. We begin with an open grid with no interior walls. We can see in the slides below that the grid lines are shown in light gray to make it easier to see where the cells are, but they’re only for illustration.

2. We divide the grid in half, either horizontally or vertically, along any of those grid lines. Furthermore, we split it vertically, leaving two columns on the west side and three on the east.

3. Next, we add a passage through the wall anywhere along that wall.

4. That completes one iteration of the algorithm. This process now repeats, recursively, on each of the halves. Next, we process the western side, dividing it in half horizontally and leaving a single passage to connect the two areas.

5. The process repeats again, here dividing the northwestern region in half.

6. At this point, the regions that were created by the newest split are too small to divide further—we don’t want to split individual cells in half—so we jump over and start processing the remaining regions.

7. When we’re all done, having processed all the regions down to the size of a single cell, we have a maze.