Skip to content

Instantly share code, notes, and snippets.

@jamis
Created March 4, 2011 05:23
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jamis/854218 to your computer and use it in GitHub Desktop.
Save jamis/854218 to your computer and use it in GitHub Desktop.
A "weave" maze implementation, using the Growing Tree maze algorithm.
# --------------------------------------------------------------------
# An implementation of a "weave" maze (with over/under passages),
# using the Growing Tree maze generation algorithm.
# --------------------------------------------------------------------
# --------------------------------------------------------------------
# Helper data and methods
# --------------------------------------------------------------------
N, S, E, W, U = 0x01, 0x02, 0x04, 0x08, 0x10
OPP = { N => S, S => N, E => W, W => E }
DX = { N => 0, S => 0, E => 1, W => -1 }
DY = { N => -1, S => 1, E => 0, W => 0 }
CROSS = { N => E|W, S => E|W, E => N|S, W => N|S }
def can_weave?(grid, dir, x, y)
cell = grid[y][x]
return false unless cell == CROSS[dir]
nx, ny = x + DX[dir], y + DY[dir]
return ny.between?(0, grid.length-1) && nx.between?(0, grid[ny].length-1) && grid[ny][nx] == 0
end
# --------------------------------------------------------------------
# Allow the maze to be customized via the command-line
# --------------------------------------------------------------------
width = (ARGV.shift || 10).to_i
height = (ARGV.shift || width).to_i
# --------------------------------------------------------------------
# Data structures
# --------------------------------------------------------------------
grid = Array.new(height) { Array.new(width, 0) }
list = [[rand(width), rand(height)]]
carved = nil
# --------------------------------------------------------------------
# Growing tree algorithm
# --------------------------------------------------------------------
while list.any?
## recursive-backtracker
index = list.length-1
## prim-like
# index = rand(list.length)
x, y = list[index]
directions = [N, S, E, W].shuffle
directions.unshift(carved) if carved && rand(2) > 0
carved = nil
directions.each do |dir|
nx, ny = x + DX[dir], y + DY[dir]
if nx.between?(0, width-1) && ny.between?(0, height-1)
if grid[ny][nx] == 0
grid[y][x] |= dir
grid[ny][nx] |= OPP[dir]
list << [nx, ny]
carved = dir
elsif can_weave?(grid, dir, nx, ny)
grid[y][x] |= dir
if rand(2) == 0
grid[ny][nx] |= U
elsif (grid[ny][nx] & N) != 0
grid[ny][nx] = E|W|U
else
grid[ny][nx] = N|S|U
end
nx, ny = nx + DX[dir], ny + DY[dir]
grid[ny][nx] |= OPP[dir]
list << [nx, ny]
carved = dir
end
break if carved
end
end
list.delete_at(index) unless carved
end
# --------------------------------------------------------------------
# Display the maze using Unicode characters (for a more unambiguous
# representation)
# --------------------------------------------------------------------
EW, NS, SE, SW, NE, NW = [0x80, 0x82, 0x8C, 0x90, 0x94, 0x98].map { |v| "\xE2\x94#{v.chr}" }
NSE, NSW, EWS, EWN = [0x9C, 0xA4, 0xAC, 0xB4].map { |v| "\xE2\x94#{v.chr}" }
TILES = {
N => ["#{NS} #{NS}", "#{NE}#{EW}#{NW}"],
S => ["#{SE}#{EW}#{SW}", "#{NS} #{NS}"],
E => ["#{SE}#{EW}#{EW}", "#{NE}#{EW}#{EW}"],
W => ["#{EW}#{EW}#{SW}", "#{EW}#{EW}#{NW}"],
N|S => ["#{NS} #{NS}", "#{NS} #{NS}"],
N|W => ["#{NW} #{NS}", "#{EW}#{EW}#{NW}"],
N|E => ["#{NS} #{NE}", "#{NE}#{EW}#{EW}"],
S|W => ["#{EW}#{EW}#{SW}", "#{SW} #{NS}"],
S|E => ["#{SE}#{EW}#{EW}", "#{NS} #{SE}"],
E|W => ["#{EW}#{EW}#{EW}", "#{EW}#{EW}#{EW}"],
N|S|E => ["#{NS} #{NE}", "#{NS} #{SE}"],
N|S|W => ["#{NW} #{NS}", "#{SW} #{NS}"],
E|W|N => ["#{NW} #{NE}", "#{EW}#{EW}#{EW}"],
E|W|S => ["#{EW}#{EW}#{EW}", "#{SW} #{SE}"],
N|S|E|W => ["#{NW} #{NE}", "#{SW} #{SE}"],
N|S|U => ["#{NSW} #{NSE}", "#{NSW} #{NSE}"],
E|W|U => ["#{EWN}#{EW}#{EWN}", "#{EWS}#{EW}#{EWS}"]
}
height.times do |y|
2.times do |row|
width.times { |x| print TILES[grid[y][x]][row] }
puts
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment