Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
An implementation of the Aldous-Broder algorithm for generating mazes.
# --------------------------------------------------------------------
# An implementation of Aldous-Broder's algorithm for generating mazes.
# This is an easy one to implement, but it is also one of the
# "dumbest" (meaning least intelligent) algorithms. It is not even
# guaranteed to finish, if you get really unlucky with the RNG.
# Watching the animation of its progress can be an exercise in
# frustration as you find yourself urging the cursor to JUST GO
# OVER THERE! Try and it see for yourself. :)
# --------------------------------------------------------------------
# NOTE: the display routine used in this script requires a terminal
# that supports ANSI escape sequences. Windows users, sorry. :(
# --------------------------------------------------------------------
# --------------------------------------------------------------------
# 1. Allow the maze to be customized via command-line parameters
# --------------------------------------------------------------------
width = (ARGV[0] || 10).to_i
height = (ARGV[1] || width).to_i
seed = (ARGV[2] || rand(0xFFFF_FFFF)).to_i
srand(seed)
grid = Array.new(height) { Array.new(width, 0) }
# --------------------------------------------------------------------
# 2. Set up constants to aid with describing the passage directions
# --------------------------------------------------------------------
N, S, E, W = 1, 2, 4, 8
DX = { E => 1, W => -1, N => 0, S => 0 }
DY = { E => 0, W => 0, N => -1, S => 1 }
OPPOSITE = { E => W, W => E, N => S, S => N }
# --------------------------------------------------------------------
# 3. A simple routine to emit the maze as ASCII
# --------------------------------------------------------------------
def display_maze(grid, cx=nil, cy=nil)
print "\e[H" # move to upper-left
puts " " + "_" * (grid[0].length * 2 - 1)
grid.each_with_index do |row, y|
print "|"
row.each_with_index do |cell, x|
if cx == x && cy == y
print "\e[43m" # cursor is yellow
elsif cell == 0
print "\e[47m" # unvisited is white
end
print((cell & S != 0) ? " " : "_")
print "\e[0m"
if cell & E != 0
print(((cell | row[x+1]) & S != 0) ? " " : "_")
else
print "|"
end
end
puts
end
end
# --------------------------------------------------------------------
# 4. The Aldous-Broder algorithm
# --------------------------------------------------------------------
print "\e[2J" # clear screen
x, y = rand(width), rand(height)
remaining = width * height - 1
while remaining > 0
display_maze(grid, x, y)
sleep 0.02
[N,S,E,W].shuffle.each do |dir|
nx, ny = x + DX[dir], y + DY[dir]
if nx >= 0 && ny >= 0 && nx < width && ny < height
if grid[ny][nx] == 0
grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]
remaining -= 1
end
x, y = nx, ny
break
end
end
end
display_maze(grid)
# --------------------------------------------------------------------
# 5. Show the parameters used to build this maze, for repeatability
# --------------------------------------------------------------------
puts "#{$0} #{width} #{height} #{seed}"
@defunkt

This comment has been minimized.

Show comment Hide comment
@defunkt

defunkt Dec 31, 2010

This is great.

defunkt commented Dec 31, 2010

This is great.

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