Bei der Entwicklung meines Echtzeit-Strategiespiels stellte sich mir
nach der Gestaltung der Landschaft das Problem, die Spielfiguren von
einem Punkt zu einem anderen zu bewegen, ohne dass sie dabei z.B. gegen
Hindernisse laufen. Nach einigen (für einen ambitionierten
Programmierer wie mich stets vorangehenden Selbstversuchen ;) wandte ich mich dem
A*-Algorithmus zu, von dem ich schon des Öfteren gelesen hatte.
Ich fand dann eine sehr gute Beschreibung des Themas von Patrick
Lester. Da dieser Artikel in
Englisch
geschrieben war, übersetzte ich ihn ins
Deutsche,
auf dass er auch für Andere leichter verstehbar sein würde.
Nach der Übersetzung schrieb ich das hier zu sehende Applet, welches
das Grundprinzip des A*-Pfadfindungsalgorithmus demonstriert und auf der Komponente JDataGrid basiert.
Die Listenverwaltung innerhalb des Algorithmus erfolgt übrigens
mittels einer "Binären Halde" (siehe den Artikel von Patrick Lester),
die in einer Implementierung der Klasse PriorityBuffer durch das
Apache Jakarta Project vorliegt.
Hinweis: Falls das Applet trotz installiertem Java nicht dargestellt
werden sollte, kann dies daran liegen, dass in Ihrer lokalen .java.policy-Datei
die Leserechte aus Eigenschafts-Dateien (Dateien mit der Endung .properties)
nicht gesetzt sind.
Da Dieses Applet aber Farbwerte aus der beigefügten astar.properties-Datei
liest, sollten in Ihrer .java.policy-Datei folgende Einträge hinzugefügt
werden:
grant {
permission java.util.PropertyPermission "height", "read";
permission java.util.PropertyPermission "width", "read";
permission java.util.PropertyPermission "hintergrund.rgb", "read";
permission java.util.PropertyPermission "kontrast.rgb", "read";
permission java.util.PropertyPermission "field.rgb", "read";
permission java.util.PropertyPermission "start.rgb", "read";
permission java.util.PropertyPermission "target.rgb", "read";
permission java.util.PropertyPermission "wall.rgb", "read";
permission java.util.PropertyPermission "path.rgb", "read";
permission java.util.PropertyPermission "pathtest.rgb", "read";
};