Mazes for Programmers

Recursive Backtracker

In a nutshell:

Starting at an arbitrary location, perform a random walk, avoiding previously visited cells. When no more moves are possible, backtrack to the most recently visited cell and resume the random walk from there. The algorithm ends when it tries to backtrack from the cell where it started.

Typical features:

Long, twisty passages (“high river”), with relatively few dead ends. Closely related to Hunt-and-Kill, but potentially faster, as it is guaranteed to visit every cell only twice, though it needs considerably more memory to keep track of previously visited cells.

More information:

​The Recursive Backtracker Algorithm ...