#### Introduction

- Pick a random cell and mark it as visited.
- Pick another random cell as the start of your path.
- 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.

- If you end up at a visited cell:
- 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.

- Slow