Mazes for Programmers

Hunt-and-Kill

In a nutshell:

Starting at an arbitrary location, perform a random walk, avoiding previously visited cells. When no more moves are possible, scan the grid, looking for an unvisited cell next to a visited cell. If found, connect the two, and resume the random walk. The algorithm terminates when it cannot find any unvisited cells.

Typical features:

Long, twisty passages (“high river”), with relatively few dead ends. Closely related to Recursive Backtracker, but potentially slower since it may scan every cell many times, though it has much lower memory requirements.

More information:

​The Hunt-and-Kill Algorithm​.