Maze generation with binary trees


Trees Show

Binary Trees Show

Data structures for mazes Show

Maze generation with binary trees


  • A perfect maze is a maze in which any two points can be connected by exactly 1 path: a perfect maze
  • We can represent these with binary trees: a maze with arrows showing the paths
    • 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

        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
            goEast = random.randint(0, 1) == 0

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


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.