Maze generation with Wilson's algorithm


Data structures for mazes Show

Maze generation with Wilson's algorithm


  1. Pick a random cell and mark it as visited.
  2. Pick another random cell as the start of your path.
  3. Build your path by moving in random a direction.
    • If you end up at a visited cell:
      • add that path to your maze.
      • Mark all the cells in the path as visited.
      • Go back to step 2.
    • If you end up at a cell that is already in your path:
      • This is called a loop.
      • Remove the loop from your path.
      • Continue building your path.
    • If the cell is neither visited nor in your path then:
      • Append it to your path.
      • Continue building the path.
  4. Once all your cells are visited, you have a perfect random maze.


an animated maze

Code (Python)

import numpy as np
import random
from maze_functions import *

def possible_moves(grid_width, grid_height, cell: (int, int)):
    moves = []

    for direction in [north, south, east, west]:
        new_cell = direction(cell)
        if 0 <= new_cell[0] < grid_width and 0 <= new_cell[1] < grid_height:

    return moves

def get_random_path(start_cell: (int, int), unvisited: np.array, grid_width, grid_height) -> [(int, int)]:
    path = [start_cell]

    while True:
        possible_cells = possible_moves(grid_width, grid_height, start_cell)
        start_cell = random.choice(possible_cells)

        if start_cell not in unvisited:
            # found the rest of the maze
            return path
        elif start_cell in path:
            # intersected with self
            # remove the loop from the path
            path = path[:path.index(start_cell) + 1]

def generate_maze():
    width = 10
    height = 10
    grid = np.zeros((width, height, 2), bool)

    # a list of indices to all the cells
    unvisited_indices = [x for x in np.ndindex((width, height))]
    # shuffle, so we can select them at random

    # set a random cell to a visited

    while len(unvisited_indices) > 0:
        cell = unvisited_indices[0]

        path = get_random_path(cell, unvisited_indices, width, height)

        for i in range(len(path) - 1):
            link_cells(grid, path[i], path[i + 1])

            # remove the cells from the unvisited_indices
            # the last cell is already removed as part of a previous path



Pros and Cons

  • Pros
    • Creates an unbiased perfect maze
  • Cons
    • Slow
      • For large mazes it can be difficult for the first path to find the single unvisited cell.