In this article, we will take a close look at the construction of a maze of rectangular shape in C++ and we will propose an algorithm that will highlight the solution for going through and getting out of the maze. Our objective here is to create a perfect maze, the simplest type of maze for a computer to generate and solve. A perfect maze is defined as a maze which has one and only one path from any point in the maze to any other point. This means that the maze has no inaccessible sections, no circular paths, no open areas. Apparently easy to be solved, this problem requires the use of several data structures : arrays, piles and lists. Our goal consists in using C++ classes in order to define hybrid structures.

Keywords: maze, data structure, pile, array, linked list, path.

Introduction

When studying a programming language, one often encounters data structures such as piles, linked list and trees, among other things. According to the paradigm, the data structure occupies a position of skeleton in the program, whereas the algorithms reflect only a way of manipulating the data. Unfortunately, in most documents referring to this subject, one introduces these structures in a simplistic way, with examples of a terrible triviality. We will hereinafter look at an interesting example, albeit slightly complex : creating a maze and finding a way out. Let us consider the following case. We start with a grid consisted of several lines and columns of rectangular cells (see figure 1). By breaking a few walls of a few cells, we can build a maze (see figure 2). One thing left to do is to determine which walls should be destroyed, at the very moment where we have finished drawing the maze or if there is a path between the ingoing cell and the outgoing cell.

To answer the previous questions, we will provide our program with three types of structure. The array comes first. It is the simplest structure. It consists of a rectangle of cells composed of a certain number of lines and columns. If the array is not numerical, there is not much we can do except reading and writing its input. Nevertheless, it is rather convenient for representing data in a compact shape, even visually esthetical. Within the framework of this article, we use it to refer to our maze inside the class of the same name. Regarding this matter, we must focus our attention on the variable Puzzle located in the listings 5 and 6. Puzzle is actually a linear array put in memory, what we can allow since we chose a rectangular-shaped maze. In this context, we provide the users of the triggered class with an indexing operator of the form : Puzzle(i,j). If this operator simply indicates the cell placed in line i and column j, the access in memory to that cell will be carried out by moving from i * total number of columns + j spaces in the memory.

Here comes the second structure and the list (doubly-linked list, in our case). It consists of several nodes, each one containing a data element independent of any implementation, including two pointers (whose values correspond to the addresses of the next and previous nodes). By convention, the "head" of a list is the node having no previous node. And the "tail", the one that has no next node. Many operations on lists can be carried out, the most usual one being the insertion (in the first, middle or last place) of new elements. For that matter, let us pay attention to the code of the listing 3. We can see that the list structure for the class Room is implemented. Here the function Glue provides the only operation, we are interested in : it carries out the addition of two lists containing given rooms. To perform this task, we look for the head in one list and the tail in another one. Then we merely "glue" the two nodes in question one upon the other. It is clear that, with respect to the array, the list gives the undeniable advantage of growing. It is therefore useless to know its size in advance.

Let us now move on to the third structure : the pile. It is a peculiar case of list that one can envision as a heap of objects. It has only one pointer and consequently, we cannot access freely to its elements since we can extract only the one that is located on the surface. We summarize these properties by calling the pile a structure LIFO in which the Last Input is the First Output. In a pile, the only possible operations are to pile up a new element (function push()) and withdraw (when possible) the last piled-up element (function pop()). This property makes precisely the pile interesting in our case. As a matter of fact, when lost in the maze, we will always get the possibility of moving backwards. So, if we store our trajectory into the pile, the last piled-up element will always be a "retreat solution". We implement this structure in the listings 3 and 4. The data of our structure are the coordinates of the cell (room) of the current location.

1. Encoding the openings and closings

Creating a maze is made by means of a class which accepts any number of lines and columns. It allocates an array of the type lines * columns = rooms. The data of each room rely mainly on two integers. One specifies the set it belongs to and the other one specifies the state of its doors. Except for the edges, all cells possess four doors (down, right, up and left). But as a door is shared by two juxtaposed rooms, we will consider that each room manages only the doors Down and Right that it contains (because they are at the down and right sides of the cells, in our drawings). Of course, the edges make an exception. We represent the state of the doors (open, closed and, let's be crazy, locked) by the bits with the following convention :

00 : the door is closed

01 : the door is open

11 : the door is locked

Moreover, we decide that the two first bits (at the right side of the usual writing of a binary number) symbolize the state of the door Down and the two following bits (going to the left side of the usual writing of a binary number) represent the one of the door Right. So here are the equivalences of some decimal numbers:

0 = 00 00

? the doors Down and Right are closed.

7 = 01 11

? the door Down is locked, the door Right is open.

All possible states are enumerated in the type DoorStates of the listing 5. In order to remember them more easily, we use D for (D)own, C for (C)losed, L for (L)ocked, O for (O)pen. With this convention, it proves rather easy to write the routines allowing to change the state of the doors. To fulfill this task, we must modify bit-by-bit their current condition by using the operators | and &.

The different functions are implemented in the listings 5 and 6. By way of illustration, consider the implementation of the function LockRight(). It only applies the disjunctive operator " | " bit-by-bit. For instance, knowing that 12 (decimal) = 11 00 (binary), the function locks the door Right and does not touch the one of Down.

2. Laying the openings and closings

This first step being defined, we want now our maze to be perfect or, in other words, we want one and only one path between two unspecified rooms. In a technical point of view, it is thus a question of representing all the possible trajectories by a tree. In a practical point of view, the rule will consist in not creating a door between two rooms if they can already connect by another path. Here is, for example, what could be the statement of the creation of a maze : "Mark each room in a single way, with an identifier. As long as the maze is not complete, place yourself - randomly - in a room. If you find a door closed, look at the identifier of the neighbor room. If the identifiers of the two rooms are different, open their common door and unify their identifiers and also their lists. Otherwise, lock the door (for that means that both rooms are already connected; open that door would make up a small island). The maze will be considered as complete when all rooms have the same identifier".

In general, the complexity of a maze can be measured by its tree. The more it is "balanced" (a tree is said to be "balanced" if each one of its branches has approximately the same size), the more complex the maze becomes. It should be noted that, instead of taking cells randomly, one can also move by chance in the maze.

The algorithm is implemented in the constructor of the class Maze. This constructor takes dimensions as input. We start the construction by choosing randomly some cells. This operation enables us to insert some corridors so as to make difficult the search for the good path. Then we insert a last loop carrying out the same task at the end. This loop is there just to check that all rooms are really connected.

3. And now... getting out !

Let us consider a virtual robot which, put in a room, must go through the array in order to find the way out. The robot can only fulfill four types of movements : up, down, left and right. If we start from the principle that it is located at the position (i, j), here is the way to formulate them :

Right : we move to (i + 1, j)

Left : we move to (i - 1, j)

Down : we move to (i, j + 1)

Up : we move to (i, j - 1)

Now it is advisable to apply the classical rule of the right hand (or left hand), which consists in always following with one hand the wall of the maze. It works very well if one starts from an edge of the maze. But if our robot gets thrown in any place of the maze, it runs the risk of turning around, because it did not choose the right hand ! Here we understand all the interest of storing the trajectory carried out in the pile : it enables us to get back and look for another bifurcation instead of retaking infinitely the same path in the same direction. The algorithm for getting out of the maze has the following appearance :

Put into the pile (push) the starting position

While we don't find the way out

Evaluate the opening of the doors of the room for each opened door

If the door has not been crossed

Go forward

Store (push) the new position

Else we are in a deadend

Go back (pop)

In the implementation, it is obvious that we must follow a strict order when looking for opened doors from the one by which we came into the room in the direction of the needles of a watch (case of the left hand) or in the opposite direction (case of the right hand). The final algorithm is implemented in the listing 8.

After compiling the source code and running the program, you will obtain something like the figure 6. It should be noted that the presented source code could implement more complex mazes, like those in a pentagonal, hexagonal shape and so forth. In fact, only the display will basically make the difference.

4. How to visualize the maze

Using Shell, you must type in :

:$ make -f Show

:$ make 30 60 10 &

These commands will enable to draw a maze with a dimension of 30 lines and 60 columns with cells having ten pixels on the side (nine, actually, since a pixel is used for drawing the wall). You will thus obtain something like the figure 5.