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