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: graph 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(nlogn) time with respect to the number of nodes in the graph.
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 Sunday. There is be 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 make your application run on a cell phone, you'll need to use Moby, a specialized Scheme compiler. To do so, you will need to switch DrScheme to the Module language, and include the line:
#lang planet dyoo/moby:2:20
at the top of your main source file (and any files you
include; see below.)
DrScheme will install Moby the first time you run a Moby program. If issues with Moby, which is still under development, arise during the course of this project, the '20' might change; this will be announced to the course list.
Moby comes with a version of Universe, which you will need to use to
create an interactive user interface. Moby's Universe is different
from the one you used earlier in the course; in particular, it adds
the functions js-big-bang and
on-location-change and the contract of on-draw
to take two two handlers. For further details, visit
http://coach.cs.uchicago.edu:8080/display.ss?package=moby.plt&owner=dyoo
and click on the 'docs' link for the latest version.
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!
You can test your application entirely in-browser by providing test coordinates. When you click 'Run' in Moby, your program will open your default browser. 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 have several Android phones for you to work with; a schedule for checking them out will be discussed in class or emailed to the list in a few days.
Once you've run some basic tests on your program, grab the actual Brown map data from mapdata.ss. You can use the include keyword to pull in content from an external file so you don't have to paste the whole mess of data into your program.
mapdata.ss contains the following struct definitions and helper functions. The map data is given in terms of the structs, and you will find the functions provided very useful.
loc : string string number number number (list-of string) (list-of number)
(define-struct loc (name desc latitude longitude radius neighbors distances)
Stores the name, description, and geographic information of a location,
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 : (list-of loc)
loc-list provides a complete list of all the locations your program will
use to find paths.
tour-dist : number number number number → number
Given the latitude and longitude of two locations, returns the approximate
distance in meters between them. Note that the argument order is
latitude1, longitude1, latitude2,
longitude2.
get-dir-string : number number number 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."
tour : string (list-of loc)
(define-struct tour (name stops))
Stores the name of a tour (which your program will need to display) and
its stops (which are of type loc).
create-tour : name (list-of string) → tour
takes a name and a list of loc-names and returns a tour
with that name and those locations
tours : (list-of 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.
A further complication is that you have very limited access to the phones. This makes testing even more important! You would be wise to build yourself a testing harness.
To install your application on the phone, you first need to download the .apk file from the page that pops up when you run your code with Moby. Once you have the file, plug the phone into a USB port on the machine. This may be a little tricky with some of the sunlab machines, but the ports are there. Once you have the phone pluged in, open a terminal and type
adb install <apk-file>where
<apk-file> is the path to the apk you just
downloaded.
When you are ready to turn the phone back in, you must uninstall your application. This prevents the next group from looking at your work, it prevents other people from having trouble installing their app if it has the same name, and it insures the phone does not have tons of apps on it later.
To uninstall your app, hit the Menu button on the phone. From there go to Settings -> Applications -> Manage applications. Then scroll down until you find your app, click on it, and hit Uninstall.
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 -> Security & Location, and select the option you want.
tourguide.ss, which Moby will compile,
and which runs in browsers and on Androids.