Maps
A map of Rhode Island with shortest path features and live traffic tracking.
Role
full-stack design
Tools
Java, JS/HTML/CSS, SQL
Timeline
90 hrs. March 2017
Results
Working product hosted locally
For one of the final projects in Brown's software engineering course CS32, I designed and implemented a map that gives directions between two locations, taking into account live traffic data.
The primary goal of CS32 is to learn how to build extensible programs that can be easily adapted to new projects in the future. Maps was built upon three of our previous projects, which incorporated nearest neighbor search, autocorrect, and shortest path features.
In programming Maps, I was challenged to integrate large amounts of code from each of my previous projects (each 1000+ lines of code), and to create a new intuitive interface with zooming, panning, and search functions.
This project took place over the course of 3 weeks, and concluded with a short demo to my teaching assistants.
Final Product
Map of Rhode Island
Hello, Navigator!
The purpose of Maps is to provide users with a friendly interface that allows them to search for directions around Rhode Island. The shortest path generated takes into account both traffic data and the earth's curvature.
Features
Search
Maps comes with two ways of searching. Users can either input street intersections into the text boxes, or click directly at points on the map.
Zoom/pan
Maps initially focuses on Brown's campus, but users can use their trackpads or mouse to zoom and pan efficiently.
Update
Get the shortest path up to date with the current amount of traffic. Users will be able to see which routes are conjested.
Demo
Implementation: Design choices and algorithms
Integration
There were 3 programs I had to integrate in order to meet the functionality requirements for Maps. There was a nearest neighbors search program that found the nearest street intersection given a location, an autocorrect program that offers suggestions to user input, and a shortest path program that returns the shortest path given two vertices. To combine all of these programs, small modifications were necessary. I had to make the nearest neighbors program more generic so that it could accept coordinates, and I had to change the distance calculation from Euclidean to the Haversine formula, which takes into account the earth's curvature. I also replaced Dijkstra's algorithm in the shortest path program with the A* Search algorithm to optimize runtime, multiplying distance by an edge weight signifying the amount of traffic on that street. Because I was using an additional server to listen for traffic updates, I had to set up multiple threads and use data structures that are thread-safe. Finally, I revised my previous SQL queries using a profiler to ensure that the queries are being made as efficiently as possible.
Front end design
On the front end, the challenge was to create an interface that zooms and pans efficiently. Since we were required to use HTML5's canvas to draw each road, building, and river in Rhode Island, optimization was essential. To tackle this problem, I approached the map of Rhode Island as a 2D array of tiles. The initial zoom to Brown's campus were 9 tiles, and as the user zoomed in or zoomed out the number of tiles would increase or decrease, respectively. Then, I added a cache in the front end to store tiles that have already been loaded from the database. Therefore, the database is only queried the first time the user zooms out, and any consequent zooming will be efficient because the tiles will have already been stored. The last feature I added to the map was traffic data, which I displayed through coloring the roads red, yellow, or green to denote the amount of traffic.
Next Steps
If I had a chance to improve Maps, I would consider the following:
Location Detection
How can I implement a feature that detects the user's current location and centers the map around their location?
Filters
How can I add filters so that users can choose which functions they want and which functions they don't need?
Reflections
Maps challenged me to integrate multiple programs and to build on top of that. It was the first project in which I extensively used Java, SQL Javascript, Jquery, HTML and CSS to produce an interactive interface, and I was able to grasp the power and importance of writing extensible code.
Shoutout to my wonderful TAs for their help and guidance.