Prototypes AtlasP37 · Map of Aarhus

Atlas against Dijkstra

Each pair of junctions below is routed twice in a Web Worker on the graphs this page loaded: once with the contraction hierarchy, and once with plain Dijkstra on the road graph before any contraction. The two must give the same travel time, and the hierarchy’s path, unpacked into roads, must be a path of the road graph that adds up to it.

Loading the graphs

ModePairsEqualHierarchyDijkstraFrom both endsFasterNodes settled by each
© OpenStreetMap contributors

The map shows the last routes compared. A route where the two differ would be drawn in red.

How Atlas is built
  1. Atlas is a map of Aarhus written for this prototype in plain JavaScript, with no dependencies at run time. Everything on it comes from one file: BBBike’s extract of OpenStreetMap for Aarhus, 25.7 MB in the PBF format.
  2. A reader of its own decodes the PBF: the blocks and their zlib framing, the protobuf wire format, the string tables, dense nodes stored as deltas, ways and relations, with the block’s granularity and offsets.
  3. The build turns the data into vector tiles of its own format for zooms 10 to 16. Each feature is simplified for its zoom, clipped to its tile with a margin, and stored as whole numbers in varints. The sea is built from the coastline, which OpenStreetMap draws as lines with the land on their left. The tiles are packed into four archives with an index, and the page reads a tile with an HTTP Range request.
  4. A Web Worker fetches the tiles in view, inflates them, cuts the areas into triangles by ear clipping with holes, and extrudes the lines into strips with joins and round caps. The page draws them with WebGPU where the browser has it and WebGL2 where it does not, from the same meshes and with the same arithmetic. While a zoom loads, the tiles of the zoom before it are drawn in its place.
  5. Labels are placed by priority: towns before districts, stops before shops, main roads before side streets. A label goes only where it overlaps nothing placed before it, and a street name follows its street letter by letter.
  6. For routes, the build makes a graph for car, bike and foot from the roads’ tags: one-way streets, roundabouts, access and speed limits, with a speed for each road class when none is tagged. An edge’s weight is its travel time in tenths of a second.
  7. Each graph is contracted into a hierarchy: nodes are removed one by one in the order of how many shortcuts that would add, and a shortcut goes in only when a witness search finds no other path as quick. A route is then two small searches upward that meet, which is why it takes a fraction of a millisecond.
  8. A pressed point is snapped to the nearest road with a grid of the road segments. The steps come from the street names and the angles between the roads. The reach in 5, 10 and 15 minutes comes from one search to every junction (PHAST), spread on a grid and drawn as areas with marching squares.
  9. The router is judged against plain Dijkstra on the same graph before contraction: the tests compare 10,000 random pairs for each mode, and the page against Dijkstra runs the same comparison in the browser.
  10. Map data © OpenStreetMap contributors, under the Open Database License.