A*-Algorithmus in Java
Für Programmierwettbewerb der Otto-von-Guericke-Universität Magdeburg 2006/2007 sollte eine Künstliche Intelligenz in Form eines Hundes programmiert werden, dessen Aufgabe es sein sollte, Schafe auf einer Karte in einen Zielbereich zu treiben.
Hauptaufgabe war es somit, einen Algorithmus zu implementieren, der es den Hunden ermöglicht Hindernissen auf der Karte auszuweichen und den kürzesten Weg zum Ziel zu finden.
Weitere Informationen zu meinem programmierten Hund befinden sich auf der Seite des Programmierwettbewerbes. Im Anschluss soll es hier ausschließlich um (m)eine Implementierung des A*-Algorithmus in Java gehen.
Allgemeines zur Implementierung des A*-Algorithmus
Zur allgemeinen Funktionsweise des A*-Algorithmus gibt es genügend Ressourcen, weshalb ich an dieser Stelle davon absehen möchte, erneut darauf einzugehen. Ich verweise auf folgende Seiten, die ich für meine Implementierung genutz habe:
- A*-Algorithmus bei Wikipedia
- detaillierte Erklärung des A*-Algorithmus mit Beispiel und C++/Blitz Basic Code bei policyamanac.org (englisch)
Um den Code später eventuell für eigene Projekte wiederverwenden zu können, versuchte ich den Code so allgemein wie nötig zu schreiben. Als Resultat entstanden zwei Klassen, die allgemein einsetzbar sind, wenn folgende Voraussetzungen erfüllt sind:
- Die Wegfindung wird über Tiles realisiert, die quadratisch sind. Somit hat jedes Tile genau 8 Nachbarn.
- Die Spielkarte kann in Form eines zweidimensionalen Arrays gespeichert werden, sodass es möglich ist Start- und Zielpunkt als Koordinaten im Array zu definieren
Werden diese Bedingungen erfüllt, kann der kürzeste Weg zwischen zwei Tiles bestimmt werden. Dabei wird beachtet, dass es nicht möglich ist, zwischen zwei schräg benachbarten Tiles, die nicht begehbar sind, hindurchzugehen. Die Geschwindigkeit, mit der man sich auf dem Tile bewegen kann, wird ebenfalls berücksichtigt. Je nach gewünschter Implementierung, müssen die letzten beiden Merkmale manuell in der Klasse geändert werden. Das im Folgenden vorgestellte Testprogramm verwendet nur Tiles, auf denen die Geschwindigkeit auf allen Tiles gleich ist. Die Pfadfindungsklasse besitzt aber auch einen Konstruktor, dem ein Feld von double Werten für die Geschwindigkeit auf den einzelnen Tiles übergeben werden kann.
Test-Applet für die Wegfindung
Der Einfachheit halber habe ich die Pfadfinder Klasse für den Wettbewerb zunächst in einem seperaten Programm getestet, um das komplexe Wettbewerbs-Framework als zusätzliche Fehlerquelle ausschließen zu können. Dieses Programm habe ich zum Darstellungszweck in ein Applet umgewandelt, dass sich an dieser Stelle zur Vorführung eignet.
Das Programm zeigt nicht die Umsetzung des A*-Algorithmus, sondern dient lediglich zur schnellen Visualisierung des Ergebnisses und somit als Testprogramm für die Pfadfinder Klasse.
Die Bedienung des Applets ist simpel. Auf der Karte können die Kästchen mit links angeklickt werden, um sie begehbar oder nicht begehbar zu machen. Weiße Quadrate sind begehbar, schwarze sind es nicht.
Mit der rechten Maustaste ist es möglich Start- und Zielpunkt neu zu setzen.
Der Button "Zurücksetzen" löscht die Karte.
"Start" beginnt mit der Visualisierung des gefundenen Weges. Während der Visualisierung kann die Karte nicht verändert werden.
Download des Quelltextes
Ohne den Quelltext wäre die ganze Vorrede natürlich sinnlos. Deshalb möchte ich an dieser Stelle die Pathfinder und Demo-Applet Packages auch zum Download bereitstellen.
Sie dürfen für jegliche Projekte weiterverwendet werden.
Das Download Archiv enthält zwei Packages. DemoApplet enthält obiges Testprogramm und aStarAlgorithm enthält die beiden Klassen zur Wegfindung. Zusätzlich ist auch eine JavaDoc enthalten, die beide Packages erklärt. Der gesamte Ordner im zip-Archiv kann auch unter Eclipse als Projekt importiert werden.
