Wegfindung mit A*
A* (A Stern) ist ein Algorithmus, um einen kürzesten oder kostengünstigsten Weg zwischen zwei Punkten zu finden. Dabei ist es egal, ob es sich um eine 2D- oder eine 3D-Spielwelt handelt. Dafür verwendet er eine Schätzfunktion, die dazu beiträgt gerichtet zu suchen, was im Allgemeinen die Effizienz der Suche verbessert. Gibt es einen Weg zwischen den zwei Punkten, so ist garantiert, dass A* ihn auch findet. Weiterhin ist garantiert, dass immer ein kürzester Weg gefunden wird.
Inhaltsverzeichnis |
Verwendung
Im Prinzip kann A* überall da verwendet werden, wo Spielobjekte (z.B. die Spielfigur oder Gegner) von A nach B gelangen müssen und dabei eigenständig ihren Weg finden sollen.
| Genre | Spielevertreter | im Detail |
|---|---|---|
| Echtzeitstrategie | Command and Conquer | eigene/gegnerische Einheiten |
| rundenbasiertes Strategiespiel | Civilization | eigene/gegnerische Einheiten |
| Ego-Shooter | Half Life | gegnerische Einheiten |
| MMORPG | World of Warcraft | eigene Begleiter / gegnerische Einheiten |
Wichtige Bestandteile von A*
Hier wird auf die wichtigsten Komponenten des Algorithmus eingegangen, weil diese Begriffe später immer wieder auftauchen.
Die Knoten
Als Knoten wird in diesem Zusammenhang ein Punkt auf dem Spielfeld bezeichnet. Ein Knoten kann, muss aber keine geometrische Form aufweisen. Diese Knoten können auch nur abstrakt existieren.
A* unterscheidet zwischen verschiedene Arten von Knoten:
- unbekannte Knoten
- bekannte Knoten
- untersuchte Knoten
Ein unbekannter Knoten muss dem A*-Algorithmus erst im Laufe der Zeit bekannt gemacht werden. Bekannte Knoten können untersucht werden. Durch diese Untersuchung können unbekannte Knoten entdeckt werden. Diese unbekannten Knoten werden analysiert und werden zu bekannten Knoten. Wenn der bekannte Knoten einmal untersucht wurde, bleibt es dabei, und er wird nicht noch einmal untersucht. Allerdings können bekannte Knoten wiederholt analysiert werden.
Die Schätzfunktion
Die Schätzfunktion wird benötigt, um dem aktuell untersuchten Knoten einen Wert zuzuweisen. Dieser Wert macht eine Aussage darüber, wie weit der Knoten schätzungsweise vom Ziel entfernt ist. Die Schätzfunktion wird im Allgemeinen als §h§ bezeichnet (für Heuristik), und die geschätzten Kosten nennen wir §H§. Die tatsächlichen Kosten bezeichnen wir mit §c§. §c(k)§ gibt die Kosten an, um vom Knoten §k§ zum Ziel zu gelangen, §c(k, k')§ gibt die Kosten an, um vom Knoten §k§ zum Knoten §k'§ zu gelangen.
Es gibt verschiedene Ansätze für die Schätzfunktion. Welche davon eine gute Wahl ist, hängt auch immer davon ab, was im Spiel genau erreicht werden soll. Damit der hier gezeigte A*-Algorithmus korrekt funktioniert, muss die Schätzfunktion eine Voraussetzung erfüllen, sie muss nämlich monoton sein. Das bedeutet in diesem Zusammenhang:
- §h(k) \leq c(k)§: Die geschätzten Kosten dürfen nie größer sein dürfen als die tatsächlichen Kosten. Die Schätzfunktion darf die Kosten also nicht überschätzen.
- §h(k) \leq c(k, k') + h(k')§ für benachbarte Knoten §k§ und §k'§: Die geschätzten Kosten von einem Knoten §k§ zum Ziel dürfen nicht größer sein als die tatsächlichen Kosten zu einem beliebigen Nachbarknoten §k'§ plus die geschätzten Kosten von §k'§ bis zum Ziel.
Eine einfache Schätzfunktion ist die direkte Distanz zwischen dem aktuellen Knoten und dem Ziel. Diese Distanz wird mittels des Satz des Pythagoras ermittelt.
Eine weitere Möglichkeit ist die Manhattan-Distanz. Bei dieser Methode werden vom entstehenden Dreieck einfach die Längen der beiden Katheten addiert. Diese darf aber nur dann angewendet werden, wenn keine diagonalen Bewegungen erlaubt sind, ansonsten würde sie die Kosten überschätzen. Ihren Namen hat diese Distanzfunktion aus dem New Yorker Stadtteil Manhattan, da man sich dort normalerweise nur vertikal und horizontal durch die Straßen um die Gebäudeblöcke bewegen kann.
Nach Pythagoras:
§Distanz = \sqrt{{x_{Laenge}}^2 + {y_{Laenge}}^2} = \sqrt{5^2 + 8^2} = 9.4 §
Manhattan-Distanz:
§Distanz = x_{Laenge} + y_{Laenge} = 5 + 8 = 13 §
Die Werte F, G und optionale Werte
Eng verbunden mit der Schätzfunktion sind zwei weitere Werte. Der Wert für den bereits zurückgelegten Weg vom Startknoten wird im Allgemeinen als §G§ bezeichnet. Ein weiterer wichtiger Wert ist die Summe aus §H§ und §G§. Dieser Wert wird §F§ genannt. Er stellt später das Suchkriterium dar, nach dem aus der Openlist ein Knoten ausgewählt wird.
Es gibt auch weitere Werte, die auf den Algorithmus einen Einfluss haben können. Zum Beispiel könnte es Extrakosten geben, die bei Strategiespielen durch unwegsames Gelände zustande kommen. Eine weitere Möglichkeit sind Drehbewegung einer Spielfigur, die ebenfalls Kosten verursachen können. Diese "optionalen Werte" sollten auch mit in die Berechnung von §F§ einfließen.
Berechnungsformel: §F = H + G + Optional§
Die Openlist
In die Openlist kommen alle Knoten, die bekannt sind. Bei der Openlist wird die Verwendung einer Vorrangwarteschlange empfohlen, in der die Knoten nach ihren §F§-Werten sortiert werden. Somit kann sehr schnell auf den erfolgversprechendsten Knoten zugegriffen werden.
Die Closedlist
In die Closedlist kommen alle Knoten, die bereits untersucht wurden. Die Closedlist kann implizit dadurch dargestellt werden, dass man sich für jeden Knoten merkt, ob er in der Closedlist steht oder nicht. Alternativ bietet sich eine sortierte Liste oder eine Hashtabelle an, da diese Datenstrukturen eine Abfrage der Art "Ist Element x enthalten?" sehr schnell beantworten können.
Arbeitsweise von A*
Im Folgenden wird beschrieben, wie alle Komponenten des A*-Algorithmus zusammen arbeiten.
Datenstruktur eines Knoten
Diese Werte sollte ein Knoten mindestens speichern können:
- H beinhaltet den Schätzwert der Wegkosten von diesem Knoten bis zum Ziel.
- G enthält die bisher zurückgelegten Wegkosten.
- F enthält die Summe aus G und H.
- CoordX, CoordY (und ggf. CoordZ) sind die Koordinaten des Knotens.
- ComeFromX, ComeFromY (und ggf. ComeFromZ) sind die Koordinaten des Knotens, von denen auf den aktuellen Knoten zugegriffen wurde.
- IsClosed ist ein optionales Flag, das angibt, ob der Knoten bereits abschließend untersucht wurde (er also in der Closedlist ist).
Beschreibung
Zu Beginn sind dem Algorithmus nur zwei Knoten bekannt, der Startknoten und der Zielknoten. Der Startknoten wird der Openlist hinzugefügt. Den Zielknoten behalten wir erst einmal nur im Hinterkopf.
In der Openlist wird nun nach dem geeignetsten Knoten gesucht. Da hier nur der Startknoten enthalten ist, fällt die Wahl nicht schwer. Jetzt wird der Startknoten untersucht, das bedeutet, dass nach allen benachbarten begehbaren Knoten gesucht wird. Für jeden gefundenen Knoten werden die Werte für §H§, §G§ und §F§ ermittelt. Die ermittelten Werte werden in den jeweiligen Knoten gespeichert. Weiterhin muss auch gespeichert werden, von welchem Knoten man auf den neuen Knoten gekommen ist. Die neu gefunden Knoten werden alle in die Openlist eingefügt. Der Startknoten wird von einem bekannten Knoten zu einem untersuchten Knoten und wird damit in die Closedlist eingefügt.
Jetzt wird in der Openlist nach dem Knoten gesucht der den geringsten §F§-Wert hat. Von diesem Knoten werden nun wieder alle benachbarten Knoten gesucht und analysiert. Dabei kann es vorkommen, dass im Laufe der Zeit Knoten die schon in der Openlist stehen, erneut analysiert werden. Wenn der §F§-Wert sich verbessert, sollten alle Daten des Knotens überschrieben werden. Sind die Daten gleich oder schlechter, können die alten Daten beibehalten werden.
So arbeitet der Algorithmus die Openlist ab, fügt unbekannte Knoten der Openlist zu und fügt untersuchte Knoten der Closedlist zu. Wenn jetzt der Zielknoten der Closedlist zugefügt wird, endet der Algorithmus. Der günstigste Weg ist gefunden.
Nun kann ausgehend vom Zielknoten nachvollzogen werden, von welchem Knoten man auf den Zielknoten kam. Von diesem ausgehend wird dann wieder geschaut, von welchem Knoten man auf diesen kam, und immer so weiter, bis man wieder am Startknoten angekommen ist. Auf diese Weise wird der komplette Weg rekonstruiert.
Wenn die Openlist leer ist, bevor man den Zielknoten erreicht hat, kann der Algorithmus abgebrochen werden, da dann kein Weg zwischen Start- und Zielknoten existiert.
Schritt für Schritt mit Bildern
Da Bilder bekanntlich mehr sagen als 1000 Worte, noch einmal alles in Bildern erklärt.
Die Rahmenbedingungen für den Algorithmus:
- Es sind keine diagonalen Schritte erlaubt.
- Die Schätzfunktion ist die Manhattan-Distanz.
- 1 Schritt kostet 1 Punkt.
- Ein Richtungswechsel kostet 1 Punkt (in der Tabelle die Spalte Z).
- Knoten werden durch ihre x- und y-Koordinaten benannt.
Spielfeld-Legende:
- Grün: Startpunkt (7/10)
- Orange: Zielpunkt (2/2)
- Weiß: unbekannte Knoten
- Gelb: bekannte Knoten (Openlist)
- Blau: untersuchte Knoten (Closedlist)
- Schwarz: nicht begehbare Knoten (Hindernis)
| Openlist | Closedlist | |||||||
| Schritt | Knotenname | H | G | Z | F | Bild | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 1 | (7/10) | 13 | 0 | 0 | 13 | 
|
N/A | N/A |
| 1 | ||||||||
| 1 | ||||||||
| 1 | ||||||||
| 1 | ||||||||
| 1 | ||||||||
| 1 | ||||||||
| 1 | ||||||||
| 1 | ||||||||
| Schritt | Knotenname | H | G | Z | F | Bild | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 2 | (6/10) | 12 | 1 | 0 | 13 | 
|
(7/10) | N/A |
| (7/9) | 12 | 1 | 0 | 13 | ||||
| (8/10) | 14 | 1 | 0 | 15 | ||||
| 2 | ||||||||
| 2 | ||||||||
| 2 | ||||||||
| 2 | ||||||||
| 2 | ||||||||
| 2 |
| Schritt | Knotenname | H | G | Z | F | Bild | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 3 | (5/10) | 11 | 2 | 0 | 13 | 
|
(7/10) | N/A |
| 3 | (7/9) | 12 | 1 | 0 | 13 | (6/10) | (7/10) | |
| 3 | (6/9) | 12 | 2 | 1 | 15 | |||
| 3 | (8/10) | 14 | 1 | 0 | 15 | |||
| 3 | ||||||||
| 3 | ||||||||
| 3 | ||||||||
| 3 | ||||||||
| 3 |
| Schritt | Knotenname | H | G | Z | F | Bild | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 4 | (4/10) | 10 | 3 | 0 | 13 | 
|
(7/10) | N/A |
| 4 | (7/9) | 12 | 1 | 0 | 13 | (6/10) | (7/15) | |
| 4 | (5/9) | 11 | 3 | 1 | 15 | (5/10) | (6/10) | |
| 4 | (6/9) | 12 | 2 | 1 | 15 | |||
| 4 | (8/10) | 14 | 1 | 0 | 15 | |||
| 4 | ||||||||
| 4 | ||||||||
| 4 | ||||||||
| 4 |
| Schritt | Knotenname | H | G | Z | F | Bild | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 5 | (3/10) | 9 | 4 | 0 | 13 | 
|
(7/10) | N/A |
| 5 | (7/9) | 12 | 1 | 0 | 13 | (6/10) | (7/10) | |
| 5 | (4/9) | 10 | 4 | 1 | 15 | (5/10) | (6/10) | |
| 5 | (5/9) | 11 | 3 | 1 | 15 | (4/10) | (5/10) | |
| 5 | (6/9) | 12 | 2 | 1 | 15 | |||
| 5 | (8/10) | 14 | 1 | 0 | 15 | |||
| 5 | ||||||||
| 5 | ||||||||
| 5 |
| Schritt | Knotenname | H | G | Z | F | Bild | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 6 | (2/10) | 8 | 5 | 0 | 13 | 
|
(7/10) | N/A |
| 6 | (7/9) | 12 | 1 | 0 | 13 | (6/10) | (7/10) | |
| 6 | (3/9) | 9 | 5 | 1 | 15 | (6/10) | (5/10) | |
| 6 | (4/9) | 10 | 4 | 1 | 15 | (4/10) | (5/10) | |
| 6 | (5/9) | 11 | 2 | 1 | 15 | (3/10) | (4/10) | |
| 6 | (6/9) | 12 | 2 | 1 | 15 | |||
| 6 | (8/10) | 14 | 1 | 0 | 15 | |||
| 6 | ||||||||
| 6 |
| Schritt | Knotenname | H | G | Z | F | Bild | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 7 | (7/9) | 12 | 1 | 0 | 13 | 
|
(7/10) | N/A |
| 7 | (2/9) | 8 | 6 | 1 | 15 | (6/10) | (7/10) | |
| 7 | (3/9) | 9 | 5 | 1 | 15 | (6/10) | (5/10) | |
| 7 | (1/10) | 9 | 6 | 0 | 15 | (4/10) | (5/10) | |
| 7 | (4/9) | 10 | 4 | 1 | 15 | (3/10) | (4/10) | |
| 7 | (5/9) | 11 | 3 | 1 | 15 | (2/10) | (3/10) | |
| 7 | (6/9) | 12 | 2 | 1 | 15 | |||
| 7 | (8/10) | 14 | 1 | 0 | 15 | |||
| 7 |
...
Wer üben will, kann Schritt 8 und folgende anhand der Animation selber ausprobieren. Wir springen jetzt gleich zum letzten Schritt, um zu zeigen, wie man nun den Weg abgehen kann.
| Schritt | Knotenname | H | G | Z | F | Bild | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 21 | (6/3) | 5 | 8 | 1 | 14 | 
|
(7/10) | N/A |
| (6/5) | 7 | 6 | 1 | 14 | (6/10) | (7/10) | ||
| (3/9) | 8 | 5 | 1 | 14 | (6/10) | (5/10) | ||
| (6/6) | 8 | 5 | 1 | 14 | (4/10) | (5/10) | ||
| (4/9) | 9 | 4 | 1 | 14 | (3/10) | (4/10) | ||
| (6/7) | 9 | 4 | 1 | 14 | (2/10) | (3/10) | ||
| (5/9) | 10 | 3 | 1 | 14 | (7/9) | (7/10) | ||
| (6/8) | 10 | 3 | 1 | 14 | (7/8) | (7/9) | ||
| (6/9) | 11 | 2 | 1 | 14 | (7/7) | (7/8) | ||
| (7/1) | 6 | 9 | 0 | 15 | (7/6) | (7/7) | ||
| (1/10) | 9 | 6 | 0 | 15 | (7/5) | (6/7) | ||
| (8/10) | 14 | 1 | 0 | 15 | (7/4) | (7/5) | ||
| (8/2) | 6 | 9 | 1 | 16 | (7/3) | (7/4) | ||
| (8/3) | 7 | 8 | 1 | 16 | (7/2) | (7/3) | ||
| (8/4) | 8 | 7 | 1 | 16 | (2/9) | (2/10) | ||
| (8/5) | 9 | 6 | 1 | 16 | (2/8) | (2/9) | ||
| (8/6) | 10 | 5 | 1 | 16 | (6/2) | (7/2) | ||
| (8/7) | 11 | 4 | 1 | 16 | (5/2) | (6/2) | ||
| (8/8) | 12 | 3 | 1 | 16 | (4/2) | (5/2) | ||
| (8/9) | 13 | 2 | 1 | 16 | (3/2) | (4/2) | ||
| (3/1) | 2 | 13 | 2 | 17 | (2/2) | (3/2) | ||
| (3/3) | 2 | 13 | 2 | 17 | ||||
| (4/1) | 3 | 12 | 2 | 17 | ||||
| (4/3) | 3 | 12 | 2 | 17 | ||||
| (5/1) | 4 | 11 | 2 | 17 | ||||
| (5/3) | 4 | 11 | 2 | 17 | ||||
| (6/1) | 5 | 10 | 2 | 17 | ||||
| (1/8) | 7 | 8 | 2 | 17 | ||||
| (3/8) | 7 | 8 | 2 | 17 | ||||
| (1/9) | 8 | 7 | 2 | 17 |
In der Closedlist steht jetzt schon der richtige Weg, zwar ist er nicht in der richtigen Reihenfolge, aber das stört nicht. Wenn man jetzt beim Zielknoten (2/2) in die Spalte ComeFrom schaut, steht dort ein Knoten (3/2). Jetzt sucht man sich in der Spalte Knotenname diesen Knoten heraus. In dieser Reihe steht unter ComeFrom wieder ein Knoten, und so "hangelt" man sich die Liste entlang bis man zum Startknoten kommt.
Der Weg, den der Algorithmus abgeht, sieht dann so aus:
(2/2) -> (3/2) -> (4/2) -> (5/2) -> (6/2) -> (7/2) -> (7/3) -> (7/4) -> (7/5) -> (7/6) -> (7/7) -> (7/8) -> (7/9) -> (7/10)
