Implementing the Recursive Backtracker
We’re going to implement more or less what was described in the previous section, using an explicit stack to manage the cells that have been visited. We’ll use an array to represent the stack (which is easy in Ruby, since Ruby’s arrays come preloaded with the standard push and pop stack operators). Put the following code in recursive_backtracker.rb.
| recursive_backtracker.rb | |
| Line 1 | class RecursiveBacktracker |
| - | |
| - | def self.on(grid, start_at: grid.random_cell) |
| - | stack = [] |
| 5 | stack.push start_at |
| - | |
| - | while stack.any? |
| - | current = stack.last |
| - | neighbors = current.neighbors.select { |n| n.links.empty? } |
| 10 | |
| - | if neighbors.empty? |
| - | stack.pop |
| - | else |
| - | neighbor = neighbors.sample |
| 15 | current.link(neighbor) ... |
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.
