Hierarchical pathfinding
Splitting the map into coarse regions and searching a rough route between them first, then refining it within each region.
A large map is made cheaper to search by abstraction. The map is divided into clusters, and only the clusters' entrances and the links between them are lifted into an abstract graph. A* first solves the small graph — which regions the path crosses — then refines each leg locally. The most-cited variant is HPA* by Botea, Müller and Schaeffer (2004).
The gain is large on sprawling levels: the abstract search touches a fraction of the nodes. The price is that the path is no longer guaranteed shortest — it is near-optimal, which is almost always enough in a game. The method pairs well with jump point search inside clusters and with a navmesh for the finer geometry.