Maze generation with binary trees

Introduction

• A perfect maze is a maze in which any two points can be connected by exactly 1 path:
• We can represent these with binary trees:
  • The root of the tree is the top right.
  • Each node can connect either north or east (but not both).

Code (Python)

import numpy as np
import random
from maze_functions import *

width = 5
height = 5
grid = np.zeros((width, height, 2), bool)

for j in range(height):
    for i in range(width):
        if i == width - 1 and j == height - 1:
            # top right cell
            # can't go east or north
            continue

        if j == height - 1:
            # top cell
            # can only go east
            goEast = True
        elif i == width - 1:
            # far right cell
            # can't go east
            goEast = False
        else:
            goEast = random.randint(0, 1) == 0

        cell = (i, j)
        if goEast:
            link_cells(grid, cell, east(cell))
        else:
            link_cells(grid, cell, north(cell))

draw_maze(grid)

Pros and Cons

• Pros:
  • Very fast, runs in O(n) time and space complexity.
• Cons:
  • There is a long corridor along the north and east walls.
  • A cell cannot be open in both the north and east directions.
  • Easy to solve:
    • From any cell, you only need to travel either north or east to reach the top right cell.