Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A possible improvement on the kruskals-weave.rb algorithm that allows fully adjacent crossings.
# --------------------------------------------------------------------
# An implementation of a "weave" maze generator. Weave mazes are those
# with passages that pass both over and under other passages. The
# technique used in this program was described to me by Robin Houston,
# and works by first decorating the blank grid with the over/under
# crossings, and then using Kruskal's algorithm to fill out the rest
# of the grid. (Kruskal's is very well-suited to this approach, since
# it treats the cells as separate sets and joins them together.)
# --------------------------------------------------------------------
# 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
density = (ARGV[2] || 50).to_i
seed = (ARGV[3] || rand(0xFFFF_FFFF)).to_i
delay = (ARGV[4] || 0.01).to_f
srand(seed)
# --------------------------------------------------------------------
# 2. Set up constants to aid with describing the passage directions
# --------------------------------------------------------------------
N, S, E, W, U = 0x1, 0x2, 0x4, 0x8, 0x10
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. Data structures and methods to assist the algorithm
# --------------------------------------------------------------------
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 = {
0 => ["\e[47m \e[m", "\e[47m \e[m"],
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}"]
}
def display_maze(grid, sets, show_sets=false)
print "\e[H" # move to upper-left
grid.each_with_index do |row, y|
2.times do |i|
row.each { |cell| print TILES[cell][i] }
if show_sets && i == 1
print " "
sets[y].each { |set| print " %2s" % set.root.id.to_s(36) }
end
puts
end
end
end
class Tree
attr_accessor :parent
attr_reader :id
@@__next_id = -1
def self.next_id
@@__next_id += 1
end
def initialize
@parent = nil
@id = self.class.next_id
end
def root
@parent ? @parent.root : self
end
def connected?(tree)
root == tree.root
end
def connect(tree)
tree.root.parent = self
end
end
def next_non_U(grid, sets, x, y, dx, dy)
while (grid[y][x] & U) != 0
x += dx
y += dy
end
return [sets[y][x], x, y]
end
grid = Array.new(height) { Array.new(width, 0) }
sets = Array.new(height) { Array.new(width) { Tree.new } }
# build the list of edges
edges = []
height.times do |y|
width.times do |x|
edges << [x, y, N] if y > 0
edges << [x, y, W] if x > 0
end
end
edges = edges.sort_by{rand}
# --------------------------------------------------------------------
# 4. Build the over/under locations
# --------------------------------------------------------------------
print "\e[2J" # clear the screen
1.upto(height-2) do |cy|
1.upto(width-2) do |cx|
next unless rand(100) < density
if rand(2) == 0
grid[cy][cx] = E|W|U
else
grid[cy][cx] = N|S|U
end
ex, ey = cx+1, cy
sx, sy = cx, cy+1
edges.delete_if do |x, y, dir|
(x == cx && y == cy) ||
(x == ex && y == ey && dir == W) ||
(x == sx && y == sy && dir == N)
end
display_maze(grid, sets)
sleep(delay)
end
end
puts
puts "--- PHASE 1 DONE; PRESS ENTER TO START PHASE 2 ---"
STDIN.gets
1.upto(height-2) do |cy|
1.upto(width-2) do |cx|
next if (grid[cy][cx] & U) == 0
nx, ny = cx, cy-1
wx, wy = cx-1, cy
ex, ey = cx+1, cy
sx, sy = cx, cy+1
north_set, nnx, nny = next_non_U(grid, sets, nx, ny, 0, -1)
south_set, ssx, ssy = next_non_U(grid, sets, sx, sy, 0, +1)
west_set, wwx, wwy = next_non_U(grid, sets, wx, wy, -1, 0)
east_set, eex, eey = next_non_U(grid, sets, ex, ey, +1, 0)
north_set.connect(south_set) unless north_set.connected?(south_set)
west_set.connect(east_set) unless west_set.connected?(east_set)
grid[nny][nnx] |= S
grid[ssy][ssx] |= N
grid[wwy][wwx] |= E
grid[eey][eex] |= W
display_maze(grid, sets)
sleep(delay)
end
end
puts
puts "--- PHASE 2 DONE; PRESS ENTER TO START PHASE 3 ---"
STDIN.gets
print "\e[2J" # clear the screen
# --------------------------------------------------------------------
# 5. Kruskal's algorithm
# --------------------------------------------------------------------
until edges.empty?
x, y, direction = edges.pop
nx, ny = x + DX[direction], y + DY[direction]
set1, set2 = sets[y][x], sets[ny][nx]
unless set1.connected?(set2)
display_maze(grid, sets)
sleep(delay)
set1.connect(set2)
grid[y][x] |= direction
grid[ny][nx] |= OPPOSITE[direction]
end
end
display_maze(grid, sets)
# --------------------------------------------------------------------
# 6. Show the parameters used to build this maze, for repeatability
# --------------------------------------------------------------------
puts "#{$0} #{width} #{height} #{density} #{seed}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.