CIS 260 - Console Maze Solver

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 is heavily oriented towards solving a graph problem using Java. You are given a Graph class that implements core graph functionality and algorithms. You should use that class (with one minor modification) to solve this graph problem. The major work involves extending a maze generating algorithm from a previous assignment. First, you must convert the generated maze into a graph. Then you feed the graph data into the supplied Graph class and request that it find the shortest path from start to finish.

Requirements

  1. Use the Graph class covered in class. It is available as Graph.java.

  2. Use your previous code that created a maze. You will need to add some code to the very end of the constructor.
  3. You will need to create an identifier for each cell in the maze. Use something simple like R1C5 for the cell at row 1, column 5. You can create these identifiers on the fly. Each cell will be entered into the graph as a vertex. Each connection between cells will be entered into the graph as an edge. Since the graph will automatically take care of vertices if you just add edges, you only have to add the edges - but you need a String ID for the vertices (cells) the edge connects. That's why you will have to create String IDs for the cells.
  4. Do the following:
    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.
  5. The shortest path method 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 method. There is a for loop which is assembling the output String. All you need to do is take the number it wants to add to the String and use that number as an index into the vertex list to get the vertex name instead.

Sample output

> java Maze1 10 10
All cells on board visited: true
All boundaries correct: true
All cells reachable: true
 _ _ _   _ _ _ _ _ _
|  _ _  |  _ _ _    |
|   | | | |   |  _| |
| | |_ _| | |_| | | |
|_|_   _ _ _|  _| | |
|   |_|  _ _ _|  _| |
| |_  |   |   |  _ _|
|_  | |_| |_| | |_  |
|  _|_|  _|  _|_  | |
| |  _ _| |  _  |_  |
|_ _|_ _ _ _ _|  _ _|

Shortest path from R00C03 to R09C07:
R00C03 R00C02 R00C01 R00C00 R01C00 R01C01 R02C01 R03C01 R03C02
R03C03 R03C04 R02C04 R01C04 R00C04 R00C05 R00C06 R00C07 R00C08
R00C09 R01C09 R02C09 R03C09 R04C09 R05C09 R05C08 R05C07 R06C07
R07C07 R07C08 R08C08 R08C09 R09C09 R09C08 R09C07