Motivation:

Team Programming Challenge (in groups of at most 2): Design and implement a GUI based C++ application to randomly construct an n X n maze with a path from a start cell to an end cell. This is a challenging problem that requires implementation of  an adjacency list, “equivalence classes”, the “union-find” algorithm, depth-first search of an undirected graph, and some understanding of the GUI programming, which is completed for you.

Methodology:

Unpack the zip file and run the Maze application. This executable is a complete randomized solution to Lab4. It draws a 40 X 40 maze with walls removed, marks the start and end cells, and finally generates a path from start to end. The path is depicted with blue squares placed in a maze cell that is on the path from start to end. The zip file also contains Maze.h and Maze.cpp, which starts the specification for the maze and completes the drawing of all maze components, main.cpp, which sets up GLUT and OpenGL, and DrawGraph.h and DrawGraph.cpp, which starts the specification of the adjacency list.

The following figures depict the steps the application executes.

Step 1 – After resetting the maze, a new grid is drawn as shown above.

Step2 – After creating the maze, the window is shown above.

Step 3 – After drawing the path, the window is shown above.

The above shows the menu options allowing the user to reset the maze to a new grid, then create the maze, and finally draw the path. These steps must be performed in exactly that order; reset, create, draw.

---

Some Hints

1. Decide on a data structure that will hold the Maze ADT. You may either store the walls that remain in the maze or those that are removed. My implementation assumes that initially all walls are intact so the following discussion is based on this initial state.2. Remove walls from the maze. This is a tricky step as we must ensure that a path from the start cell to the end cell is eventually constructed. For this step you MUST use equivalence classes and the union-find algorithm (refer to Kruskals’ MST algorithm and the UNION algorithm in the text for implementation ideas).

• Initially, each cell in the maze is placed in its own equivalence class with the single cell acting as the representative of the class. So n X n equivalence classes are required. I used a vector<vector<bool>> for my equivalence classes and the union-find algorithm. I found this choice to be “a little easier” than the text suggestions – not more efficient.

• The BEST solution is to randomly select a cell (call it currentCell) in the maze and then randomly select a wall to remove for currentCell. Note this process can get “hairy” if you don’t think about a way to control special cases. Realize that it is possible to consider only EAST and SOUTH walls for all cells except the last column and the last row. Why? Removal of an EAST wall also removes the WEST wall of a neighbor cell. Removal of a SOUTH wall also removes the NORTH wall of a neighbor cell. For the last row of cells we may only remove EAST walls and for the last column of cells we may only remove SOUTH walls. This should also indicate that initially the Maze ADT need only store at most, EAST and SOUTH walls. For the whimpy version of this problem instead of randomly selecting a cell, I used a nested for loop that moved from cell 0 to cell NXN -1, so the whimpy maze and path is always very linear and the path moves nearly on a diagonal – you can do much better!

• Once a wall has been selected for removal, determine which cell in the maze is adjacent to the wall (call it neighborCell). If currentCell and neighborCell are NOT in the same equivalence class then “union” the two classes selecting a new representative for the unioned class. Make sure that all cells in the unioned class “point to” the new representative.

• When an equivalence class contains both the start cell and the end cell the process of wall removal stops. We are guaranteed that a path from start to end exists.

Suggestions: Use a much smaller maze while in the implementation phase. Use a boolean flag for debug output, i.e., if(debug) cout << (“…….”). Carefully test each phase before progressing.  The start cell is fixed as cell ₀ and the end cell as cell _n*n-1. Document your code rigorously.

Step3: Decide on a data structure for a bidirectional undirected Graph ADT. An adjacency list representation works well here and its implementation is spec’ed in DrawGraph ADT. Construct the graph using the information stored in your Maze ADT. As an example, if cell i has no walls then it is connected to cell i+1 and cell i+n (special cases are an exception => last row and last column), additionally cell i+1 and cell i+n are connected to cell i. Cell i may only have a single wall, but it cannot have two walls. The maze is drawn using this adjacency matrix, which is currently specified as a vector<vector<int>> in the DrawGraph ADT. If you use another data structure you will have to modify the code that draws the maze.

Step4: Write a Stack based depth-first search algorithm that traverses the Graph ADT finding a path from the start to end cell. Store your path in the Stack. The specification for this method can be found in the DrawGraph ADT.

Step5: The path is drawn using the contents of the Stack in step4. This step is written for you.