class MazeMagic::MazeGenerator::RecursiveBacktracking
RecursiveBacktracking
algorithm for generating Maze
original author Jamis Buck
weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking
I've wraped the algorith with objects
Attributes
grid[R]
maze[R]
Public Class Methods
new(grid:)
click to toggle source
# File lib/maze_magic/maze_generator/recursive_backtracking.rb, line 22 def initialize(grid:) @grid = grid end
Public Instance Methods
generate()
click to toggle source
# File lib/maze_magic/maze_generator/recursive_backtracking.rb, line 26 def generate preseeder.call carve_instructions_to_grid(grid, grid.start_x, grid.start_y) generate_maze maze end
Private Instance Methods
carve_instructions_to_grid(grid, current_x, current_y)
click to toggle source
# File lib/maze_magic/maze_generator/recursive_backtracking.rb, line 35 def carve_instructions_to_grid(grid, current_x, current_y) directions = [ North.instance, South.instance, East.instance, West.instance ] .sort_by{randomizer.call} directions.each do |direction| next_x, next_y = current_x + direction.direction_x, current_y + direction.direction_y if next_y.between?(0, grid.length-1) && next_x.between?(0, grid[next_y].length-1) && grid[next_y][next_x] == 0 grid[current_y][current_x] |= direction.to_i grid[next_y][next_x] |= direction.oposite.to_i carve_instructions_to_grid(grid, next_x, next_y) end end end
edge()
click to toggle source
# File lib/maze_magic/maze_generator/recursive_backtracking.rb, line 88 def edge MazeMagic::Maze::Edge.instance end
generate_maze()
click to toggle source
# File lib/maze_magic/maze_generator/recursive_backtracking.rb, line 55 def generate_maze @maze = [] @maze << [edge] + Array.new((width * 2 - 1), hw) + [edge] height.times do |y| row = [] row << vw width.times do |x| row << ((grid[y][x] & South.instance.to_i != 0) ? passage : hw) if grid[y][x] & East.instance.to_i != 0 row << (((grid[y][x] | grid[y][x+1]) & South.instance.to_i != 0) ? passage : hw) else row << vw end end @maze << row end end
hw()
click to toggle source
# File lib/maze_magic/maze_generator/recursive_backtracking.rb, line 80 def hw MazeMagic::Maze::HorizontalWall.instance end
passage()
click to toggle source
# File lib/maze_magic/maze_generator/recursive_backtracking.rb, line 84 def passage MazeMagic::Maze::Passage.instance end
vw()
click to toggle source
# File lib/maze_magic/maze_generator/recursive_backtracking.rb, line 76 def vw MazeMagic::Maze::VerticalWall.instance end