OverviewIn this assignment, students write the back end for a web based street maps application. While that may seem intimidating, the project provides a well defined API that makes this task approachable by students who are assumed to have no web programming experience whatsoever. A live demo of a correct implementation is available at this link. Check it out! The two primary tasks for the students are rastering and routing. In the rastering part of the assignment, students write a function that takes as input latitude, longitude, browser window width, and browser window height, and returns a list of file names that should be displayed. For example, suppose the latitude and longitude provided cover the Berkeley campus. In this case, the student function should return the list of file names for all images corresponding to campus. In the routing part of the assignment, students write a function that takes as input a start latitude / longitude, a destination latitude / longitude, and returns a list of coordinates that correspond to a route between those two points. The assignment uses real world data. In terms of data, students are provided with:
- A large number of PNG files corresponding to the region of the world of the instructor's choice, drawn from the Open Street Map dataset.
- An XML file containing all road, business, and intersection information from the same region as the PNG files, also drawn from the Open Street Map dataset.
GoalsThis assignment covers the following goals, in decreasing order of importance:
- Building one piece of a large application and interacting with an existing code base.
- Writing code that converts a slightly messy real world dataset into useful data structures.
- Implementing a graph search algorithm (BFS, Dijkstra's, A*, or similar, per choice of the instructor).
MaterialsSpecification for this assignment: Link
Starter files (Java): Link
Demo video showing off what students will be building: Link
Hint videos provided to Berkeley students: Link
Web demo of a correct implementation (provided to students for reference): Link Credit to former TA Alan Yao for developing the original assignment idea.
Students write the Java back end of a browser based street mapping application. They must fill in two functions. The first takes coordinates corresponding to a region of the world, and outputs a list of String filenames to display. The second takes a starting and ending point, and generates a route along real streets.
||OOP, working with real data, graphs, graph search, optionally Quad Trees.|
||Medium to difficult. Can be varied based on how much you give them and what you require.
||Rastering is Tricky: Figuring out the correct filenames to display is a tricky and may require considerable hand holding for less mature students. Interaction with a Large Codebase: Students might not feel like the ultimate product is really theirs, given that so much is done for them under the hood.|
||None beyond those provided.|
||The assignment can be made more complex or simplified in many ways. Some ways to enhance the complexity (that we've done at Berkeley): require students to implement a Trie-based Autocomplete feature that allows business name search, require students to parse the XML data containing street (and business) information and build a graph, require students to use A* for routing. Some ways to simplify: require only rastering, require only routing, allow any graph traversal algorithm instead of one that guarantees finding of the shortest route, provide a QuadTree implementation to simplify rastering.|