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.
Introduction
When studying a Data Structures Course 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.
Introduction
When studying a Data Structures Course 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.
Comments
Post a Comment