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 später diese Begriffe 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.
Die Schätzfunktion
Die Schätzfunktion wird benötigt um dem aktuelle 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.
???
Eng verbunden mit der Schätzfunktion sind 2 weitere Werte.