Pathfinding gerarchico
Suddividere la mappa in regioni grossolane, cercare prima un percorso approssimativo tra di esse e poi rifinirlo all'interno di ciascuna.
Una mappa grande diventa più economica da esplorare grazie all'astrazione. La mappa viene divisa in cluster e solo gli ingressi dei cluster e i collegamenti tra loro entrano in un grafo astratto. A* risolve prima il grafo ridotto — quali regioni attraversa il percorso — poi ogni tratto viene rifinito localmente. La variante più citata è HPA* di Botea, Müller e Schaeffer (2004).
Il guadagno è notevole nei livelli molto estesi: la ricerca astratta tocca una frazione dei nodi. Il prezzo è che il percorso non è più garantito come il più breve, ma quasi ottimale, il che in un gioco basta quasi sempre. Il metodo si abbina bene alla jump point search dentro i cluster e a una navmesh per la geometria più fine.