3.43. Building and Running Mazes. The task of finding a path through a maze seems forever fascinating (see Ball and Coxeter 1974). Elaborate mazes may be generated on a computer, and graphics allows you to watch them generated and traversed. The goal is to find a path from the opening at the left edge to the opening at the right edge. Trial and error ultimately pays off, but it's more interesting to develop an algorithm to trace a maze automatically.
Write and exercise a program that generates and displays a rectangular maze of R rows and C columns. The program also must find (and display) the path from start to end. The mazes are generated randomly but must be proper; that is, every one of the R-by-C cells is connected by a unique, albeit tortuous, path to every other cell. Think of a maze as a graph: A node corresponds to each cell where either a path terminates or two paths meet, and each path is represented by a branch. Figure 3.39 shows a small maze and its associated graph. A node occurs at every cell for which there is a choice of which way to go next. For instance, when Q is reached there are three choices, whereas at M there are only two. The graph of a proper maze is "acyclic" and has a "tree" structure. How should a maze be represented? One way is to state for each cell whether its north wall is intact and its east wall is intact, suggesting the following data structure:
var north_wall, east_wall : array[0..num_rows, 0..num_cols] of boolean;
If north-wall[i, j] is true, the ij-th cell has a solid upper wall; otherwise the wall is missing. The 0-th row is a phantom row of cells below the maze whose north walls comprise the bottom edge. Similarly, east_wall[i, 0] specifies where any gaps appear in the left edge of the maze.
Generating a Maze. Start with all walls intact so that the maze is a simple grid of horizontal and vertical lines. The program draws this grid. An invisible mouse is initially placed in a random cell, whose job is to eat through walls to connect adjacent cells. It checks the four neighbor cells (above, below, left, and right) and for each asks whether the neighbor has all four walls intact. If not, the cell has previously been visited and so is on some path. The mouse may detect several candidate cells that haven't been visited: It chooses one randomly and eats through the connecting wall, saving the locations of the other candidates on a stack. The eaten wall is erased, and the mouse repeats the process. When it becomes trapped in a dead end-surrounded by visited cells-it pops an unvisited cell and continues. When the stack is empty, all cells in the maze have been visited. A "start" and "end" cell is then chosen randomly, most likely along some edge of the maze. It is delightful to watch the maze being formed dynamically as the mouse eats through walls.
Running the Maze. Use a "backtracking" algorithm. At each step, the mouse tries to move in a random direction. If there is no wall, it places its position on a stack and moves to the next cell. The cell the mouse is in can be drawn with a red dot. When it runs into a dead end, it can change the color of the cell to blue and backtrack by popping the stack. The mouse can even put a wall up to avoid ever trying the dead-end cell again.
Addendum: Proper mazes aren't too challenging because one can always traverse them using the "shoulderto-the-wall rule." Trace the maze by rubbing your shoulder along the left-hand wall. At a dead end, sweep around and retrace the path, always maintaining contact with the wall. Because the maze is a "tree," you will ultimately reach your destination. In fact, there can even be cycles in the graph and you still always find the end, as long as both the start and the end cells are on outer boundaries of the maze. To make things more interesting, place the start and end cells in the interior of the maze and also let the mouse eat some extra walls (maybe randomly 1 in 20 times). In this way, some cycles may be formed that encircle the end cell and defeat the shoulder method.
Some program specifications:
1) All programming is to be done using an object oriented approach and coded in C++ with extensive use of classes (as discussed in class).
2) Using the graphics library from class, create the maze on the screen dynamically. We will assume 10 pixels across and 10 pixels down for the walls, so calculate the dimensions of the array accordingly.
3) Do not use recursion. Define a class stack and use this data structure.
4) Show the mouse as it dynamically tries to find a path through the maze with the ultimate goal of marking the path through the maze in a color different from the maze color.
5) Use pointer notation for all array manipulation.