Maze generation with Wilson's algorithm

Introduction

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.

Demo

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:
            moves.append(new_cell)

    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
            path.append(start_cell)
            return path
        elif start_cell in path:
            # intersected with self
            # remove the loop from the path
            path = path[:path.index(start_cell) + 1]
        else:
            path.append(start_cell)


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
    random.shuffle(unvisited_indices)

    # set a random cell to a visited
    unvisited_indices.pop()

    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
            unvisited_indices.remove(path[i])

    draw_maze(grid)

generate_maze()

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.