Teil 1: A*Pathfinder

[damuddamc]

Willkomen zu meinem ersten Tutorial zum A* Pfadfindungsalgorithmus.

Da der A* der wohl der wichtigste Algorithmus ist um Wege für KI gesteuerte Figuren in einem Spiel zu berechnen,

auch in den meisten modernen, sollte jeder der einmal eine künstliche Intelligenz schaffen will wissen wie dieser funktioniert.

Im ersten Teil dieses Tutorials erkläre ich ersteinmal an einem Tiledbased Ansatz wie der A* Algorithmus funktioniert,

im zweiten Teil werde ich ihn dann in 3D für Unity umsetzen.

 

 

 

Zu Beginn werde ich erst einmal das grundlegende Prinzip hinter dem A* Algorithmus versuchen zu erklären.

 

Im A* Algorithmus werden zwei verschiedene Listen/ Arrays gespeichert, die OpenList und die ClosedList.

 

OpenList: In die OpenList kommen alle Wegpunkte die schon einmal von einem anderen Wegpunkt aus berechnet wurden.

 

ClosedList: In die ClosedList kommen alle Wegpunkte von denen aus ihre Nachbarn schon berechnet wurden.

 

Innerhalb jedes Wegpunktes wiederum sind deren erreichbare Nachbarwegpunkte gespeichert die zu Beginn des Spiels berechnet wurden. Also sieht unsere Klasse Waypoint ungefähr so aus:

Position:Vector3
Neighbours:Waypoint[]

 

 

Um den Pfad zum Ziel zu finden müssen allerdings zu jedem Wegpunkt noch einige Werte berechnet und abgespeichert werden, daher behelfe ich mir mit einer eigenen Klasse die ich einfach mal PathNode nenne die ich für jeden berechneten Wegpunkte instanziere. In C# braucht man dafür keine extra Klasse man kann sich auch eine Struct anlegen, dies ist in Javascript allerdings nicht möglich.

Innerhalb dieser Klasse PathNode werden standardmäßig der Wegpunkt gespeichert der zu diesem gehört, ein G-Wert der angibt wie weit der Wegpunkt vom Start entfernt ist, bzw. welche tatsächliche Strecke bisher zurückgelegt wurde um zu diesem Wegpunkt zu gelangen.

Dazu kommt noch der H-Wert (heuristischer Wert) der angibt wie weit der Wegpunkt vom Ziel entfernt ist, dabei wird immer der direkte Weg genommen ohne Rücksicht auf Hindernisse. Aus dem G- und dem H-Wert errechnet sich durch Addition der F-Wert welcher somit nun einen Anhaltspunkt gibt ob der Wegpunkt zum Ziel hin führt oder nicht. Zu guter letzt wird noch der ParentNode in jedem PathNode gespeichert der angibt von welchem Wegpunkt aus dieser berechnet wurde. Dies ist wichtig da sich beim A* Algorithmus der Weg zum Ziel nicht direkt beim errechnen ergibt sonder der Pfad erst korrekt zurückgegeben werden kann wenn das Ziel gefunden ist, dann nämlich kann vom Ziel aus rückwärts über die ParentNodes der korrekte Weg ermittelt werden.

 

Also brauchen wir für den PathNode:

gValue:float
hValue:float
fValue:float
wayPoint:WayPoint
parentNode:PathNode

 

 

Dazu aber gleich noch mehr.

 

Nehmen wir an dies ist unsere Ausgangsposition, Jede Kachel ist ein Wegpunkt, der grüne Punkt ist der Start und der blaue das Ziel. Rote Felder sind Hindernisse.

Nun muss der kürzeste Weg zum Ziel gefunden werden.

Wir kennen den Start- Wegpunkt und den Ziel- Wegpunkt.

Zu unserem Startfeld legen wir direkt einen neuen PathNode an der nun direkt in die OpenList gelegt wird. In dieser befindet sich also nun genau ein Objekt, unser Startfeld. F, G und H sind in diesem 0 und der ParentNode = null.

 

 

Nun legen wir noch eine Variable an die ich targetField nenne welches ebenfalls vom Typ PathNode ist, dieses ist aber zu Beginn noch null.

Zudem noch eine Variable currentPathNode vom Typ PathNode in der das Feld gespeichert ist von dem aus im Moment berechnet wird.

 

Erst jetzt geht’s richtig los, innerhalb einer while Schleife die sich immer solange wiederholt solange das targetField nicht gefunden wurde werden alle nötigen Berechnungen durchgeführt.

Begonnen wird damit das aus der OpenList der PathNode genommen wird der den niedrigsten F-Wert besitzt, da zu Beginn nur das Startfeld in dieser ist, ist es klar das dieses genommen wird. Dieser PathNode wird somit aus der OpenList entfernt und in die ClosedList geworfen. Da nun von diesem Feld aus berechnet wird setzten wir den currentPathNode auf dieses.

 

Nun müssen alle Nachbarwegpunkte dieses Wegpunktes kontrolliert werden und zu jedem ein PathNode angelegt werden, sofern dies nicht schon geschah. Im ersten Durchlauf ist klar das es zu keinem der Nachbarwegpunkte schon ein PathNode gibt in den nächsten Durchläufen aber nichtmehr.

 

Das nächste Bild zeigt nun alle Nachbarwegpunkte durch eine Linie, in der oberen linken Ecke steht der G-Wert, unten links der H-Wert und oben Recht der F-Wert. Das nächste Feld mit dem niedrigsten F-Wert ist rot markiert, von diesem aus wird als nächstes berechnet.

Der G-Wert ergibt sich also durch die Strecke vom Start zu diesem, ich habe jetzt für eine horizontale oder vertikale Strecke von einem Feld zum nächsten 10 Punkte genommen und für eine Diagonale 14. Dies trifft ungefähr auf das Verhältnis zu welche eine Diagonale länger ist als eine vertikale oder horizontale Bewegung. Im 3D Raum kann man auf diese Zahlen verzichten und die direkte Entfernung verwenden, in einem Tilebased Ansatz aber nicht und um das Prinzip des A* zu erklären greife ich auf diesen zurück. Der H-Wert wird im Tilebased Ansatz lediglich durch abzählen der horizontalen und vertikalen Felder zum Ziel errechnet und mit 10 multipliziert, keine diagonalen. Zum Beispiel vom Feld oben rechts sind es 3 Felder in horizontaler und 2 Felder in vertikaler Entfernung das macht 5 und mit 10 multipliziert 50.

Der F-Wert ergibt sich dann aus der Addition von G und H.

 

 

Jedem nun errechnete Nachbar bzw. dessen PathNode wird der currentPathNode von dem aus berechnet wurde als ParentPathNode zugewiesen und der nun vollständig berechnete PathNode in die OpenList gelegt. Der Parent eines jeden Feldes wird durch einen Pfeil gekennzeichnet der in dessen Richtung zeigt.

 

Wir stellen also fest dass das Ziel noch nicht erreicht wurde, das targetField ist also immer noch null. Also geht es erneut in die while Schleife.

Wieder wird aus der OpenList der PathNode genommen der den niedrigsten F-Wert besitzt, dies ist wie schon erwähnt das rot markierte Feld. Dieses wird nun aus der OpenList entfernt, in die ClosedList geworfen und dem currentPathNode zugeordnet. Jetzt befinden sich 7 Felder in der OpenList und 2 in der ClosedList.

 

 

 

Nächstes Bild:

In Pink sind wieder die Linien zu den Nachbarn eingezeichnet und am G-Wert in der linken oberen Ecke sieht man nun wie dieser tatsächlich berechnet wird. Dieser ergibt sich also aus dem G-Wert des currentPathNode und dem Weg von diesem zum Wegpunkt.

Wie man feststellt sind einige der Nachbarfelder bereits berechnet worden, diese liegen also entweder in der OpenList oder in der ClosedList. 2 Dieser bereits berechneten Felder habe ich markiert.

Das blau markierte Feld ist das Startfeld, es wurde im ersten Durchlauf bereits in die ClosedList gelegt. Felder die in der ClosedList liegen bleiben unangetastet im Gegensatz zu Feldern die in der OpenList liegen. Das grün markierte ist ein solches, da es auch ein Nachbar des currentPathNode ist muss geschaut werden ob der G-Wert kleiner werden würde wenn man die Berechnung von diesem erneut ausführen würde. Im Moment ist der G-Wert 10, würde man nun vom currentPathNode ausgehen würde sich ein G-Wert von 14 (der G-Wert des currentPathNode) + 10 (für die vertikale Bewegung) also 24 ergeben, der G-Wert wird also nicht kleiner denn 10 ist ja niedriger als 24. Dieses Feld bleibt also ebenfalls unangetastet. Wenn der G-Wert allerdings durch eine Neuberechnung kleiner geworden wäre, müsste dieser nun umgeschrieben werden und der ParentPathNode dieses Feldes auf den currentPathNode gesetzt werden.

 

 

 

 

 

Das Ziel wurde wieder nicht gefunden und erneut wird im nächsten durchlauf das rot markierte Feld als currentPathNode abgelegt, aus der OpenList entfernt und in die ClosedList geworfen.

 

 

Nächstes Bild:

 

Die pinken Linien zeigen erneut die Nachbarn, bis auf das Feld oben links wurden alle bereits berechnet.

Es würde sich auch durch Neuberechnung kein Wert verringern, daher gehen wir direkt weiter zum nächsten PathNode mit dem niedrigsten F-Wert. Das wäre mit 70 das Feld rechts neben dem Start-Feld. Es gibt zwar noch ein weiteres Feld mit 70, um dieses Tutorial aber nicht unnötig in die Länge zu ziehen gehen wir von dem besten Fall aus, das unser Algorithmus das Feld rechts neben dem Start-Feld wählen würde.

 

 

 

Ich denke das Grundprinzip wie die Berechnung funktioniert ist nun klar, es wird immer das Feld mit dem niedrigsten F-Wert aus der OpenList genommen, dies muss also auch nicht zwingend ein Nachbarwegfeld des currentPathNode sein. Dieses Feld das aus der OpenList genommen wird, wird dann zum currentPathNode, alle Nachbarn werden berechnet. Ist ein Nachbar bereits in der ClosedList bleibt dieser unangetastet, ist er in der OpenList wird geschaut ob der G-Wert kleiner werden würde wenn man vom currentPathNode aus geht. Ist der Nachbar noch nicht in einer der beiden Listen wird ein neuer PathNode erzeugt und in die OpenList gelegt. Dies wird solange gemacht bis Das Ziel gefunden wird.

 

Nächstes Bild:

Rot markiert ist wieder das aktuelle Feld von dem aus berechnet wird.

Das grün markierte Feld wurde zuvor bereits berechnet, der G-Wert hat sich aber von dem aktuellen Feld aus geändert, von 28 auf 20. Somit wurde auch der Pfeil zu dessen Parent geändert.

Genau dieses grün umrandete Feld ist das mit dem niedrigsten F-Wert, wleches wir als nächstes berechnen.

 

 

Die folgenden Bilder zeigen die weiteren Berechnungen bis zum Ziel:

 

 

 

 

 

 

 

Das Ziel wurde also gefunden und weitere Felder brauchen wir nicht mehr berechnen.

Der Pfad vom Start zum Ziel ergibt sich jetzt durch das folgen vom Zielfeld zum ParentPathNode und von diesem wiederum zu dessen Parent und immer so weiter bis man am Start angekommen ist. Dieser Pfad muss dann nur noch umgedreht werden.

 

Auf dem nächsten Bild sind alle Werte ausgeblendet und nur noch die Pfeile zu den Parents sowie die Felder die in der Closed List liegen zu sehen.

 

 

 

Und hier der Pfad vom Ziel zum Start entlang der Parents:

 

 

Ich hoffe es wurde etwas klar wie der A* funktioniert, um es aber noch etwas zu veranschaulichen hier das ganze einmal in einem pseudo-Code:

 

function AStarPathfinder(start:WayPoint,target:Waypoint):Array
{

startWaypoint:Waypoint = start;
targetWaypoint:Waypoint = target;

OpenList:Array;
ClosedList:Array;
currentPathNode:PathNode;


startField:PathNode = new PathNode();
startField.wayPoint = startWaypoint;

var path:Array;

targetField:PathNode = null;

while(targetField == null)
{

currentPathNode = PathNode mit niedrigstem F-Wert aus OpenList;
OpenList.Remove(currentPathNode);
ClosedList.Add(currentPathNode);

for(jeden nachbarwegpunkt von currentPathNode)
{

	if(nachbarwegpunkt nicht in ClosedList)
	{

		if(nachbarwegpunkt nicht in OpenList)
		{


			var newPathNode:PathNode = new PathNode();
			newPathNode.wayPoint = nachbarwegpunkt;
			newPathNode.ParentPathNode = currentPathNode;
			newPathNode.gValue = currentPathNode.gValue + (Distanz von currentPathNode zu newPathNode);
			newPathNode.hValue = Distanz von newPathNode zu targetWaypoint;

			if(nachbarwegpunkt == targetWaypoint)
			{

				targetField = newPathNode;
									pathArray = Berechne Pfad;
				break;
			}
		}
		else if(nachbarwegpunkt ist bereits in OpenList)
		{
			var newGValue:int = currentPathNode.gValue + (Distanz von currentPathNode zu nachbarwegpunkt);
			if(newGValue < nachbarwegpunkt.gValue)
			{

				nachbarwegpunkt.gValue = newGValue;
				nachbarwegpunkt.fValue = newGValue + nachbarwegpunkt.hValue;
				nachbarwegpunkt.ParentPathNode = currentPathNode;
			}

		}


	}


}

}


return path;


}

 

 

 

Ich hoffe ich konnte es einwenig verständlich rüberbringen wie der A* Pfadfindungsalgorithmus funktioniert.

In einem nächsten Tutorial werde ich das ganze dann in Unity umsetzen.

 

JavaScript

-->Weiter zu Teil 2 JS<--

 

C#

-->Weiter zu Teil 2 C#<--

 

mfg Stephan

[tomkro]

hast echt tolle arbeit geileistet, das versteh sogar ich

 

ich zieh mir gleich dia andern tuts rein

[Pantheon777]

Auch wenn es das tut nun schon ne weile gibt kann ICH erst jetzt dazu sagen TOP

[Silveryard]

Schade, die Bilder sind weg...

[Hrungdak]

Schade, die Bilder sind weg...

Tja, Freehoster halt. 3 Monate nicht angeschaut -> löschen.

[Silveryard]

Wirklich schade, denn die Bilder fand ich immer sehr aussagekräftig. Vlt könnte man sich mal um eine neue Version für dieses Tutorial bemühen

[damuddamc]

Habe die Bilder, zumindest in diesem Teil neu eingestellt bzw. neue gestaltet da ich die alten nicht mehr finden konnte. Diesmal nicht über einen Freehoster

Weil die Bilder nicht mehr den alten entsprechen musste ich auch die Texte anpassen, sollte jemand Fehler finden dann bitte mir sagen.

[Hrungdak]

Top Service! Schön, dass das gute Tutorial erhalten bleibt.