Mazes for Programmers/

...

/

Implementing the Aldous-Broder Algorithm

Implementing the Aldous-Broder Algorithm

Learn to implement the Aldous-Broder algorithm in Ruby.

We'll cover the following...

The AldousBroder class

As might be expected, the random walk forms the core of our implementation, repeatedly visiting neighboring cells until no unvisited cells remain. It comes together without any surprises, just as described.

We'll create a new file named aldous_broder.rb. As before, we’ll put the algorithm in its own class so we can reuse it more easily.

Press + to interact
class AldousBroder
  def self.on(grid)
    cell = grid.random_cell 
    unvisited = grid.size - 1 
    while unvisited > 0 
      neighbor = cell.neighbors.sample 
      if neighbor.links.empty?
        cell.link(neighbor) 
        unvisited -= 1 
      end
      cell = neighbor 
    end
    grid
  end
end

Code explanation

Lines 4–5: We start everything off by choosing one cell at random. The random walk will begin at that cell. To make sure the algorithm knows when everything has been visited, line 5 ...