HOW TO BUILD A MAZE
David Matuszek
Department of Computer Science
8 Ayres Hall
University of Tennessee
Knoxville TN 37916
Taken from Byte’s December 1981, page 190 (I only typed a
part of the article).
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Mazes are fun to solve. With a little imagination,
mazes can be incorporated into many different computer
games. If you know how, it’s a simple matter to use the
computer to generate random mazes.
A traditional maze has one starting point and one
finishing point. In addition, all locations inside the maze
are reachable from the start, and there is one and only path
from start to finish. While it is easy to place doorways and
barriers randomly inside a maze, it is more difficult to
satisfy the two later constraints. This article describes a
fairly simple method that efficiently produces a random
traditional maze.
THE GENERAL APPROACH
We begin with a rectangular array. Each cell of the
array is initially completely “walled in,” isolated from
its neighbors (see figure 1).
ЙННННННННННННННННННННННННННННННННННННН» Secondly, we
є ЪВВВВВї FIGURE 1 є judiciously erase
є ГЕЕЕЕЕґ є walls inside the
є ГЕЕЕЕЕґ The initial array from є array until we
є ГЕЕЕЕЕґ which the maze will be є arrive at a
є ГЕЕЕЕЕґ constructed. є structure with the
є ГЕЕЕЕЕґ є following property:
є АБББББЩ є for ANY two cells
ИНННННННННННННННННННННННННННННННННННННј of the array, there
is only one path between them. Thus, any cell can be reached
from any cell, but only by a single unique (see figure 2).
Computer science jargon refers to such a structure as a
SPANNING TREE, and it is the creation of this spanning tree
that is the tricky pary of building a maze.
ЙННННННННННННННННННННННННННННННННННННН» Finally, the
є ЪДВДВДї FIGURE 2 є of the maze is
є ГїііГїі є broken in to
є і іАЩіі One possible spanning є provide a start and
є ГД ЪД і tree for the array in є a finish position.
є іЪДґ Ъґ figure 1. є Since there is a
є іАДЕДіі є unique path between
є АДДБДДЩ є any two cells of the
ИНННННННННННННННННННННННННННННННННННННј maze, there will be
a unique path from start to finish. Hence, start and finish
can be chosen in any convenient manner, say, random
locations on the opposite sides of the maze (see figure 3).
ЙННННННННННННННННННННННННННННННННННННН» BUILDING THE
є ЪДВДВДї FIGURE 3 є SPANNING TREE
є АїііГїі є starting with a
є іАЩіі The spanning tree from є fully “walled-up”
є ГД ЪД і figure 2 with possible є array (see figue 1),
є іЪ і Ъґ entry and exit points є pick a single cell
є іАДЕДіі added. є in the array and
є АДДБДД є call this cell the
ИНННННННННННННННННННННННННННННННННННННј spanning tree. Then
add cells one at a time to the spanning tree until it fills
the entire array.
At any point during this procedure, there will be three
types of cells in the array:
o those that are already in the spanning tree.
o those that are not in the spanning tree, but are
immediatly adjacent (horizontally or vertically) to some
cell in the spanning tree (we call there cells FRONTIER
CELLS)
o all other cells
The algorithm follows:
1. Choose any cell of the array and call it the spanning
tree. The four cells immediatly adjacent to it (fewer if it
is on an edge or in a corner) thus become frontier cells.
2. Randomly choose a frontier cell and connect it to ONE
cell of the current spanning tree by erasing ONE barrier. If
it is adjacent to more than one cell of the spanning tree
(and it could be adjacent to as many as four!), randomly
choose one of them to connect it to, and erase the
appropriate barrier.
3. Check the cells adjacent to the cell just added to the
spanning tree. Any such cells that are not part of the
spanning tree and have not previously been marked as
frontier cells are now marked as frontier cells.
4. If any frontier cells remain, back to step 2.
5. Choose start and finish points.
The article goes on, but I won’t. This part is enought to
show how to build a maze.
