Skip to content

Instantly share code, notes, and snippets.

# jamis/recursive-backtracker.rb Created Dec 24, 2010

Implementation of the recursive backtracking algorithm for maze generation
 # 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 || 10).to_i height = (ARGV || width).to_i seed = (ARGV || 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}"
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.