DFS Mazes |
Programming Assignment
|
Goals
- Learn about graph data structures.
- Learn about depth-first search.
- Find out why slime molds are so awesome.
Submission
This is a two-part assignment. Part I
is hw06, Part II is hw07. 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 (hw06): Submit Maze.java with all the API
methods marked "(Part I)" implemented, and a
completed readme_maze_I.txt
file.
- Part II (hw07): 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.
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 list of vertices will end either with a line
"-1 -1" at the end of the file.
For example, here is a
sample .maze file:
8
C 0 0
I 0 1
S 1 1
A 1 0
1 2 1
1 1 2
B 2 0
0 2 3
0 1
1 2
2 4
2 3
3 4
4 6
4 5
5 7
-1 -1
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 sample.maze
...
- 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.
This assignment was developed by Benedict Brown, Vivian Huang, Jason Merrin, Samantha Merritt, and Hamza Qaisar
Copyright © 2013