Implementing Aldous-Broder
As might be expected, that 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.
Put the following code in a file named aldous_broder.rb. As before, we’ll put the algorithm in its own class so we can reuse it more easily.
| aldous_broder.rb | |
| Line 1 | class AldousBroder |
| - | |
| - | def self.on(grid) |
| - | cell = grid.random_cell |
| 5 | unvisited = grid.size - 1 |
| - | |
| - | while unvisited > 0 |
| - | neighbor = cell.neighbors.sample |
| - | |
| 10 | if neighbor.links.empty? |
| - | cell.link(neighbor) |
| - | unvisited -= 1 |
| - | end |
| - | |
| 15 | cell = neighbor |
| - | end |
| - | |
| - | grid |
| - | end |
| 20 | |
| - | end |
Line 4 starts everything off ...
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.
