Interaktive Demo
A*-Suche
A* (A-Stern), 1968 von Peter Hart, Nils Nilsson und Bertram Raphael veröffentlicht, ist der Standard für Wegfindung in Spielen und Robotik. Der Algorithmus erweitert Zellen nach den bisherigen Kosten plus einer Schätzung der restlichen Entfernung.
Zeichne Wände oder Schlamm ins Gitter und ziehe Start und Ziel. Ist eine Suche fertig, wird nach jeder Änderung sofort neu gesucht. Setze das Gewicht der Heuristik über 1: A* erweitert weniger Zellen, aber der Weg kann mehr kosten. Mit diagonalen Schritten überschätzt die Manhattan-Heuristik und kann ebenfalls den optimalen Weg kosten.
Ablauf
- Erweitert
- –
- Front (max.)
- –
- Wegkosten
- –
Drücke Abspielen oder Nächster Schritt, um die Suche zu starten.
Raster
Optionen
Legende
- Start (ziehen zum Verschieben)
- Ziel (ziehen zum Verschieben)
- Wand
- Schlamm
- Front (Open List)
- Besucht (Closed List)
- Gerade erweitert
- Weg
Eigenschaften
Optimal
Mit Bedingung
Optimal mit Gewicht 1 und einer Schätzung, die nie überschätzt. Manhattan überschätzt, wenn diagonale Schritte erlaubt sind.
Gewichtete Zellen
Ja
Die bisherigen Kosten enthalten den Schlamm, wie beim Dijkstra-Algorithmus.
Heuristik
Ja
f = g + w · h: die bisherigen Kosten plus die gewichtete Schätzung des Rests.
Beliebiger Winkel
Nein
Bewegt sich von Zelle zu Zelle, gerade oder diagonal.
Alle Wegfindungsalgorithmen im Vergleich
| Algorithmus | Optimal | Gewichtete Zellen | Heuristik | Beliebiger Winkel |
|---|---|---|---|---|
| Breitensuche | Ohne Schlamm und Diagonalen | Nein | Nein | Nein |
| Tiefensuche | Nein | Nein | Nein | Nein |
| Dijkstra-Algorithmus | Ja | Ja | Nein | Nein |
| Bidirektionale Suche | Ja | Ja | Nein | Nein |
| Gierige Bestensuche | Nein | Nein | Ja | Nein |
| A*-Suche diese Seite | Mit Gewicht 1 und zulässiger Heuristik | Ja | Ja | Nein |
| Jump Point Search | Ohne Schlamm | Nein | Ja | Nein |
| Theta* | Nein | Abkürzungen nur über freies Gelände | Ja | Ja |
1. f = g + h
Für jede Zelle sind g die Kosten des besten gefundenen Wegs vom Start und h die geschätzten Kosten bis zum Ziel. A* erweitert immer die Zelle mit dem kleinsten f = g + h, also den vielversprechendsten Weg durch sie. Bei Gleichstand gewinnt die Zelle näher am Ziel.
2. Zulässige Schätzungen
Überschätzt h die echten Restkosten nie, findet A* den günstigsten Weg, und je besser h ist, desto weniger Zellen erweitert er. Mit h = 0 ist er der Dijkstra-Algorithmus, die Oktil-Distanz ist die beste sichere Schätzung für Gitter mit diagonalen Schritten.
3. Gewichtetes A*
Mit f = g + w · h und w > 1 zählt die Schätzung mehr: Die Suche steuert direkter auf das Ziel zu und erweitert weniger Zellen. Der Weg kostet dann höchstens das w-Fache des Optimums. Bei großen Gewichten verhält sich A* wie die gierige Bestensuche.
Quellen
- Peter E. Hart, Nils J. Nilsson und Bertram Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths (IEEE Transactions on Systems Science and Cybernetics, 1968).