Creating a perfect maze - an event-driven animation
Die Animation, die kostenlos heruntergeladen werden kann, demonstriert, wie ein perfektes Labyrinth mit Hilfe der Tiefensuche erzeugt werden kann. Zuerst wird erklärt, was ein perfektes Labyrinth ist. Dann wird der Entstehungsprozess ausführlich geschildert und mit Hilfe einer Pseudocode-Darstellung konkretisiert. Anschließend wird gezeigt, dass zwischen der Erzeugung eines perfekten Labyrinths und der Zusammenstellung eines minimalen aufspannenden Baums für einen Graphen eine enge Beziehung besteht. Der Artikel schließt mit einer kurzen Einführung in die Benutzung des Programms.
The animation, which can be downloaded free of charge, demonstrates the creation of a perfect maze using depth-first strategy. In this presentation, we will first explain what a perfect maze is. Then we shall describe the creation process in detail, finally concretizing the description by giving a pseudocode formulation of the algorithm. Afterwards we will show that there is a close connection between the creation of a perfect maze and the construction of a minimum spanning tree for a graph. The presentation ends with a short introduction to the use of the program.
What is a perfect maze?
We call a maze perfect if there is exactly one path from any point in the maze to any other point. There are no circular paths and no inaccessible sections in such a maze. But there may be dead ends.
Normally, a maze has an entrance and an exit. How else should one traverse it? But note that the positions of entrance and exit are not important for the construction of the maze. This means that you can create a perfect maze and insert entrance and exit points afterwards.
The following picture shows a perfect maze. There is an underlying grid of cells so that we can express the size of the maze by the number of rows and the number of columns of this grid. In the picture below, the grid is a square of 12 rows and columns respectively.
How to create a perfect maze: the depth-first wall carving strategy
We will now demonstrate how a perfect maze is created based on a grid of cells. In order to keep things easy we will use a rather small grid, namely a 3-by-3 one. In the picture below you see this grid on the left. On the right there is the same grid once again, but this time with the cells numbered. This will allow us to refer to particular cells when discussing the maze creation procedure.
The whole procedure will be exemplified using the following series of images. The first of these images shows the underlying grid as described above. Let us assume that this grid is the place where the maze will be constructed, and that the lines represent removable walls.
First, we take an arbitrary cell as a starting point. In the second picture, and in all pictures that follow, this point is marked using pink color. There is also a small circle in the middle of the starting cell. You can think of this circle as being a worker who will carve the aisles of the maze by successively pulling down walls.
From his position in the starting cell, the worker first searches for a neighbor cell which is still unvisited. If there is more than one possibility he chooses one of these cells at random. He removes the wall between the chosen cell and the starting cell. Then he proceeds to the cell just found, thus making this cell his current position (picture 3).
By now, the aisle carved so far is only two cells long. Now the worker searches again for an unvisited cell adjacent to his current position. When he finds it, he removes the wall between the current cell and the cell found and then goes into it.
The procedure is continued until the worker finds himself in a position where no unvisited neighbor cells can be found. In our example, this is the case when the worker has arrived in cell 9 (see picture 9 of the series, third row, last column).
As there have not all the cells of the grid been visited, the creation of the maze cannot be finished at this point. How can the worker gain access to the cells which are still unvisited?
Pictures 10 – 18 illustrate how this can be done. The worker goes back in direction of the starting cell. At every cell on his way back, he checks if there are still unvisited neighbor cells. If he finds one he removes the wall and visits it. Then he searches again for an unvisited neighbor and visits it. He continues his visits until he is again stuck at a point where there are no unvisited cells left. He then returns the second time, going back in direction of the starting cell, searching at every position if there are still unvisited neighbors, and so on.
The creation of the maze will be completed as soon as the worker has re-arrived at the starting point and there are no more possibilities to access unvisited cells.
Why do we call this approach a depth-first strategy? In order to illustrate this, let us consider once again the first actions of the worker. He visited a neighbor of the starting cell, then a neighbor of this neighbor, then a neighbor of the neighbor’s neighbor, and so on. By doing this, he advanced into the depth of the grid.
Another approach would have been to first visit all neighbors of the starting point, then visit all neighbors of the first neighbor, then all neighbors of the second neighbor, and so on. We would call this a breadth-first strategy.
A more concrete description of the maze creation procedure
You are now ready to face a more concrete and technical formulation of the maze creation procedure. In this formulation, we will do without the idea of a real worker removing walls. We will assume that the program will do that by manipulating a suitable data structure. And we will facilitate the actions of the program by using two artifices:
We will give status labels to the cells, the possible values being “unvisited”, “visited” and “exhausted”, the last one meaning that there are definitely no more
unvisited neighbors of the cell in question.
- We will use a stack to memorize the cells which constitute our way back to the starting point.
A stack is a certain form of data store. We can put elements on the store (“push”) and take elements from it (“pop”). A popped element is always the one most recently pushed. Thus the stack implements a last-in, first-out, or Lifo, policy.
Here is the algorithm in a pseudocode that has some resemblance with VBA:
Begin with a grid of cells where every cell is separated from its neighbors by walls. All cells are labeled “unvisited”.
Choose an arbitrary starting cell within the grid. Mark it as “visited” and make it the current cell
Try to find at random an unvisited neighbor c of the current cell
If such a neighbor has been found then
Remove wall between c and the current cell
Mark c as “visited”
Push the current cell on stack
Make c the current cell
Mark the current cell as “exhausted”
Pop the stack and make the popped cell the current cell
Loop until stack is Empty
Perfect maze creation and graph theory
Imagine that, in our grid, all the walls were only fictitious. Then we could from every cell easily reach its neighbors without having to remove walls. We can represent this situation by a graph where the cells’ centers are marked by little circles (“vertices”) and the paths between them by lines (“edges”). The next picture shows this graph on the left.
Now assume that the walls were solid ones, with exception of those which have been pulled down during the process of maze creation. To adapt the graph to this situation we would have to remove the lines between every pair of cells which are separated by a solid wall. The resulting graph (the maze graph) is shown on the right of the picture below. In order to make the relation between the graph and the maze evident, the starting point of maze creation is indicated by a filled circle.
Please note that all vertices of the maze graph are, directly or indirectly, connected with each other. You can also see that, if we choose at random two vertices of the graph, there will be only one path to get from the first cell to the second, and vice versa.
In graph theory, a graph like the one on the right is called a minimum spanning tree of the graph on the left. It is a tree because there are no cycles in it, and it is minimal because you could not remove an edge without losing the accessibility of every vertex from every other vertex.
It should become clear by contemplating the two pictures above that the minimum spanning tree on the right is not the only possible, even if we let the starting point unchanged. There are several possible minimum spanning trees, and each of them represents a perfect maze which may be constructed on the basis of our grid.
The depth-first strategy described above is not the only method to derive minimum spanning trees from graphs. There are other well-known algorithms, the most popular being those written by Prim and Kruskal.
How to use the animation program
The animation workbook contains two worksheets. The first one,called About, gives a short introduction to the purpose of the program and its use, the second, called Animation, serves as user interface.
When you select worksheet Animation for the first time, it will present itself like shown in the picture below. Most of the visible space will be occupied by a maze that has been created before; above it you will recognize a blue-colored area containing a command button on the left.
Having pressed the button you will see a small form where you can enter the parameters necessary for the program’s execution (see next picture). These are
The extension of the maze, i.e. the number of rows of
the underlying grid. As the mazes created by the program are always squares, the number of rows is equal to the number of columns. Possible values for this parameter are 5, 7, 10, 12, 15, 17,
20, 25, 30, and 50. If you choose a high number, say 30 or 50, the resulting maze will probably not be visible in its entirety. To avoid this, don’t forget to adjust the scale of the display
before you press the start button.
The speed of the animation. Possible values are “low”, “medium”, “high”, and “growing”. Choose “growing” if the desired maze is a large one. In this mode, the first steps are displayed at a rather low speed. Speed increases from step to step, but
not above a certain limit. So you can still track the creation process without getting bored by unnecessary delays.