Data structures for mazes

Introduction

• 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:
• 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

NORTH = 0
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()
    ax.set_aspect('equal')

    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")

plt.show()