The Buckblog

(Note: if you’re reading this in a feed reader, you’re going to be missing out on the illustrations and demonstrations.)

Alright, so the theme last week was “algorithms for generating uniform spanning trees.” If this week has a theme, it might be something like “algorithms that sometimes act like the recursive backtracker, but only kind of.”

Today’s algorithm is the “hunt-and-kill algorithm”. Sounds violent, doesn’t it? It’s actually quite tame. In a nutshell, it works like this:

1. Choose a starting location.
2. Perform a random walk, carving passages to unvisited neighbors, until the current cell has no unvisited neighbors.
3. Enter “hunt” mode, where you scan the grid looking for an unvisited cell that is adjacent to a visited cell. If found, carve a passage between the two and let the formerly unvisited cell be the new starting location.
4. Repeat steps 2 and 3 until the hunt mode scans the entire grid and finds no unvisited cells.

Let’s walk through an example.

An example

I’ll just use a basic 4×4 grid:

Now, I’ll give you the walk phase as a sequence of frames here; it’s not that interesting, really, until it reaches a dead-end.

And there our liesurely inebriated stroll comes to a screeching halt. All possible directions lead either out of bounds, or into an already-visited neighbor. At this point, the recursive backtracker would begin backtracking, looking for a previously visited cell in the stack that had unvisited neighbors. The hunt-and-kill algorithm is not nearly so sophisticated: stuck? Go hunting.

And so we hunt. Beginning at the first row, we begin scanning each row for an unvisited cell with a visited neighbor. It turns out to be our lucky day: our very first cell is a match: unvisited, with a visited neighbor. We connect the two:

And then we start a random walk from our new starting point:

Stuck again, so we go hunting. There are no cells in the first row that match:

And no matches in the second row, either. (Remember, we’re looking for unvisited cells with visited neighbors.)

The third row, however, has a match in its last cell:

So, we connect that unvisited cell to any one of its visited neighbors (at random), and do our random walk:

And we again stub our digital toes (see what I did there?) on another dead-end. We’re stuck, so we go hunting again, looking row-by-row for an unvisited cell.

The scan completed without finding any unvisited cells, so the algorithm terminates and leaves us with our maze.

Try the following demonstrations to see how the algorithm behaves at larger resolutions:

Implementation

This algorithm is pretty straightforward to implement. It even has a few simple optimizations that you can do, though I won’t touch on those here.

My implementation begins by choosing a random starting point, and then looping over the two phases, “walk” and “hunt”, until the hunt phase terminates without finding any new location. My walk and hunt implementations both return either a two-element array (indicating the coordinates of the next starting location), or a nil (indicating that the phase in question has terminated).

1
2
3
4
5
6
7

x, y = rand(width), rand(height)

loop do
  x, y = walk(grid, x, y)
  x, y = hunt(grid) unless x
  break unless x
end

The walk implementation is straightforward. It just iterates over a randomized list of directions, and returns nil if none of the directions are valid:

1
2
3
4
5
6
7

def walk(grid, x, y)
  [N, S, E, W].shuffle.each do |dir|
    # ...
  end

  nil
end

For each direction, it computes the neighbor in that direction, and then tests it to see if it is within the bounds of the maze and unvisited:

1
2
3
4

nx, ny = x + DX[dir], y + DY[dir]
if nx >= 0 && ny >= 0 && ny < grid.length && nx < grid[ny].length && grid[ny][nx] == 0
  # ..
end

When a neighbor is found that fits the bill, the neighbor and the current cell are connected, and the neighbor is returned as the new current cell:

1
2
3

grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]
return [nx, ny]

The hunt phase, on the other hand, is a little more involved (but not much). It iterates over each cell in the grid, row-wise, skipping visited cells, and returning nil if it does not find any unvisited cellls:

1
2
3
4
5
6
7
8
9
10
11

def hunt(grid)
  grid.each_with_index do |row, y|
    row.each_with_index do |cell, x|
      next unless cell == 0

      # ...
    end
  end

  nil
end

Within that innermost loop, if the cell is unvisited, we compute a list of neighbors that are already part of the maze:

1
2
3
4
5

neighbors = []
neighbors << N if y > 0 && grid[y-1][x] != 0
neighbors << W if x > 0 && grid[y][x-1] != 0
neighbors << E if x+1 < grid[y].length && grid[y][x+1] != 0
neighbors << S if y+1 < grid.length && grid[y+1][x] != 0

Then, we randomly choose one of them (skipping to the next cell if there are no neighbors to select):

1

direction = neighbors[rand(neighbors.length)] or next

Then, we compute the coordinates of the neighbor in the chosen direction, carve a passage to it, and then return the new current coordinates:

1
2
3
4
5
6

nx, ny = x + DX[direction], y + DY[direction]

grid[y][x] |= direction
grid[ny][nx] |= OPPOSITE[direction]

return [x, y]

And there’s your hunt-and-kill algorithm!

Conclusion

The random walk phase tends to produce long, windy passages that are reminiscent of the recursive backtracking algorithm, so if you like the aesthetic of one, you’ll probably enjoy the other, too. Both algorithms produce mazes with fewer dead-ends than most of the other algorithms.

The hunt-and-kill algorithm will always have a place in my heart, because it was a variation on it that introduced me to maze generation back in high school. It was first shown to me by Stefano Mazzocchi when he was an exchange student at my alma mater (Siuslaw High School, in tiny Florence, Oregon). In fact, it was this variation on the hunt-and-kill that I used when I wrote a (somewhat popular) random dungeon generator for D&D back in 2001! (All that remains now is some C source code on GitHub, alas.)

Anyway, enough nostalgic wallowing. Have a go at the hunt-and-kill algorithm, and share links to your creations in the comments. For reference, the complete source for my own implementation is here:

Enjoy!