Data structures for mazes

Data structures for mazes


  • Many choices are available for storing mazes.
  • However they can broadly be split into 3 types:
    • Array-based structures:
      • Mazes are 2D grids of cells.
      • This makes them ideal for storing in 2D arrays.
      • Individual cells can be accessed very quickly.
    • Graph-based structures:
      • Mazes are cells that are connected together with paths.
      • This makes them ideal for storing as graphs.
      • Navigating a maze can be done very simply.
    • Hybrid structures:
      • Hybrid structures store cells in a 2D array.
      • But each cell is linked to the cells around it.
      • It is both a 2D array and a graph.
      • This gives strengths of both types, but with extra complexity.
  • The algorithms on this website prefer to use an array for storing the maze.

Array-based data stucture

  • Given a maze such as: a 10x10 maze
  • We can store this as a 2D grid of cells.
  • For each cell we store whether it has a wall on each side.
  • However storing every side will lead to duplicate data:
    • The west wall of one cell is the same as the east wall of the cell to it's left.
  • We only store the north and east walls for each cell.
  • This is done using a array containing 2 booleans for each cell:
    • The first boolean is for north.
    • The second boolean is for east.
Storing the data
import numpy as np

EAST = 1

width = 10
height = 10
grid = np.zeros((width, height, 2), bool)
Moving in each direction:
def north(cell):
    return cell[0], cell[1] + 1

def south(cell):
    return cell[0], cell[1] - 1

def east(cell):
    return cell[0] + 1, cell[1]

def west(cell):
    return cell[0] - 1, cell[1]
Checking if a wall exists in each direction:
can_go_north = grid[i, j][NORTH]
can_go_east = grid[i, j][EAST]
can_go_south = grid[south((i, j))][NORTH]
can_go_west = grid[west((i, j))][EAST]
And drawing the maze to the screen:
import matplotlib.pyplot as plt

def draw_maze(grid):
    fig, ax = plt.subplots()

    width = grid.shape[0]
    height = grid.shape[1]

    # draw the south and west outer walls
    plt.plot([0, width], [0, 0], color="black")
    plt.plot([0, 0], [0, height], color="black")

    for j in range(height):
        for i in range(width):
            value = grid[i, j]

            if not value[EAST]:
                # draw a east wall
                plt.plot([i + 1, i + 1], [j, j + 1], color="black")

            if not value[NORTH]:
                # draw a north wall
                plt.plot([i, i + 1], [j + 1, j + 1], color="black")