Maze Generation: Hunt-and-Kill algorithm

Posted by Jamis on January 24, 2011 @ 07:24 AM

(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!

Posted in Under the Hood

Comments

Have something to add? Click here to leave a comment.

24 Jan 2011

1. Matthijs van der Vleuten said...

You could speed up the hunt phase by remembering the first row with unvisited cells. Rows with only visited cells can’t become rows with unvisited cells.

2. Jamis said...

@Matthijs, exactly. That’s one of the simple optimizations I hinted at. It can speed up the later stages of the algorithm quite a bit.

3. Pito Salas said...

I am loving this series. I think you should make it into a book!

4. lakshmanan said...

cool :)

5. Jamis said...

@Pito, thanks! I’m definitely considering it. :)

6. Matt Jones said...

The comment in the conclusion raises an interesting question: is there a metric for defining “twistyness” or whatever you’d call the differences between the different maze types? I suspect that a relevant measure might be the maximum stack depth required by a recursive backtracker to find the path, but that may or may not really capture the obvious qualitative differences.

7. Jamis said...

@Matt, “Think Labyrinth” is more-or-less the definitive maze site on the Internet (http://www.astrolog.org/labyrnth/algrithm.htm), and the author there defines a concept called “river” that is used to describe whether a maze has longer passages and fewer dead-ends (“more river”) or shorter passages and more dead-ends (“less river”). I don’t know of a quantitative measure, but some ideas for one might be the ratio of dead-ends to the total number of cells in the maze, or maybe computing how many cells have more than 2 passages leading out of the (measuring the number of choices to be made in the traversing the maze). Interesting question!

8. TechNeilogy said...

For some reason, the mazes generated by this algorithm are visually challenging. It seems difficult to look and one and see a “Gestalt” solution. I think the long, twisty passages entail the visual flow more that algorithms with frequent intersections.

9. Stefano Mazzocchi said...

Good memories :-)

10. Jamis said...

Thanks for dropping in, Stefano! Good memories, indeed. :) As far as high-school-level “computer science” classes go, it left a lot to be desired, but it was fun to figure it out as we went along!

27 Jan 2011

11. Mike Subelsky said...

ahh but your dungeon generator lives on! http://www.myth-weavers.com/generate_dungeon.php – very impressive results!

12. Jamis said...

@Mike, isn’t that a PHP reimplementation of my generator? Mine was written in C and C++. I imagine the one at myth-weavers could just be a PHP wrapper around my code, though. If anyone knows for sure, I’d like to know. :)