# Data structures for mazes

### 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()``````