Introduction to Random Walks (the Hunt-and-Kill Algorithm)

Adding constraints

Aimless random walking may be a good strategy if we absolutely need a perfectly unbiased algorithm, but for most purposes, it’s kind of excessive. An algorithm with the right kind of bias can often generate mazes that convey atmosphere, personality, or even challenge in a way that an unbiased algorithm can’t. Biases aren’t automatically a bad thing!

The Hunt-and-Kill algorithm explained and illustrated

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 while Aldous-Broder allows us to step anywhere, even on cells that we’ve already visited, Hunt-and-Kill requires us to only walk on unvisited cells.

Let’s go through the algorithm together by looking at the following slides.

1. 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.

2. This works just fine right up until the moment we find ourselves with no unvisited cells to move on to, meaning that we’ve ended at a cell surrounded by visited cells, and since we’re not allowed to walk on those, we’re stuck.

3. This is where we enter hunt mode. Starting at the top, we scan left to right until we encounter an unvisited cell, bordered by at least one visited cell. When we find it, we make it our current cell and link it to any one of its neighboring visited cells. In this case, we pick the first cell we encounter that meets our requirements. Since it only has one visited neighbor (the cell immediately to the south), we simply link the two together—if there had been two or more, we’d have picked one at random.

4. We walk the random walk again, as far as we’re able to.

5. Then, once again, we scan row-by-row from the northwest corner, looking for another unvisited cell with at least one visited neighbor, and then carve another random walk from there.

6. This process repeats until the hunt phase can't find any more unvisited cells, at which point we know the maze is finished.

The algorithm has been explained with illustrations in the slides below.