A* (A-Stern)
Pathfinding-Algorithmus, der den kürzesten Weg in einem Graphen findet — Dijkstra plus eine Heuristik, die die Suche auf das Ziel zulenkt.
Hart, Nilsson & Raphael (Stanford, 1968). Bewertet Knoten nach f(n) = g(n) + h(n), wobei g die Kosten ab dem Start und h die geschätzten Kosten bis zum Ziel sind. Ist h "zulässig" (schätzt nie zu hoch), garantiert A* eine optimale Lösung.
Standardalgorithmus für Navigation in Spiele-KI, Roboternavigation und GPS-Routenplanung. Manhattan-Distanz und euklidische Distanz sind gängige Heuristiken für 2D-Gitter. Konkurrenten: Dijkstra (ohne Heuristik), Jump Point Search (Gitter-Optimierung), HPA* (hierarchisch).