[bikelang]

This is super cool. I’ve been kicking around an idea for ages regarding tile-based routing that I think would be excellent for offline routing. You could leverage the quadtree aspect of tiling to encapsulate faster, direct routes (ie highways) and as you go to deeper zoom levels you’d unlock small roads - even down to pathways. This keeps your in-memory graph small while traversing large distances (which would just be highways anyways) and once you eliminated most of the distance your remaining graph traversal on local roads would be small

[michaelt]

You might enjoy reading the papers "Highway Hierarchies Hasten Exact Shortest Path Queries" [1] and "Exact Routing in Large Road Networks using Contraction Hierarchies" [2] if you're interested in hierarchical approaches to shortest path routing.

The algorithms do divide the map up into chunks that are themselves divided up and so on, but not on the strict geographical basis a quadtree uses. You might not want to divide Manhattan in two for routing purposes, even if the 74th longitude line runs straight through it.

[1] https://turing.iem.thm.de/routeplanning/hwy/esaHwyHierarchie... [2] https://publikationen.bibliothek.kit.edu/1000028701/14297392...

[packet_mover]

That’s a really interesting framing - you’re basically describing hierarchical routing / "zoom-level" graphs: do the long leg on a coarse network (highways), then refine locally as you get closer to origin/destination.

FWIW, Valhalla already does a version of this: it partitions the routing graph into hierarchical tiles and runs with multiple hierarchy levels (highway / arterial / local) specifically to keep search + in-memory working set smaller on long routes: https://valhalla.github.io/valhalla/tiles/

The "quadtree tile unlock" mental model is a nice way to think about it though - if you have a favorite paper / implementation that leans harder into the tiling aspect, I’d love a pointer. I’m currently focused on packaging + offline data consistency, but routing performance on constrained edge boxes is definitely a core constraint I care about.

[krapht]

What you suggested has been done before - you might find a review of the literature fun if this sort of thing interests you, even if academic papers are pretty dry reading normally.

[tomaskafka]

Also game engines need to do painting very fast