A*-Algorithmus: Wegfindung in Spielen und Karten

Kurz: A* findet kürzeste Wege in Graphen oder Rastern effizient, indem es mit einer Schätzung (Heuristik) zum Ziel die vielversprechendsten Felder zuerst untersucht.

Genauer: Spielfiguren, Navigationsgeräte und Roboter brauchen Wege um Hindernisse. Dijkstra findet sicher den kürzesten Weg, durchsucht aber in alle Richtungen. A* (A-Stern) lenkt die Suche mit einer Heuristik zum Ziel.

Im Detail

Idee: f = g + h

Jeder Knoten bekommt f(n) = g(n) + h(n):

• g(n): bisherige Kosten vom Start bis n.
• h(n): Schätzung der Restkosten bis zum Ziel (Heuristik). A* nimmt immer den Knoten mit kleinstem f aus einer Prioritätswarteschlange (Open-Liste), expandiert Nachbarn, aktualisiert günstigere Wege und merkt sich erledigte Knoten (Closed-Liste). Ist h = 0, wird A* zu Dijkstra; ist g = 0, zur gierigen Bestensuche.

Heuristiken

• Manhattan-Distanz |dx| + |dy|: Raster ohne Diagonalen.
• Chebyshev max(|dx|, |dy|): Raster mit Diagonalen (gleiche Kosten).
• Oktil/Euklid: Diagonalen √2 teurer / freie Bewegung (√(dx²+dy²)).
• Zulässig (admissible): h überschätzt nie die echten Kosten → A* liefert den optimalen Weg. Konsistent: zusätzlich Dreiecksungleichung → jeder Knoten wird nur einmal expandiert.
• Zu große (überschätzende) h machen es schneller, aber der Weg ist ggf. nicht kürzester.

Pseudocode

open = PrioritaetsQueue(); open.add(start, f=h(start))
g[start] = 0
while open nicht leer:
    n = open.pop_min()
    wenn n == ziel: Weg rekonstruieren (Vorgänger)
    für jeden Nachbarn m von n:
        neu = g[n] + kosten(n, m)
        wenn neu < g.get(m, ∞):
            g[m] = neu; vorgaenger[m] = n
            open.add_or_update(m, f = neu + h(m))

Beispiel: Raster mit Hindernissen, Start (0,0), Ziel (7,5): A* untersucht deutlich weniger Felder als Dijkstra. Datenstruktur: Binärer Heap (Python heapq). Gitter vs. Waypoints/Navmesh in 3D-Spielen.

Praxis in Spielen

• Karten: Gelände mit unterschiedlichen Kosten (Sumpf teurer), Diagonalschneiden über Ecken vermeiden.
• Viele Einheiten: Pfad-Caching, *hierarchische Suche (HPA)**, Flow Fields, Jump Point Search (Raster).
• Dynamische Welt: D* Lite passt Wege an, wenn sich Hindernisse ändern.
• Wegglättung, Steering.
• Navigation/Straßennetze: Contraction Hierarchies & Co. schneller als reines A*.
• Rätsel: 8er-Puzzle, Sokoban-Solver.
• Verwandt: BFS/DFS, Dijkstra, Graphen, Prioritätswarteschlange.

Siehe auch: Dijkstra-Algorithmus, Breitensuche und Tiefensuche, Heap und Prioritätswarteschlange, Game Loop