ellers.rb

# 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
# constant memory!

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

class EllersMaze
  attr_reader :row_count

  SOUTH = 0x01
  EAST  = 0x02

  def initialize(width)
    @row_count = 0
    @state = State.new(width).populate
    @finished = false
  end

  def width
    @state.width
  end

  def finished?
    @finished
  end

  def next_row(final=false)
    return if @finished
    @finished = final

    connected_sets = []
    connected_set = [0]

    (@state.width-1).times do |c|
      if @state.same?(c, c+1) || (!final && 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

    verticals = []
    next_state = @state.next

    unless final
      @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

    row = []
    connected_sets.each do |connected_set|
      connected_set.each_with_index do |cell, index|
        last = (index+1 == connected_set.length)
        map = last ? 0 : EAST
        map |= SOUTH if verticals.include?(cell)
        row << map
      end
    end

    @state = next_state.populate
    @row_count += 1

    return row
  end

  def finish
    next_row(true)
  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 & EllersMaze::SOUTH != 0)
    next_south = (row[index+1] && row[index+1] & EllersMaze::SOUTH != 0)
    east = (cell & EllersMaze::EAST != 0)

    s << (south ? " " : "_")

    if east
      s << ((south || next_south) ? " " : "_")
    else
      s << "|"
    end
  end

  return s
end

width = (ARGV[0] || 10).to_i
seed = (ARGV[1] || rand(0xFFFF_FFFF)).to_i

srand(seed)

spinning = true
trap("INT") { spinning = false }

maze = EllersMaze.new(width)

puts " " + "_" * (maze.width * 2 - 1)
puts row2str(maze.next_row) while spinning
puts row2str(maze.finish)

puts "rows: #{maze.row_count}"
puts "seed: #{seed}"