Spielstände speichern und laden
Inhaltsverzeichnis |
Was ist A-Stern
A-Stern ist ein Algorithmus um den kürzesten oder kostengünstigsten Weg zwischen 2 Punkten zu finden.
Dafür verwendet er eine Schätzfunktion, die dazu beiträgt gerichtet zu suchen. Gibt es einen Weg zwischen den 2 Punkten findet A-Stern ihn.
Wo findet A-Stern Verwendung
Im prinzip kann A-Stern überall da verwendet werden wo Spielobjekte (z.B eigene Spielfigur oder Gegner) von A nach B müssen, auf nicht vorgefertigten Wegen.
| Genre | Spiele Vertreter | im Detail |
|---|---|---|
| Echtzeitstrategie | Command and Conquer | eigene/gegnerische Einheiten |
| rundenbasiertes Strategiespiel | Civilization | eigene/gegnerische Einheiten |
| Ego Shooter | Half Life | gegnersiche Einheiten |
| MMORPG | World of Warcraft | eigene Begleiter/gegnerische Einheiten |
Wichtige Bestandteile von A-Stern
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 Element des Spielfeldes bezeichnet. Sie können Verschiedene Geometrische Formen annehmen Viereckig, Sechseckig oder Achteckig. Diese Knoten können in manchen Spielen auch gar keine sichtbare Formen annehmen aber sie Existieren auf jeden fall irgendwo in form von Code.
Es gibt verschiedene Arten von Knoten:
- unbekannte Knoten
- bekannte Knoten
- untersuchte Knoten
Ein unbekannter Knoten muss dem A-Stern Algorithmus erst im laufe der Zeit bekannt gemacht werden. Bekannte Knoten können untersucht werden. Durch diese Untersuchung können unbekannt Knoten entdeckt werden. Diese unbekannten Knoten werden analysiert und werden zu bekannten Knoten. Wenn der bekannte Knoten einmal untersucht wurden, bleibt es dabei und er wird nicht noch einmal untersucht. Allerdings können bekannte Knoten öfters Analysiert werden.
Die Schätzfunktion H
Die Schätzfunktion wird benötigt um dem aktuell untersuchten Knoten einen Wert zu zuweisen. Dieser Wert macht darüber eine Aussage wie weit weg der Knoten ca. vom Ziel entfernt ist.
Es gibt verschiedene Ansätze für die Schätzfunktion und es hängt auch immer davon ab was genau erreicht werden soll im späteren Programm.
Die Berechnung der direkten Distanz zwischen dem Aktuellen Knoten und dem Ziel ist eine Möglichkeit. Diese Distanz wird mittels des Pytagoras ermittelt. Eine weitere Möglichkeit ist die Manhatten Distanz. Bei dieser Methode werden vom entstehenden Dreieck einfach die Längen der beiden Seiten a und b Addiert.
Nach Pytagoras :
§Distanz = \sqrt {{X_{Laenge}}^2 + {Y_{Laenge}}^2} = \sqrt { 5^2 + 9^2 } = 10,3 §
Manhatten Distanz :
§Distanz = X_{Laenge} + Y_{Laenge} = 5 + 9 = 14 §
Da der Wert für die Schätzfunktion im allgemeinen als H bezeichet wird werde ich mich ebenso daran halten.
Das H wird im späteren Verlauf immer wieder auftauchen.
Die Werte F,G und Optionale Werte
Eng verbunden mit der Schätzfunktion sind 2 weitere Werte. Der Wert für den bereits zurückgelegten Weg vom Startknoten. Dieser Wert wird genau berechnet und im allgemeinen als G Bezeichnet. Ein Weiterer wichtiger Wert ist die Summe aus H und G. Dieser Wert wird allgemein 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 Einfluss haben könnten auf den Algorithmus. Zum Beispiel extra Kosten die bei Strategiespielen durch unwegsames Gelände zu stande kommen. Eine weitere Möglichkeit sind auch Drehbewegung einer Spielfigur die auch Kosten verursachen können. Es gibt bestimmt noch unzählige weitere Dinge die einfluss nehmen können auf den Algorithmus.
Diese Optionalen Werte sollten auch mit in die Rechnung für F einfliessen.
Berechnungs Formel: §F = H + G + Optional§
Die Openlist
In die Openlist kommen alle Knoten die bekannt sind. Bei der Openlist kann es sich um eine Verkettete Liste oder einem Array handeln. In dieser List können die Knoten nach ihren F werten sotiert werden. Somit kann schneller auf den viel versprechendsten Knoten zugegriffen werden.
Die Closedlist
In die ClosedList kommen alle Knoten die bereits untersucht wurden. Bei diese Liste handelt es sich ebenfals um eine Verkettete Liste oder einem Array. Die Reihenfolge in der Closedlist spielt keine Rolle.
Arbeitsweise von A-Stern
Hier wird jetzt beschrieben wie alle Komponenten des Algorithmus zusammen arbeiten.
Datenstrukture eines Knoten
Diese Werte sollte ein Knoten mindestens Speichern können.
- H - Beinhaltet den Schätzwert
- G - Zurückgelegte Weg Kosten
- F - Summe aus G und H
- Coord_X - X Koordinate des Knoten
- Coord_Y - Y Koordinate des Knoten
- ComeFrom_X - X Koordinate des Knoten von dem auf den aktuellen Knoten zugegriffen wurde
- ComeFrom_Y - Y Koordinate des Knoten von dem auf den aktuellen Knoten zugegriffen wurde
Vielleicht auch noch 2 zusätzliche Flags:
- isOpenList
- isClosedList
Das erspart dann lästige vergleiche zwischen den 2 listen ob ein Knoten schon in der Closedlist ist.
Beschreibung
Zu begin sind nur 2 Knoten dem Algorithmus bekannt, der Startknoten und der Zielknoten. Der Startknoten wird der Openlist zugefügt. Den Zielknoten behalten wir erstmal nur im Hinterkopf.
In der Openlist wird nun nach dem geeignetesten Knoten gesucht. Da hier nur der Startknoten drin steht fällt die Wahl nicht schwer. Jetzt wird der Startknoten untersucht, das bedeutet das nach allen benachbarten Knoten gesucht wird. Für jeden gefundenen Knoten werden die Werte für H, G und F ermittelt. Die ermittelten Werte werden natürlich in den jeweiligen Knoten gespeichert. Weiterhin muss auch gespeichert von welchem Knoten man auf den neuen Knoten gekommen ist. Die neu gefunden Knoten kommen alle in die Openlist. Der Startknoten wird von einem bekannten Knoten nun zu einem untersuchten Knoten und kommt damit in die ClosedList.
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 das im laufe der Zeit Knoten die schon in der Openlist stehen nochmal analysiert werden. Wenn der F wert sich verbessert sollten alle Daten des Knoten Ü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 ist es vollbracht. Der günstigste weg ist gefunden.
Nun kann ausgehend vom Zielknoten geschaut werden von welchem Knoten man auf den Zielknoten kamm. Von dem wird dann geschaut von welchem Knoten man auf diesen kamm und immer so weiter bis man wieder am Startknoten angekommen ist. So wird dann der beste Weg abgebildet.
Wenn die Openlist leer ist bevor man den Zielknoten erreicht hat kann der Algorithmus abgebrochen werden, da dann kein Weg zwischen Start- und Zielnoten existiert.
Step by Step mit Bildern
Da Bilder mehr sagen als 1000 Worte nochmal alles in Bildern erklärt.
Es sind keine Diagonalen Schritte erlaubt. Die Distanz zum Ziel wird mit hilfe der Manhatten Distanz bestimmt. Die Kosten für einen Schritt betragen 1 Punkt. Um Treppenartige Wege zu verhinden wird ein Richtungs Wechsel auch ein Punkt kosten. Die Knoten werden nach ihren Koordinaten benannt (X Koordinate zuerst).
Spielfeld Legende:
- grün - Startpunkt (10/7)
- Orange - Zielpunkt (2/2)
- weiß - unbekannte Knoten
- gelb - bekannte Knoten (OpenList)
- blau - untersuchte Knoten (ClosedList)
- schwarz - nicht begehbare Knoten
| Schritt | Knotenname | H | G | Z | F | __ | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 1 | (10/7) | 14 | 0 | 0 | 14 | N/A | N/A |
| Schritt | Knotenname | H | G | Z | F | __ | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 2 | (10/6) | 13 | 1 | 0 | 14 | (10/7) | N/A | |
| (9/7) | 13 | 1 | 0 | 14 | ||||
| (10/8) | 15 | 1 | 0 | 16 |
| Schritt | Knotenname | H | G | Z | F | __ | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 3 | (10/5) | 12 | 2 | 0 | 14 | (10/7) | N/A | |
| (9/7) | 13 | 1 | 0 | 14 | (10/6) | (10/7) | ||
| (9/6) | 13 | 1 | 1 | 15 | ||||
| (10/8) | 15 | 1 | 0 | 16 |
| Schritt | Knotenname | H | G | Z | F | __ | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 4 | (10/4) | 11 | 3 | 0 | 14 | (10/7) | N/A | |
| (9/7) | 13 | 1 | 0 | 14 | (10/6) | (10/7) | ||
| (9/5) | 12 | 2 | 1 | 15 | (10/5) | (10/6) | ||
| (9/6) | 13 | 1 | 1 | 15 | ||||
| (10/8) | 15 | 1 | 0 | 16 |
| Schritt | Knotenname | H | G | Z | F | __ | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 5 | (10/3) | 10 | 4 | 0 | 14 | (10/7) | N/A | |
| (9/7) | 13 | 1 | 0 | 14 | (10/6) | (10/7) | ||
| (9/4) | 11 | 3 | 1 | 15 | (10/5) | (10/6) | ||
| (9/5) | 12 | 2 | 1 | 15 | (10/4) | (10/5) | ||
| (9/6) | 13 | 1 | 1 | 15 | ||||
| (10/8) | 15 | 1 | 0 | 16 |
| Schritt | Knotenname | H | G | Z | F | __ | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 6 | (10/2) | 10 | 4 | 0 | 14 | (10/7) | N/A | |
| (9/7) | 13 | 1 | 0 | 14 | (10/6) | (10/7) | ||
| (9/3) | 10 | 4 | 1 | 15 | (10/6) | (10/5) | ||
| (9/4) | 11 | 3 | 1 | 15 | (10/4) | (10/5) | ||
| (9/5) | 12 | 2 | 1 | 15 | (10/3) | (10/4) | ||
| (9/6) | 13 | 1 | 1 | 15 | ||||
| (10/8) | 15 | 1 | 0 | 16 |
| Schritt | Knotenname | H | G | Z | F | __ | Knotenname | ComeFrom |
|---|---|---|---|---|---|---|---|---|
| 7 | (9/7) | 13 | 1 | 0 | 14 | (10/7) | N/A | |
| (9/2) | 9 | 5 | 1 | 15 | (10/6) | (10/7) | ||
| (9/3) | 10 | 4 | 1 | 15 | (10/6) | (10/5) | ||
| (9/4) | 11 | 3 | 1 | 15 | (10/4) | (10/5) | ||
| (9/5) | 12 | 2 | 1 | 15 | (10/3) | (10/4) | ||
| (9/6) | 13 | 1 | 1 | 15 | (10/2) | (10/3) | ||
| (9/1) | 10 | 6 | 0 | 16 | ||||
| (10/8) | 15 | 1 | 0 | 16 |
