A* (A-star)
Pathfinding-algoritm som hittar den kortaste vägen i en graf — Dijkstra plus en heuristik som styr sökningen mot målet.
Hart, Nilsson & Raphael (Stanford, 1968). Utvärderar noder enligt f(n) = g(n) + h(n) där g är kostnaden från start och h är estimerad kostnad till mål. Om h är "admissible" (aldrig överskattar) garanterar A* optimal lösning.
Standardalgoritm i spel-AI för navigation, robotnavigering, GPS-rutter. Manhattan-distans och euklidisk distans är vanliga heuristiker för 2D-grid. Konkurrenter: Dijkstra (utan heuristik), Jump Point Search (grid-optimering), HPA* (hierarkisk).