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
          �  ����ij�                            � 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
          �  ����ij�  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.