Rangliste

Ich hab zwar schon ein paar Threads erstellt, möchte mich aber trotzdem noch kurz vorstellen. Ich heiße Markus, bin Ü40 und mein erster Computer war der C64, auf dem ich schon Bits geschubst habe. Inzwischen bin ich über Amiga, DOS und Windows seit 2007 bei Linux angekommen. Seit etwas über einem Jahr spiele und programmiere ich mit dem Minecraft Clone namens Minetest. Leider stößt man schnell an die Grenzen des Spiels und der Community. Deshalb habe ich mir überlegt, ein eigenes Projekt zu starten. Ich bin zwar nicht der erste, der mit Unity ein Boxel Game erstellen möchte, aber ich denke, dass mein Ansatz doch relativ einzigartig sein wird. Kernelement wird nicht Unity sein sondern ein unabhängig laufender Server, auf dem die Kartendaten erzeugt und andere Informationen verwaltet werden. Gegner und Monster zB werden auf dem Server gesteuert und lediglich die Koordinaten und andere Daten an den Client gesendet. Auch die Lichtberechnung erfolgt auf dem Server, unabhängig von der visuellen Darstellung auf dem Client. Das ist nötig um zB festzustellen, ob Pflanzen wachsen können. Der Client erhält dann die fertigen Kartendaten und erstellt daraus ein Mesh, um die Daten dann auch darstellen zu können. Ich bin gespannt, wie weit ich komme, da ich mit Grafikprogrammierung noch keine Erfahrung habe.

------------------------------------------------------------------------- Du programmierts in JS?--> Teil 3:A* Pathfinder JS ------------------------------------------------------------------------- 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 C# Dokument anlege, ich nenne es PathNode, in dieser wird die Klasse PathNode deklariert, sie erbt von ScriptableObject und nicht von MonBehaviour da wir es nicht als Componente einem GameObject zuweisen möchten! Die Klasse PathNode soll zu jedem Wegpunkte alle Werte speichern die zur Pfadberechnung nötig sind. 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: using UnityEngine; using System.Collections; public class PathNode:ScriptableObject { public float fValue = 0f; public float gValue = 0f; public float hValue = 0f; public PathNode parentPathNode; public Waypoint waypoint; } Damit hätten wir Schritt 1 schon erledigt! Jetzt erstellen wir die Klasse "PathFinder" einem gleichnamige C# File. using UnityEngine; using System.Collections; public class PathFinder:MonoBehaviour { } Die static Funktion die wir jetzt erstellen und 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 ArrayList. 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: 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 = new ArrayList(); 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.Count > 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 . 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 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 = (PathNode)openL[i]; index = i; } else if(pathNode.fValue > ((PathNode)openL[i]).fValue) { pathNode = (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. int index = ReturnPathNodeWithLowestFValue(openList); currentPathNode = (PathNode)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. ArrayList neighbourWaypoints = 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: public static bool IsInCL(ArrayList closedL, Waypoint wayPoint) { bool isIn = false; for(int i = 0;i<closedL.Count;i++) { if(((PathNode)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 int IsInOL(ArrayList openL, Waypoint wayPoint) { int index = -1; for(int i = 0; i<openL.Count; i++) { if(((PathNode)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: int indexInOL = 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: 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 = new ArrayList(); openList.Add(startField); if(startWaypoint != targetWaypoint) { while(targetField == null && openList.length > 0 ) { int index = ReturnPathNodeWithLowestFValue(openList); currentPathNode = (PathNode)openList[index]; openList.RemoveAt(index); closedList.Add(currentPathNode); ArrayList neighbourWaypoints = currentPathNode.waypoint.waypointsInRange; for(int i = 0;i<neighbourWaypoints.Count;i++) { if(!IsInCL(closedList,(Waypoint)neighbourWaypoints[i]))//Wenn der Wegpunkt nicht in der closedList ist { int indexInOL = IsInOL(openList,(Waypoint)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. float GValue = currentPathNode.gValue + Vector3.Distance(currentPathNode.waypoint.transform.position,((Waypoint)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. float HValue = Vector3.Distance(((Waypoint)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. float FValue = 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. PathNode newPathNode = (PathNode)ScriptableObject.CreateInstance<PathNode>(); newPathNode.waypoint = (Waypoint)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: int indexInOL = 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 { float GValue = currentPathNode.gValue + Vector3.Distance(currentPathNode.waypoint.transform.position,((Waypoint)neighbourWaypoints[i]).transform.position); float HValue = Vector3.Distance(((Waypoint)neighbourWaypoints[i]).transform.position,targetWaypoint.transform.position); float FValue = GValue + HValue; PathNode newPathNode = (PathNode)ScriptableObject.CreateInstance<PathNode>(); newPathNode.waypoint = (Waypoint)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: float newGValue = currentPathNode.gValue + Vector3.Distance(currentPathNode.waypoint.transform.position,((PathNode)openList[indexInOL]).waypoint.transform.position); if(newGValue < ((PathNode)openList[indexInOL]).gValue) { ((PathNode)openList[indexInOL]).parentPathNode = currentPathNode; ((PazhNode)openList[indexInOL]).gValue = newGValue; ((PathNode)openList[indexInOL]).fValue = (newGValue + ((PathNode)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 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; } } 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 nochmal beide Dokumente auf einem Blick: 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; } using UnityEngine; using System.Collections; public class PathFinder : MonoBehaviour{ static public ArrayList GetPath(Waypoint startWaypoint, Waypoint targetWaypoint) { ArrayList openList = new ArrayList(); ArrayList closedList = new ArrayList(); PathNode currentPathNode; PathNode startField = (PathNode)ScriptableObject.CreateInstance<PathNode>(); startField.waypoint = startWaypoint; PathNode targetField = null; ArrayList pathArray = new ArrayList(); currentPathNode = startField; openList.Add(startField); if(startWaypoint != targetWaypoint) { while(targetField == null && openList.Count > 0) { int index = ReturnPathNodeWithLowestFValue(openList); currentPathNode = (PathNode)openList[index]; openList.RemoveAt(index); closedList.Add(currentPathNode); ArrayList neighbourWaypoints = currentPathNode.waypoint.waypointsInRange; for(int i = 0; i < neighbourWaypoints.Count; i++) { if(!IsInCL(closedList,(Waypoint)neighbourWaypoints[i])) { int indexInOL = IsInOL(openList,(Waypoint)neighbourWaypoints[i]); if(indexInOL >= 0)//Wenn der Wegpunkt in der openList ist { float newGValue = currentPathNode.gValue +Vector3.Distance(currentPathNode.waypoint.transform.position,((PathNode)openList[indexInOL]).waypoint.transform.position); if(newGValue < ((PathNode)openList[indexInOL]).gValue) { ((PathNode)openList[indexInOL]).parentPathNode = currentPathNode; ((PathNode)openList[indexInOL]).gValue = newGValue; ((PathNode)openList[indexInOL]).fValue = (newGValue +((PathNode)openList[indexInOL]).hValue); } } else//Wenn der Wegpunkt nicht in der openList ist { float GValue = currentPathNode.gValue + Vector3.Distance(currentPathNode.waypoint.transform.position, ((Waypoint)neighbourWaypoints[i]).transform.position); float HValue = Vector3.Distance(((Waypoint)neighbourWaypoints[i]).transform.position, targetWaypoint.transform.position); float FValue = GValue + HValue; PathNode newPathNode = (PathNode)ScriptableObject.CreateInstance<PathNode>(); newPathNode.waypoint = (Waypoint)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(((PathNode)closedL[i]).waypoint == wayPoint) { isIn = true; break; } } return isIn; } //////////////////////////////////////////////////////////////////////////// static public int IsInOL(ArrayList openL, Waypoint wayPoint) { int index = -1; for(int i = 0; i<openL.Count; i++) { if(((PathNode)openL[i]).waypoint == wayPoint) { index = i; break; } } return index; } //////////////////////////////////////////////////////////////////////////// static public 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 = (PathNode)openL[i]; index = i; } else if(pathNode.fValue > ((PathNode)openL[i]).fValue) { pathNode = (PathNode)openL[i]; index = i; } } } return index; } //////////////////////////////////////////////////////////////////////////// static public 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; } }

Über damuddamc's A* Pathfinding-Tutorials Wann immer in einem Spiel der kürzeste Weg zwischen zwei Positionen gefunden werden soll und Hindernisse im Weg stehen oder nur bestimmte Wege benutzt werden können, steht man als Programmierer vor einem Problem für Fortgeschrittene - sowohl mathematisch als auch der Implementierung wegen. Dabei braucht man automatische Wegfindung so oft: Sei es ein Gegner bei einem Shooter, einer Einheit in einem Strategiespiel oder vielleicht sogar einem Kontrahenten in einem Wettrennen - immer muss dem Spiel beigebracht werden, wie es den kürzesten, schnellsten oder anderweitig besten Weg findet. @damuddamc's Tutorialreihe beschreibt Schritt für Schritt, wie einer der bekanntesten und beliebtesten Pathfinding-Algorithmen nicht nur funktioniert, sondern auch in Unity verwendet werden kann. A* Pathfinding - Teil 1 Grundfunktionsweise des A* Algorithmus A* Pathfinding - Teil 2 Erstellen eines Wegpunktesystems in Unity A* Pathfinding - Teil 3 Umsetzung des A* Algorithmus in Unity mittels JS Ein großes Dankeschön an dieser Stelle an @damuddamc für die ausführlichen Schilderungen der Abläufe vor und hinter der Fassade.