# Games - Example - Maze

It can be useful to incorporate a maze as part of a game. In a first person game the player would be inside the maze in other types of game the player might see a map looking down on the maze. The maze nature of the game may be hidden in all sorts of ways, for example, as some sort of terrain.

## Possible Requirements

It is usual for a maze to have the following features but anything can be changed.

• One starting point on the outside of the maze
• One finishing point near the centre
• One path from start to finish
• All locations are reachable from the start

## Constructing the Maze

step 1
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
We start with a regular grid of cells forming a large rectangle or square. Give all squares an initial value of zero and give them all borders on all sides.
step 2
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Choose a cell at random and mark it (in this case with a yellow background) and mark the cells that border it (in this case with a blue background)
step 3
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Choose one of the border (blue) cells at random and mark it and its border cells in the same way as the last stage.

Where this borders a previosly chosen cell we modify both numbers of these adjacent cells as follows:

• bottom add 1
• top add 2
• right add 4
• left add 8

We remove the lines between these chosen cells.

step 4
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 9 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Choose one of the border (blue) cells at random and mark it and its border cells in the same way as the last stage.
step 5
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 9 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Continue this prosess. If our new cell happens to border on two yellow cells then we only remove one of the borders. So, for example, the bottom two yellow cells still have a line between them (with the corresponding numbers)
step 6
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 9 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Continue this prosess until all border cells have been used.
step 1 Choose a square at the edge for the start and a square near the centre for the finish.

## Spanning Tree

This type of maze is related to the concept of a spanning tree.