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.

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
               
               
               
      start        
               
              start
               
               
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.


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Developing Games in Java

other games programming books

Commercial Software Shop

Where I can, I have put links to Amazon for commercial software, not directly related to this site, but related to the subject being discussed, click on the appropriate country flag to get more details of the software or to buy it from them.

cover LEGO Mindstorms NXT - Allows you to build a robot and program it from a PC or Mac. Contains an Intelligent Brick with 32-bit microprocessor, memory and FLASH, 3 Interactive Servo motors with built-in rotation sensors, sound sensor, ultrasonic sensor, touch sensor, light sensor, USB 2.0 and Bluetooth support. Icon-based drag-and-drop program "building" environment.

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.