HuskyMaps

Rastering

The first part of this project's goal was to implement the backend for HuskyMaps Rasterer.java. This involved creating a rastering algorithm to decide which images to display. The underlying algorithm for this section was to use the search query's top left point and bottom right point, as well as the depth of the zoom, to determine the dimensions of the tile array to be returned. Next, using the AStar path-finding algorithm I implemented earlier in the course, I returned the shortest path between two points.

Rastering

The second part of this project involved implementing the contraction hierarchies algorithm on HuskyMaps Graph. This is a two part algorithm designed for creating a smarter representation of a street map in a graph. Essentially, we go through the graph and assign shortcuts two the nodes which represent "important" roads. This is because generally it does not make sense to explore all the highway exits and smaller roads once you are on the highway. The parallel algorithm was the following: While there are uncontracted nodes:

• Update each roads importance while caching the road's associated shortcuts in parallel.
• Create a set of independent nodes in parallel.
• Contract each independent node.
• Remove the contracted nodes from the uncontracted nodes.

The parallel work was done using Java's functional interfaces as well as Lambda expressions.

The Result

Now, any husky is capable of navigating their way through the U-District. Made in collaboration with code from CSE 332, Kevin Lin, HuskyMaps Server , Contraction Hierarchies