💾 Archived View for spam.works › mirrors › textfiles › fun › maze.how captured on 2023-06-14 at 16:38:26.
-=-=-=-=-=-=-
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.