CMSC 132 -- Project 4
Maze Solver
Project Due: Wednesday 3/30/05 at 11:00 PM [This project is LONGER than previous ones, so start EARLY!]
This is a closed project. You are expected to do all of the work on this project without consulting with anyone other than the CMSC 132 instructors and TAs. Treat this project as though it were a take home exam. If you have any questions about whether or not a certain topic is okay to discuss with classmates or friends, please ask your instructor.
The goals of this project are:
Practice with the Java collections framework
Practice constructing a graph
Implement Depth-First-Search, Breadth-First-Search, and Dijkstra's algorithm
To see the finished product, click here!
In the demo, when you click the DFS or BFS buttons, the red squares are vertices that have been visited, the green squares are vertices that have been seen but not visited. When you run Dijkstra's, the black numbers are the weights, the red numbers are distances that have been optimized, the green numbers are distances that are better than "infinity", but may not yet be optimal.
Before you read further about the project, it would be a good idea to experiment for a few minutes with the demo program, above. Try all three of the search algorithms several times and try to understand what they are doing. (To see Dijkstra's algorithm working to its fullest, you should generate a maze with more than 1 solution. For a 10 by 15 maze, 20 solutions works well for Dijkstra's.) If you do not understand why the three algorithms are behaving as they are, please visit office hours for some assistance.
Most of this project is provided for you. You will be responsible for implementing three methods of the MazeGraph class:
public MazeGraph(Maze m) -- Construct a graph based on an existing Maze. (Details later.)
public void doSearch(boolean isDFS, Callback callback) -- Perform either DFS or BFS on an existing Graph. The flag "isDFS" specifies which type of search you must perform. The "callback" object must be notified every time a vertex is seen or visited. (Details later.)
public void doDijkstra(Callback callback) -- Perform Dijkstra's algorithm on an existing Graph. The "callback" object must be notified every time the "best known distance" to a vertex is improved, and any time the "best known distance" to a vertex if finally optimized. (Details later.)
Important: You may add private methods to the MazeGraph class, but you may not add instance variables (fields) of any kind!
If you are running the program that we have provided (the main method is in the Controller.java class), the mazes are created automatically -- you don't have to worry about it. However, while you are testing your project, you might want to create your own mazes. Take a look at the two Maze constructors -- it's easy to make mazes on the fly.
Each maze consists of a two-dimensional array of Juncture objects. A Juncture represents one location in the maze where you might "walk". For example, below is a Maze with 4 rows and 5 columns. It has 20 Junctures. One of the junctures is marked with a red rectangle.
There are "weights" between adjacent junctures that are not separated by a wall. (They are hidden in the picture above.) These weights are only used when Dijkstra's algorithm is performed. Here is a picture of the same maze with the weights revealed:
There are a lot of things in the Maze class that you should ignore! There are only three methods that you will use:
public int getHeight() -- returns the number of rows (4 in the example above)
public int getWidth() -- returns the number of columns (5 in the example above)
public Juncture getJuncture(int x, int y) -- returns the Juncture object located at position (x, y). IMPORTANT: The coordinate system for doing graphics is a little bit strange. To give you an idea: The juncture in the diagram above marked "start" is at position (0, 0). The juncture marked "finish" is at position (4, 3). The juncture with the red rectangle is at position (2, 1). Make sure that you understand this coordinate system before reading further.
There are a lot of things in the Juncture class that you should ignore! The only methods that you should concern yourself with are the following. To help you understand what they do, we have specified what their return values would be when called on the juncture with the red rectangle:
| Method | Value of method for juncture with red rectangle |
| public boolean hasWallAbove() | false |
| public boolean hasWallBelow() | true |
|
public boolean hasWallRight() |
false |
| public boolean hasWallLeft() | false |
| public int weightAbove() | 5 |
| public int weightBelow() | 0 |
| public int weightRight() | 1 |
| public int weightLeft() | 9 |
The "hasWall" methods will look at one of the four directions surrounding the juncture and will tell you whether or not there is a wall there. They will return true if there IS a wall there, and false otherwise.
The "weight" methods will look at one of the four directions surrounding the juncture and will tell you what the weight is in that direction. If there is a wall in that direction, then the method will return 0.
Your first job will be to turn an existing maze into a graph! (To do this, you will write a special constructor for the MazeGraph class, described later.) Your graph will consist of a Set of Vertex objects and a Set of Edge objects. The Vertex and Edge classes are already written for you. Here is an idea of how the graph will be constructed: Your graph will have one Vertex for each Juncture in the maze. If two Junctures in the maze are adjacent and there is no wall between them, then the corresponding Vertices of the graph will be connected by an Edge. Think about that before reading further.
Note: There are more efficient ways of storing the data for this project! We are aware of that, so please do not bother mentioning it -- and NO, you cannot do it any other way.
A Vertex object corresponds to one Juncture from the maze. In the example maze pictured above, there are 20 Junctures. That means that the corresponding Graph should have 20 vertices -- one for each Juncture. When you create the Vertices, you will use a constructor that looks like this: public Vertex(int x, int y)
The parameters for the constructor are the x and y coordinates of the corresponding juncture. Once the Vertex is constructed, you will never need to access the x and y coordinates -- they are there so that the GUI will be able to visually show how the three algorithms (DFS, BFS, Dijkstra) are progressing.
Each Vertex keeps track of the other Vertices that are adjacent to itself. (There is an internal List). The methods you will use to access the list of Adjacencies for a particular Vertex are:
public boolean addAdjacency(Vertex v) // add the Vertex v to the list of adjacencies for the current Vertex
public List getAdjacencies() // return the list of adjacent Vertices to the current Vertex
There are other methods of the Vertex class that you will be using. They will be described later when we discuss the DFS, BFS, and Dijkstra's algorithms.
An edge object knows about the two Vertices that it "connects". Each edge has a weight. Below are the Edge methods that you will use:
public Edge(Vertex x, Vertex y, int weight) // Construct an Edge connecting x to y with weight weight
public Vertex getFirstVertex() // Returns one of the vertices
public Vertex getSecondVertex() // Returns the other vertex
public int getWeight() // Returns the weight
You must implement this method first! The signature is: public MazeGraph(Maze m)
The basic idea is that you will create a graph with one vertex for each juncture in the maze. The vertices in your graph will be connected by an edge whenever the corresponding junctures in the maze are adjacent and there is no wall between them. The weight of the edge connecting two vertices will be the weight that appears on the maze between the two corresponding junctures. Think about the paragraph you have just read and make sure you understand it before you try to implement this method!
As you can see, a MazeGraph is constructed from an existing Maze object, m. There are exactly four fields of the MazeGraph class. You may not add any other fields to the MazeGraph class! The fields are:
private Set vertices // a set of Vertex objects
private Set edges // a set of Edge objects
private Vertex start; // the Vertex corresponding to the "Start" juncture in the maze (upper left corner)
private Vertex finish; // the Vertex corresponding to the "Finish" juncture in the maze (lower right corner)
When this method is over, the Set "vertices" should contain one vertex for each Juncture in the maze m (including the "start" and "finish" Junctures). After you have constructed all of the vertices, it is your job to populate the set of adjacencies for each Vertex. Again, two vertices are "adjacent" if their underlying junctures in the maze are adjacent (one is situated directly above, below, left, or right of the other) and there is no wall between them. Going back to the example pictured earlier, the Vertex corresponding to the juncture containing the red rectangle is adjacent to exactly three other Vertices: The vertex corresponding to the juncture above, the vertex corresponding to the juncture to the right, and the vertex corresponding to the juncture to the left. Note that there is some redundancy in the adjacency lists: If vertex A appears in the adjacency list for vertex B, then vertex B must also appear in the adjacency list for vertex A.
When the method is over, the Set "edges" should contain one edge for each pair of adjacent vertices. The weight of the edge is determined by the weight between the corresponding junctures of the maze. Going back to the example pictured earlier, there are three Edges extending from the vertex corresponding to the juncture with the red rectangle. One edge connects it to the vertex corresponding to the juncture above (weight 5), another edge connects it to the vertex corresponding to the juncture to the right (weight 1), a third edge connects it to the vertex corresponding to the juncture to the left (weight 9). (Note that the edge from vertex A to vertex B and the edge from vertex B to vertex A are considered "equal" -- to see this take a look at the equals method of the Edge class. That means that if you try to add both of these to the set of edges, no harm is done, but only one copy stays in the set.)
You may implement this method independently of the Dijkstra method, but you cannot write this method until your MazeGraph constructor is complete.
Note: There are a few variations of DFS that you will find published in various places. We expect you to implement the one described below, which is NOT the most popular one.
The signature for this method is: public void doSearch(boolean isDFS, Callback callback)
The parameter "isDFS" specifies which kind of search you must perform (if it is true you must do Depth-First, otherwise Breadth-First).
The parameter "callback" is an object that must be notified when vertices are "seen" and "visited" during the search. This is used by the Controller of the MazeGUI to display the progress of the search. It is also used by the testing framework, so it is vitally important that you notify the callback object as described herein.
Below are methods of the Vertex class that you will use while implementing this method:
public void markAsVisited()
public void markAsSeen()
public boolean beenVisited()
public void setPredecessor(Vertex p)
Important: You may not access the xMazeLocation and yMazeLocation fields of the Vertex class while writing this method!
The algorithm you will write is essentially the same as what was presented in class or found in your textbook. The basic idea is to maintain a list of vertices that have been seen, and then to visit them one by one. Below are some important distinctions:
Starting the Algorithm
You may assume that when your method is called, none of the vertices are marked as seen or as visited
Create an empty list that will contain vertices that have been seen but not visited
Begin by adding the vertex "Start" to the List. Mark it as seen by calling markAsSeen()
notify the callback object that the Start vertex has been seen by calling the callback's seen() method
Now go through a loop where each pass through the loop will "visit" one of the vertices that are in the List. If you are doing DFS, then you should treat the List as a stack; if you are doing BFS, then you should treat the List as a queue. (In other words, the distinction is merely: which end of the List do you remove things from?)
Whenever a vertex is "visited" you must:
remove the vertex from the List
check if the vertex has already been visited, if it has then just skip over it and process the next one. (Use beenVisited() to check.)
mark it as visited by calling markAsVisited()
notify the callback object by calling its visited() method
check if the vertex is equal to the vertex "finish". If it is, then your search is over, so you must notify the callback object by calling its doneSearch() method and then return from the doSearch method.
proceed by cycling through the adjacencies of this vertex looking for ones that have not yet been visited. (You can use the method beenVisited() to determine if each adjacency has already been processed.) For any adjacency you discover that has not been visited before, follow instructions below:
When a Vertex is discovered that has not been visited before:
set it's predecessor to be equal to the vertex you are currently visiting by calling setPredecessor()
mark it as seen by calling markAsSeen()
notify the callback object by calling its seen() method
add this vertex to the list of vertices that have been seen but not visited
Note: The mazes that we create always have a solution leading from the start to the finish, so the search algorithm will always eventually visit the vertex "finish".
You may implement this method independently of the doSearch() method, but you cannot write this method until your MazeGraph constructor is complete.
Important: Only the last two release tests will require that you have implemented Dijkstra's algorithm, so you should work on this portion of the project AFTER you are already passing the release tests for DFS/BFS. (The 2 tests for Dijkstra's will be worth 20% of your grade on the project.)
The signature for the method is: public void doDijkstra(Callback callback)
The parameter callback is an object that must be notified when vertices are added to the "Finished Set" (after the vertex's optimal distance has been obtained), and also when the "best known distance" for a vertex improves. This mechanism is used by the Controller of the MazeGUI to display the progress of the search. It is also used by the testing framework, so it is vitally important that you notify the callback object as described herein.
Below are methods of the Vertex class that you will use while implementing this method:
public void markAsFinished()
public void setBestDistance(int b)
public void setPredecessor(Vertex p)
public int getBestDistance()
Important: You may not access the xMazeLocation and yMazeLocation fields of the Vertex class while writing this method!
The algorithm you will write is essentially the same as what was presented in class or found in your textbook. Below are some important distinctions:
Starting the Algorithm:
Set the "best known distance" for the vertex "start" to 0. (Call the setBestDistance() method.) The best known distances for the other vertices are automatically set to "Infinity" when the vertices are constructed, so you don't have to set them all.
Perform the usual loop for Dijkstras -- each pass through the loop processes the vertex with the smallest "best distance so far". (Use the method "getBestDistance" to obtain the best known distances for the vertices.) For each pass through the loop do the following with this vertex:
Processing the vertex with smallest "best known distance"
mark the vertex as finished by calling markAsFinished()
notify the callback object that the optimal distance for this vertex has been obtained, by calling the callback's distanceOptimized() method
Check if this vertex is equal to the "finish" vertex. If it is, you are done, so you should notify the callback that you are done by calling its doneDijkstra() method, and then return from the doDijkstra() method.
cycle through this vertex's adjacency list, trying to find vertices (that are not already finished) whose best known distances can be improved. For each such adjacency you find, do the following:
Processing a vertex whose "best known distance" can be improved
Set the new "best known distance" for the vertex by calling setBestDistance()
Set the predecessor for this vertex to be the one that was used to improve the distance. (Use the setPredecessor() method)
notify the callback object that this vertex's distance has been improved, by calling the callback's distanceImproved() method
Important Note: Suppose vertex A is adjacent to vertex B. During this algorithm you will need to obtain the weight of the edge connecting A to B. Do not be surprised if you search the set "edges" but do not find an edge from A to B! The edge may be in the set, but listed as a connection from B to A. We do not allow both versions of the edge in the set. (To see how this is enforced, take a look at the equals method for the Edge class.)
The first two public tests will test if your MazeGraph constructor is doing it's job. They will use the three-by-three maze below:
The first test will check that you have 9 vertices, that the fields "start" and "finish" are assigned to the correct vertices, and that the adjacency lists for all of the vertices are correctly populated. The second test will check that you have 8 edges, that they are connecting the correct vertices, and that the weights are correct.
The third public test will check to see if you are calling the callback methods in the correct sequence. It uses the two-by-two maze, below:
The correct sequence is:
mark vertex (0, 0) as seen
visit vertex (0, 0)
mark vertex (1, 0) as seen
visit vertex (1, 0)
mark vertex (1, 1) as seen
visit vertex (1, 1)
done
The first 4 release tests will test your DFS/BFS algorithm. The last two will test Dijsktra's algorithm.
Your grade on this project will be calculated as follows: