Mazes for Programmers

Recursive Division

The Recursive Division algorithm is unique among the algorithms we’ve looked at, for two reasons. First of all, 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.

We begin with an open grid, with no interior ...