Hierarkisk vägsökning
Att dela upp kartan i grövre regioner och söka en grov väg mellan dem först, sedan förfina den inom varje region.
En stor karta görs billigare att söka genom att abstraheras. Kartan delas i kluster, och bara klustrens entréer och förbindelserna mellan dem lyfts upp i en abstrakt graf. A* löser först den lilla grafen — vilka regioner vägen passerar — och förfinar sedan varje delsträcka lokalt. Den mest citerade varianten är HPA* av Botea, Müller och Schaeffer (2004).
Vinsten är stor på vidsträckta nivåer: den abstrakta sökningen rör en bråkdel av noderna. Priset är att vägen inte längre garanterat är kortast — den är nästan optimal, vilket nästan alltid räcker i ett spel. Metoden kombineras gärna med jump point search inom klustren och med ett navmesh för den finare geometrin.