Search⌘ K
AI Features
Home
Courses
Mazes for Programmers

Solution: Modified Prim's Algorithm

Learn how to apply a modified version of Prim's algorithm to generate mazes by selecting cells from the frontier, distinguishing visited and unvisited neighbors, and growing the maze structure step-by-step.

We'll cover the following...

Solution

Let's execute the following solution code and see how it works:

C++
class ModifiedPrims
  def self.on(grid, start: grid.random_cell)
    visited = Set.new
    frontier = Set.new([ start ])
    while frontier.any?
      cell = frontier.entries.sample
      frontier.delete(cell)
      visited.add(cell)
      in_neighbors, out_neighbors = cell.neighbors.partition { |n| visited.include?(n) }
      in_neighbor = in_neighbors.sample 
      cell.link(in_neighbor) if in_neighbor
      frontier += out_neighbors 
    end
    grid
  end
end

Code explanation

...