Jump to content
Unity Insider Forum

Teil 3: A* Pathfinder


Recommended Posts

-------------------------------------------------------------------------

Du programmierts in C#? --> Teil 3:A* Pathfinding Tutorial

-------------------------------------------------------------------------

 

Willkommen zu Teil 3 des A* Pathfinding- Tutorials in Unity.

In diesem Teil werde ich den A* Algorithmus in Unity umsetzten.

Dieses Tutorial baut direkt auf Teil 2 auf und eine Testszene sollte bereits bestehen.

Auch das Grundverständnis für den A* sollte da sein, wenn nicht vielleicht Teil 1 noch mal lesen.

 

Anfangen tu ich indem ich ein neues Javascript Dokument anlege, ich nenne es Pathfinder.

Das aller erste das ich in dieser Datei machen werde ist die Klasse „PathNode“ zu deklarieren die uns zu jedem Wegpunkt die erforderlichen Werte speichert. Dazu gehören der G-Wert, H-Wert, F-Wert, der dazu gehörende Wegpunkt und der parentPathNode der den PathNode speichert von dem aus dieser berechnet wurde.

 

So sollte die Klasse aussehen:

 

class PathNode
{
public var fValue:float = 0;
public var gValue:float = 0;
public var hValue:float = 0;	
public var parentPathNode:PathNode;
public var waypoint:Waypoint;


public function PathNode(wayPoint:Waypoint)
{
	waypoint = wayPoint;
}


}

Der Konstruktor übergibt einfach einen Wegpunkt an den zu instanzierenden PathNode.

 

Damit hätten wir Schritt 1 schon erledigt, jetzt machen wir uns an die Funktionen die uns den Pfad errechnen soll.

 

Wir bleiben im gleichen Dokument schreiben aber nicht in die Klasse PathNode sondern unten drunter.

Die static Funktion die wir später von überall aus aufrufen können um einen Pfad zurück zu bekommen nenne ich „GetPath“, sie bekommt 2 Parameter vom Typ Waypoint, den startWaypoint und den targetWaypoint. Als Rückgabe bekommen wir von der Funktion ein Array.

 

 

In der Funktion deklarieren wir zunächst einmal alle wichtigen Variablen.

Dazu gehören die openList und die closedList vom Typ Array. In die OpenList kommen alle schon berechneten Wegpunkte bzw. die PathNodes die diese repräsentieren. In die closedList kommen die Wegpunkten von denen aus die Nachbarwegpunkte schon berechnet wurden.

 

Die Variable currentPathNode beinhaltet den PathNode von dem aus die Nachbarn momentan berechnet werden.

Das startField, ebenfalls vom Typ PathNode wird direkt mit dem startWaypoint instanziert, das targetField, nach dem ja gesucht wird bleibt zu Beginn noch null.

 

Als letzte Variable haben wir noch das pathArray in dem der errechnete Pfad zurückgegeben wird.

 

Zu Beginn werfen wir das startField auch gleich in die openList damit diese nicht leer ist, denn wenn die openList zu irgend einem Zeitpunkt der Berechnung einmal leer sein sollte heißt dass, das es keinen Weg zum Ziel gibt, In diesem Fall muss die Berechnung abgebrochen werden, aber dazu später.

 

Damit ist der erste Schritt eledigt, die Funktion sieht momentan so aus:

static public function GetPath(startWaypoint:Waypoint,targetWaypoint:Waypoint):Array
{


var openList:Array = new Array();
var closedList:Array = new Array();
var currentPathNode:PathNode;
var startField:PathNode = new PathNode(startWaypoint);
var targetField:PathNode = null;
var pathArray:Array;

openList.Add(startField);



//Berechnungen


return pathArray;

}

 

 

Jetzt kommen wir zum Kern der Funktion, wir benötigen eine While- Schleife die solange ausgeführt wird bis das targetField gefunden ist oder die openList leer ist.

Zuvor sollte aber noch getestet werden ob nicht zufällig der startWaypoint gleich der targetWaypoint ist damit es auch da nicht zu einem Fehler kommen kann.

 

Also dort wo oben //Berechnungen steht kommt jetzt folgender Code hinein.

if(startWaypoint != targetWaypoint)
{
while(targetField == null && openList.length > 0 )
{

	//Berechnungen

}


}

Würden wir die Funktion jetzt aufrufen würden wir in eine Endlosschleife kommen, also lassen wir das mal lieber.

 

Was als nächstes kommen muss ist uns aus der openList das Element mit dem niedrigsten F-Wert heraus zu holen, als currentPathNode zu setzen und in die closedList zu stecken. Im ersten Durchgang ist natürlich nur ein Objekt in der openList das ändert sich aber ganz schnell.

Um das zu machen brauchen wir aber ersteinmal eine Funktion die uns dieses Element aus der openList zurück gibt.

 

Dafür schreiben wir unter die Funktion GetPath eine neue static Funktion, diese hab ich „ReturnPathNodeWithLowestFValue“ genannt, vielleicht fällt euch ja ein besserer Name ein smile.gif . Die Funktion empfängt einen Parameter, nämlich ein Array, die openList. Zurück gibt uns die Funktion nur die Indexposition des PathNodes mit dem niedrigsten F-Wert in dem übergebenen Array.

 

So sieht die Funktion aus.

static public function ReturnPathNodeWithLowestFValue(openL:Array):int
{
var pathNode:PathNode = null;
var index= -1;

if(openL.length >0)
{

	for(var i:int = 0;i<openL.length;i++)
	{

		if(index == -1)
		{

			pathNode = openL[i];
			index = i;
		}
		else if(pathNode.fValue > openL[i].fValue)
		{
			pathNode = openL[i];
			index = i;
		}

	}

}

return index;
}

 

Als erstes deklarieren wir in dieser Funktion die Variable pathNode die uns das Element zwischenspeichert das momentan den niedrigsten F-Wert hat. Die Variable index speichert dessen Indexposition im Array, zu Beginn steht diese auf -1 um anzuzeigen dass noch kein Element als pathNode zwischengespeichert wurde.

 

Anschließend kommt eine If-Anweisung die einfach noch mal kontrolliert ob die openList wirklich nicht leer ist erst dann geht’s mit einer For-Schleife weiter in der wir das gesamte Array durchlaufen. In dieser stehen 2 If- Anweisung, die erste schaut ob der Index momentan auf -1 steht, d.h. das dies momentan der erste Durchlauf der For-Schleife ist, damit wird das erste Element des Arrays auch direkt als pathNode abgespeichert weil es eben bisher den niedrigsten F-Wert hat.

In der zweiten If-Anweisung wird geschaut ob der fValue des Objektes an Stelle i der openList kleiner ist als der fValue des zwischengespeicherten Objektes pathNode dessen fValue bis dahin am kleinsten war. Ist der fValue dieses Objekts nun kleiner wird dieses als pathNode und dessen Index abgespeichert.

 

Wenn Die For-Schleife durch ist haben wir die Indexposition des PathNodes in der openList mit dem niedrigsten fValue und geben diesen Index zurück.

 

 

Jetzt können wir wieder in die Funktion GetPath gehen und endlich den currentPathNode ein Objekt zuweisen.

 

Dazu fügen wir direkt in die While-Schleife folgende Zeilen ein.

var index:int = ReturnPathNodeWithLowestFValue(openList);
currentPathNode = openList[index];
openList.RemoveAt(index);
closedList.Add(currentPathNode);

Jetzt haben wir also den PathNode mit dem niedrigsten F-Wert gefunden, als currentPathNode abgespeichert, aus der openList entfernt und in die closedList geworfen.

Nun können wir uns daran machen alle Nachbarwegpunkte dieses PathNodes bzw. dessen Waypoints zu berechnen. Was wir dafür zunächst machen ist uns dessen Nachbarwegpunkte ersteinmal in einem Array zwischen zu speichern um schneller an diese ran zu kommen.

var neighbourWaypoints:Array = currentPathNode.waypoint.waypointsInRange;

Anschließend machen wir folgendes:

Wir schreiben uns eine For-Schleife in der wir alle Nachbarwegpunkte durchlaufen, für jeden Nachbarwegpunkt müssen wir aber nun zunächst kontrollieren ob dieser nicht schon als PathNode in der openList oder der closedList abgelegt wurde.

Zunächst überprüfen wir auf die closedList, denn sollte dieser Wegpunkt dort schon drin liegen heißt dass für uns das wir für diesen keinesfalls mehr irgendwelche Berechnungen durchführen müssen.

 

Um jetzt aber heraus zu bekomme ob der Wegpunkt schon in der closedList liegt brauchen wir wieder eine Funktion.

Diese schreiben wir wieder unter die Funktion GetPath, ich habe dies „IsInCL“ genannt. Diese empfängt 2 Parameter, einmal die closedList und den Wegpunkt nach dem gesucht werden soll. Zurück gibt uns die Funktion einen booleschen Wert, also ob er drin ist oder nicht.

 

Die Funktion sieht so aus:

static public function IsInCL(closedL:Array,wayPoint:Waypoint):boolean
{
var isIn:boolean = false;
for(var i:int = 0;i<closedL.length;i++)
{

	if(closedL[i].waypoint == wayPoint)
	{

		isIn = true;
		break;
	}

}
return isIn;

}

Ich denke die Funktion ist selbsterklärend, wir haben einen Boolean der zu Beginn auf false steht und uns angibt ob der Wegpunkt schon drin ist. Jedes Element der closedList wird dann durchlaufen. Wurde der Wegpunkt gefunden wird der Boolean auf true gesetzt und die For-Schleife abgebrochen. Sollte der Wegpunkt nicht gefunden werden wird false zurückgegeben.

 

Da wir auch die openList durchsuchen müssen falls der Wegpunkt nicht schon in der closedList ist brauchen wir dafür auch noch eine Funktion, diese sieht im Grunde genauso aus wie IsInCl allerdings liefert sie statt eine Boolean die Indexposition in der openList zurück wenn der Wegpunkt in der openList liegen sollte. Liegt der Wegpunkt nicht in der openList wird -1 zurückgegeben.

 

Diese Funktion habe ich „IsInOL“ genannt und sie sieht so aus:

static public function IsInOL(openL:Array,wayPoint:Waypoint):int
{
var index:int = -1;
for(var i:int = 0;i<openL.length;i++)
{

	if(openL[i].waypoint == wayPoint)
	{

		index = i;
		break;
	}

}
return index;
}

 

Damit hätten wir schon fast alle Funktionen die wir brauchen, nur ein fehlt uns noch aber die kommt später.

Jetzt können wir uns wieder an die Funktion GetPath machen und die Nachbarwegpunkte des currentPathNode darauf kontrollieren ob sie schon in einer der beiden Listen liegen.

 

Wir fangen also damit an zu überprüfen ob der Wegpunkt schon in der closedList ist bzw. ob er nicht drin ist, dafür schreiben wir eine If-Anweisung:

if(!IsInCL(closedList,neighbourWaypoints[i]))

 

Ist der Wegpunkt nun nicht in der closedList, gibt uns IsInCL also false zurück muss noch geschaut werden ob er in der openList ist. Dafür deklarieren wir zunächst in dieser If-Anweisung eine Variable „indexInOL“ vom Typ Integer und übergeben ihr sofort den Rückgabe Wert des Funktionsaufrufes IsInOL:

var indexInOL:int = IsInOL(openList,neighbourWaypoints[i];

Nun wissen wir wenn der Rückgabewert größer oder gleich 0 ist und nicht -1 dann liegt der Wegpunkt in der openList. Ist dies der Fall muss der G-Wert dieses Wegpunktes bzw. dessen PathNodes eventuell neu berechnet werden.

Dafür schreiben wir jetzt unter die Variable indexInOL eine weiter If-Anweisung in der genau darauf kontrolliert wird ob der Index größer gleich 0 ist.

if(indexInOL >= 0)

Für den Fall das der Rückgabe Wert -1 ist schreiben wir zu dieser If-Anweisung noch ein else in der wenn nötig ein neuer PathNode zu diesem Wegpunkt angelegt wird.

So sieht bis dahin unsere gesamte Funktion GetPath aus:

static public function GetPath(startWaypoint:Waypoint,targetWaypoint:Waypoint):Array
{


var openList:Array = new Array();
var closedList:Array = new Array();
var currentPathNode:PathNode;
var startField:PathNode = new PathNode(startWaypoint);
var targetField:PathNode = null;
var pathArray:Array;
currentPathNode = startField;
openList.Add(startField);


if(startWaypoint != targetWaypoint)
{
	while(targetField == null && openList.length > 0 )
	{
		var index:int = ReturnPathNodeWithLowestFValue(openList);
		currentPathNode = openList[index];
		openList.RemoveAt(index);
		closedList.Add(currentPathNode);

		var neighbourWaypoints:Array = currentPathNode.waypoint.waypointsInRange;
		for(var i:int = 0;i<neighbourWaypoints.length;i++)
		{

			if(!IsInCL(closedList,neighbourWaypoints[i]))//Wenn der Wegpunkt nicht in der closedList ist
			{
				var indexInOL:int = IsInOL(openList,neighbourWaypoints[i]);
				if(indexInOL >= 0)//Wenn der Wegpunkt in der openList ist
				{
						//Eventuell neu berechnen

				}
				else//Wenn der Wegpunkt nicht in der openList ist
				{

					//Neuen PathNode erzeugen

				}

			}


		}
	}


}



return pathArray;

}

 

Das Grundgerüst des A* steht schon, jetzt müssen wir nurnoch die PathNodes erzeugen.

Wir machen weiter mit der else – Verzweigung in der die neuen PathNodes zu noch nicht berechneten Wegpunkten instanziert werden, erst danach kümmern wir uns um die If-Anweisung oben drüber.

 

Was wir als erstes machen müssen ist den G-, H- und F-Wert zu berechnen, dazu legen wir uns 3 neue Variablen vom Typ float an. GValue, HValue und FValue.

Diese berechnen wir auch gleich. Der G-Wert ergibt sich wie wir wissen aus dem G-Wert des currentPathNodes von dem dieser Wegpunkt berechnet wird plus die Entfernung von currentPathNode zum Wegpunkt.

var GValue:float =  currentPathNode.gValue +  Vector3.Distance(currentPathNode.waypoint.transform.position,neighbourWaypoints[i].transform.position);

Im dreidimensionalen brauchen wir natürlich keine Schätzwerte verwenden wie ich es in Teil 1 des Tutorials getan habe, dies ist ja nur nötig wenn man die Karte in ein Raster unterteilt hat und jedes Feld in einem Mehrdimensionalen Array abgelegt hat.

Wir können also die tatsächlich Entfernung verwenden.

 

Als nächstes der H-Wert.

var HValue:float = Vector3.Distance(neighbourWaypoints[i].transform.position,targetWaypoint.transform.position);

Dieser ermittelt sich aus der Entfernung vom Wegpunkt zum Ziel.

Zu guter letzt noch der F-Wert der sich aus der Addition von G und H ergibt.

var FValue:float = GValue + HValue;

Jetzt müssen wir nur noch den neuen PathNode erzeugen und ihm die Werte als auch seinen parentPathNode, also unseren currentPathNode von dem dieser berechnet wurde zuweisen.

Anschließend werfen wir diesen neuen PathNode auch gleich in die openList.

 

var newPathNode:PathNode = new PathNode(neighbourWaypoints[i]);
newPathNode.gValue = GValue;
newPathNode.hValue = HValue;
newPathNode.fValue = FValue;
newPathNode.parentPathNode = currentPathNode;		
openList.Add(newPathNode);

Jetzt fehlt natürlich noch etwas ganz wesentliches, und zwar die überprüfung ob der Wegpunkt nicht auch das gesuchte Ziel ist. Dazu schreiben wir einfach eine weitere If-Anweisung unter das gerade geschriebene in der wir dies abfragen. Sollte es wirklich der gesuchte targetWaypoint sein wird der eben erzeugte PathNode an das targetField übergeben und die For-Schleife mit einem break abgebrochen.

if(newPathNode.waypoint == targetWaypoint)
{

targetField = newPathNode;
//Pfad berechnen
break;
}

An der Stelle an der momentan „//Pfad berechnen“ steht rufen wir später noch eine Funktion auf die uns den Pfad in unser pathArray schreibt.

So sieht es momentan aus:

var indexInOL:int = IsInOL(openList,neighbourWaypoints[i]);
if(indexInOL >= 0)//Wenn der Wegpunkt in der openList ist
{
//Eventuell neu berechnen

}
else//Wenn der Wegpunkt nicht in der openList ist
{

var GValue:float =  currentPathNode.gValue +  Vector3.Distance(currentPathNode.waypoint.transform.position,neighbourWaypoints[i].transform.position);
var HValue:float = Vector3.Distance(neighbourWaypoints[i].transform.position,targetWaypoint.transform.position);
var FValue:float = GValue + HValue;


var newPathNode:PathNode = new PathNode(neighbourWaypoints[i]);
newPathNode.gValue = GValue;
newPathNode.hValue = HValue;
newPathNode.fValue = FValue;
newPathNode.parentPathNode = currentPathNode;

openList.Add(newPathNode);

if(newPathNode.waypoint == targetWaypoint)
{

	targetField = newPathNode;
	break;
}

}

 

Jetzt kümmern wir uns um den Fall das der Wegpunkt schon berechnet in der openList liegt.

Dafür müssen wir in der If-Anweisung if(indexInOL>=0) den G-Wert des Wegpunktes neu berechnen und schauen ob er eventuell kleiner ist als der bisherige.

Dafür legen wir uns wieder eine neue Variable vom Typ float an, ich nenne sie newGValue.

Der neue G-Wert ergibt sich aus der Addition des G-Wertes des currentPathNode + die Entfernung von diesem zum Wegpunkt.

Wenn dieser nun berechnet ist müssen wir in einer weiteren If-Anweisung überprüfen ob der G-Wert kleiner ist als der alte. Ist dies der Fall wird der parentPathNode auf den currentPathNode geändert, der neue G-Wert übergeben und der F-Wert neu berechnet.

Das ganze sieht so aus:

var newGValue:float = currentPathNode.gValue + Vector3.Distance(currentPathNode.waypoint.transform.position,openList[indexInOL].waypoint.transform.position);
if(newGValue < openList[indexInOL].gValue)
{

openList[indexInOL].parentPathNode = currentPathNode;
openList[indexInOL].gValue = newGValue;
openList[indexInOL].fValue = (newGValue + openList[indexInOL].hValue);
}

Damit sind wir so gut wie fertig. Würden wir die Funktion jetzt aufrufen sollten wir zwar keinen Fehler bekommen, allerdings bekommen wir ein leeres Array zurück, der Pfad wurde also nicht wirklich berechnet.

 

Wie wir wissen können wir den Pfad ermitteln indem wir vom gefundenen targetField aus die parentPathNodes rückwärts gehen und alle Wegpunkte abspeichern bis wir wieder am Start angelangt sind. Dann müssen den Pfad gerade noch rumdrehen damit er auch in der richtigen Reihenfolge vorliegt.

 

Dafür brauchen wir wieder eine neue static Funktion. Ich habe sie „ReturnPath“ genannt. Diese erhält 2 Parameter. Das startField und das targetField vom Typ PathNode. Als Rückgabewert erhalten wir das Array mit unserem korrekten Pfad.

 

In dieser legen wir uns als erstes wieder ein neues Array an, ich habe es wieder pathArray genannt weil es ja schließlich auch genau dieses ist.

Dazu noch eine Variable vom Typ PathNode die gleich zu Beginn unser targetField entgegen nimmt. In dieser Variable die ich auch currentPathNode genannt habe wird immer der PathNode gespeichert dessen Wegpunkt gleich anschließend in das PathArray geworfen wird.

 

Anschließend erzeugen wir wieder eine while-Schleife die solange durchläuft bis der currentPathNode das startField ist. In dieser While-Schleife wird der Wegpunkt des currentPathNode in das pathArray gelegt und der currentPathNode auf dessen parentPathNode geändert.

 

Sollte dieser jetzt das startField sein, wird die While-Schleife nicht mehr ausgeführt und somit der Wegpunkt des startField auch nicht in das pathArray gespeichert. Dies wäre ja auch nicht sinnvoll da auf diesem ja die Figur steht, also brauch sie dort auch nicht mehr hinlaufen.

 

Zu guter letzt drehen wir das Array noch über den Befehl Reverse() um und geben es zurück.

So sieht die Funktion vollständig aus.

static public function returnPath(startField:PathNode,targetField:PathNode):Array
{
var pathArray:Array = new Array();
var currentPathNode:PathNode = targetField;
while(currentPathNode!=startField)
{
	pathArray.Add(currentPathNode.waypoint);
	currentPathNode = currentPathNode.parentPathNode;
}

pathArray.Reverse();

return pathArray;
}

 

Was wir jetzt noch machen müssen ist noch einmal in die Else-Verzweigung unserer Funktion GetPath zu gehen in der wir die neuen PathNodes instanzieren und überprüfen ob das Ziel gefunden wurde.

 

Dort rufen wir nur noch, wenn das Ziel gefunden wurde die Funktion ReturnPath auf und übergeben den Rückgabewert an unser pathArray.

if(newPathNode.waypoint == targetWaypoint)
{	
			targetField = newPathNode;
pathArray = ReturnPath(startField,targetField);
break;
}

 

Damit ist der A* Algorithmus fertig programmiert und kann angewendet werden.

Aufgerufen werden kann er dann von überall durch Pathfinder.GetPath(startWaypoint,targetWaypoint).

 

Außerdem wissen wir dass wenn das pathArray das zurück geliefert wird null ist oder die Länge gleich 0 das es keinen Weg zum Ziel gibt.

 

Hier noch mal die gesamte Datei auf einen Blick:

class PathNode
{
public var fValue:float = 0;
public var gValue:float = 0;
public var hValue:float = 0;	
public var parentPathNode:PathNode;
public var waypoint:Waypoint;


public function PathNode(wayPoint:Waypoint)
{
	waypoint = wayPoint;
}

}


////////////////////////////////////////////////////////////////////////////

static public function GetPath(startWaypoint:Waypoint,targetWaypoint:Waypoint):Array
{


var openList:Array = new Array();
var closedList:Array = new Array();
var currentPathNode:PathNode;
var startField:PathNode = new PathNode(startWaypoint);
var targetField:PathNode = null;
var pathArray:Array;
currentPathNode = startField;
openList.Add(startField);


if(startWaypoint != targetWaypoint)
{
	while(targetField == null && openList.length > 0 )
	{
		var index:int = ReturnPathNodeWithLowestFValue(openList);
		currentPathNode = openList[index];
		openList.RemoveAt(index);
		closedList.Add(currentPathNode);

		var neighbourWaypoints:Array = currentPathNode.waypoint.waypointsInRange;
		for(var i:int = 0;i<neighbourWaypoints.length;i++)
		{

			if(!IsInCL(closedList,neighbourWaypoints[i]))//Wenn der Wegpunkt nicht in der closedList ist
			{
				var indexInOL:int = IsInOL(openList,neighbourWaypoints[i]);
				if(indexInOL >= 0)//Wenn der Wegpunkt in der openList ist
				{
					var newGValue:float = currentPathNode.gValue + Vector3.Distance(currentPathNode.waypoint.transform.position,openList[indexInOL].waypoint.transform.position);
					if(newGValue < openList[indexInOL].gValue)
					{

						openList[indexInOL].parentPathNode = currentPathNode;
						openList[indexInOL].gValue = newGValue;
						openList[indexInOL].fValue = (newGValue + openList[indexInOL].hValue);

					}

				}
				else//Wenn der Wegpunkt nicht in der openList ist
				{

					var GValue:float =  currentPathNode.gValue +  Vector3.Distance(currentPathNode.waypoint.transform.position,neighbourWaypoints[i].transform.position);
					var HValue:float = Vector3.Distance(neighbourWaypoints[i].transform.position,targetWaypoint.transform.position);
					var FValue:float = GValue + HValue;


					var newPathNode:PathNode = new PathNode(neighbourWaypoints[i]);
					newPathNode.gValue = GValue;
					newPathNode.hValue = HValue;
					newPathNode.fValue = FValue;
					newPathNode.parentPathNode = currentPathNode;

					openList.Add(newPathNode);

					if(newPathNode.waypoint == targetWaypoint)
					{

						targetField = newPathNode;
						pathArray = ReturnPath(startField,targetField);
						break;
					}

				}//else

			}//if


		}//for
	}//while


}



return pathArray;

}

////////////////////////////////////////////////////////////////////////////

static public function IsInCL(closedL:Array,wayPoint:Waypoint):boolean
{
var isIn:boolean = false;
for(var i:int = 0;i<closedL.length;i++)
{

	if(closedL[i].waypoint == wayPoint)
	{

		isIn = true;
		break;
	}

}
return isIn;

}

////////////////////////////////////////////////////////////////////////////


static public function IsInOL(openL:Array,wayPoint:Waypoint):int
{
var index:int = -1;
for(var i:int = 0;i<openL.length;i++)
{

	if(openL[i].waypoint == wayPoint)
	{

		index = i;
		break;
	}

}
return index;
}

////////////////////////////////////////////////////////////////////////////

static public function ReturnPathNodeWithLowestFValue(openL:Array):int
{
var pathNode:PathNode = null;
var index= -1;

if(openL.length >0)
{

	for(var i:int = 0;i<openL.length;i++)
	{

		if(index == -1)
		{

			pathNode = openL[i];
			index = i;
		}
		else if(pathNode.fValue > openL[i].fValue)
		{
			pathNode = openL[i];
			index = i;
		}

	}

}

return index;
}

////////////////////////////////////////////////////////////////////////////

static public function ReturnPath(startField:PathNode,targetField:PathNode):Array
{
var pathArray:Array = new Array();
var currentPathNode:PathNode = targetField;
while(currentPathNode!=startField)
{

	pathArray.Add(currentPathNode.waypoint);
	currentPathNode = currentPathNode.parentPathNode;
}

pathArray.Reverse();

return pathArray;
}

 

 

Falls ihr das ganze mal testen wollt habe ich hier ein kurzes Script geschrieben. Legt es einfach auf ein Objekt eurer Wahl und zieht im Inspektor grad 2 Wegpunkte auf targetWaypoint und startWaypoint. über drücken der P Taste und angewähltem Objekt könnt ihr den Pfad als rote Linie sehen. Vorausgesetzt ihr habt Gizmos aktiviert.

 

var startWaypoint:Waypoint;
var targetWaypoint:Waypoint;
var pathArray = new Array();
function Update () {


if(Input.GetKeyUp("p"))
{

	pathArray = Pathfinder.GetPath(startWaypoint,targetWaypoint);

	if(pathArray == null)
	{

		Debug.Log("Ziel ist nicht zu erreichen!!");

	}

}


}


function OnDrawGizmosSelected ()
{


	if(pathArray!=null && pathArray.length>0)
	{

		var currentWaypointPos:Vector3 = pathArray[0].transform.position;

		for(var i:int = 1;i < pathArray.length; i++)
		{
			Gizmos.color = Color(1,0,0,1);
			Gizmos.DrawLine(currentWaypointPos,pathArray[i].transform.position);
			currentWaypointPos = pathArray[i].transform.position;
		}

	}


}

 

Ich habe zum testen auch mal einige Wegpunkte so gesetzt das sie nicht zu erreichen sind, wenn ihr das macht wird kein Pfad gezeichnet und es kommt die Meldung "Ziel ist nicht zu erreichen!!.

 

Ich hoffe ich konnte es verständlich rüber bringen und das euch dieses Tutorial weiter hilft wenn ihr eine KI entwickeln wollt.

Ich werde demnächst noch einen vierten Teil machen in dem ich eine kleine KI programmiere die das Wegpunktesystem und den Pathfinder nutzt.

 

 

Gruß Stephan

Link zu diesem Kommentar
Auf anderen Seiten teilen

  • 5 months later...

Ich habe jetzt endlich mal etwas Zeit gefunden und dieses Tutorial durch gearbeitet. Sehr gut! :)

 

Hier im letzten Teil ist dir ein kleiner Fehler unterlaufen, den du noch korrigieren solltest.

Und zwar schreibst du beim Funktionsaufruf : ReturnPathNodeWithLowestFValue

Aber die Funktion heisst: ReturnNeighbourWithLowestFValue

 

Jetzt habe ich aber noch ne kleine Blockade, was das Emitteln des Starts und Ziels angeht. Wir übergebe ich denn die Wegpunkte, wenn z.B. der Start beim Player ist und das Ziel ein anderes Objekt. In deinem Beispielscript habe ich ja die Wegpunkte rein gezogen und somit ist das ganz leicht. Aber wie ich diese entsprechenden Wegpunkte jetzt im Spiel übergebe will mir einfach nicht einfallen. ;)

 

Edit:

 

Ach, ist doch einfacher als gedacht. Ich gebe dem Waypointscript einfach ne Abfrage und sende "this"

 

So wie hier:

function OnTriggerStay(other: Collider){
if (other.tag=="start"){
	testscript.startWaypoint=this;
}
if (other.tag=="ziel"){
	testscript.targetWaypoint=this;
}
} 

 

Ich wüsste sonst nicht, wie ich die Waypoints unterscheiden kann. Aber so gehts ja. :)

Link zu diesem Kommentar
Auf anderen Seiten teilen

Fehler behoben, Funktion heißt jetz durchgehend "ReturnPathNodeWithLowestFValue"!!

 

Hm okay also mit Tags würde ich das nicht machen :)

Kommt eben drauf an ob du nur eins oder ob du mehrere Ziele hast, kleines Beispiel:

In meinem Spiel hatte ich eine Spielfigur die vom Anwender gesteuert wird, in diesem "PlayerScript" habe ich stets den Wegpunkt festgehalten auf dem sich der Spieler gerade befindet..

 

public var currentWayPoint:Waypoint;

function OnTriggerEnter(other: Collider)
{
  if(other.tag == "Waypoint")
 { 
     currentWayPoint = other.gameObject.GetComponent("Waypoint");
 }
}

 

Alle KI gesteuerten Figuren haben den Spieler beim initialisieren übergeben bekommen und hatten somit stets zugriff auf dessen position bzw dessen zuletzt betretenen Wegpunkt.

In jeder KI gesteuerten Figur habe ich wiederum deren aktuellen Wegpunkt gespeichert... somit hat man um einen Weg für die KI zu berechnen sowohl start (currentWayPoint der KI) und das ziel(currentWayPoint der Spielfigur).

 

Sobald ein Weg berechnet wurde interessieren mich die Trigger eigentlich nicht mehr wirklich, da ich jetzt eine Liste mit allen Wegpunkten habe, hab ich auch dessen Koordinaten im 3D Raum, jetzt lauf ich nurnoch die Punkte im Array nacheinander ab, sobald ich einen Wegpunkt auf dem Pfad erreciht habe, werf ich diesen aus dem Array raus und steuer den nächsten an wenn es noch einen gibt, gibt es in meiner Liste keinen mehr habe ich das Ziel erreicht!

 

Anderes Beispiel wäre ein echtzeitstrategiespiel, aber da ist es eigentlich noch einfacher, wenn du eine Figur zu einem Punkt schicken willst hast du ja den Startpunkt der Figur wenn dieses wiederum ihre Position bzw seinen aktuellen Wegpunkt speicherst, und Ziel ist dann der Wegpunkt den du beim Klicken durch einen Raycast triffst..

Bei einem Rundenbasierten Strategiespiel würde ich es allerdings etwas anders machen und tatsächlich auf die Trigger verzichten, das sollte man sowieso machen wenn man das Spielfeld in ein Raster einteilen kann. Dann brauchst du den aktuellen Wegpunkt ja nichtmehr über betreten eines Triggers ermitteln, sondern du kannst ihn aus deinen x/y Koordinaten errechnen!

 

Nochmal zurück zu den Triggern und dem pfad berechnen, wenn eine Figur eine andere verfolgen soll kommt es ja durch aus vor das der verfolgte ständig eine andere Position hat und somit in einem anderen Wegpunkt steht, wenn das der Fall sein sollt, das Ziel ist also nicht fest dann ist es sinnvoll nur dann eine Pfadberechnung durch zu führen wenn der verfolger den Verfolgten nicht sieht, andernfalls kann dieser ja direkt auf ihn zu gehen es sei denn es ligt ein Gegenstand im direkten weg dann kann ebenfalls wieder ein Pfad berechnet werden!

So hab ich es zumindest in dem Spiel gehalten für das ich dieses System geschrieben habe.. Die Figur läuft stets auf sein Ziel zu, kommt die Figur nicht direkt hin weil etwas den Weg blockiert, sieht das Ziel aber noch dann wird ein Pfad berechnet.. sobald die Figur ihr Ziel aus den Augen verliert dann wird sich der Wegpunkt gemerkt an dem das Ziel zuletzt gesehen wurde.. hat die Figur diesen Wegpunkt erreciht und sieht das Ziel wieder wird weiter verfolgt, sieht die Figur das ziel jetzt nichtmehr kehrt die Figur zu einer ausgangsposition zurück oder bleibt an der Stelle stehen!

 

Ich hoffe ich konnte dir etwas helfen..

 

Gruß Stephan

Link zu diesem Kommentar
Auf anderen Seiten teilen

Jo, du hast mir da schon sehr geholfen. :)

Ich habe da ganz andere Probleme, die echt doof umzusetzen sind. Da ja diese Waypoints alle über Trigger arbeiten, wird der OnMouseDown() Befehl auf dem Boden nicht mehr ausgeführt. Ich klicke ja nicht auf den Boden, sondern auf den Trigger vom Waypoint da drüber. Dummerweise brauche ich den Klick auf dem Boden, da ich dann einen Raycast von der Camera zum Boden schicke um die genaue Position zu ermitteln.

Verzwicktes Dingen. ;) Ignore Raycast, kann ich den Triggern nicht geben, da sie sich über den Raycast ja organisieren.

Mal sehen, was ich mir da zurecht lüge, denn die Position des Waypoints ist mir zu grob. (Muss Ressourcen sparen und hab die Waypoints recht groß gewählt.)

 

Jedenfalls funktionier das Wayfindingsystem sehr zufrieden stellend. Je nach Anzahl der Waypoints, braucht es ein paar Sec. beim Start, bis alle Nachbarn ermittelt wurden. Die Wegberechnung geht aber schön schnell. :)

Link zu diesem Kommentar
Auf anderen Seiten teilen

Hmm okay das is natürlich doof, was du machen könntest wäre nachdem die wepunkte berechnet wurden die trigger auf ignore raycast stellen!

Andere Möglichkeit wäre wenn du nicht unbedingt das OnMouseDown() brauchst, das du einen raycast stattdessen nimmst der die trigger über eine layermask ignoriert.

var layerMask:LayerMask = 1 << 5;//wenn der wegpunkt Layer an Stelle 5 ist erstellst du so eine layermask die nur diesen Layer beinhaltet
layerMask =~layerMask;//so drehst du sie um wodurch alle Layer drin sind außer der wegpunkte Layer

 

Und dann beim raycast die layermask einfach in die Parameter des funktionsaufrufs und den raycast in kamerrichtung aus losschicken.

 

Was natürlich das beste wären wenn du dein Spielfeld rastern könntest um dir die trigger zu sparen!

Machst du grad zufällig nen spiel für iPhone?

 

Gruß Stephan

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ich werde beide Varianten mal austesten. Momentan habe ich mir damit geholfen, dass ich die Mouse-Funktion hole, indem ich einen Klick auf dem Waypointtrigger auswerte und dann in mein Floorscript springe und da das ausführe, was eigentlich beim Mouseklick auf dem Floor kommen würde. Über RaycastAll bekomme ich dann die Koordinaten auf dem Boden.

 

Ja, unser Spiel wird auch auf dem iPad laufen. Tuts eigentlich jetzt schon, aber eben ohne A*.

iOS hat da aber so seine Probleme mit dynamischen Arrays. Mal sehen wie ich das dort löse oder ob ich für iOS einen anderen Weg gehe.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Also für unser aktuelles Spiel für IPhone/IPad(ein rundenbasiertes Strategiespiel) verwenden wir auch den A* allerdings in C# geschrieben (im Grunde aber genauso wie er hier im Tutorial funktioniert) und das Spielfeld ist gerastert, also ohne trigger denn die verbrauchen eine unmenge rechenleistung und sind vollkommend überflüssig!

Aber es läuft einwandfrei und auch die dynamischen Arrays machen keine probleme...

Link zu diesem Kommentar
Auf anderen Seiten teilen

Sehr gut zu wissen, dass es auf iOS läuft. :)

Ich habe es jetzt auch fertig (PC). Schalte nach der Berechnung einfach die Trigger auf ignore Raycast und schon geht alles wie gewünscht.

Da ich das Waypointsystem nur für den Helden brauche, muss es auch nur einmal beim Start der Szene berechnet werden.

Nach jedem Erreichen eines Waypoints schau ich, ob ich jetzt ohne Hindernis zum Ziel komme. Wenn ja, dann bin ich nicht mehr im Waypointmodus und gehe direkt zum Ziel. Funktioniert prima und sieht dadurch auch recht natürlich aus. Nur manchmal macht er einen kleinen Schlenker in die falsche Richtung, wenn der erste Wegpunkt nicht direkt in Blickrichtung liegt.

Den Start- und Zielwegpunkt ermittle ich über die Entfernung zum Helden bzw. Zielmarker. Wenn die Dinger innerhalb eines definirten Radius zum Wegpunkt sind, ist es dieser Wegpunkt.

Bin sehr zufrieden mit deinem Script! Hast du gut gemacht! :)

Link zu diesem Kommentar
Auf anderen Seiten teilen

  • 2 months later...

Hi. :)

Zunächstmal: Danke, damuddamc! Ich hab Monate lang versucht, im Internet Artikel zum A* Star Algorithmus zu finden, die man als Scripting Anfänger auch kapieren kann. Endlich ist die Suche vorüber.^^

Diese Tutorialreihe ist einfach nachzuvollziehen und es macht Spaß sie zu lesen, denn währenddessen kommt mir eine Offenbarung nach der anderen.

 

Nun habe ich den Code der ersten beiden Tutorials erfolgreich nach c# umgeschrieben und versuche derweil, mit dem "Instantiate"-Befehl erschaffene Würfel als waypoints in dein Wegpunkte-System einzubinden, was mir aber nicht so recht gelingen will. Die Würfel haben alle das Waypoint Skript drauf und werden bei Spielbeginn als children einem empty gameobject hinzugefügt, welches das WaypointManager Skript beinhaltet. Ich war der Ansicht, der einzige Unterschied zu deinem System wäre, dass die Wegpunkte halt später reingespawnt werden. Was ich nicht bedacht hatte, war, dass meine Methode das Timing der beiden Skripte total durcheinanderwirft.

Ich dachte durch das Trennen gewisser Codepassagen und durch das Aktivieren der Skripte zu verschiedenen Zeitpunkten würde was nützen. Tuts aber nicht.

 

Dieses Skript ruht auf dem zu spawnenden Waypoint-Prefab:

 

using UnityEngine;
using System.Collections;

public class Waypoint : MonoBehaviour {

public static ArrayList Waypoints = new ArrayList();
public static ArrayList waypointsInRange;

void Awake()
{
 // Dies ist die einzige Zeile die ich eingefügt hab, um dieses Object dem Waypointmanager unterzuordnen.
 transform.parent = GameObject.Find("WaypointManager").transform;
 transform.renderer.enabled = false;
}

public static void AddNeighbour(Waypoint neighbour)
{
 if(waypointsInRange == null)
 {
  waypointsInRange = new ArrayList();
 }

 waypointsInRange.Add(neighbour);
}

void OnDrawGizmosSelected()
{
 Gizmos.color = Color.cyan;
 Gizmos.DrawCube(transform.position, new Vector3(0.2f, 0.1f, 0.2f));

 if(waypointsInRange != null && waypointsInRange.Count > 0)
 {
  foreach(Waypoint neighbour in waypointsInRange)
  {
Gizmos.color = Color.red;
Gizmos.DrawLine(transform.position, neighbour.transform.position);
  }
 }
}
}

 

Dieses Skript hab ich auf den WaypointManager gepackt (den Code von mir markiere ich mit Slashes):

 

using UnityEngine;
using System.Collections;

public class WaypointManager : MonoBehaviour {

public float maxDistanceBetweenWaypoints = 6;
public Transform node;////////////////////////////////////////////
public float scaleValue = 0.3f;/////////////////////////////////////
public int gridSizeX = 20;////////////////////////////////////////////
public int gridSizeZ = 20;////////////////////////////////////////////

void Awake()
{
///////////////////// Diesen Abschnitt habe ich hinzugefügt, um die waypoint-prefabs als Grid zu spawnen.
///////////////////// Alles was danach kommt, blieb unangetastet.
   for(int x = 0; x < gridSizeX; x++)
	{								  
  			for(int z = 0; z < gridSizeZ; z++)
		{
			Vector3 cachedPosition = transform.TransformPoint(x,0,z);
			Instantiate(node, cachedPosition * scaleValue, transform.rotation);
		}
  	 }
///////////////////////////////////////////////////////////////////////////////////////////////////
  		 Waypoint.Waypoints = new ArrayList();
	CalculateWaypoints(transform);
	CalculateNeighbours();
}

void CalculateWaypoints(Transform parentTransform)
{
	foreach(Transform child in parentTransform)
	{
		if(child.GetComponent(typeof(Waypoint)))
		{
			Waypoint wp = child.GetComponent(typeof(Waypoint)) as Waypoint;
			Waypoint.Waypoints.Add(wp);
		}
		if(child.childCount > 0)
		{
			CalculateWaypoints(child);
		}
	}
}

void CalculateNeighbours()
{
	foreach(Waypoint waypoint in Waypoint.Waypoints)
	{
		foreach(Waypoint neighbour in Waypoint.Waypoints)
		{
			if(neighbour != waypoint)
			{
				Vector3 pos1 = waypoint.transform.position;
				Vector3 pos2 = neighbour.transform.position;
				float deltaL = Vector3.Distance(pos1, pos2);

				if(deltaL <= maxDistanceBetweenWaypoints)
				{
					RaycastHit[] hits;
					hits = Physics.RaycastAll(pos1, Vector3.Normalize(pos2 - pos1), deltaL);

					bool isWayFree = true;

					for(int i = 0; i < hits.Length; i++)
					{
						if(!hits[i].collider.isTrigger)
						{
					   	 isWayFree = false;
							break;
						}
					}
					if(isWayFree)
					{
						Waypoint.AddNeighbour(neighbour);
					}
				}
			}
		}
	}
}
}

 

Wenn ich es so laufen lasse, werden die Prefabs fein säuberlich gespawned, die Gizmo-Cubes werden erstellt, aber nicht die Gizmo-Lines und das Raycasting startet auch garnicht erst. Meine Frage ist nun: Was kann ich tun, damit die gespawnten prefabs als Wegpunkte anerkannt werden? Ich wäre für jeden Hinweis sehr dankbar.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Hi Noah,

 

danke für dein Lob :) freut mich sehr.. gut das du es auf C# umgeschrieben hast hätte ich demnächst warscheinlich auch noch getan denn mitlerweile programmiere ich auch nicht mehr mit JS...

 

So jetzt zu deinem Problem, ich nehme an weil der Waypointmanager die jeweiligen Nachbarn in der Awake methode errechnet und jeder Instanzierte Wegpunkt sich auch in der Awake dem Waypointmanager unterordnet gibt es da nen konflikt!

mach einfach folgendes, rufe die funktionen CalculateWaypoints und CalculateNeighbours erst in der Start Methode auf:

 


void Start()
{
  CalculateWaypoints(transform);
  CalculateNeighbours();
}

 

vieleicht behebt das schon dein problem:

 

Gruß Stephan

Link zu diesem Kommentar
Auf anderen Seiten teilen

Hi Stephan. Danke für die rasche Antwort.

Leider ändert sich dadurch nichts. Wäre auch zu schön gewesen.^^ Aus irgendeinem Grund wird weder das Raycasting ausgeführt, noch der DrawLineTeil in OnDrawGizmos(). Der DrawCube Befehl hingegen erfüllt seinen Zweck.

 

Es liegt wahrscheinlich an irgendeinem Fehler der mir beim Umschreiben auf c# unterlaufen ist. Ich werde mal ein wenig Debugging betreiben um zu sehen wo es hapert. Ich melde mich zurück, sobald ich was rausgefunden habe.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Oha. Mein Fehler war, dass ich nach dem Umschreiben nach C# nicht sofort getestet habe, ob auch alles auf die von dir beschriebene Weise funktioniert. Sprich, mit manuell platzierten Wegpunkten. Wenn man also alle von mir hinzugefügten Lines of Code entfernt, lässt sich folgendes Spektakel im Editor sowie zur Laufzeit begutachten:

 

unityimage01.jpg

 

Das muss wohl an meiner direkten java-c# übersetzung liegen, denn die Werte maxDistanceBetweenWaypoints (beim Debuggen: 5.0f) und deltaL(beim Debuggen: 2.6f) scheinen in Ordnung zu sein. Außerdem ist es egal wieviele Würfel ich platziere oder wie groß die Distanz zwischen den Wegpunkten ist, jeder von ihnen hat eine Verbindung zu jedem anderen.

 

isTrigger ist bei den Wegpunkten aktiviert und sie sind allesamt Children vom WaypointManager. Ich bin ratlos. :/ Liegt es vielleicht an den ArrayLists?...

 

EDIT: @Stephan: wird gemacht.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Also. Bei der Methode mit manuell platzierten Wegpunkten (6 stk. während des Testlaufs) ist Waypoint.Waypoints.Count = 6. Also scheint damit alles in Ordnung zu sein, bis auf das Problem natürlich, dass jeder Wegpunkt mit jedem anderen verbunden wird.

 

Bei der Methode wo das Grid aus prefabs gespawned wird, ist Waypoint.Waypoints.Count = 0.

 

Bei beiden Methoden sind die Wegpunkte ziemlich genau 1 Einheit voneinander entfernt. deltaL war beim Testen ungefähr 1.8f und maxDistanceBetweenWaypoints war 2.0f.

 

Mein Scripting-Verständnis reicht leider noch nicht ganz aus, um das Problem selbstständig zu beheben. Ich werde wohl noch ein wenig debuggen und bescheidgeben wenn ich irgendwas Nennenswertes rausfinde.

 

@Stephan: Das ist das Seltsame. Wenn ich maxDistanceBetweenWaypoints übertrieben runterschraube z.B auf 0.1f wird nichts verbunden. Logisch. Aber sobald ich in 0.1 Schritten die richtige Distanz zu finden versuche, ist bei 1.1f nichts verbunden und bei 1.2f sind wieder alle mit jedem verbunden... wobei dieser 0.1f Unterschied doch eigentlich nicht so viel ausmachen sollte, immerhin ist die Distanz zwischen all den Wegpunten 1.0f bis 2.0f. :-/

 

EDIT:

unityimage02.jpg

 

Auf diesem Bild beträgt die Distanz zwischen den 9er Grids ca. 5 Einheiten. Der Abstand zwischen den einzelnen Wegpunkten pro Grid beträgt genau 1 Einheit. maxDistanceBetweenWaypoints habe ich auf 2.0f eingestellt. Das grüne Hindernis inklusive BoxCollider, welcher kein Trigger ist, unterbricht die GizmoLines/Rays nicht (weder zur Laufzeit noch im Editor).

Das ist alles sehr mystisch. ... Hat jemand eine Idee wo das Problem liegen könnte?

 

EDIT2: Ich hab das Problem mittlerweile etwas mehr eingegrenzt: Zunächstmal hab ich 2 Versionen des Wegpunktesystems nebeneinandergepackt(C# + Java). Im Gegensatz zur C# Version läuft die Java Version des Wegpunktsystems wie erwartet reibungslos. Da ich die Skripte der C# Version mit Debug.Logs zugeballert hab, lässt sich Folgendes mit Sicherheit sagen:

 

Der Inhalt von "if(!hits.collider.isTrigger)" wird niemals ausgeführt.

 

Darüber hinaus werden die GizmoLines in der C# Version nach einmaligem Spielstart auch im Editor angezeigt wenn das Spiel beendet wird und verschwinden erst nach erneutem Kompilieren. Bei der Java Version sind die GizmoLines ausschließlich zur Laufzeit sichtbar. Sagen tut mir das jedoch nichts.

 

Im übrigen sind die Transform-Attribute der Wegpunkte und alle anderen Einstellungen identisch mit denen der Java Version (die selben wie im 2. Tutorial). Ich hoffe immernoch dass mir jemand helfen kann das ganze in C# auf die Reihe zu kriegen. Ich werd dann mal weiterschauen...

Link zu diesem Kommentar
Auf anderen Seiten teilen

Das Problem ist beseitigt. Die beiden Skripte "Waypoint" und "WaypointManager" die ich oben gepostet habe, funktionieren einwandfrei. Sogar mit dem Gridspawning Zusatz, wenn man im Waypoint Skript aus dieser Zeile:

 

public static ArrayList waypointsInRange;

 

das static tilgt, dass ich fälschlicherweise hinzugefügt hatte.

Die Zeile muss also so aussehen:

 

public ArrayList waypointsInRange;

 

 

und im WaypointManager Skript in dieser Zeile:

 

Waypoint.AddNeighbour(neighbour);

 

das W von Waypoints klein schreibt:

 

waypoint.AddNeighbour(neighbour);

 

Ich weiß auch nicht wie ich das sogar nach dem 50. mal drübergucken übersehen konnte. ~.~

 

Wie dem auch sei. Ich hab mich an die übersetzung des Pathfinder Skripts gemacht. Im Prinzip sieht alles gut aus und wenn man es testet gibt es sogar nur eine einzige Fehlermeldung, aber die hats in sich. Hier erstmal der PathFinder in c#.

 


using UnityEngine;
using System.Collections;

public class PathFinder : MonoBehaviour {

class PathNode
{

 public float fValue = 0;
 public float gValue = 0;
 public float hValue = 0;  
 public PathNode parentPathNode;
 public Waypoint waypoint;


 public void PathNode(Waypoint wayPoint)
 {
   waypoint = wayPoint;
 }
}  

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

public static ArrayList GetPath(Waypoint startWaypoint ,  Waypoint targetWaypoint)
{

	ArrayList openList = new ArrayList();
	ArrayList closedList = new ArrayList();
	PathNode currentPathNode;
	PathNode startField = new PathNode(startWaypoint);
	PathNode targetField = null;
	ArrayList pathArray;
	currentPathNode = startField;
	openList.Add(startField);

	if(startWaypoint != targetWaypoint)
	{
			while(targetField == null && openList.Count > 0)
			{
					int index = ReturnPathNodeWithLowestFValue(openList);
					currentPathNode = openList[index];
					openList.RemoveAt(index);
					closedList.Add(currentPathNode);

					ArrayList neighbourWaypoints = currentPathNode.waypoint.waypointsInRange;
					for(int i = 0; i < neighbourWaypoints.Count; i++)
					{

							if(!IsInCL(closedList,neighbourWaypoints[i]))//Wenn der Wegpunkt nicht in der closedList ist
							{
									int indexInOL = IsInOL(openList,neighbourWaypoints[i]);
									if(indexInOL >= 0)//Wenn der Wegpunkt in der openList ist
									{
											float newGValue = currentPathNode.gValue + Vector3.Distance(currentPathNode.waypoint.transform.position,openList[indexInOL].waypoint.transform.position);
											if(newGValue < openList[indexInOL].gValue)
											{

												 openList[indexInOL].parentPathNode = currentPathNode;
												 openList[indexInOL].gValue = newGValue;
												 openList[indexInOL].fValue = (newGValue + openList[indexInOL].hValue);

											}

									}
									else//Wenn der Wegpunkt nicht in der openList ist
									{

											float GValue =  currentPathNode.gValue +  Vector3.Distance(currentPathNode.waypoint.transform.position, neighbourWaypoints[i].transform.position);
											float HValue = Vector3.Distance(neighbourWaypoints[i].transform.position, targetWaypoint.transform.position);
											float FValue = GValue + HValue;

											PathNode newPathNode = new PathNode(neighbourWaypoints[i]);
											newPathNode.gValue = GValue;
											newPathNode.hValue = HValue;
											newPathNode.fValue = FValue;
											newPathNode.parentPathNode = currentPathNode;

											openList.Add(newPathNode);

											if(newPathNode.waypoint == targetWaypoint)
											{

												 targetField = newPathNode;
												 pathArray = ReturnPath(startField,targetField);
												 break;
											}

									}//else

							}//if


					}//for
			}//while


	}


	return pathArray;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 public static bool IsInCL(ArrayList closedL, Waypoint wayPoint)
 {
	 bool  isIn = false;

	for(int i = 0;i<closedL.Count;i++)
	{

			if(closedL[i].waypoint == wayPoint)
			{

					isIn = true;
					break;
			}

	}
	return isIn;
 }

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 public static int IsInOL(ArrayList openL, Waypoint wayPoint)
 {

	int index = -1;

	for(int i = 0; i<openL.Count; i++)
	{

			if(openL[i].waypoint == wayPoint)
			{

					index = i;
					break;
			}

	}
	return index;
 }

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 public static int ReturnPathNodeWithLowestFValue(ArrayList openL)
 {
	PathNode pathNode = null;
	int index = -1;

	if(openL.Count >0)
	{

			for(int i = 0; i < openL.Count; i++)
			{

					if(index == -1)
					{

							pathNode = openL[i];
							index = i;
					}
					else if(pathNode.fValue > openL[i].fValue)
					{
							pathNode = openL[i];
							index = i;
					}

			}

	}

	return index;
 }

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 public static ArrayList ReturnPath(PathNode startField, PathNode targetField)
 {
	ArrayList pathArray = new ArrayList();
	PathNode currentPathNode = targetField;
	while(currentPathNode != startField)
	{

			pathArray.Add(currentPathNode.waypoint);
			currentPathNode = currentPathNode.parentPathNode;
	}

	pathArray.Reverse();

	return pathArray;
 }
}

 

Folgender Fehler wird beim kompilieren dieses Skripts verursacht:

 

PathFinder.cs(17,25): error CS0542: `PathFinder.PathNode.PathNode(Waypoint)': member names cannot be the same as their enclosing type

 

1. Entweder muss bei "class PathNode" oder "public void PathNode" der Name geändert werden was dazu führt, dass man sich durch den Rest des Codes durchklamüsern muss um alle andern "PathNode"'s zu ändern, was ich nicht hinbekomme, da ich die Klasse "PathNode" und die Funktion "PathNode" nicht auseinanderhalten kann. Oder

 

2. man entfernt bei "public void PathNode" einfach das void, was aber auch irgendwie nicht in Frage kommt, da das diesen Fehler zur Folge hat:

 

PathFinder.cs(188,33): error CS0051: Inconsistent accessibility: parameter type `PathFinder.PathNode' is less accessible than method `PathFinder.ReturnPath(PathFinder.PathNode, PathFinder.PathNode)'

 

Das führt somit auch nirgens hin. :S

 

Also ich brauch jetzt erstmal ne Asperin gegen die Kopfschmerzen die mir dieses Skript beschert. :D Falls ich Fortschritte mache meld ich mich, falls mich vorher jemand erleuchtet, um so besser. ;)

Link zu diesem Kommentar
Auf anderen Seiten teilen

Es ist so, in JS kann eine klasse einen Konstruktor haben solange sie nicht von MonoBehaviour erbt... in Unitys C# nicht... der Konstruktor von PathNode ist eben diese gleichnamige Methode! In C# sollte die Klasse PathNode übrigens von Scriptable objekt abstammen und somit so aussehen:

 

using UnityEngine;
using System.Collections;
public class PathNode:ScriptableObject
{
public float fValue = 0.0f;
public float gValue = 0.0f;
public float hValue = 0.0f;
public PathNode parentPathNode;
public Waypoint waypoint;
}

 

Die Klasse PathNode so wie ich sie dir oben geschrieben habe, die bisher in der Klasse PathFinder deklariert war steckst du jetzt einfach in nen eigenes File mit dem Namen PathNode...

 

So was du jetzt noch tun musst ist die Zeile :

 

PathNode newPathNode = new PathNode(neighbourWaypoints[i]);

 

durch folgende zu ersetzen:

 

PathNode newPathNode = (PathNode)ScriptableObject.CreateInstance<PathNode>();
newPathNode.waypoint = neighbourWaypoints[i];

 

dann sollte es geh...

 

Gruß Stephan

Link zu diesem Kommentar
Auf anderen Seiten teilen

Sorry für die späte Rückmeldung. Vielen Dank für den Tipp Stephan.

Ich werd das jetzt gleich mal ausprobieren.

 

 

EDIT: Jetzt meckert der Compiler wegen dieser Funktion rum:

public void PathNode(Waypoint wayPoint)
{
 waypoint = wayPoint;
}

 

Wenn ich die Funktion mit in das neue PathNode Skript packe, sagt mir der Compiler natürlich wieder dass die Namen unterschiedlich sein müssen.

 

Wenn ich sie im PathFinder Skript an der Stelle belasse, wo sich zuvor die Klasse PathNode befand hat das 26 Fehler zufolge, die meisten davon CS1061 'er. Die ErrorLog Datei befindet sich im Anhang.

CompilerErrorLog.txt

Link zu diesem Kommentar
Auf anderen Seiten teilen

Das hab ich auch schon ausprobiert... das verursacht jedoch 34 Fehler wobei ich annehme, das der erste vom Compiler entdeckte Fehler der Grund für alle anderen ist. Der erste Fehler lautet:

 

PathFinder.cs(12,58): error CS1729: The type `PathNode' does not contain a constructor that takes `1' arguments

 

was sich in dem Pathfinder Skript auf folgende Zeile bezieht:

 

PathNode startField = new PathNode(startWaypoint);

 

ansonsten befindet sich das komplette ErrorLog im Anhang, diesmal ein wenig übersichtlicher

 

 

danke für die Hilfe Stephan

CompilerErrorLog.txt

Link zu diesem Kommentar
Auf anderen Seiten teilen

dann musste die Zeile auch noch gegen diese austauschen, hatte ich übersehen das noch an anderer Stelle nen pathNode erzeugt wird:

 

 

PathNode newPathNode = (PathNode)ScriptableObject.CreateInstance<PathNode>();

newPathNode.waypoint = startWaypoint;

 

 

Und die methode PathNode nimmst du aber auf jeden Fall aus der Klasse PathNode raus!!

Link zu diesem Kommentar
Auf anderen Seiten teilen

Nur um nochmal sicherzugehen: Die Methode "PathNode(Waypoint wayPoint)" nehm ich nicht nur aus dem Script PathNode raus, sondern ich soll sie komplett entfernen?

 

Wenn ja, dann entsteht nach ändern der oben genannten Zeile mit den Zeilen die du gepostet hast folgender Error. :S

 

PathFinder.cs(54,38): error CS0136: A local variable named `newPathNode' cannot be declared in this scope because it would give a different meaning to `newPathNode', which is already used in a `parent' scope to denote something else

 

EDIT: Der Fehler bezieht sich auf die mit Slashes markierte Zeile:

else//Wenn der Wegpunkt nicht in der openList ist
{					
 float GValue =  currentPathNode.gValue + Vector3.Distance(currentPathNode.waypoint.transform.position, neighbourWaypoints[i].transform.position);
 float HValue = Vector3.Distance(neighbourWaypoints[i].transform.position, targetWaypoint.transform.position);
 float FValue = GValue + HValue;

 PathNode newPathNode = (PathNode)ScriptableObject.CreateInstance<PathNode();///////////////////////////////////////////////////////////////////////
 newPathNode.waypoint = neighbourWaypoints[i];
 newPathNode.gValue = GValue;
 newPathNode.hValue = HValue;
 newPathNode.fValue = FValue;
 newPathNode.parentPathNode = currentPathNode;

 openList.Add(newPathNode);

Link zu diesem Kommentar
Auf anderen Seiten teilen

man :) du musst doch auch mal überprüfen was ich dir da schreibe ^^

die variable darf nicht newPathNode sondern muss startField heißen:

PathNode startField = (PathNode)ScriptableObject.CreateInstance<PathNode>();
startField.waypoint = startWaypoint;

 

Aber nicht in dem Code-Ausschnitt verändern den du mir eben gepostet hast sondern in dem oben dran!!!

Link zu diesem Kommentar
Auf anderen Seiten teilen

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung jetzt entfernen

  Only 75 emoji are allowed.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Lädt...
×
×
  • Neu erstellen...