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