Don Scales
Lose yourself in this amazing game
Labyrinth is a fairly large program written in Tiny BASIC. Each time the program is run it will construct a different two dimensional maze and then allow the player to explore a three dimensional projection of this maze.
The program is divided roughly into two halves. The first half randomly builds a maze with a single route through it. A 2D plot of the maze is available at the end of this stage for those who suffer from claustrophobia. The second half of the program produces 3D projections as the player wanders along the corridors of the maze.
Building The Maze
The basic maze is a 'simple connected' maze (one which has no closed circuits). It is constructed using two, two dimensional arrays. The first array holds an indication of which cells of the maze have been used and the order in which they have been allocated. The second array holds the description of the topology of the maze.
The maze construction starts by randomly selecting an entrance along the width of the maze. This location is saved in a spare element of the array.
From this start location the maze is constructed. At each cell, the program scans the adjacent cells to see which are available to use. Having decided which are available, the program then selects one cell randomly.
Consider the following examples. In each of these four there are three possible choices, A, B and C
Code: Select all
O A
| |
A <-o-> C B <-o-- O
| |
B C
B C
| |
C <-o-> A O <-o-- B
| |
O A
hence the route can be chosen from the three possibilities.
Next there are six combinations of two choices.
Code: Select all
O B
| |
A <-o-- O o-> B O --o-> A
| |
B A
A B
| |
B <-o A <-o-> B o-- O
| | |
O O A
To arrive at these choices, the program must first scan the adjacent cells. As the program knows the direction it has just come from, it only needs to check the other three directions.
The program continues its random route through the
maze until it hits a dead end. A branch is then made from the first route at this point and continued until the next dead end. This procedure is continued until the maze is complete.
At this point, the player can obtain a two dimensional display of the maze. Each element of the second array contains information about one cell of the maze. This information is incomplete as it is only for the top and right hand wall.
Code: Select all
.-. . . .-. . .
0=. | 1=. | 2=. . 3=. .
The Third Dimension
To produce a three dimensional picture, it is necessary to complete the cell information and organize it in such a manner that it can be rotated. The binary system fulfils both these requirements. A bit is used to indicate a wall. So we get
Code: Select all
. . . . .-. .-. . . . . .-. .-.
| | | | | | | |
. . . . . . . . . . . . . . . .
0 1 2 3 4 5 6 7
. . . . .-. .-. . . . . .-. .-.
| | | | | | | |
.-. .-. .-. .-. .-. .-. .-. .-.
8 9 10 11 12 13 14 15
To turn left, the cell information is cyclicically shifted right one bit. 2 becomes 4, 3 becomes 6, 8 becomes 1. To turn right, the cell information is cyclicically shifted left one bit. 2 becomes 1, 1 becomes 8, 10 becomes 5.
The information for the 2d maze is therefore translated and the information completed by inspecting the neighbouring cells. The 3D pictures are produced using memory mapping and the graphics available on the
TRITON. As most systems have both memory mapped displays and graphic symbols, it should be very easy to convert this part of the program to run on most machines.
The display is constructed simply with horizontal, vertical and diagonal lines. A reasonable display would be possible with | — and / \ To move in the maze, the player can turn left or right or move forward. The players current position can also be obtained.
Giving The Picture
To produce the 3D picture, the program starts with the cell corresponding to the players current position. This cell is then rotated, as described earlier, until facing the same way as the player. The program then decodes the cell information and checks for the walls left, right and in front of the player. At the first depth, either a blank wall or two columns are produced. If a blank wall is produced, no further information is available. If looking out of the maze, no further information is produced and if outside the maze and looking away from it, a blank screen is all you get.
If, on the other hand, a passage exists to the next cell, the program obtains the information about the next cell by making the appropriate index and rotates and decodes this cell. At the second depth, it is possible to have walls or passages to the left, right and straight ahead.
Each depth has its own display routine which checks
14 COMPUTING TODAY JANUARY 1980