CIS 110 Programming Assignment: Mazes

DFS Mazes

Programming Assignment

Goals

Learn about graph data structures.
Learn about depth-first search.
Find out why slime molds are so awesome.

URGENT

Solve secrets.maze to receive the first clue to Dr. Brown's whereabouts! (If you missed it, the video played during lecture is here). The 10am lecture video is here and the 12pm lecture video is here).

Submission

This is a two-part assignment. Part I is hw09, Part II is hw10. Part II builds on Part I, and will not work if your Part I is incomplete. You should not assume that Part I is easier than Part II, or vice versa.

Part I (hw09): Submit Maze.java with all the API methods marked "(Part I)" implemented, and a completed readme_maze_I.txt file.
Part II (hw10): Submit Maze.java with all API methods implemented (we will only grade the methods from Part II, but they build on Part I), and a completed readme_maze_II.txt file. You may optionally submit a DrawMazeEC.java and/or an extra.zip file containing your extra credit submissions.
WARNING: You may not use late days on Part II (hw10). The usual grace period rules apply though. It is due Sunday night rather than Thursday for everyone, but we need them in by then so we can get them graded.

Background

Imagine it's the first day of CIS 110 and you're trying to find your way around the engineering building to Towne 100. You're trying to make it to lecture on time so that your absolutely terrifying 110 professor doesn't humiliate you in front of the entire class for being late. But you're lost! Corridors double back on themselves. The third floor of Levine connects to the second of Towne. You decide to follow the corridor and it somehow leads you to the floor above, though you have no memory of climbing stairs. You're running out of food and water. If only you knew how to get to the engineering cafe!

In this totally plausible scenario, what do you do? You could strike out in random directions, bouncing off walls until you're lucky enough to get out and see your family again. Or you could be strategic. Pick a path, follow it until it either doubles back or reaches your destination. Do this with every possible path and, maybe by the end of the semester, you'll know a path to your 110 lecture! Alternatively, you could use a computer to solve the maze for you, and have it show you the path to take (we'll pretend GPS works inside SEAS).

Tips for this assignment.

Here are some suggestions for things to look at that should make you more comfortable with the concepts in this assignment:

Review the FloodFill.java example from lecture to understand how depth-first search works. You can use floodfill.png as a test image. This example does not use a graph, but the algorithm is the same. The key is to think of every pixel in the image as a vertex that is connected to the pixels above, below, left, and right of it.
Work on your program in very small steps. After each step, make sure your program compiles, and if possible test it. For example, when you write your constructor, write only the code to read in the vertices. Compile your program. Add test code to print a graph, and write a main function to test it. Don't move on to reading edges from the .graph file until this works.

Part I

In Part I of the assignment, you will write a Maze data type that can read in .maze files, and print them out in the same format. You should be able to use your Maze class with our DrawMaze and NavigateMaze programs. (We do not give you source for these programs, only the compiled .class files because the source would reveal how to do Part II; you are invited to write your own versions as extra credit.) If you also download pop.wav and put it in the same directory as NavigateMaze.class, you'll get sound.

Representing mazes as graphs.

There are many different ways to represent a graph in Java. We will use a simple data structure that works well when there are relatively few edges in the graph. We will store the vertices in an array rooms[], and refer to them by their index in the array. So vertex i means the vertex stored at rooms[i].

Vertex class. Each vertex stores a linked list of the edges leaving it. It also stores two ints, x and y, to indicate the position of the vertex/room in the maze and a string name for referring to it. The purpose of name is strictly descriptive — for example, this would be where you would store the name of a lecture hall. (If we were making a full-fledged, object-oriented design, we would make the name and edges instance variables private and provide methods to manipulate. But each of those methods would have only one or two lines of code, and we would be complicating the program rather than simplifying it. Instead, we just make the name and head variables public.)

public class Vertex {
    public String name;
    public int x;
    public int y;
    public EdgeListNode edges; // list of edges leaving this vertex
}

EdgeListNode class. As the name suggests, an EdgeListNode is a node in a linked list. Each Vertex object that you create will have a pointer called edges to the first node of a linked list of edges. Each EdgeListNode defines an outgoing edge from that particular Vertex. Since we're storing the vertices in an array (rooms[]), an EdgeListNode object defining an edge only needs to contain the index of the vertex it is pointing to in order to define an edge. Remember, this is a directed graph. (You can make the corridors in your maze two-way by adding edges in each direction, although the animation in NavigateMaze may look a bit funny if you have two-way corridors.) If the edge is A to B, the EdgeListNode defining this edge will be in the linked list of A and its target will be the index of B. Another way of thinking about this is that edges is just the head of a list of vertices/rooms that can be reached directly from v without going through any other vertex/room.

public class EdgeListNode {
    public int target;  // index of target vertex of this edge
    public EdgeListNode next;   // next node in linked list of edges
}

Note: When you create a Vertex, say v, create a dummy node dummy for v.edges to point to. Set the dummy.target to -1 and a dummy.next to null. Never insert any new nodes before this one, so it remains at the beginning of the list, and you can avoid some edge cases on your loops. Even though this is an implementation detail that you would normally be free to decide for yourself, the testing programs we give you will assume you have a dummy node.

Your Program.

Write a class Maze with the following API. We recommend implementing and testing the methods in the order they are described in the paragraphs below.

public class Maze
-------------------------------------------------------------------------------------------
Maze(String filename)                 // Maze constructor                         (Part I)
Vertex[] getRooms()                   // return the array of rooms in the graph   (Part I)
String toString()                     // print out the Maze data structure in the (Part I)
                                      // same format as the input files

EdgeListNode findPath()                       // uses DFS to find a path through the maze (Part II)
                                      // only calculates the solution the first time
                                      // it is called, but returns it every time

The Constructor Your constructor will read in a .maze file and use the information it contains to construct and store a graph in a private instance variable rooms[]. (You may give this variable a different name if you prefer.)

The .maze File A .maze file is basically a text file that contains all the information you need to construct your maze. It consists of:

Number of rooms/vertices An integer that tells you how many vertices are in the graph.
name x y The next n lines each contain the name of a room (String) and its x and y coordinates (integers).
room1 room2 After the list of vertices comes the edges/corridors. Each edge is listed as two integers, room1 and room2, the indices of its start and end vertices. Store each valid edge by adding an EdgeListNode with the target room2 to the tail of room1's list of edges.
-1 -1 The .maze file will end with a line "-1 -1".

For example, here is a sample .maze file:

Now that you know what the .maze file looks like, how do you read it in?

You should read in the .maze file using the In class from the book's standard library.

Read the next line and store the value as the number of vertices N in the array.
Using the information you just read in, for the next N lines, read the name, x- and y- coordinates of a vertex, create a new vertex with those values and store it in the array. Also create the dummy node for the beginning of the vertex's edge list.
Next, read in the edges. For each edge you read in, add it to the tail of the linked list of each vertex the edge is referring to.
The list of edges ends either at the end of the file, or when it reads the line
```
  -1 -1
  
```
Everything after the line "-1 -1" should be ignored. That way it is possible to include a description of the graph as a long comment at the end of the file.

Reading and writing files using In and Out. The book's standard library includes classes for reading and writing file called In and Out. They are very similar to StdIn and StdOut, but work for any file. You will find more information about them in Section 3.1 of the book and booksite, and in the corresponding lecture slides.

Error Checking, break, and continue. You may assume that the input file is correctly formatted, except that some edges may point to non-existent vertices.

You should ignore any invalid edges ie. keep going without adding them to your graph.
The only test file we provide is sample.maze, which does not include any invalid edges. You should create you own test cases to test for invalid edges and other special cases. (You don't need to submit your test cases, but we will be teseting your program rigorously when we grade it.)
When you are testing for invalid edges, or for "-1 -1", you will find the break and continue statements useful.
break ends for and while loops immediately, without executing the rest of the body or the update statement of the for loop, and without checking the continuation condition.
continue immediately goes to the next loop iteration. It skips over the rest of the body, but does execute the update statement in for loops, and checks the continuation condition.
If you create boolean variables called isValidEdge and isEndEdge that are true when the edge is valid and when the edge is "-1 -1", you can include the following statements inside the loop that reads edges to handle these cases:
```
if ( isEndEdge) break;
if (!isValidEdge) continue;
```
Do not move on until you code compiles! Next you will write the methods that will help you test your constructor, but there is no point doing so if the constructor doesn't even compile.

toString(). Implement the toString method. It should produce a string representation of the maze in the exact format of a .maze. It does not need to look identical to the file you read in, but it should have the same vertices in the same order, and the same edges (not including invalid edges, not necessarily in the same order, nor necessarily in the same order as PrintMaze). It will not have any comments from the end of the file, since you do not save those when you read it in.

Write a main function that can read in a graph, and calls toString().
You will need to add line breaks in the string you produce. You can get line break character in a string in Java with the special code \n (the \ character is above the Enter key on US keyboards). A string literal containing only a newline character is written "\n".
Write a private helper method to make a string with the number of vertices and the list of vertex names and coordinates. Call it from toString().
Compile and test with graphs that have different numbers of vertices. Think about which cases might cause problems.
Write a private helper method to make a string with the list of edges leaving a particular vertex. Add a call to toString() to add the edges leaving vertex 0.
Compile and test. You should have the list of vertices, and all the valid edges leaving vertex 0 (but no other edges). Test with maze files that have different numbers of vertices (which possibilities might cause problems?), different numbers of edges, and different numbers of edges leaving vertex 0 (again, which possibilities might cause problems?). Create an input file that has invalid edges leaving vertex zero; they should not get printed out.
Extend toString() to include the edges leaving all vertices. Compile and test.
Add "-1 -1" after all the edges. Even though the file format doesn't require this, you should still do so so that it's easy to add comments to the end.

getRooms(). This method should be a one-liner that return the array of vertices. (Normally, you wouldn't want to expose the array of vertices at all — it's an implementation detail — but we need it for testing.)

Download PrintMaze and save it to the same folder as your (compiled) Maze class. If your Maze class is working correctly you should be able to use PrintMaze to print out a maze:
```
% java PrintMaze sample.maze

...
```
PrintMaze may print out the edges in a different order than they are specified in the original file, but the list of edges should be the same. In other words, it does pretty much the same thing as your toString() method, but without calling toString(). You may find it useful to compare your toString() output to PrintMaze's output. If your graph structure is not consistent or contains invalid edges, you will get a generic error that will not be very helpful for debugging.

Download DrawMaze and save it to the same folder as your (compiled) Maze class. You can use it to display a maze, if your Maze class is working properly:
```
% java DrawMaze test.sample

...
```
Download NavigateMaze and pop.wav, and save them to the same folder as your (compiled) Maze class. You can use NavigateMaze just like DrawMaze to see your maze get solved.

Extra Maze Files. Use seas.maze and bigmaze.maze for further testing.

Part II

The goal of Part II is to solve the maze, using depth-first search. Since this is a two-part assignment, not two separate assignments, your solution must build on your own code from Part I. You are welcome to fix bugs in Part I for this submission, but only the code that is specific to Part II will be graded.

Depth-First Search (DFS). Now let us return to the original problem. Your goal is to find the first possible path from the first room in the maze (rooms[0]) to the last one by applying the depth first search algorithm.

Starting with the first vertex in the maze, recursively explore each of the (un-visited) vertices that can be directly reached from that first vertex by carrying out steps 2-4.
Mark the current vertex as visited.
For each of its outgoing edges, check the vertex the edges leads to. If that vertex is not marked as visited, recursively carry out steps 2-3 until you find the last room on the list.
Once you find the last room on the list, add this room to the solution path, and then recursively add all the rooms that you 'walked' through to get to that last room.

Additional methods and instance variables. You will need some instance variables, e.g. to store your maze. You may create whatever methods and instance variables you need, but all of them must be private because they are internal details of your class. Only the methods listed above (and the main function) should be public, and these must all conform exactly to the API. As in Part I, all your code must be in the Maze class.

findPath() This method should find the maze's solution the first time it is called, using the DFS algorithm described above, and store the resulting linked list in a private variable. If there is no solution it should store null. The idea is to compute the solution only once, and remember it. If you get asked for the solution twice, the second time you just return the solution you remembered.

Study FloodFill.java to understand how DFS works, and how it marks visited nodes. You need to do the same thing on graphs. You can use floodfill.png as a test image.
Create a private dfs() method that takes the indices of a starting Vertex, an end Vertex, a boolean array of which vertices have been visited, and returns a path from the starting to the ending node as a linked list. For now, dfs() should just return null so it compiles; you will fill it in later.
findPath() should create a boolean array to store which vertices are visited (none so far). Then start the actual search by calling dfs() with the Maze's array of vertices, the first vertex as the start, and the last vertex as the end.
Compile! Check that dfs() returns null.
Modify findPath() so it only calls dfs() the first time it is called, and just returns that solution every subsequent time.
Add some print statements to findPath() so you can see whether or not it is calling dfs(). Write a main function that calls findPath() more than once. Since dfs() is still returning null anyway, you can test this with an empty maze (no vertices or edges).

dfs() This is where the real work happens. By taking in a boolean array to keep track of whether or not an array has been visited or not, we can make sure we don't add rooms we've already seen onto the final path solution.

dfs() should return null if it can't find a path to the end vertex. Otherwise it should return a linked list representing the path.
Don't forget to define your base case.
Each vertex that you call dfs() on should be marked as 'visited' in your boolean array.
Warning: Only call dfs() recursively on edges where the target vertex has not already been visited. Even though this condition should be one of your base cases, you need to do the check before calling dfs() to match the behavior of NavigateMaze. It turns out that the animation looks much better if you do the check before calling dfs(), especially if the maze includes two-way corridors.
Add error checking to make sure that vertices are in the maze.

Testing dfs(). Write a main function that:

Add debug code to dfs() to print out the array of visited vertices, start vertex, end vertex, and return value of every recursive call to dfs().
Test your program on progressively more complex mazes. Draw the maze out on paper, and compare the progress of your algorithm to working it out by hand.
Any time you modify your code, start over with the simplest tests to make sure nothing has broken.
Compare your path and the order you visit vertices to NavigateMaze. If you follow the directions to the letter, you should visit vertices in the same order and arrive at the same solution. If you always find a solution, but don't visit vertices in the same order, your program may or may not be correct.
As you test more complex mazes, you may want to write a helper method that prints out a linked list of vertices in a human-readable way (e.g. "A -> B -> C -> null"). If you write such a helper method, you may leave it in your code when you submit.
When simple mazes are working, start testing more complex mazes. You may need to comment out your debug statements so you aren't overwhelmed. If you run into crashes or problems, uncomment the ones that seem most relevant. Sometimes it helps to print things out only for a particular vertex that seems to cause problems, e.g.:
```
if (startVertex == vertices[3]) {
  // print out some debug information
}
```

NavigateMaze is a program you can use to compare your solver results to our solution. Put it in the same directory as your Maze.java, and pass it a .maze file as the command-line argument. As long your implementation of Part I of the assignment is working, it will animate the process of finding the solution to the maze.

Extra Credit

Extra Credit 1. Design one or more interesting mazes of your own and submit them in a zip file names extra.zip. Your mazes must have a different structure than the provided examples. Make sure to end the edge list with "-1 -1", and follow that with a comment. The comment should include your name, "University of Pennsylvania, CIS 110 Spring 2013", and a description of graph if appropriate. We will include especially creative examples in future versions of the assignment.

Extra Credit 2. Write a program DrawMazeEC.java to draw mazes.

You must rely on Maze.java to read in the .maze file, and call getRooms() to retrieve the graph.
Calculate the scale for StdDraw by looking at the coordinates of the maze's vertices.
Our DrawMaze program uses StdDraw.setPenRadius() to draw the corridors as fat white lines on a black background. This is probably the simplest, but not the prettiest, way to draw corridors.
You don't have to make your drawing look identical to DrawMaze. You do not need to indicate the direction of corridors or the names of rooms. If you want to draw the names of rooms, you will find the StdDraw.text() method useful.

Extra Credit 3. Write a NavigateMazeEC.java that animates the maze solution like NavigateMaze. You will include this program in your extra.zip and your TA will run it manually. If you need helper classes, image files, etc., include them in the zip file too. You may use a modified version of your Maze.java for this, but give the modified version a different name so there is no confusion during grading.

Enrichment (Slime Molds)

DFS comes up in numerous applications, and is one of the most fundamental algorithms in computer science. But that isn't really surprising, so let's talk about slime molds instead.

Slime molds are an organisms that spends much of their time looking around for food, and leaving a trail of slime behind them. If they can't find any slime, they form stalks to launch spores toward more fertile ground.
Slime molds aren't quite single-celled (they have many nuclei), but they also aren't quite multi-cellular (there are no cell walls between the nuclei when the mold is in "ooze" mode). We'll call it sesqui-cellular ("Sesqui" is a prefix meaning "one-and-a-half." Technically, slime molds are heterokaryotes according to Wikipedia, but sesqui-cellular sounds much better.)
When a slime mold goes hunting for food and doesn't find any, it retreats and leaves a trail of slime behind. Since it never crosses its own slime (cue Ghostbusters), it doesn't re-explore empty areas.
One effect of the slime mold's behavior is that it is extremely good at navigating mazes. It explores all paths it finds, and retreats when it gets to dead ends. This is very similar to breadth-first search (BFS), which is another staple of computer science.
Slime molds are also very good at figuring out efficient connections between food sources. Humans are pretty good at this too. So if you put some outs down at the positions of major cities, the network a slime creates to feed on them looks remarkably similar to the road and rail networks we come up with to connect the very same cities. Here are the Tokyo rail network, Iberian motorways, and the good 'ol US of A.
Heather Barnett has made oodles (oozles?) of awesome slime mold movies.

CIS 110 Spring 2013 - Introduction to Computer Programming