Programming withData Structures and Algorithms
Programming withNo doubt you remember the campus tour—the walking backwards, the explanation of meal plans, the intramural sports speech... It's a fine tradition, but the admissions department is running out of willing volunteers. That's where you come in–you've been asked to write a virtual tour guide that will run on a visitor's cell phone. Users can select the type of destinations they wish to see and receive real-time directions from their current location to the nearest destination.
Specifically, the Admissions Office wants an application with the following features:
Your program should run on a mobile phone and give dynamically updated tour directions based on its current location relative to a map supplied by the Admissions Office (see below for the exact data definition).
The user should be able to pick from predefined 'tours', such as a 'Campus Art Tour' or a 'Freshman Dorm Tour'. These tours will also be supplied by the Admissions Office.
A tour consists of a list of stops and a short description of each. Your program should lead the user to each of the stops and display the appropriate descriptions on arrival.
Unlike normal tours, these tours should have no fixed order; your program should simply lead the user toward the closest unvisited stop. If multiple tours are selected, your program should choose the closest unvisited stop from all selected tours, even if this results in tours being interleaved.
The user should be able to add and drop tours at any time. If the user drops a tour while being directed toward a stop on that tour, the program should switch to the closest unvisited stop from the remaining tours. If the user adds a tour that introduces a new, closer unvisited tour stop, the program should switch to that stop.
If the user adds a tour they have previously dropped, they should not be directed to any stops on that tour they have already visited this session. You should, however, provide a way to reset the program entirely without quitting out of it.
Once the user has visited all the stops on all the tours they have chosen, you should display a generic thank-you message until they reset the program or add another tour.
If no tours are selected, your program should give no directions until the user selects one.
The map data you receive will contain many sites that are not tour stops, such as intersections and intermediate landmarks.
All map sites, together with the footpaths between them, form a graph. Since these sites are fairly large, each site will have a specified radius; if the user's current location is within this radius, your program should assume that the user has reached this site (this also helps compensate for GPS inaccuracies).
When the program starts and tours are first selected, your program should find the user's current location. If the user is at a site on the Admissions Office map, your program can give directions from that site to the closest tour stop. Otherwise, your program should first direct the user on the straight-line path toward the nearest site on the map. Once the user has reached a map site, you can proceed to give directions from that site to the desired tour stop.
Once the user reaches a tour stop, your program should display the description until the user is ready to progress. When the user is ready to travel to the next tour stop, the program should construct the shortest route and lead the user to the map sites on this route in order. While directing the user from one map site to the next, your program should give constantly updating heading and distance to the next map site. This way, if the user starts walking in the wrong direction, the distance to travel should increase to reflect the increasing distance to this next map site.
However, if the user gets way off track or decides to take an alternate route, your program should notice and respond accordingly. If the user gets far enough off track that they arrive at a site on the map other than the one they were being directed to, your program should recalculate the closest unvisited tour stop and route of map sites to reflect the user's new location. Your program should also allow the user to tell the program to recalculate if, for instance, the user gets lost. When this happens, your program should once again direct the user on the straight-line path toward the nearest site on the map.
In order to find routes of map sites from the user's location to a tour stop, your program will need to find shortest paths on a weighted graph. You should use Dijkstra's algorithm, which you will learn about in class, to achieve this functionality.
Your implementation of Dijkstra's Algorithm should have roughly the following signature:
dijkstra : (node -> collection of distances and previous nodes)
The exact data definition is up to you, but Dijkstra's algorithm needs to take in a graph and a starting node from that graph and return some collection (vectors work well) of information about each node. This information should include both the total distance from the start node to the node in question and the previous node along the shortest path from the start node to that node. Your algorithm should run in O([s -> s * log s]) time where s is the number of nodes in the graph.
Note that if the graph is well-connected, you have to examine s^2 connections, and the algorithm would run in O([s -> s^2]) time. However, the graphs we are working with, and in general any graph representation of a real-world map, are inherently not well connected. Your algorithm should run in O([s -> s * log s]) time with respect the number of vertices, assuming each vertex has only up to some constant number of neighbors.
Once you have a working implementation of Dijkstra's algorithm, start thinking about how to apply it to the problem at hand. Remember that you need to lead the user between many different tour stops and dynamically update the directions. Plan out your user interface, and think about what GUI functionality you will need to produce a satisfactory product.
This assignment will have a design check, in which you and your partner meet with a TA to discuss what you have completed and your design for the remainder of the assignment. The design check will be part of your grade, so make sure you sign up for a slot by Tuesday. The design checks will take place Tuesday and Wednesday. There is a sign-up sheet on the door to the Fishbowl (CIT 271, at the top of the front stairs).
At the design check you will be asked to:
Demonstrate your working implementation of Dijkstra's Algorithm (including test cases!).
Walk the TA through your code and defend its efficiency.
Describe how you will use it to guide tours and dynamically update directions.
Describe your planned user interface.
Make sure you have thought about all the edge cases that can come up. For example, the same location might end up being part of two tours–what issues might this cause? Do some real brainstorming. There are a lot of little things you can add and/or fix to make your program better. Doing well on this project requires thinking of and implementing a good number of them (though not necessarily specific ones, or even one's we've thought of!).
To run racket on mobile phones you will be using a new language called Whalesong, which compiles Racket to Javascript that can be run in the browser of any smartphone or desktop machine.
Instructions for using Whalesong can be found at: http://hashcollision.org/whalesong/cs019.html
Note: Some of this documentation assumes knowledge of HTML and CSS. We do not assume you already have this knowledge, so if you need help please come talk to us!Opening the generated HTML file can let you test your application entirely on a desktop machine. You will of course eventually need to do actual field tests on a phone to ensure that your program works with real-world coordinates and tours as you think it should. We will distribute Android phones for you to test on, and we will be using these phones to grade so be sure to test with them.
Once you've run some basic tests on your program, require mapdata.rkt to get the actual Brown map data.
mapdata.rkt contains the following definitions and helper functions. The map data is given in terms of the structs, and you will find the functions provided very useful.
(define-struct: loc
([name : String$]
[desc : String$]
[latitude : Number$]
[longitude : Number$]
[radius : Number$]
[neighbors : (Listof: Loc$)]
[distances : (Listof: Number$)]))
including its visitation radius in meters, neighbors, and the
distances in meters to those neighbors. Every location will have a
unique, unambiguous name.
loc-list : (Listof: Loc$)
loc-list provides a complete list of all the locations your program will
use to find paths.
tour-dist : ([latitude1 : Number$]
[longitude1 : Number$]
[latitude2 : Number$]
[longitude2 : Number$]
-> Number$)
Given the latitude and longitude of two locations, returns the
approximate distance in meters between them.
get-dir-string : ([latitude1 : Number$]
[longitude1 : Number$]
[latitude2 : Number$]
[longitude2 : Number$]
-> String$)
Given the latitude and longitude of two locations as above, returns the
approximate heading of the path from the second
location to the first as a string such as
"North" or "Southwest".
(define-struct: tour ([name : String$]
[stops : (Listof: String$)]))
Stores the name of a tour (which your program will need to display) and
its stops.
create-tour : ([name : String$]
[loc-names : (Listof: String$)]
-> Tour$)
takes a name and a list of loc-names and returns a tour
with that name and those locations
tours : (Listof: Tour$)
tours provides a complete list of the tours your program will use.
This is a very large project. It is your job to nail it down a set of concrete specifications, and the best way to do this is to build yourself an extensive testing harness before you dive into coding. Make sure you can quickly find out, for instance, whether a given version of your code still correctly handles the user getting lost and pressing recalculate, or adding a tour, visiting some of its stops, dropping the tour, and then re-adding it.
To access your generated HTML and Javascript on a smartphone use
our cs019-upload script to upload them to the web to
be loaded from anywhere. Simply run the script with any necessary
files as arguments.
$ cs019-upload tour_guide.html tour_guide.js tour_guide.appcache
...
The script will then output a URL you can visit from another machine or a smartphone for testing.
Note on Getting Coordinates: The phones have two ways of getting coordinates: GPS and WIFI. Unfortunately, the GPS is extremely unreliable when it is cloudy, and the WIFI is extremely inaccurate. Feel free to try either option, but be aware of these problems. To switch between them, hit the Menu button on the phone. Then go to Settings -> Location & Security, and select the option you want.dijkstra.rkt, which implements the core of Tour Guide - using Dijkstra's algorithm to generate tours. Note: this should use Whalesong.
tour_guide.rkt, which implements your entire Tour Guide program. This file should use Whalesong to compile a program which runs on Android phones.README.pdf/text, which contains a brief write-up about the high-level decisions you made in Tour Guide. This could include what you chose to put in your world, what collection you chose to return from dijkstra among other things. This is the place to defend all your choices, so please take this seriously. Be sure to include any bugs in your code (hint: this should be empty) and any extra features you implemented.