Skip to content

Instantly share code, notes, and snippets.

@jamis
Created December 24, 2010 03:17
  • Star 8 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jamis/753860 to your computer and use it in GitHub Desktop.
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[0] || 10).to_i
height = (ARGV[1] || "-") == "-" ? nil : ARGV[1].to_i
seed = (ARGV[2] || 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 = [0]
# ---
# 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
Copy link

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
Copy link

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

@jamis
Copy link
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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment