Implementing Hunt-and-Kill
There really aren’t any surprises in the implementation here. As you’d expect, we start by choosing a cell at random, and then doing our random walk. In that respect, it looks a lot like our implementation of the Aldous-Broder algorithm. The similarity ends, though, when we discover we’ve boxed ourselves in, and there are no more unvisited neighbor cells. That triggers the hunt phase, where we’ll loop over the grid, looking for unvisited cells with visited neighbors.
Put the following in hunt_and_kill.rb.
| hunt_and_kill.rb | |
| Line 1 | class HuntAndKill |
| - | def self.on(grid) |
| - | current = grid.random_cell |
| - | |
| 5 | while current |
| - | unvisited_neighbors = current.neighbors.select { |n| n.links.empty? } |
| - | |
| - | if unvisited_neighbors.any? ... |
Get Mazes for Programmers now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
