An implementation of Prim's algorithm for generating mazes.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -------------------------------------------------------------------- | |
# An implementation of Prim's algorithm for generating mazes. | |
# This is a pretty fast algorithm, when implemented well, since it | |
# only needs random access to the list of frontier cells. It does | |
# require space proportional to the size of the maze, but even worse- | |
# case, it won't be but a fraction of the size of the maze itself. | |
# As with Kruskal's, this algorithm tends to generate mazes with many | |
# short cul-de-sacs. | |
# -------------------------------------------------------------------- | |
# 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) | |
# -------------------------------------------------------------------- | |
# 2. Set up constants to aid with describing the passage directions | |
# -------------------------------------------------------------------- | |
N, S, E, W = 1, 2, 4, 8 | |
IN = 0x10 | |
FRONTIER = 0x20 | |
OPPOSITE = { E => W, W => E, N => S, S => N } | |
# -------------------------------------------------------------------- | |
# 3. Data structures and methods to assist the algorithm | |
# -------------------------------------------------------------------- | |
grid = Array.new(height) { Array.new(width, 0) } | |
frontier = [] | |
def add_frontier(x, y, grid, frontier) | |
if x >= 0 && y >= 0 && y < grid.length && x < grid[y].length && grid[y][x] == 0 | |
grid[y][x] |= FRONTIER | |
frontier << [x,y] | |
end | |
end | |
def mark(x, y, grid, frontier) | |
grid[y][x] |= IN | |
add_frontier(x-1, y, grid, frontier) | |
add_frontier(x+1, y, grid, frontier) | |
add_frontier(x, y-1, grid, frontier) | |
add_frontier(x, y+1, grid, frontier) | |
end | |
def neighbors(x, y, grid) | |
n = [] | |
n << [x-1, y] if x > 0 && grid[y][x-1] & IN != 0 | |
n << [x+1, y] if x+1 < grid[y].length && grid[y][x+1] & IN != 0 | |
n << [x, y-1] if y > 0 && grid[y-1][x] & IN != 0 | |
n << [x, y+1] if y+1 < grid.length && grid[y+1][x] & IN != 0 | |
n | |
end | |
def direction(fx, fy, tx, ty) | |
return E if fx < tx | |
return W if fx > tx | |
return S if fy < ty | |
return N if fy > ty | |
end | |
# -------------------------------------------------------------------- | |
# 4. Routines for displaying the maze | |
# -------------------------------------------------------------------- | |
def empty?(cell) | |
cell == 0 || cell == FRONTIER | |
end | |
def display_maze(grid) | |
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| | |
print "\e[41m" if cell == FRONTIER | |
if empty?(cell) && y+1 < grid.length && empty?(grid[y+1][x]) | |
print " " | |
else | |
print((cell & S != 0) ? " " : "_") | |
end | |
print "\e[m" if cell == FRONTIER | |
if empty?(cell) && x+1 < row.length && empty?(row[x+1]) | |
print((y+1 < grid.length && (empty?(grid[y+1][x]) || empty?(grid[y+1][x+1]))) ? " " : "_") | |
elsif cell & E != 0 | |
print(((cell | row[x+1]) & S != 0) ? " " : "_") | |
else | |
print "|" | |
end | |
end | |
puts | |
end | |
end | |
# -------------------------------------------------------------------- | |
# 5. Prim's algorithm | |
# -------------------------------------------------------------------- | |
print "\e[2J" # clear the screen | |
mark(rand(width), rand(height), grid, frontier) | |
until frontier.empty? | |
x, y = frontier.delete_at(rand(frontier.length)) | |
n = neighbors(x, y, grid) | |
nx, ny = n[rand(n.length)] | |
dir = direction(x, y, nx, ny) | |
grid[y][x] |= dir | |
grid[ny][nx] |= OPPOSITE[dir] | |
mark(x, y, grid, frontier) | |
display_maze(grid) | |
sleep 0.01 | |
end | |
display_maze(grid) | |
# -------------------------------------------------------------------- | |
# 6. Show the parameters used to build this maze, for repeatability | |
# -------------------------------------------------------------------- | |
puts "#{$0} #{width} #{height} #{seed}" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment