public
Last active

An implementation of Kruskal's algorithm for generating mazes.

  • Download Gist
kruskals.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
# --------------------------------------------------------------------
# An implementation of Kruskal's algorithm for generating mazes.
# Fairly expensive, memory-wise, as it requires memory proportional
# to the size of the entire maze, and it's not the fastest of the
# algorithms (what with all the set and edge management is has to
# do). Also, the mazes it generates tend to have a lot of very short
# dead-ends, giving the maze a kind of "spiky" look.
# --------------------------------------------------------------------
# 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
delay = (ARGV[3] || 0.01).to_f
 
srand(seed)
 
# --------------------------------------------------------------------
# 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. Data structures to assist the algorithm
# --------------------------------------------------------------------
 
class Tree
attr_accessor :parent
 
def initialize
@parent = nil
end
 
def root
@parent ? @parent.root : self
end
 
def connected?(tree)
root == tree.root
end
 
def connect(tree)
tree.root.parent = self
end
end
 
class Maze
attr_reader :grid, :width, :height
 
def initialize(w,h)
@width, @height = w, h
 
@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}
end
 
def display
print "" # 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 "" if cell == 0
print((cell & S != 0) ? " " : "_")
print "" if cell == 0
 
if cell & E != 0
print(((cell | row[x+1]) & S != 0) ? " " : "_")
else
print "|"
end
end
puts
end
end
end
 
maze = Maze.new(width, height)
 
# --------------------------------------------------------------------
# 4. Kruskal's algorithm
# --------------------------------------------------------------------
 
class Maze
def step
return false if @edges.empty?
 
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)
set1.connect(set2)
@grid[y][x] |= direction
@grid[ny][nx] |= OPPOSITE[direction]
break
end
end
 
return @edges.any?
end
end
 
print "" # clear the screen
 
while maze.step
### comment these lines if you don't want to animate the algorithm
maze.display
sleep(delay)
end
maze.display
 
# --------------------------------------------------------------------
# 5. Show the parameters used to build this maze, for repeatability
# --------------------------------------------------------------------
 
puts "#{$0} #{width} #{height} #{seed}"

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.