Hiërarchische padvinding
De kaart opdelen in grove regio's, eerst een ruwe route tussen die regio's zoeken en die daarna binnen elke regio verfijnen.
Een grote kaart wordt goedkoper te doorzoeken door abstractie. De kaart wordt in clusters verdeeld, en alleen de ingangen van de clusters en de verbindingen ertussen komen in een abstracte graaf. A* lost eerst de kleine graaf op — welke regio's het pad doorkruist — en verfijnt daarna elk deeltraject lokaal. De meest geciteerde variant is HPA* van Botea, Müller en Schaeffer (2004).
De winst is groot op uitgestrekte levels: de abstracte zoektocht raakt maar een fractie van de knopen. De prijs is dat het pad niet langer gegarandeerd het kortste is — het is bijna optimaal, wat in een spel vrijwel altijd volstaat. De methode combineert goed met jump point search binnen clusters en met een navmesh voor de fijnere geometrie.