ECE297 Communication and Design Winter 2020
ECE297 Milestone 3
Pathfinding and Giving Directions
“If you don’t know where you are going, you’ll end up someplace else.”
– Yogi Berra
“If you don’t know where you’re going, any road will take you there."
– Lewis Carroll
Assigned on Monday, March 2 User Interface and In-lab demo = 5/16
Due on Tuesday, March 24 Autotester = 9/16
Coding Style and Project Management = 2/16
Total marks = 16/100
1 Objective
In this milestone you will extend your code to find good travel routes between two points
embedded in a graph. Algorithms to find paths in graphs are important in a very wide range
of areas, including GIS applications like yours, integrated circuit and printed circuit board
design, networking / internet packet routing, and even marketing through social media.
By the end of this assignment, you should be able to:
1 Find the shortest path between nodes in a graph.
2 Develop a user interface for finding and reporting travel directions.
2 Path Finding
Your code should implement the three functions shown in m3.h; we will automatically test
these functions with unit tests. Your load_map function will always be called by the unit
tests before we call any of the functions in Listing 1. Some tests of each function will be
public and available to you to run with ece297exercise 3 while others will be private and
run only by the automarker after you submit your code.
1 /*
2 * Copyright 2020 University of Toronto
3 *
Page 1 of 7
ECE297 Communication and Design Winter 2020
4 * Permission is hereby granted, to use this software and associated
5 * documentation files (the "Software") in course work at the University
6 * of Toronto, or for personal use. Other uses are prohibited, in
7 * particular the distribution of the Software either publicly or to third
8 * parties.
9 *
10 * The above copyright notice and this permission notice shall be included in
11 * all copies or substantial portions of the Software.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
19 * SOFTWARE.
20 */
21 #pragma once
22
23 #include "StreetsDatabaseAPI.h"
24
25 #include <vector>
26 #include <string>
27
28 // Returns the time required to travel along the path specified, in seconds.
29 // The path is given as a vector of street segment ids, and this function can
30 // assume the vector either forms a legal path or has size == 0. The travel
31 // time is the sum of the length/speed-limit of each street segment, plus the
32 // given turn_penalty (in seconds) per turn implied by the path. If there is
33 // no turn, then there is no penalty. Note that whenever the street id changes
34 // (e.g. going from Bloor Street West to Bloor Street East) we have a turn.
35 double compute_path_travel_time(const std::vector<StreetSegmentIndex>& path,
36 const double turn_penalty);
37
38
39 // Returns a path (route) between the start intersection and the end
40 // intersection, if one exists. This routine should return the shortest path
41 // between the given intersections, where the time penalty to turn right or
42 // left is given by turn_penalty (in seconds). If no path exists, this routine
43 // returns an empty (size == 0) vector. If more than one path exists, the path
44 // with the shortest travel time is returned. The path is returned as a vector
45 // of street segment ids; traversing these street segments, in the returned
46 // order, would take one from the start to the end intersection.
47 std::vector<StreetSegmentIndex> find_path_between_intersections(
48 const IntersectionIndex intersect_id_start,
49 const IntersectionIndex intersect_id_end,
50 const double turn_penalty);
51
52
53 // Returns the time required to "walk" along the path specified, in seconds.
54 // The path is given as a vector of street segment ids. The vector can be of
55 // size = 0, and in this case, it the function should return 0. The walking
56 // time is the sum of the length/<walking_speed> for each street segment, plus
57 // the given turn penalty, in seconds, per turn implied by the path. If there
Page 2 of 7
ECE297 Communication and Design Winter 2020
58 // is no turn, then there is no penalty. As mentioned above, going from Bloor
59 // Street West to Bloor street East is considered a turn
60 double compute_path_walking_time(const std::vector<StreetSegmentIndex>& path,
61 const double walking_speed,
62 const double turn_penalty);
63
64
65 // This is an "uber pool"-like function. The idea is to minimize driving travel
66 // time by walking to a pick-up intersection (within walking_time_limit secs)
67 // from start_intersection while waiting for the car to arrive. While walking,
68 // you can ignore speed limits of streets and just account for given
69 // walking_speed [m/sec]. However, pedestrians should also wait for traffic
70 // lights, so turn_penalty applies to whether you are driving or walking.
71 // Walking in the opposite direction of one-way streets is fine. Driving is
72 // NOT! The routine returns a pair of vectors of street segment ids. The first
73 // vector is the walking path starting at start_intersection and ending at the
74 // pick-up intersection. The second vector is the driving path from pick-up
75 // intersection to end_interserction. Note that a start_intersection can be a
76 // pick-up intersection. If this happens, the first vector should be empty
77 // (size = 0). If there is no driving path found, both returned vectors should
78 // be empty (size = 0).
79 // If the end_intersection turns out to be within the walking time limit,
80 // you can choose what to return, but you should not crash. If your user
81 // interface can call this function for that case, the UI should handle
82 // whatever you return in that case.
83 std::pair<std::vector<StreetSegmentIndex>, std::vector<StreetSegmentIndex>>
84 find_path_with_walk_to_pick_up(
85 const IntersectionIndex start_intersection,
86 const IntersectionIndex end_intersection,
87 const double turn_penalty,
88 const double walking_speed,
89 const double walking_time_limit);
Listing 1: m3.h
A key function in m3.h is find_path_between_intersections. This function must pass
3 types of tests; you can obtain part marks if you pass some of the checks but fail others, but
you will have to pass them all to obtain full marks.
? The route must be legal – that is, it must be a sequence of street segments which form a
connected path from the start intersection to the end intersection. You must also respect
one way streets, and not try to travel down them in the wrong direction. Note that it is
also possible that no legal route exists between two intersections, in which case you should
return an empty (size = 0) vector of street segments.
? Your route should have the minimum possible travel time between the two intersections,
where travel time is defined below.
? You should find the route quickly; you will fail performance tests if your path-finding
code is not fast enough.
The travel time required to traverse a sequence of street segments is the sum of two
components.
Page 3 of 7
ECE297 Communication and Design Winter 2020
? The time to drive along each street segment, which is simply the length of the street
segment divided by its speed limit.
? The time to make turns between street segments. We assume that no turn is required
when you travel from one street segment to another if they are both part of the same street
– that is, we are assuming you hit only green lights when you are going straight down a
street. When you travel from a street segment that is part of one street (e.g. Yonge Street)
to a street segment that is part of another street (e.g. Bloor Street) however, you will have
to make a turn and this will cost turn_penalty extra time. turn_penalty models the
average time it takes for you to wait for a break in traffic and/or a traffic light to turn
green so you can turn.
See Figure 1 for an example of driving paths and travel times.
Blue path:
Figure 1: Two driving paths between Cecil & Ross and College & McCaul; one has a lower travel
time than the other. The turn_penalty is 15 seconds in this example.
The second major function in m3.h is find_path_with_walk_to_pick_up. It is a path
finding function in which you can walk for a specified time to reach an intermediate intersection;
at that intermediate intersection you will meet a car (e.g. an uber or taxi) and you will then
drive the rest of the way to the end_intersection. The walking path must take less than
the walking_time_limit to walk to from the start_intersection and the driving path
must have the minimum travel time possible to the end_intersection from any intersection
that is reachable by walking for at most the walking_time_limit. This function returns a
pair of vectors, with the first representing the walking path and the second the driving path.
Figure 2 gives an example. In this case the start intersection is St. Joseph St. & Queen’s
Park Cres., and the person has a walking time limit of 360 s and a walking speed of 2 m/s.
The person can reach multiple intersections before the car arrives to take him/her to the
Page 4 of 7
ECE297 Communication and Design Winter 2020
end_intersection (Yonge St. & Elm St.). Walking to Bay St. & Wellesley is possible within
the 360 s walking time, and minimizes the driving time to the end_intersection.
start
end_intersection
Walking
path Driving
path
Figure 2: A path from St. Joseph St. & Queen’s Park Cres. to Yonge St. & Elm that consists of a
walking path (to Bay & Wellesley) and a driving path from there to the destination.
To make it easier to verify that you compute turns and travel times correctly, m3.h requires
you to implement compute_path_travel_time (for driving) and compute_path_walking_time
functions; ece297exercise provides unit tests for them. Make sure you pass these unit tests,
as you will not be able to find shortest travel time routes if these basic functions are incorrect.
3 User Interface
Implementing your path finding algorithm is only part of this milestone; you also need to
make this functionality usable by end users. You should decide on commands that will be
typed and/or entered with mouse clicks by the user to specify what path he/she is interested
in finding. The required features of your user interface are:
Page 5 of 7
ECE297 Communication and Design Winter 2020
? Your program must work with any map without recompilation, so the user should be
able to specify the map of interest.
? Users must be able to enter commands that exercise your code to find a path between
two intersections (specified by entering street names at each intersection, e.g. Yonge Street
and Bloor Street).
? Your interface must have some method that allows users to specify partial street names
(e.g. Yong) instead of full street names to identify the street.
? Users must also be able to find paths between intersections by mouse clicking on intersections.
? You must have some method for users to request both types of path finding (drive only
and walk + drive) implemented in this milestone. For the walk + drive function, users
should be able to enter a walking speed and walking time limit as well as the start and end
intersections.
? You must display the found path(s) in the user interface; for full marks this path should
be easy to understand and give a good sense of how to follow it.
? You must print out detailed travel directions to the console or in the graphics. For full
marks, these travel directions must be sufficiently detailed and clear that a typical driver
could follow them.
? You must give informative error messages if the user mistypes something (e.g. an invalid
street or map name).
? You must have some method (e.g. a help GUI button or notes in dialog boxes) so new
users can learn the interface.
Beyond meeting the basic requirements above, your user interface will be evaluated on
how user-friendly and intuitive it is. You should produce user-friendly walking and driving
directions, using both text and graphical drawing. For example, directly printing the sequence
of street segment ids that your path finding code returns would be a completely unusable user
interface! Print out clear directions giving all the information you would want if you were
being given driving directions. Draw an informative picture of the route to follow. Integrating
both your intersection input and driving directions output into the graphics will generally
lead to a more user-friendly design than having the user type and read text at the command
prompt.
When creating a user interface like this it is a good idea to test it on people who are
not part of the development group. Feedback from a person not involved in the design
(friends, family, etc.) is very useful in identifying what is intuitive and what is obscure in
your interface.
Page 6 of 7
ECE297 Communication and Design Winter 2020
Page 1 of 1
file:///C:/Users/Mohamed/Desktop/light-bulb-7.svg 7/8/2014
One part of making your interface more user-friendly is to support good
matching of (partial) input text to street names. You can use your milestone1
functions to achieve a basic partial name matching, but you can also explore
other options to do more than match string prefixes. One option is using
the regular expression < regex> feature in the C++ standard library, which
lets you match general patterns in strings.
4 Grading
? 9/16 marks will come from the autotester.
The auto tester will test basic functionality, speed and that your code has no memory
errors or leaks (via a valgrind test).
? 5/16 marks will be assigned by your TA based on an in-lab demo of your interface.
Your interface should meet all the requirements listed above, be easy to use, and feel fast
and interactive. The sophistication and ease of use of your interface will be compared to
that of the average design in the class to help assess this mark.
? 2/16 marks will be based on your TA’s evaluation of your code style and project management,
which includes planning and tracking tasks on your wiki and using git effectively.
Your TA will review git logs and your wiki page, and ask team members questions about
the design and each member’s contribution to it. If a team member has made a small
contribution or shows poor knowledge of the design, his or her mark may be reduced and if
merited some marks may be transferred to other team members.
Page 7 of 7
版权所有：留学生编程辅导网 2020 All Rights Reserved 联系方式：QQ:99515681 微信：codinghelp 电子信箱：99515681@qq.com
免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。
