Instantly share code, notes, and snippets.

# jamis/ellers.rb

Created Dec 24, 2010
An implementation of Eller's algorithm for generating mazes
 # -------------------------------------------------------------------- # Eller's algorithm for maze generation. Novel in that it only # requires memory proportional to the size of a single row; this means # you can generate "bottomless" mazes with it, that just keep going # and going and going, using not only constant memory, but little # memory in general. # -------------------------------------------------------------------- # -------------------------------------------------------------------- # 1. Allow the maze to be customized via command-line parameters # -------------------------------------------------------------------- width = (ARGV || 10).to_i height = (ARGV || "-") == "-" ? nil : ARGV.to_i seed = (ARGV || rand(0xFFFF_FFFF)).to_i srand(seed) # -------------------------------------------------------------------- # 2. Set up constants to aid with describing the passage directions # -------------------------------------------------------------------- S, E = 1, 2 # -------------------------------------------------------------------- # 3. Data structures to assist the algorithm # -------------------------------------------------------------------- class State attr_reader :width def initialize(width, next_set=-1) @width = width @next_set = next_set @sets = Hash.new { |h,k| h[k] = [] } @cells = {} end def next State.new(width, @next_set) end def populate width.times do |cell| unless @cells[cell] set = @next_set += 1 @sets[set] << cell @cells[cell] = set end end self end def merge(sink_cell, target_cell) sink, target = @cells[sink_cell], @cells[target_cell] @sets[sink].concat(@sets[target]) @sets[target].each { |cell| @cells[cell] = sink } @sets.delete(target) end def same?(cell1, cell2) @cells[cell1] == @cells[cell2] end def add(cell, set) @cells[cell] = set @sets[set] << cell self end def each_set @sets.each do |id, set| yield id, set end end end def row2str(row, last=false) # the \r makes sure we always start at the beginning of the line, even after # ctrl-C (which prints "^C" to the console) s = "\r|" row.each_with_index do |cell, index| south = (cell & S != 0) next_south = (row[index+1] && row[index+1] & S != 0) east = (cell & E != 0) s << (south ? " " : "_") if east s << ((south || next_south) ? " " : "_") else s << "|" end end return s end state = State.new(width).populate row_count = 0 # -------------------------------------------------------------------- # 4. Eller's algorithm # -------------------------------------------------------------------- def step(state, finish=false) connected_sets = [] connected_set =  # --- # create the set of horizontally connected corridors in this row # --- (state.width-1).times do |c| if state.same?(c, c+1) || (!finish && rand(2) > 0) # cells are not joined by a passage, so we start a new connected set connected_sets << connected_set connected_set = [c+1] else state.merge(c, c+1) connected_set << c+1 end end connected_sets << connected_set # --- # create the set of vertically connected corridors from this row, but # only if this is not the last row # --- verticals = [] next_state = state.next unless finish state.each_set do |id, set| cells_to_connect = set.sort_by { rand }[0, 1 + rand(set.length-1)] verticals.concat(cells_to_connect) cells_to_connect.each { |cell| next_state.add(cell, id) } end end # --- # translate the connected sets and verticals into a bitmap that can be # returned and displayed # --- row = [] connected_sets.each do |connected_set| connected_set.each_with_index do |cell, index| last = (index+1 == connected_set.length) map = last ? 0 : E map |= S if verticals.include?(cell) row << map end end [next_state.populate, row] end # --- # allow ctrl-c to stop the program gracefully, letting the final row # be generated and displayed before aborting. # --- spinning = true trap("INT") { spinning = false } puts " " + "_" * (width * 2 - 1) while spinning state, row = step(state) row_count += 1 puts row2str(row) spinning = row_count+1 < height if height end state, row = step(state, true) row_count += 1 puts row2str(row) # -------------------------------------------------------------------- # 5. Show the parameters used to build this maze, for repeatability # -------------------------------------------------------------------- puts "#{\$0} #{width} #{row_count} #{seed}"

### JamesYeoman commented Aug 23, 2018

 The "last" parameter on line 80 is never used, the "return" on line 99 isn't needed and single quotes are recommended when you don't need string interpolation. I don't mean to be pedantic, but rubocop is going crazy with warnings about this code.

### DavidBechtel commented Dec 19, 2019

 What about entry and exit locations? How to define where to enter and exit the maze?
Owner Author

### jamis commented Dec 19, 2019

 @DavidBechtel, because the result is a perfect maze (meaning that there is exactly one path between any two locations in the maze), you can pick any entry and exit point you want, and be guaranteed that there is one path (or solution) between the two.