Búsqueda jerárquica de rutas
Dividir el mapa en regiones gruesas y buscar primero una ruta aproximada entre ellas, para luego refinarla dentro de cada región.
Un mapa grande se vuelve más barato de recorrer mediante abstracción. El mapa se divide en clústeres, y solo las entradas de los clústeres y los enlaces entre ellos se elevan a un grafo abstracto. A* resuelve primero el grafo pequeño — qué regiones cruza la ruta — y después refina cada tramo localmente. La variante más citada es HPA* de Botea, Müller y Schaeffer (2004).
La ganancia es grande en niveles extensos: la búsqueda abstracta toca una fracción de los nodos. El precio es que la ruta ya no se garantiza la más corta — es casi óptima, lo que casi siempre basta en un juego. El método se combina bien con jump point search dentro de los clústeres y con un navmesh para la geometría más fina.