Search⌘ K
AI Features
Home
Courses
Mazes for Programmers

Implementing Recursive Division

Explore the Recursive Division algorithm to understand how to generate mazes by recursively splitting a grid into smaller regions and adding walls. Learn to implement this method by linking cells, deciding division orientation, and creating passages, helping you generate intricate maze patterns.

We'll cover the following...

The RecursiveDivision class

The algorithm really is as simple as described. First, we’ll “blank out” the grid by linking every cell to its neighbors (effectively removing all interior walls) and then recursively split the grid in half by adding walls back in. Unlike the other algorithms we’ve implemented, we’re going to break this one into a few different methods to help with the recursion. It’ll start with the on(grid) method.

C++
class RecursiveDivision
  def self.on(grid)
    @grid = grid
    @grid.each_cell do |cell| 
      cell.neighbors.each { |n| cell.link(n, false) }
    end 
    divide(0, 0, @grid.rows, grid.columns) 
  end
  def self.divide(row, column, height, width)
    return if height <= 1 || width <= 1 
    if height > width
      divide_horizontally(row, column, height, width)
    else
      divide_vertically(row, column, height, width)
    end
  end
  def self.divide_horizontally(row, column, height, width)
    divide_south_of = rand(height-1) 
    passage_at = rand(width) 
    width.times do |x|
      next if passage_at == x
      cell = @grid[row+divide_south_of, column+x] 
      cell.unlink(cell.south) 
    end
    divide(row, column, divide_south_of+1, width) 
    divide(row+divide_south_of+1, column, height-divide_south_of-1, width) 
  end
  def self.divide_vertically(row, column, height, width)
    divide_east_of = rand(width-1)
    passage_at = rand(height)
    height.times do |y|
      next if passage_at == y
      cell = @grid[row+y, column+divide_east_of]
      cell.unlink(cell.east)
    end
    divide(row, column, height, divide_east_of+1)
    divide(row, column+divide_east_of+1, height, width-divide_east_of-1)
  end
end
...