True Prim’s Algorithm
Although the algorithm we’ll implement next is called a “true” Prim’s algorithm, it’s still slightly modified. Rather than assigning weights to passages, it assigns weights to cells, and then chooses cells based on those costs. This gives us mazes very similar to those from a fully passage-weighted Prim’s algorithm, and for significantly less effort.
Open up prims.rb again and add the following class at the bottom of it:
| | class TruePrims |
| | |
| | def self.on(grid, start_at: grid.random_cell) |
| | active = [] |
| | active.push(start_at) |
| | |
* | costs = {} |
* | grid.each_cell { |cell| costs[cell] = rand(100) } |
| | |
| | while active.any? |
* | cell = active.min { |a,b| costs[a] <=> costs[b] } |
| | available_neighbors = cell.neighbors.select { |n| n.links.empty? ... |
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.
