public
Last active

Implementation of the recursive backtracking algorithm for maze generation

  • Download Gist
recursive-backtracker.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
# Recursive backtracking algorithm for maze generation. Requires that
# the entire maze be stored in memory, but is quite fast, easy to
# learn and implement, and (with a few tweaks) gives fairly good mazes.
# Can also be customized in a variety of ways.
 
DIRS = (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 }
 
width = (ARGV[0] || 10).to_i
height = (ARGV[1] || width).to_i
seed = (ARGV[2] || rand(0xFFFF_FFFF)).to_i
 
srand(seed)
 
cells = Array.new(height) { Array.new(width, 0) }
stack = [[0, 0, DIRS.sort_by{rand}]]
 
until stack.empty?
x, y, directions = stack.last
 
until directions.empty?
direction = directions.pop
nx, ny = x + DX[direction], y + DY[direction]
 
if nx >= 0 && ny >= 0 && nx < width && ny < height && cells[ny][nx] == 0
cells[y][x] |= direction
cells[ny][nx] |= OPPOSITE[direction]
stack.push((x, y, directions = [nx, ny, DIRS.sort_by{rand}]))
end
end
 
stack.pop
end
 
puts " " + "_" * (width * 2 - 1)
height.times do |y|
print "|"
width.times do |x|
print((cells[y][x] & S != 0) ? " " : "_")
if cells[y][x] & E != 0
print(((cells[y][x] | cells[y][x+1]) & S != 0) ? " " : "_")
else
print "|"
end
end
puts
end
 
puts "#{$0} #{width} #{height} #{seed}"

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.