# Maze generation with Wilson's algorithm

## Prerequisites

### 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.

#### 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.