You type two addresses into a map app and a route appears before you lift your finger. Behind that is a chain of problems, each one a classic: read a compressed binary map file, turn streets into a graph, and find the shortest path among hundreds of thousands of roads faster than a plain search could.

I had read about all of these and implemented none. routing-from-scratch is where I did: car routing on real OpenStreetMap data, written from scratch in Go with no dependencies beyond the standard library. It is a learning project, and it says so about itself: for anything real, use OSRM, Valhalla or GraphHopper.

What it does

The project has four parts:

  1. An OSM PBF reader and writer with a hand-written protobuf wire codec, plus an OSM XML reader.
  2. A road graph: CSR arrays, oneway rules, speeds per highway type, and reduction to the largest strongly connected component.
  3. Dijkstra, then A*, then contraction hierarchies, all checked against each other and against Floyd–Warshall.
  4. A benchmark table and a small HTTP endpoint with a map page.

On the map page, you click twice to set A and B, and the markers can be dragged. The page asks for the route with all three algorithms and shows their travel time (always identical), settled nodes and query time.

The API is one route: GET /route?from=lon,lat&to=lon,lat&algo=dijkstra|astar|ch returns a GeoJSON Feature (a LineString) with duration_s, distance_m, settled, query_us and snap_m, which is how far each point was from its snapped node. GET /info returns the graph size and bbox.

How to use it

Install the route-server, route-bench and osm2pbf binaries with Go:

go install github.com/AbdeldjalilChougui/routing-from-scratch/cmd/...@latest 

Or clone the repository, which includes a small fixture of central Tlemcen, and run from there:

git clone https://github.com/AbdeldjalilChougui/routing-from-scratch.git cd routing-from-scratch go test ./... # ~30 s, includes brute-force cross-checks go run ./cmd/route-server # committed Tlemcen fixture, http://127.0.0.1:8090/ go run ./cmd/route-bench testdata/tlemcen-centre.osm.pbf # benchmark table 

For a bigger extract (not committed), download roads with Overpass and convert them with the project's own PBF writer:

scripts/fetch-osm.sh 35.60 -0.80 35.80 -0.45 data/oran.osm # ~11 MB XML go run ./cmd/osm2pbf data/oran.osm data/oran.osm.pbf # ~0.9 MB PBF go run ./cmd/route-server data/oran.osm.pbf 

What I built from scratch

The PBF codec (internal/pbf). A PBF file is a sequence of [4-byte length][BlobHeader][Blob]. Blobs are zlib-compressed protobuf PrimitiveBlocks, each with a string table, granularity and offsets, and groups of DenseNodes (delta and zigzag encoded ids and coordinates) or Ways (string-table tags, delta-encoded refs). The decoder reads raw protobuf fields (varints, length-delimited, packed) without generated code. The writer does the reverse and is used by cmd/osm2pbf and the round-trip tests. Unsupported required_features such as HistoricalInformation are rejected, as the spec requires.

The graph (internal/graph). Every node of a drivable way becomes a vertex and every consecutive pair becomes an edge. The weight is travel time in tenths of a second, rounded up. Speed comes from maxspeed (km/h or mph) or a per-type default. Direction comes from oneway=yes/-1/no, roundabouts and motorways. Access rules drop access=no/private, parking aisles and driveways. Parallel edges keep the minimum weight. Finally the graph is cut down to its largest strongly connected component (iterative Kosaraju), so every snapped point can reach every other one. Storage is CSR (FirstOut, Head, W) plus a reverse CSR.

Dijkstra and A* (internal/route/dijkstra.go). A binary heap with lazy deletion. Buffers are reused between queries, and only the touched entries are reset. A* adds haversine(v, t) / MaxSpeed. MaxSpeed is computed from the edges themselves (max straight-line metres divided by weight), so the heuristic is admissible and consistent whatever the data.

Contraction hierarchies (internal/route/ch.go):

  • Ordering. Priority is the edge difference (shortcuts needed minus edges removed) plus the number of already contracted neighbours. Updates are lazy: pop the minimum, recompute it, and only contract it if it is still the minimum.
  • Contraction. For each in-neighbour u of v, a bounded witness Dijkstra (avoiding v, at most 200 settled nodes) checks every out-neighbour x. If no path of cost at most w(u,v)+w(v,x) exists, it adds the shortcut u→x and records v as its middle node.
  • Query. Bidirectional Dijkstra on the upward graphs. It stops when both queue minima are at least the best meeting cost, then shortcuts are unpacked recursively through their middle nodes.

What I learned

A* is not automatically faster. This was the surprise. go run ./cmd/route-bench -n 1000 <file> runs 1000 random queries per algorithm and checks that all three return the same costs (0 mismatches on every run). On the Oran extract (91,547 nodes, 188,329 edges; CH preprocessing 10.1 s, 212,760 shortcuts):

algorithm avg query avg settled nodes speed-up vs Dijkstra
Dijkstra 46.8 ms 45,972 1.0x
A* 73.3 ms 25,324 0.6x
CH 0.40 ms 142 116x

On the Tlemcen extract (30,047 nodes, 60,815 edges; CH preprocessing 4.5 s), Dijkstra averaged 18.6 ms, A* 24.6 ms and CH 0.12 ms, with 15,339, 9,205 and 79 settled nodes.

A* settles about 40% fewer nodes but is slower here. Its heuristic, straight-line distance divided by the fastest speed in the graph, is weak when most streets are 25 km/h and a few roads allow 80 to 100 km/h, and each heuristic evaluation costs a Haversine. CH settles two orders of magnitude fewer nodes in exchange for a few seconds of preprocessing.

A caveat that comes with these numbers: they were measured on a laptop that was busy with other builds, so the absolute times are noisy. The settled-node counts are the stable signal.

Integer weights make comparisons exact. With travel time in tenths of a second as integers, three algorithms either agree to the unit or they have a bug. With floats, I would have been arguing with rounding.

A witness-search limit affects speed, not correctness. Hitting the 200-node limit only adds unnecessary shortcuts. A test with a limit of 1 checks that correctness never depends on it.

Brute force keeps you honest. On 10 random road-like graphs (30 to 120 nodes, partly one-way, some unreachable pairs), all pairs for Dijkstra, A* and CH are compared with Floyd–Warshall. Path validity is checked too: the returned node sequence is made of real edges and sums to the cost. Other tests cover a 30×30 grid, the heap, the PBF write-then-read round trip, OSM tagging rules on a hand-written XML, the grid index against brute-force nearest, and the /route error codes (400/404/422).

Things to know

  • Car profile only. There are no turn restrictions, turn costs or traffic signals, and no maxspeed:forward/backward.
  • Snapping goes to the nearest node, not the nearest point on an edge.
  • CH preprocessing is single-threaded and unoptimised. It takes seconds for a city and would need work for a country.
  • The PBF reader handles nodes and ways (dense and plain). Relations are skipped, and only zlib/raw blobs are supported (no lzma/zstd).
  • The map page loads MapLibre from unpkg and raster tiles from tile.openstreetmap.org.

Why I built it

Routing engines are easy to use and hard to see into. The ideas behind them, shortest paths, heuristics, preprocessing, are standard material, but reading about contraction hierarchies and making one return the same answer as Dijkstra on a real city are different things. Starting from the raw PBF bytes, with no library in the way, meant every layer was mine to get wrong and then fix. That was the point.

Get the code

The source, the Tlemcen fixture and the tests are on GitHub: https://github.com/AbdeldjalilChougui/routing-from-scratch. The code is MIT licensed. The fixture testdata/tlemcen-centre.osm.pbf contains OpenStreetMap data, © OpenStreetMap contributors, under the Open Database License (ODbL) 1.0; anything you produce from it must keep that attribution and licence.

Originally published at abdeldjalilchougui.biz.