Bear Maps: Creating Routes with Open Street Maps

Overview

In 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.

Students are also provided with a significant amount of starter code, including an HTML mapping application that tries to make calls to the students Java code for rastering and routing. Students do not need to know anything about graphical rendering, user interfaces, or web and Javascript programming.

Goals

This 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).

This assignment was used as a 2 week project at the very end of a second semester data structures course at Berkeley. The difficulty can be reduced considerably by requiring less parsing by the students, and by providing out-of-the-box implementations of useful data structures and algorithms (QuadTrees for rastering, graph search for routing).

Materials

Specification 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.

Metadata

Summary 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.
Topics
 OOP, working with real data, graphs, graph search, optionally Quad Trees.
Audience
 Late CS2
Difficulty
 Medium to difficult. Can be varied based on how much you give them and what you require.
Strengths
 Feels Real: Students write the back end to a web application that utilizes real data and handles actual queries, given students the chance to feel like they just built Google Maps.

Interaction with a Large Codebase: Students get a chance to interact with a large codebase via a simple sharly delineated API. The given codebase is huge (and includes lots of Javascript), so students must learn to avoid going below the suggested level of abstraction and instead trust the API.

Rastering is Tricky: Figuring out the correct filenames to display is a really interesting puzzle that can be solved in at least two completely different ways, one of which involves using a QuadTree.

Forces Good Debugging Habits: Given the complexity of the codebase, students who try to use print statements in combination with just dropping queries into their web browser will not get anywhere. Instead students will need to debug in a smarter, more deliberately targeted way (tips provided in the assignment spec).
Weaknesses
 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.
Library Dependencies
 None beyond those provided.
Variants
 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.