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 H
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.
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 Optianlen Werte sollten auch mit in die Rechnung für F einfliessen.
Berechnungs Formel: §F = H + G + Optional§
