Assignment 7: Trailblazer
Updated by Anton Apostolatos, Chris Gregg, Chris Piech and Keith Schwarz. Thanks to Julie Zelenski, Nick Parlante, Jerry Cain, Eric Roberts, Dawson Zhou, Leonid Shamis (UC Davis), Marty Stepp, and Marissa Gemma.
For your final assignment of the quarter, you will use the skills you’ve learned in this course to implement several classic graph algorithms– including breadth-first search, Dijkstra’s algorithm, and A* search – as you build your own version of Google Maps. In the course of doing so, you’ll get to see how pathfinding algorithms work in the real world. This assignment gives you lots of practice in thinking about how to represent abstract concepts like graphs and paths in software, and how to use your understanding of those abstractions to develop the code. We hope you’ll have fun and see this as a capstone to your CS106B experience!
Turn in the following files:
trailblazer.cpp: code to perform graph path searchesmap-custom.txt: a world map of your own creationmap-custom.jpg: a world map of your own creation
IMPORTANT NOTE: You may use at most 1 late day on this assignment.
Pair Programming
You may optionally work on this assignment as a pair programming assignment.
If you would like to work in a pair on this assignment, you may, under the following
conditions:
- Both partners must be in the same section (time and location).
- At no time should partners be coding alone. To be clear: all coding must be done together, on a single computer. One partner should type, and the other should watch over that partner's shoulder. Each partner should take turns at the keyboard.
- When you go to the LaIR or office hours for help on your assignment, both students must be present in the pair to receive help. Only one partner should sign up for help in the LaIR Queue at a time.
- Pair programming is less about sharing the workload and more about sharing ideas and working together. During the IG for the assignment, if a Section Leader does not think both partners contributed equally and worked together, the SL may forbid pair programming on a future assignment.
- Pairs who "split the assignment" where one partner does part of the assignment alone, and the other partner does another part of the assignment alone, will be in violation of the Honor Code.
Overview
This program displays various road maps and allows users to find the shortest path between any two nodes. For example, if the user loaded the Stanford map and selected a node at the top of the Oval and another node at FroSoCo, your program should display the best route:
As it does so, it will color the vertexes green and yellow based on the colors the algorithm assigns to them (more on these colors below). Once the path is found, the program will highlight it and display information about the path cost in the console.The user can select one of four path-searching algorithms from the drop-down menu at the top:
- Breadth-first search (BFS)
- Dijkstra's algorithm
- A* search
- Alternative Route
The window contains several controls. You can load world maps by selecting them from the drop-down menu and then clicking the "Load" button. The maps for this assignment use real road map data; the Stanford, San Francisco, and Istanbul maps are open source, provided by www.openstreetmaps.org.
In trailblazer.cpp, you will implement the following four functions:
Path breadthFirstSearch(RoadGraph& graph, RoadNode* start, RoadNode* end) Path dijkstrasAlgorithm(RoadGraph& graph, RoadNode* start, RoadNode* end) Path aStar(RoadGraph& graph, RoadNode* start, RoadNode* end) Path alternativeRoute(RoadGraph& graph, RoadNode* start, RoadNode* end)
Provided Data Types
Each of the first three algorithms you will implement is a path-searching algorithm taught in class; the fourth will be explained in greater detail later in the spec. For all of them, you will need to make use of a few special data types that we provide for you: RoadGraph, RoadNode, RoadEdge, and Path.
The road network world is represented by a RoadGraph, which is a thin wrapper around the BasicGraph we saw in class. A vertex (RoadNode) represents a specific location in the world. An edge (RoadEdge) between two vertices means that there is a direct road between the two. The cost of the path is the time it takes to traverse that road.
Path is an alias for a Vector<RoadNode*>. In other words, Path is a typedef, which is essentially a shorthand for another type; we use typedefs for readability— it’s much easier to manage the expression Path than Vector<RoadNode*> in your code.
Here are the member functions contained in RoadGraph, which you must use to implement your algorithms:
RoadGraph
| RoadGraph Methods | Description |
|---|---|
Set<RoadNode*> neighborsOf(RoadNode* v) |
gets all RoadNodes that can be reached by a single edge from v |
RoadEdge * edgeBetween(RoadNode* start, RoadNode* end) |
returns the edge that connects start to end |
double maxRoadSpeed() |
the fastest speed of any edge in the graph |
double crowFlyDistanceBetween(RoadNode* start, RoadNode* end) |
the distance between two nodes as the crow flies. |
Each vertex in the graph is represented by an instance of the RoadNode structure, which has the following members for you to use:
RoadNode
| RoadNode Member | Description |
|---|---|
string nodeName() |
vertex's name, such as "r34c25" or "vertex17" |
Point location() |
returns the position of the node on the map |
void setColor(Color c) |
sets the color of the node in the display |
string toString() |
returns a printable string representation of the vertex for debugging |
When you call setColor on a RoadNode, the GUI is automatically updated, the program’s internal count of the number of vertices that you touch is increased, and a delay is added (so you can see your algorithm animate). All vertex colors are reset before each of your path-searching algorithms is called.
Finally, each edge in the graph is represented by an instance of the RoadEdge structure, which has the following members:
RoadEdge
| RoadEdge Member | Description |
|---|---|
RoadNode* from() |
the starting vertex of this edge |
RoadNode* to() |
the ending vertex of this edge |
double cost() |
cost to traverse this edge |
string toString() |
returns a printable string representation of the edge for debugging |
Graph Algorithm Details
For each of your path-finding algorithms, you should search the given graph for a path from the given start vertex to the given end vertex. If you find such a path, you should return a list of all vertices along that path, with the starting vertex first (index 0 of the vector) and the ending vertex last.
If no path is found, return an empty path. If the start and end vertices are the same, return a one- element vector containing only that vertex. Though some graphs may be undirected (i.e., all edges go both ways), your code should not assume this. You may, however, assume that the graph passed in is not corrupt.
Our provided main client program will allow you to test each algorithm one at a time before moving on to the next. You can (and should) add more functions as helpers, particularly to remove redundancy between some algorithms containing similar code.
Your algorithm should work on any RoadGraph instance, such as this map of Middle Earth that can help Frodo get from the Shire to Mount Doom:
Coloring: In addition to searching for a path in each algorithm, we also want you to add some code to give colors to various vertices at various times. This coloring information is used by the GUI to show the progress of your algorithm and to provide the appearance of animation. To give a color to a vertex, call the color member function on that vertex’s RoadNode object, passing it a global color constant such as Color::GRAY, Color::YELLOW, or Color::GREEN. For example:
// set the start vertex's color to green start->setColor(Color::GREEN);
Here is a list of which colors you should use and when:
- enqueued = yellow: Whenever you enqueue a node to be visited for the first time, such as in BFS and Dijkstra’s algorithm when you add a node to a data structure for later processing, color it yellow (
Color::YELLOW). - visited = green: Whenever your algorithm directly visits and examines a particular vertex, such as when it is dequeued from the processing queue in BFS, color it green (
Color::GREEN).
The provided GUI has an animation slider that you can drag to set a delay between coloring calls. As long as the slider is not set all the way to the left, each call to setColor on a vertex will pause the GUI briefly, causing the appearance of animation, so that you can watch your algorithms run.
Path Finding
See the expected output files for reference on what your program should do. For Dijkstra's and A* you should get the same path costs as shown in the expected outputs. But you do not need to exactly match our path itself, nor its "locations visited", so long as your path is a correct one.
Check out the search handout for an example of the search algorithms. You can choose to rely on the pseudocode we go over in lecture, or try to come up with your own pseudocode of the algorithms on your own.
Breadth-first search implementation notes: Implement the version of the algorithm pseudo-code from lecture. Make sure to keep track of nodes that you have already visited.
Dijkstra's algorithm implementation notes: The version of Dijkstra that we talk about in class is slightly different than the version in the book. Your implementation of Dijkstra's algorithm can follow any version. The one we talked about in lecture is probably the easiest. The priority queue should store paths, and once you find a path that ends in the destination, you should reconstruct the shortest path back. See the lecture slides for more details.
A* implementation notes: As discussed in class, the A* search algorithm is essentially a variation of Dijkstra's algorithm that uses heuristics to fine-tune the order of elements in its priority queue to explore more likely desirable elements first. So when you are implementing A*, you need a heuristic function to incorporate into the algorithm - this is discussed below.
One handy feature of the display is that it lets you easily compare the behavior of Dijkstra's algorithm and A* (or any pair of algorithms). Simply try performing a search between two points using Dijkstra's algorithm, then select A* and press the "Run" button at the top of the GUI window. This will repeat the same search using the currently selected algorithm, so you can see how much more efficient A* is. If you run "Alternative Path" as your second algorithm, it will keep the previously-run algorithm visible so you can compare the original and alternate paths.
A* Heuristic
In order for A* to work, you need to define a heuristic function which under-estimates the cost of travelling between two vertices.
For a road map (where cost is travel time), a simple heuristic is to calculate the time it would take to get between the nodes assuming that there was a direct super highway between the two nodes. If the speed of a super highway is as fast or faster than the speed on any road, then the algorithm will underestimate the true graph distance (which makes it an admissable heuristic). To calculate how long it would take to travel along a super highway between two nodes, use the two RoadGraph functions crowFlyDistanceBetween and maxRoadSpeed.
Recall that travelTime = distance / speed .
Your A* search algorithm should always return a path with the same length and cost as the path found by Dijkstra’s algorithm. If you find that the algorithms give paths of different costs, it probably indicates a bug in your solution.
Alternative Route
When travelling between two points on a road map, you may want to take the fastest route, but if there is a reasonable alternative you might prefer that instead. For example, though highway 101 is often the slightly faster way to get to San Francisco from the peninsula, highway 280 is more beautiful. (Chris Gregg thinks that you should also consider going all the way to highway 1.) Your final task is to implement the alternativeRoute function.
In this example the shortest path between the oval and the back of MemChu is shown in red, and a next best alternative is shown in blue:
We already know how to find a shortest path from a start to a goal. How do we find an alternate route?
To find an alternate path from a start node to an end node, first we are going to calculate the best (i.e., shortest) path between start and end. Then, for each edge in the best path we are going to calculate the shortest path from start to end that ignores that edge. Each search will thus return a candidate “alternate route”. Your function should return the lowest cost alternate route that is sufficiently different from the original best path. (When we say “sufficiently different,” we mean according to a threshold that we define for you as a constant, SUFFICIENT_DIFFERENCE, with a value of 0.2.)
To calculate the difference between two paths: we define the difference of an alternate path P from the best path B to be the number of nodes that are in P but are not in B, divided by the number of nodes in B:
For each edge in the best path you will produce one candidate alternate route. Your function should choose, from those candidates, the shortest path that has a difference score greater than 0.2 when compared to the original best path (i.e. greater than the defined constant SUFFICIENT_DIFFERENCE).
The shortest alternate route is the path Start -> D -> A -> B -> C -> End. However it has a difference score of 0.2 (recall that we are looking for a path with difference score greater than 0.2). The shortest alternative that also has a difference greater that 0.2 is: Start -> A -> E -> F -> C -> End
That is the path that your alternative path algorithm should return.
There are different ways to accomplish this modification to your path algorithm. One option is to simply write a separate and modified Dijkstra or A* function that can ignore or exclude an edge. While this option is allowed for your project, it does duplicate a lot of code. A better option would be to refactor your code and write a modified function that performs Dijkstra or A*, and can either perform the standard algorithm or can ignore a given edge. Then, modify your original Dijkstra or A* function to simply call your new function.
