Search⌘ K
AI Features
Home
Courses
Mazes for Programmers

Implementing Eller's Algorithm

Explore the implementation of Eller's algorithm to generate mazes one row at a time using a row-centric state object. Understand managing cell sets, linking adjacent cells, carving paths south, and merging sets. Learn to compare Eller's results with other maze algorithms like Sidewinder to solidify your grasp of maze generation techniques.

We'll cover the following...

The Ellers class

Eller’s algorithm works strictly one row at a time, so our implementation will take advantage of that by leaning on a row-centric state object. Once we have that state object, the rest of the algorithm comes together quickly. We’ll start with the RowState class, which we’ll place under the namespace of the Ellers class. So, let’s first create the RowState class.

The RowState class

C++
  class RowState
    def initialize(starting_set=0)
      @cells_in_set = {}
      @set_for_cell = []
      @next_set = starting_set
    end
    def record(set, cell)
      @set_for_cell[cell.column] = set
      @cells_in_set[set] = [] if !@cells_in_set[set]
      @cells_in_set[set].push cell
    end
    def set_for(cell)
      if !@set_for_cell[cell.column]
        record(@next_set, cell)
        @next_set += 1
      end
      @set_for_cell[cell.column]
    end
    def merge(winner, loser)
      @cells_in_set[loser].each do |cell|
        @set_for_cell[cell.column] = winner
        @cells_in_set[winner].push cell
      end
      @cells_in_set.delete(loser)
    end
    def next
      RowState.new(@next_set)
    end
    def each_set
      @cells_in_set.each { |set, cells| yield set, cells }
      self
    end
  end

Code explanation

Lines 2–6: The initialize method has a starting_set parameter (defaulting to 0), which ...