The Amazing MazeWalker Version 2.02
Labyrinthe generieren und traversieren
MazeWalker ist ein kleines, in Excel-VBA geschriebenes Programm, das zufallsgesteuert perfekte Labyrinthe erzeugt, die der Benutzer anschließend mit Hilfe der Pfeiltasten durchqueren kann. Wenn die eigene Lösung nicht sofort gelingt, kann man das Labyrinth auch speichern und später wieder laden, sobald man einen neuen Versuch wagen will.
Es ist auch möglich, die Traversierung einem Algorithmus zu überlassen und dessen Lösung hinterher zu studieren. Zwei Algorithmen stehen zur Auswahl. MazeRunner, ein von C. Y. Lee veröffentlichter Algorithmus, findet den kürzesten Weg zwischen Eingang und Ausgang mit Hilfe von „Wave Propagation“ und „Retracing“. Da diese Methode nur mit Kenntnis des gesamten Labyrinths durchgeführt werden kann, muss man sie eher als Wegoptimierungsmethode denn als praktische Hilfe bei der Durchquerung ansehen. Dagegen ist der zweite Algorithmus, WallFollower, eine Strategie, die ohne vorherige Kenntnis des Labyrinths genutzt werden kann. Man legt einfach die rechte Hand an die Wand und lässt sie dort während der gesamten Durchquerung.
Die Arbeitsmappe mit dem kompletten Programm kann kostenlos heruntergeladen werden (s. unten). In der Arbeitsmappe befindet sich ein Arbeitsblatt namens „about“, das eine kurze Einführung in die Benutzung des Programms enthält.
MazeWalker is a little program written in Excel-VBA. It creates perfect mazes at random which you can then try to traverse. If you are not successful in finding the right traversal for a maze immediately, you can save it and retrieve it later for another attempt.
You may also study maze traversals found by algorithms. There are two algorithms available in the program. MazeRunner, published by C. Y. Lee, finds the shortest path between entrance and exit using wave propagation and retracing. As it requires knowledge of the maze’s structure, it is rather a routing method than a practical aid that could be used during maze traversal. In contrast, WallFollower is a traversal strategy which can be applied without any prior knowledge of the maze. Simply put your right hand on the wall and leave it there until you have arrived at the exit.
The workbook with the complete program can be downloaded free of charge (see bottom of the page). It contains a worksheet ‘about’ which provides a short introduction to how MazeWalker can be used.
There are two worksheets in the MazeWalker workbook, maze and about. The first one represents the user interface, the second provides a short introduction into the features of the program.
To get an overview of these features simply have a look on worksheet about (picture below):
Having opened the workbook you should see on worksheet maze a newly created maze based on a grid of 29 rows and 29 columns (see next picture). If there is no such maze you have probably forgotten to allow the execution of macros (i.e. VBA programs).
On the left of the screen there are six buttons which you may use in order to enjoy the features of the program.
The mazes are created using a method called depth-first search (dfs). As this is a well-known standard technique I don’t want to go into details here. But there is one important consequence of using dfs: the mazes created will be perfect. 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.
Traverse the maze
Press the go-to-start button if you want to traverse the maze from entrance to exit. Pressing the button alters slightly the maze’s appearance: the entrance cell is now occupied by a little blue square (next picture). You can use the arrow keys in order to steer the square through the maze.
As soon as you have reached the exit cell (always situated in the bottom row) you will be shown a motivating message
It is easier to find a path through the maze when looking on it from above than it is from inside. Nonetheless perfect mazes can be quite complicated. So, if you are not successful in solving it immediately, you might want to save it for another attempt. The next paragraph will show you how this can be done.
Save the maze and retrieve it later
If, for any reason, you want to preserve the maze, e.g. have another attempt later or give a friend the chance to solve it, you can save it by pressing the save-maze button. There is a hidden worksheet named Data where the structure of the maze will be stored. Only the structure will be stored, but not the moves the user has made during his attempt to traverse it.
Press the retrieve-maze button if you want to replace the current maze on worksheet Maze by the maze which has been stored on worksheet Data. Please note that the current maze will be lost when you click the button.
Study the solution found by an algorithm
There are two algorithms available, MazeRunner and WallFollower, and there exist buttons for both of them on the left of the screen.
MazeRunner, published by C.Y. Lee in 1961, finds the shortest path between entrance and exit. The procedure consists of two phases, called wave propagation and retracing.
In the wave-propagation phase, we assign numbers (labels) to the cells of the maze. This is done stepwise, or, as Lee puts it, in waves. Initially, we assign label 0 to the entrance cell. Then the neighbor cells of the entrance cell are found and assigned label 1. This is the first wave. In wave 2, the neighbors of the cells labeled in the first wave are detected. They get label 2. The procedure continues until the exit cell has been assigned a label.
In the retracing phase, we use the labels to find a path from exit to entrance (which can of course also be taken in the opposite direction). In order to compile this path, we take the exit cell, which has the highest label in the grid, as its first element. Then we search for a neighbor of the exit cell having a label that is lower by 1. This cell becomes the second element of the path. The third element of the path will be a neighbor of the second element having a label that is lower by 1, compared to that of the second element. The procedure is continued until the entrance cell, which has the lowest label, has become an element of the path.
In the picture below, the path is highlighted in blue color. You can also see the labels which have been given to the cells during wave propagation. Note that there are cells in the grid which don’t have labels but are still on their original value -1. This is due to the fact that wave propagation stops as soon as the exit cell has been assigned a label.
It should be clear from the description above that MazeRunner requires knowledge of the maze’s structure. Therefore it is rather a routing method than a practical aid that could be used by a person within a maze.
In contrast, WallFollower is a traversal strategy which can be applied without any prior knowledge of the maze. For the person traversing the maze, it is sufficient to act according to a simple rule of conduct. When entering the maze she puts her right hand on the wall (right-hand rule). She leaves it there until she has reached the exit. It is also possible to use the left hand instead (left-hand rule). Only changing the hand during the traversal would not be a good idea.
The next picture shows the path found by WallFollower. Since the maze is a perfect one which has in principle only one path of traversal, there is no great difference between the solutions found by MazeRunner and WallFollower. In contrast to WallFollower, MazeRunner avoids running into dead ends. As a consequence, its path is usually shorter.
Adapting the program to your needs
As the VBA code of the workbook is not protected by a password, you can easily change the program if you are capable of VBA programming. There are just two things I ask you for:
- Don’t pass the program on to somebody else under your name
- If you have considerably changed the program, don’t pass it on under my name
There are some changes to the program, however, which can be mastered by a person having only little programming experience. These alterations are described in the following picture which is a part of worksheet about: