Search⌘ K
AI Features
Home
Courses
Mazes for Programmers

Implementing Wilson's Algorithm

Explore the implementation of Wilson's algorithm to create unbiased mazes using loop-erased random walks. Understand the process of initializing unvisited cells, performing random walks to form paths without loops, and carving passages to generate complete maze structures. Gain hands-on experience coding and testing this algorithm to observe its unbiased maze patterns.

We'll cover the following...

The Wilsons class

The following code uses an array to keep track of all unvisited cells in the grid. Besides letting us query whether a cell has been visited or not, this also lets us quickly choose an unvisited cell from which we can start our loop-erased random walk.

C++
class Wilsons
  def self.on(grid)
    unvisited = [] 
    grid.each_cell { |cell| unvisited << cell }
    first = unvisited.sample 
    unvisited.delete(first) 
    while unvisited.any? 
      cell = unvisited.sample 
      path = [cell]
      while unvisited.include?(cell) 
        cell = cell.neighbors.sample 
        position = path.index(cell) 
        if position
          path = path[0..position] 
        else
          path << cell 
        end
      end 
      0.upto(path.length-2) do |index| 
        path[index].link(path[index + 1]) 
        unvisited.delete(path[index]) 
      end 
    end
    grid
  end
end

Code explanation

This implementation really consists of three different parts: the initialization (lines 4–8), the loop-erased random walk (lines 10–22), and carving passages (lines 24–27).

Lines 4–8 ...