Turn-by-Turn: Guidance from a Graph With No Names

Background

Grubhub's routing engine — Pathfinder, built on Customizable Route Planning — answered "how long from here to there" a few hundred thousand times a minute: dispatch offers, delivery estimates, boundary generation, the works. Nothing in that list needs to know that the edge it just relaxed is West Madison Street. So the graph didn't carry it. The continental North American graph was already north of 30 GB resident per node even as a proprietary bit-packed, memory-mapped file, and every byte per edge was a byte multiplied by a hundred and fifty million.

Then the driver app wanted navigation. Our couriers were bouncing out to Google Maps for every leg, which cost us the screen — no order context, no re-offer, no arrival detection while they were in someone else's app. Competitors had it in-app. We ran paid trials with Mapbox and with Google's Navigation SDK; both worked fine and both cost, at our volume, an eye-watering amount per month. And the executives who signed those invoices wanted the A/B test that showed deliveries got faster. It never showed up — not because in-app navigation is worthless, but because the effect on delivery time is small next to a merchant that's running twelve minutes late. What it improves is the courier's experience, which is a harder number to put on a slide.

The counter-proposal was that we already had a routing engine, and the marginal cost of guidance on top of it was mostly memory we'd deliberately thrown away. This page is that argument, rebuilt in the browser on real Chicago roads.

What Was Missing

Turn-by-turn needs three things the routing graph didn't have, in increasing order of difficulty:

Street names. Not in the graph at all. This is the memory problem, and it has a satisfying answer.

Maneuvers. Also not in the graph — and this one can't be solved by adding a column, because a maneuver isn't a property of an edge. It's a property of the relationship between two consecutive edges and everything else at the junction between them. It has to be derived per query.

Everything a signage vendor sells. Lane counts, exit numbers, shield artwork, the physical layout of an interchange. We had none of it and never got it. What that buys you is polish — "keep left, then use the second from the left lane to take exit 51B" — and the honest version of this project's scope is that we shipped the first half of that sentence.

Names, at 2.6 Bytes a Segment

The naive fix is a name pointer per segment. On the JVM, where all of this ran, that's an 8 byte reference into an array plus a String that is itself a 32 byte object wrapping a byte[] with its own 16 byte header — call it 76 bytes per segment once you account for the objects the references point at. Interning helps a lot, because a street is cut into dozens of segments and they all share one name: an id per segment plus one String per distinct name lands near 9 bytes per segment. Better. Still 1.3 GB on a continental graph, for data that's idle except during the seconds a courier is actually being guided.

The observation that makes it cheap is that street names are not arbitrary strings. They're a small grammar. "West Madison Street" is a direction, a base name, and a street type; so is "North Clark Street" and so is "South Dr Martin Luther King Junior Drive". Factor the grammar out and what's left to store is the base names — and there are far fewer of those than there are names, because West Madison and East Madison and Madison Avenue all point at one string.

The layout that falls out has four pieces:

A base-name dictionary, sorted and front-coded. Each entry stores a shared-prefix length, a suffix length, and the suffix bytes — sorted neighbors share long prefixes, so "Wabash", "Wacker", "Walton" cost a few bytes each after the first. Every eighth entry restarts from a zero-length prefix and its byte offset goes in a sample array, so decoding any name scans at most eight entries rather than the whole dictionary.

A name record, one 32-bit word per distinct full name: 20 bits of base-name id, 5 bits of street type, 4 bits of direction, and 1 bit saying whether the direction goes in front ("West Madison Street") or behind ("Madison Street West"). Type and direction are tokens shared by every map on Earth, so they're compiled in and cost nothing per city.

A per-segment index, two bytes pointing at a name record, zero meaning unnamed.

A literal escape, because a format with no escape hatch is a format that corrupts data. Type token 31 means "the base field is an index into a list of verbatim strings," which catches anything the grammar can't parse.

On the demo's extract that's 2.6 bytes per segment against 76 for the naive version — the per-segment index is most of it, and the dictionary, records, and offsets together are under 4 KB for the whole of downtown Chicago. The abbreviation everyone actually wants on a phone screen falls out for free: "W Madison St" is the same record read with the short token table. The demo shows a real name being unpacked, bit fields and dictionary bytes and all, for whichever step you select.

Maneuvers Are Derived, Not Stored

The second half is more interesting, because no amount of memory fixes it. Once the router unpacks a path, what it has is a sequence of directed edges and their polylines. Everything a driver needs to be told has to come out of that.

The angle comes from the geometry, but not from the endpoints. A contracted segment is a polyline that may bend sixty degrees over its length; the chord between its endpoints can point somewhere the driver never faces. So headings are averaged over the last and first ~18 meters of the two edges — the part of the road you're actually pointing along when you arrive at the junction and when you leave it.

The junction matters more than the angle. The graph's adjacency gives every branch out of that vertex, and the branches decide whether the angle is worth a sentence. A forty-degree bend on a road with no other option is not an instruction — the driver has nowhere else to go, and saying "bear right" makes the app sound like it's guessing. A five-degree deviation where another branch is also nearly straight is an instruction, and it's the one people miss.

Name continuity is the tiebreaker, and it's the reason the name side-car pays for itself twice. If the street you're on and the street you're taking are the same name, the driver experiences the junction as continuing rather than turning — even when the geometry says otherwise. Comparing name records makes this a single integer compare; no string is ever materialized to answer it.

The upshot is that almost all of the work is deciding what not to say. A four-kilometer downtown route runs through sixty to a hundred junctions. Thirty or forty of them present a real choice. A good instruction list has around ten entries. The demo shows all three numbers, and draws a dot at every junction where the engine decided to keep quiet — that set of dots is the algorithm.

Going Off Route

Guidance is a loop, not a list, and the loop closes through the map matcher. The courier's phone streams positions; the matcher pins each one to a directed edge; if that edge isn't on the route and stays off it, the driver has left the plan and the engine reroutes from the matched edge — not from the raw GPS position, which in a downtown canyon is regularly a block away and would have couriers rerouting at every stoplight. Rerouting from the head of the matched edge rather than the current position is deliberate too: by the time the new route is computed the vehicle has moved, and a route that starts behind you begins with a U-turn.

The demo has a button that makes the driver miss the next turn. It takes a real branch at the real junction, drives down it, crosses the off-route threshold, and recomputes — instructions and all — while still moving.

About the Demo

Everything below runs in a web worker on the same downtown Chicago extract as the other routing demos: ~5,300 OSM ways contracted into a road graph of about 4,700 junctions and 6,300 segments. On load it builds the graph, strips the names out into the packed side-car described above, and reports what that cost. Every route is a live A* on the graph followed by a live maneuver pass — the instruction list is derived on each query, and the panel shows how long both halves took.

Drive the route and watch the banner; click any step to see its street name unpacked from the bit-packed record and the front-coded dictionary; turn on the silent-junction dots to see what got suppressed; miss a turn on purpose and watch the reroute. Voice guidance uses the browser's speech synthesis — not what shipped, but the right shape; it ranks the voices your browser exposes and takes the best English one, which on most machines means a neural voice rather than the default robot.

The playback clock is deliberately nonlinear. Real guidance is mostly nothing happening punctuated by a few seconds that matter, so with cruise on, the chosen rate is held whenever a maneuver is close — far enough out that the quarter-mile warning, the 500-foot warning, and the turn itself each get real seconds of their own — and winds up to 3× that in the middle of a long leg where there's nothing to say. Two maneuvers closer together than about 110 m chain into a single "turn left, then turn right" rather than talking over each other, which is a rule production needs for exactly the same reason.

Honest idealizations: this demo routes point-to-point with plain A* rather than through the CRP overlay — the interesting part is downstream of the path, and the CRP demo next door covers the upstream half. Speeds are OSM limits under a fixed congestion factor, not live traffic. Turn restrictions, lane counts, exit numbers, and signage aren't in the extract and aren't modeled, so no instruction here will tell you which lane to be in. There's no roundabout handling, because downtown Chicago gave me nothing to test it against. And the off-route trigger here is geometric distance from the planned path rather than a full matched-edge comparison; the matcher that would feed it is its own project. The parts that are real: the packing format and its decoder, the derivation rules, the suppression logic, and the reroute loop.