Mazes for Programmers/

...

/

Implementing the Hunt-and-Kill algorithm

Implementing the Hunt-and-Kill algorithm

Learn to implement the Hunt-and-Kill algorithm in Ruby.

We'll cover the following...

The HuntAndKill class

There really aren’t any surprises in the implementation here. As expected, 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’re at a dead end and there are no more unvisited neighbor cells. That triggers the hunt phase, where we loop over the grid, looking for unvisited cells with visited neighbors. Let's look at the code.

Press + to interact
class HuntAndKill
  def self.on(grid)
    current = grid.random_cell 
    while current 
      unvisited_neighbors = current.neighbors.select { |n| n.links.empty? } 
      if unvisited_neighbors.any? 
        neighbor = unvisited_neighbors.sample 
        current.link(neighbor) 
        current = neighbor 
      else 
        current = nil 
        grid.each_cell do |cell| 
          visited_neighbors = cell.neighbors.select { |n| n.links.any? }
          if cell.links.empty? && visited_neighbors.any? 
            current = cell 
            neighbor = visited_neighbors.sample 
            current.link(neighbor) 
            break 
          end
        end 
      end
    end
    grid
  end
end

Code explanation

The code has two parts corresponding to the two ...