CIS 250 - Solve a maze

The objective of this assignment is:

1. convert a maze into a graph
2. solve a maze using a graph shortest path algorithm

Assignment

This assignment uses the maze creation program you have created in a previous assignment and the graph code given in class to create and then solve mazes. The code for the graph class is available via links later in this document and on the server in the directory: ~dklick/examples/cis250/graph. You can use the graph class with only one small modification to the shortestPath function.

The first step will be to convert the maze you create into a graph. The cells will be the vertices of the graph, and the connections between the vertices/cells will be the edges of the graph. Once the maze is turned into graph data, you just ask the graph for the shortest route from the start cell to the finish cell.

Requirements

1. Create a new graph object.
2. For each cell in the board
1. If the cell is not in the first row and it does not have a wall on its north side, then add an edge to the graph that represents the connection between this cell and the cell to its north.
2. If the cell is not in the first column and it does not have a wall on its west side, then add an edge to the graph that represents the connection between this cell and the cell to its west.
3. The Board class has methods for getting the start and end cells. Get the start and end cells, and send their IDs to the graph's shortest path method. You should get back a String. Print it.
4. The shortestPath function in the Graph class outputs internal vertex numbering. Change it to output the vertex name instead. The spot you want to make the modification is near the very end of the shortestPath function. There is a for loop which is printing the vertex numbers. All you need to do is take the number it wants to display and use that number as an index into the vertex list to display the vertex name instead.

Notes

1. You can create a formatted string in a memory buffer using sprintf.

   Example: sprintf(buffer, formatString, variableList);
   char buf[100];
   sprintf(buf, "%d squared is %d\n", 5, 5*5); // in: <cstdio>
   cout << buf << '\n';

2. You can create a string object from an array of chars as follows: string newString(charArray);
3. You can create a C-style string from a C++ string object using the .c_str() method/function that string objects have.

Graph resources

• edge.h
• edge.cpp
• edgelist.h
• edgelist.cpp
• tovert.h
• tovert.cpp
• vertex.h
• vertex.cpp
• vertexlist.h
• vertexlist.cpp
• graph.h
• graph.cpp

Sample output

$ ./msolve 10 10
All cells on board visited: true
All boundaries correct: true
All cells reachable: true
   _ _ _ _ _ _ _ _ _
|     |   |   |_    |
|_| |_ _|_ _|_  | | |
|  _|   |   |  _| | |
|  _ _| | |_ _|_ _| |
|_  |  _| |  _ _ _  |
| | | |_ _ _|   | | |
|  _|_ _ _  | | | | |
|_ _  |_  |_ _| | | |
|   | |  _|  _ _|  _|
|_|_ _ _|_ _|_ _ _  |

The shortest path from R00C00 to R09C09 is:
R00C00 R00C01 R00C02 R01C02 R01C03 R00C03 R00C04
R01C04 R01C05 R00C05 R00C06 R01C06 R01C07 R02C07
R02C06 R03C06 R03C05 R02C05 R02C04 R03C04 R04C04
R05C04 R05C05 R04C05 R04C06 R04C07 R04C08 R04C09
R05C09 R06C09 R07C09 R08C09 R08C08 R09C08 R09C09