Assignment 5: Sewer navigation

Learning Objectives

In this assignment you will gain experience with graph algorithms and the binary heap data structure. You will write algorithms to navigate graphs and learn how to test them. Additionally, you will have the opportunity to optimize your graph searches using various data structures like heaps.

Just as importantly, you will practice working in a large codebase that you did not write yourself. You will need to seek out and read documentation for many classes and methods in order to determine which are relevant to your task, and you will need to juggle your role as “client” vs. “implementer” as you compose new and existing functionality to complete the project.

Timeline For Submision

This is a two-week assignment. So we can make sure that you are on the right track, you will need to turn in a checkpoint submission. This checkpoint submission constitutes 20% of your overall A5 grade.

The checkpoint submission will entail:

This checkpoint submission will not be graded for correctness, just for completion. As long as we see that you’ve seriously attempted to implement these three classes, you will get full credit for this portion of the assignment.

Reminder: Make sure you have made a group on Assignment 5 Checkpoint on CMSX with your partner before you submit!

Introduction

The London Sewer System is well known for its complex web of underground tunnels. In this project you will model and navigate this sewer network, represented as a graph. Our protagonist, McDiver, is tasked with finding a ring with special powers that has been hidden in the sewer. His job is to navigate the maze to find the ring. Fortunately, this does not have to be a completely blind search—McDiver has a detector that can measure the distance to the ring, so he can tell when he is getting closer.

When McDiver finds the ring, it turns out that it is booby-trapped. McDiver is dropped into a lower level of tunnels where there is additional treasure sprinkled all through the maze. Fortunately, McDiver immediately finds the map to this lower level and wants to collect some treasure on the way out. But toxic fumes in the sewer are starting to take a toll. So the goal is to head to the exit in the prescribed number of steps while still picking up as much treasure as possible along the way—quickly enough to avoid falling victim to those noxious fumes!

The student submission that is the most successful at maximizing points will be recognized for excellence by the coveted McDiver Award.

Collaboration Policy

Given the timeline for the summer semester, this assignment should be completed with one other person. If you want to work on this assignment individually, you must have the permission of the instructor to do so. You must review the syllabus policies pertaining to partners under “programming assignments” and “academic integrity.” Partnerships must be declared by forming a group on CMSX before starting work. The deadline to form a CMS partnership or to email the instructor to work individually is Monday, July 22nd, at 6PM. If you do intend to work with a partner, you must review the syllabus policies pertaining to partners under “programming assignments” and “academic integrity.”

As before, you may talk with others besides your partner to discuss Java syntax, debugging tips, or navigating the IntelliJ IDE, but you should refrain from discussing algorithms that might be used to solve the problems, and you must never show your in-progress or completed code to another student who is not your partner.

Frequently asked questions

If needed, there will be a pinned post on Ed where we will collect any clarifications for this assignment. Please review it before asking a new question in case your concern has already been addressed. You should also review the FAQ before submitting to see whether there are any new ideas that might help you improve your solution.

Tasks To Complete

The list of concrete tasks you need to complete is given below. It is organized in parts based on the anticipated timeline: Part 1 should be completed during Week 1, and Part 2 should be completed during Week 2.

Part 1

Task 1: Application infrastructure - Implement Dijkstra’s algorithm

In this task, you will complete the implementation of Dijkstra’s single-source shortest-paths algorithm in the class graph.ShortestPaths. This implementation is needed by the program in order to generate the mazes the diver searches. In addition, you are likely to find the algorithm useful for other tasks.

Note that the algorithm is to be implemented in a generic way that allows it to be reused in different parts of the program, or even in different programs. The types of vertices and nodes in the graph are parameters to the algorithm, which means you can’t call methods on them directly. Instead, the WeightedDigraph interface (and its parent, DirectedGraph) provide the methods you need to navigate the graph.

By reading its methods’ specifications, you might notice that the ShortestPaths class appears to have two “lifecycle stages”—the methods getDistance() and bestPath() may not be invoked until after singleSourceDistances() has been run. For this reason, you as the implementer should not call these methods while computing shortest paths.

The algorithm uses a priority queue; we have given you a (slow) implementation of the priority queue that should be good enough for this application. Once you implement Tasks 4 and 5, you must substitute the slow priority queue with your new priority queue implementation.

Task 2: Application infrastructure - Test Dijkstra’s algorithm

Having implemented Dijkstra’s algorithm, you must write additional test cases to ensure that your implementation is correct. Add at least two more test cases to tests/graph/ShortestPathsTests.java. An example test case has been provided for reference, but it does not provide sufficient coverage.

The A5 program requires a correct implementation of ShortestPaths in order to run, so if you get stuck on this method, seek assistance from consulting early!

Task 3: London Sewer System - Seek Phase

In this task, you will implement the seek() method in diver/McDiver.java.

On the way to the ring (see figure below), the layout of the sewer system is unknown. McDiver does not know the full maze, but only about the place on which McDiver is standing and the immediately neighboring ones (and perhaps others that McDiver remembers). McDiver also knows the Manhattan distance to the ring (note: the length of the path may be longer). When standing on the ring, the distance is 0.

The figure below corresponds to what you will see in your GUI when running the program. In the lower left, McDiver can be seen diving into the sewer with feet sticking out. This image indicates McDiver’s starting point. Currently, McDiver has traversed all the pink tiles on the way to the ring. The figure with the yellow hat is McDiver; to McDiver’s east, the glowing ring can be seen.

To find the ring, McDiver will potentially have to visit all reachable points in the maze. Fortunately, the maze can be viewed as a graph, and you have seen algorithms for graph traversal! This video on JavaHyperText suggests one way to organize such a traversal (See “dfs walk”).

The goal is to make it to the ring in as few steps as possible. Write your solution to this part as one or more new methods in class diver.McDiver, then call them from method seek(). Be sure to fully document the specifications for your solution’s methods and to assert any preconditions you impose. If your solution uses iteration rather than recursion, then document and assert any invariants of your loop. Trust us—doing this up front will make your life easier. The vast majority of bugs in code like this come from not understanding and enforcing preconditions. Consultants will ask to see your specifications before assisting you in diagnosing your solution.

Implement your solution using the methods of the SeekState interface to inspect the maze and to move McDiver:

long currentLocation()
Return the unique identifier associated with McDiver’s current location.
int distanceToRing()
Return McDiver’s current distance along the grid (NOT THE GRAPH) from the ring.
void moveTo(long id)
Change McDiver’s current location to the node given by id.
Collection<NodeStatus> neighbors()
Return an unordered collection of NodeStatus objects associated with all direct neighbors of McDiver’s current location.

Because your seek() method cannot see the whole maze in advance, you are unlikely to get lucky and walk the shortest possible path. However, there are heuristics you can use to improve your chances of taking a more direct route. The fewer steps you take beyond the minimum possible, the larger a score multiplier you’ll receive (“Bonus” in the GUI).

Screenshot of maze in seek phase.
Figure 1: Exploring the maze in the seek phase.

Part 2

Task 4: London Sewer System - Scram Phase

In this task, you will implement the scram() method in diver/McDiver.java.

Because the sewer system is an unhealthy environment, McDiver must get to the exit of the lower level within a prescribed number of steps, while also trying to pick up treasure on the way. Fortunately, McDiver now has a complete map. See Fig. 2, which also shows the pane on the right of the GUI, giving information about the sewer system. To summarize, the goal of the “scram” phase is to get to the exit within a prescribed number of steps, which will always be possible. In the figure below, the exit/entrance is in the upper-left corner of the sewer system—you see McDiver with feet still showing.

McDiver’s score is the product of these two quantities:

  1. The value of the coins that McDiver picks up during the scram phase.
  2. The score multiplier from the seek phase.
Screenshot of GUI during scram phase.
Figure 2: Collecting coins in the scram phase.

As with the seek phase, implement your solution to this part as new methods in class diver.McDiver, then call them from method scram(). Your methods must have complete specifications, and you should assert any preconditions and invariants. A good starting point is to write an implementation that takes the shortest path to the exit, which is guaranteed to succeed. (Hint: use your implementation from Task 1!) After that, consider how to traverse the sewer system to pick up more coins to optimize your score using more advanced techniques. However, the most important part is always that McDiver successfully gets to the exit of the sewer system in the prescribed number of steps. If you improve on your solution, make sure that McDiver never fails to get out in time.

The scram phase is implemented by interacting with the maze and driver using the following methods from the ScramState interface:

Collection<Node> allNodes()
Return a collection containing all the nodes in the graph.
Node currentNode()
Return the `Node`` corresponding to McDiver’s location in the graph.
Node exit()
Return the Node associated with the exit from the sewer system.
void moveTo(Node n)
Change McDiver’s location to n.
int stepsToGo()
Return the steps remaining to get out of the sewer system.

If you want to use your ShortestPaths as part of your solution to scram() (highly recommended), you might find the class game.Maze to be useful.

Task 5: Priority queue

In Task 1, we gave you a priority queue implementation that you can use for ShortestPaths.java. But as we said, it is a slow implementation. Your next task is to implement HeapPQueue, a Priority Queue implementation using the heap data structure, as a replacement.

Study the provided source code for graph.HeapPQueue, paying careful attention to its invariants. You will need to implement its methods for adding, removing, and updating elements. We recommend doing so in this order:

  1. TODO 5a: Implement swap(), which will be useful in future methods and will give you practice maintaining the class invariant (since heap and index need to stay in-sync).
  2. TODO 5b: Define “bubble up” and “bubble down” helper methods for the binary heap data structure, using swap() to help you maintain the class invariant. Don’t forget to write clear specifications!
  3. TODO 5c: Implement peek() and peekAtPriority().
  4. TODO 5d: Implement extractMin(), with the help of your swap() and “bubble down” methods.
  5. TODO 5e: Implement add() with the help of your “bubble up” method.
  6. TODO 5f: Implement update().

Once your confidence in your HeapPQueue implementation increased after finding and debugging, replace your usage of our slow priority queue with your new HeapPQueue! Now, ShortestPaths depends on HeapPQueue, so it’s important that HeapPQueue doesn’t have any bugs! So, we should write tests to increase our confidence in our implementation.

Task 6: Testing priority queue

Having implemented HeapPQueue, you must write additional test cases to ensure that your implementation is correct. Some example test cases have been provided for reference, but they do not provide sufficient coverage.

Structure of Codebase

The structure of the code is shown below. Most of the files have helper code that you do not have to (and should not) modify. The file names colored in green have TODOs you have to complete. Files in blue have main() methods that you can run.

A detailed description of each of the packages is also indicated below. You should also consult the JavaDoc documentation for the code release.

a5/src
├── cms.util
│   ├── maybe [dir..]
│   └── FastException.java
├── datastructures
│   ├── HeapPQueue.java
│   ├── PQueue.java
│   └── SlowQueue.java
├── diver
│   ├── McDiver.java
│   └── SewerDiver.java
├── game
│   ├── Main.java
│   ├── GameState.java
│   ├── GUIControl.java
│   ├── Edge.java
│   ├── Maze.java
│   ├── Node.java
│   ├── NodeStatus.java
│   ├── Tile.java
│   ├── ScramState.java
│   ├── SeekState.java
│   └── Sewers.java
├── graph
│   ├── ShortestPaths.java
│   ├── DirectedGraph.java
│   └── WeightedGraph.java
├── gui
│   ├── GUI.java
│   ├── DiverSprite.java
│   ├── MazePanel.java
│   ├── OptionsPanel.java
│   ├── Sprite.java
│   └── SelectPanel.java
a5/tests
├── datastructures
│   └── HeapPQueueTest.java
├── graph
│   └── ShortestPathsTest.java
a5/res [Images needed for GUI]
a5/reflection.txt
a5/checkpoint.txt

Here is an overview of all the packages contained in this codebase.

Running Your McDiver Program

The McDiver application can be run from the class game.Main.

Make sure to turn on assertions (VM option -ea) to get more useful feedback. If you run the program after completing just Task 1, McDiver stands still on the screen and an error message appears telling you that seek() returned at the wrong location.

Some optional flags can be used to run the program in different ways.

Scoring

Most of your points on McDiver come from implementing a solution that always finds the ring and always gets out within the prescribed number of steps. Your priority should be to make sure that your code always does this successfully. If you can always find the ring and always escape, you will get at least 85% of the points for these tasks.

Beyond that basic goal, you can think of ways to optimize the score by taking fewer steps to find the ring and by collecting as much treasure as possible. Algorithms that find the ring more efficiently or that collect more treasure while escaping will get more points. Your score will not be determined by comparing to the work of other students. Full points should be achievable if your solution makes effective use of the ring distance and does a reasonable job of seeking out coins in the scram phase. Beyond an average score of about 20,000 (i.e. when running with -n 30 -s 1), additional performance is just for bragging rights on our leaderboard.

We will also care about the efficiency of your implementation. A single maze should be able to complete within 10 seconds.

Restrictions

Tips

What to Submit

Before you submit, make sure you have made a group on CMSX with your partner! (Remember: you are expected to do this before starting work together.) Also make sure to update the file reflection.txt with information like the time you spent and your group’s identification.

Then upload a zip file named “a5.zip” containing at least the following six files: McDiver.java, ShortestPaths.java, ShortestPathsTest.java, HeapPQueue.java, HeapPQueueTest.java, and reflection.txt to Assignment 5 on CMSX before the deadline. The zip file should be structured like the released code, with a top-level a5/ directory. For example, McDiver.java should be in a5/src/diver and ShortestPathsTest.java should be in a5/tests/graph. You may also include in the zip file any extra Java source files that you added for your implementation, in the appropriate directories. Do not change any given code outside of their TODOs—when we test your program, reference implementations of all other classes will be used.

After you submit, CMSX will automatically send your submission to a smoketester. The purpose of the smoketester is to give you confidence that you submitted correctly. You should receive an email from the smoketester shortly after submitting. Read it carefully, and if it doesn’t match your expectations, confirm that you uploaded the intended version of your file and that your ZIP archive is organized correctly (it will be attached to the smoketester feedback).

Good luck, and have fun!