GENWiki

Premier IT Outsourcing and Support Services within the UK

User Tools

Site Tools


archive:fun:maze.how
                            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.
/data/webs/external/dokuwiki/data/pages/archive/fun/maze.how.txt · Last modified: 1999/08/01 17:07 by 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki