Finde den Weg

Suche mit A*

In vielen Spielen müssen Spielfiguren einen Weg von einem zu einem anderen Ort finden und zurücklegen. Dieser Weg sollte möglichst realistisch aussehen. Der A* Algorithmus sucht daher nicht unbedingt den kürzesten, sondern den (kosten)günstgsten Weg. A* kann solch einen Weg finden, wenn er existiert.

In der hier bearbeiteten Version wird dazu eine in Zellen aufgeteilte Karte genutzt. Die Zellen sind quadratisch, könnten aber auch gleichseitige Sechsecke, Dreiecke oder sonst etwas sein. Für jede Zelle sind die Wegekosten zur Durchquerung bekannt. Daraus lassen sich die Wegekosten zum Nachbarn ermitteln. Wegekosten könnten die Schwierigkeit oder den Zeitbedarf durchs Gelände zu kommen widerspiegeln. Sollten für alle Zellen die Wegekosten gleich sein, fällt der kostengünstigste mit dem kürzestem Weg zusammen. Während der Suche werden für jede besuchte Zelle drei Kostenwerte mit folgendem Zusammengang ermittelt: Gesamtkosten = Kosten für den bisherigen Weg + geschätze Kosten bis zum Ziel.

Letztendlich handelt es sich bei dem Problem um die Durchsuchung eines Graphen. Die Zellen entsprechen den Knoten, die 'Verbindungskosten' der (positiven) Gewichtung der Kanten, die jeweils 2 Knoten verbinden. Daher spielt die Form der Knoten keine Rolle.

Welche Voraussetzungen braucht A*?

Der Startknoten und Zielknoten müssen bekannt sein. Es gibt eine Möglichkeit von jedem Knoten die Kosten bis zum Ziel zu schätzen. Wenn die geschätzten Kosten die tatsächlichen nie überschreiten, ist der gefundene Weg der günstigste. Die Qualität der Schätzung hat unmittelbaren Einfluß auf die 'Zielgerichtetheit' und damit auf die Laufzeit der Suche.

A* untersucht immer den 'besten' Knoten zuerst. Der 'beste' Knoten ist der mit den geringsten Gesamtkosten. Zu jedem Knoten werden neben den Kosten noch die eigene Position und ein Verweis auf den vorherigen Knoten gespeichert.

Für die zielgerichtete Suche und zur Vermeidung doppelter Begehungen werden zwei Listen geführt, die Open List und die Closed List. Außerdem werden die Knoten unterschieden nach den Kategorien unbekannt (in keiner Liste), besucht (in Open List) und abschließend untersucht (in Closed List).

Wie geht A* vor?

Motor von A* ist die nach Gesamtkosten sortierte Open List. In ihr sind die zu untersuchenden Knoten eingetragen. Am Anfang ist das nur der Startknoten. Aus der Open List wird der Knoten mit den niederigsten Gesamtkosten entnommen und in die Closed List verschoben.

Für diesen Knoten werden die möglichen Folgeknoten ermittelt und ggf. in die Open List eingetragen. Potentielle Folgeknoten sind in diesem Beispiel die 8 direkten Nachbarknoten des aktuellen Knotes. Ein gültiger Folgeknoten darf nicht der Vorgängernoten des aktuellen Knotens sein, darf nicht bereits in der Closed List sein, muß eine erlaubte Position haben und darf betreten werden.

Für den Folgeknoten werden die Kostenbestandteile, seine Position und die seines Vorgängers ermittelt. Falls der Folgeknoten nicht in der Open List ist, wird er eingefügt. Sollte er bereits vorhanden sein, werden die Gesamtkosten verglichen. Sind die Gesamtkosten des Folgeknotens kleiner als die des Vorhandenen, so wird der Vorhandene vollständig mit den Daten des Folgeknotens überschrieben. Andernfalls wird der Folgeknoten verworfen.

Wird auf diese Weise das Ziel erreicht, ist die Suche erfolgreich beendet. Da jeder Knoten seinen Vorgänger kennt, kann man sich rückwärts in der Closed List, von Vorgänger zu Vorgänger, bis zum Startknoten hangeln und so den Pfad ermitteln.

Sollte die Open List komplett leer sein, bevor das Ziel erreicht ist, so wird die Suche erfolglos abgebrochen. Das Ziel ist unerreichbar. Siehe Funktion 'SingleStep' in der Astar Klasse.

Das Programm

Das Beispielprogramm soll zeigen, wie die Wegsuche arbeitet. Zu dem Zweck wird eine Map mit Feldern unterschiedlicher Wegekosten (Kantengewichten) angezeigt. Jedes Feld ist nummeriert, so daß sich die Tabelleninhalte den jeweiligen Feldern zuordnen lassen.

Auf der Map wird mit dünnen roten Linien das aktuell getestete Wegstück markiert. In zwei Tabellen werden die aktuellen Inhalte der Closed - und Open List angezeigt.

Um die Schritte des Programms nachvollziehbar zu machen, wird per Mausklick in die Map, nur ein einzelner Suchschritt ausgeführt.

In den Editfeldern lassen sich unterschiedliche Start- und Endpositionen eingeben. Man kann so das Verhalten der Suche bei unterschiedlichen Aufgaben beobachten.

Die App XAML

Das Programm braucht zwei Label zur Bezeichnung der Textboxen, die Textboxen, ein Menu für den Start, eine Canvas als Zeichenfläche, zwei Listviews und ein Grid um all das zu arrangieren. Message handler für die Mauscklicks im Canvas und zur Prüfung der Textboxeingabe.

Quelltext ein-/ausblenden

Dia App Klasse

Der 'code behind' für das Hauptfenster enthält nur die Messagehandler für das Menü, die Textboxen und das Canvas. Außerdem hält es die map und Astar.

Quelltext ein-/ausblenden

Die Klasse AStar

AStar kennt die Map, Start, Ziel, die Open- und Closed List. Diese Information wird per Konstruktoraufruf übergeben.

SingleStep prüft die Abbruchbedingungen 'Ziel erreicht' und 'Ziel nicht erreichbar', verscheibt den jeweils besten Knoten von der Open in die Closed List und ruft die Expansion des Knotens auf.

Expand(Node) ermittelt die acht Indices der Nachbarfelder des Kotens, der expandiert werden soll. Für gültige Positionen und erlaubte Nachfolger wird InsertNextNode aufgerufen.

IsNextNodeAllowed prüft ob das Feld begehbar ist, ob NextNode des Herkunftsfeld des aktuellen Knotens ist und ob NextNode bereits in der Closed List ist.

InsertNextNode macht die eigentliche Arbeit. Falls der Knoten nicht in der Open List ist, wird ein Knoten erzeugt, mit den entsprechenden Daten gefüllt und in die Open List eingefügt. Andernfalls werden die Gesamtkosten des vorhandenen mit denen des neuen verglichen. Hat der Neue geringere Gesamtkosten, werden die Daten des vorhandenen vollständig mit den des Neuen überschrieben. Anderfalls wird der neue Knoten verworfen.

Quelltext ein-/ausblenden

Die Klasse Node

Ein Knoten enthält seine Position und die seines Vorgängers. In diesem Fall als Feldindex der Map. Zusätzlich muß er noch die bereits investierten Kosten bis zu seiner Position, die geschätzen Kosten bis zum Ziel und deren Summe, die Gesamtkosten bis zum Ziel speichern.

Quelltext ein-/ausblenden

Die Klasse Map

Die Map repräsentiert die Karte. Sie enthält eine eindimensionale Liste von Zellen sowie Funktionen um sich selbst zu zeichen. Die Zeichenfläche (Canvas) und der Pfad zur Map Datei werden dem Konstruktor übergeben.
Die Funktion GetFromToCost liefert das Kantengewicht für die Kante zwischen den Knoten. Abhängig von der Lage der Kante, diagonale Verbindung oder horizonzal bzw. vertikal liefert sie die Häfte der Summe der Querungskosten der beiden Zellen oder das 0.7 Fache (Näherung für √2).
DrawPathSegment zeichnet die Kante des jeweils letzten Knotens der Close List.
Die anderen Zeichenfunktionen zeichnen die Map.

Quelltext ein-/ausblenden

Die Klasse Cell

Die Klasse Zelle repräsentiert ein Feld der Karte. Abhängig vom Zelltyp erhält das Feld eine bestimmte Farbe, Kantenkosten und ein Flag für die 'Begehbarkeit'.

Quelltext ein-/ausblenden