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...

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.

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.