Road Graph Storage
A map is modeled as a directed weighted graph. Nodes represent intersections and road endpoints, each storing a latitude/longitude coordinate pair and a unique node ID. Edges represent road segments connecting two nodes, storing: distance (meters), speed_limit (km/h), road_type (motorway, primary, residential, etc.), allowed travel direction (one-way or bidirectional), and turn restrictions.
The graph is stored in an adjacency list: for each node, a list of outgoing edges with their target node IDs and weights. This structure fits well in memory for routing algorithms. A spatial index (R-tree or a geohash grid) enables area queries: "find all nodes within this bounding box" — essential for map display and snapping a GPS coordinate to the nearest road. A major city road network contains millions of nodes and tens of millions of edges; the full graph of a continent fits in tens of gigabytes of RAM on a routing server.
Routing Algorithms
Dijkstra’s algorithm finds the shortest path from a source node to all reachable nodes. It runs in O(E log V) time using a min-priority queue, where E is the number of edges and V the number of nodes. Edge weights are set to travel time (distance / speed) rather than distance to optimize for fastest route. Dijkstra is optimal but explores nodes in all directions from the source, making it slow on continental-scale graphs.
A* (A-star) improves on Dijkstra by adding a heuristic: for each node, the estimated remaining cost to the destination. Using straight-line distance divided by max possible speed as the heuristic is admissible (never overestimates) and consistent. A* focuses the search toward the destination, visiting far fewer nodes than Dijkstra on typical queries.
Contraction Hierarchies (CH) is the practical choice for production routing at scale. In a preprocessing step, nodes are assigned an importance order and "contracted": each node is temporarily removed and shortcut edges are added between its neighbors if the shortest path between them went through it. The bidirectional CH query runs Dijkstra forward from source and backward from destination on the augmented graph, meeting in the middle. Query time is sub-second on continental road networks — several orders of magnitude faster than plain Dijkstra.
Traffic Integration
Real-time traffic data is collected from probe vehicles (anonymous GPS traces from mobile devices and connected cars) and fixed sensors (induction loops, cameras). Probe data is aggregated by road segment: observed speeds are averaged over the last 5-10 minutes per segment and pushed to the routing servers periodically.
Edge weights in the routing graph are updated dynamically: edge_time = edge_distance / current_speed. When current speed is unavailable, the historical average for that segment at the current time-of-day and day-of-week is used as a fallback. This historical baseline is precomputed from months of probe data and accounts for predictable patterns like rush-hour slowdowns.
Accurate ETA computation uses time-dependent routing: the weight of an edge depends not just on current conditions but on the estimated time of arrival at that edge. A route that takes 45 minutes starting now will encounter different traffic conditions at each segment than the traffic seen at departure time. The routing algorithm propagates the estimated arrival time through each segment and looks up the appropriate traffic speed for that time window.
Turn-by-Turn Instructions
A route is a sequence of edges. Instructions are generated at each maneuver point — a node where the driver must change direction or the road name changes. The turn type is derived from the bearing change between the incoming and outgoing edge: less than 20 degrees is "continue straight," 20-60 degrees is "slight turn," 60-120 degrees is "turn," 120-160 degrees is "sharp turn," ~180 degrees is "U-turn." Left/right is determined by the sign of the angle.
Street names, road numbers, and exit labels are embedded in edge metadata and included in the instruction text: "Turn right onto Main Street" or "Take exit 12 toward Downtown." Roundabout handling counts the exit number by traversing roundabout edges. The distance to the next maneuver is computed by summing edge lengths along the route.
Voice prompts are triggered by distance thresholds: a preparatory prompt at 500m ("In 500 meters, turn right"), a confirmation prompt at 50m ("Turn right"), and a missed-turn prompt if the driver passes the maneuver point without turning. Prompt timing accounts for vehicle speed to avoid prompts being too early at low speed or too late at high speed.
Re-Routing
The device reports GPS position every second. Each position fix is map-matched: projected onto the nearest road segment using the spatial index, accounting for heading and speed to disambiguate between parallel roads. The matched position is compared against the planned route.
Deviation detection triggers when the distance from the matched position to the nearest route segment exceeds a threshold (typically 30-50 meters) for more than 2-3 consecutive seconds. False positives from GPS noise are suppressed by requiring sustained deviation rather than a single outlier fix.
When deviation is confirmed, a background thread immediately computes a new route from the current map-matched position to the original destination. The re-route query uses the same CH routing algorithm as the initial route. The new route is presented to the driver within 2-3 seconds of confirmed deviation. The original route is discarded and navigation continues on the new route.
Map Tile Rendering
The world is divided into a grid of tiles at each zoom level using the slippy map tile scheme: at zoom level Z, there are 2^Z × 2^Z tiles. Each tile is identified by (z, x, y) coordinates. At low zoom levels (0-8), tiles cover large areas and are pre-rendered once. At high zoom levels (14-18), tiles are numerous but each covers a small area; they are generated on-demand and cached aggressively.
Raster tiles (PNG images) are pre-rendered by a tile server (Mapnik, TileServer GL) from the underlying geodata and served from a CDN keyed by z/x/y. Vector tiles in Mapbox Vector Tile (MVT) format contain the raw geometry and attributes for a tile area, compressed with protobuf. The client renders vector tiles on the GPU using WebGL or a native map SDK, enabling smooth zoom animations and client-side style customization without re-fetching tiles for style changes.
Points of Interest
The POI database stores: poi_id, name, category (restaurant, gas_station, hospital, etc.), lat, lon, address, hours (structured JSON), phone, rating, and review_count. POIs are spatially indexed for bounding-box queries: fetching all POIs visible in the current map viewport requires a fast range query on coordinates.
Name search supports fuzzy matching using trigram similarity or an Elasticsearch index, tolerating typos and partial inputs. Category filtering (show only restaurants) is applied as a pre-filter before spatial ranking. POIs are displayed on the map with category-appropriate icons; at lower zoom levels, clustering groups nearby POIs into a single icon with a count badge.
POI data is integrated with routing: when the user taps a POI as a destination, its coordinates are snapped to the nearest road node to serve as the routing graph destination. Business hours data feeds the "open now" filter in search results.
Offline Maps
An offline map pack for a geographic region bundles everything needed for navigation without a network connection. Map tiles for the region at all zoom levels are stored in an SQLite MBTiles file — a standard format with a tiles table keyed by (zoom_level, tile_column, tile_row). The routing graph for the region is serialized to a binary file (adjacency list, node coordinates, edge weights) optimized for fast memory-mapped access.
POI data for the offline region is embedded in the pack as a SQLite database with a spatial index. The on-device routing engine runs the same CH algorithm as the server, loading the precomputed hierarchy from the pack. Storage estimates vary by region density: a major city offline pack is 100-500MB; a country-level pack can reach several gigabytes.
Offline packs have a version number tied to the map data release. The app checks periodically for pack updates and downloads diffs when significant road network changes have been made. Traffic data is inherently online-only; offline navigation uses historical speed estimates and static speed limits for ETA computation.