Mazes for Programmers

The Hunt-and-Kill Algorithm

Hunt-and-Kill will seem, at first, very similar to the Aldous-Broder algorithm. We arbitrarily pick a cell to start, and then perform a random walk from there. The difference is that whereas Aldous-Broder allows you to step anywhere, even on cells that you’ve already visited, Hunt-and-Kill requires you to walk only on unvisited cells.

Let’s go through it.

Since we can start anywhere, we’ll just choose the southwest corner.

From there, we do a random walk, avoiding any cell that we’ve already visited. This is on purpose! Remember that the algorithm itself disallows revisiting cells during the random walk.

But hey, no ...