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