Jump to content
Unity Insider Forum

Teil 2: A* Pathfinder


Recommended Posts

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

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

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

 

 

So willkommen zum 2. Teil zur Umsetzung eines Wegpunktesystems in Unity und des A* Algorithmus um Pfade zu berechnen. In diesem Teil kümmern wir uns um das erstellen eines Wegpunktesystems, die Umsetzung des A* kommt dann in Teil 3.

 

Ich fange an indem ich ein neues Projekt anlege. Ich habe als erstes eine neue Plane auf Position 0,0,0 mit einer skalierung von 3,3,3 erzeugt. Auf dieser habe ich 4 Cubes platziert die ich ebenfalls in x Richtung um 5 skaliert habe. Auf diese habe ich auch noch ein dafür erstelltes graues Material gelegt um diese vom Untergrund abzuheben. Alle Cubes haben einen Boxcollider und die Plane einen Meshcollider, diese sollten standardmäßig schon vorhanden sein. Die Szene sieht nun so aus:

 

bild1vn.jpg

 

Jetzt fangen wir an die Wegpunkte zu erzeugen.

Dazu legen wir eine neue Javascript Datei an die wir Waypoint nennen.

In der neuen Datei fangen wir an eine neue Klasse zu definieren diese nennen wir wie die Datei Waypoint.

In dieser haben wir zunächst 2 Listen, einmal ein static Array Waypoints indem alle Waypoints abgelegt werden, somit ist dieses Array mit allen existierenden Waypoints über Waypoint.Waypoints erreichbar.

Die zweite Liste waypointsInRange beinhaltet alle Nachbarwegpunkte dieses Wegpunkts.

 

Zudem schreiben wir uns noch eine Funktion „addNeighbour“ über die wir einen Nachbarwegpunkt in das Array waypointsInRange einfügen können. Diese hat einen Parameter „neighbour“ vom Typ Waypoint.

 

@script RequireComponent (MonoBehaviour)
class Waypoint extends MonoBehaviour
{

static var Waypoints:Array = new Array();

var waypointsInRange:Array;

public function addNeighbour(neighbour:Waypoint)
{

	if(waypointsInRange==null)
	{

		waypointsInRange = new Array();

	}

	waypointsInRange.Add(neighbour);

}

}

 

Damit ist der Wegpunkt schon fast fertig, jetzt müssen wir ihn nur noch instanzieren. Dafür habe ich einen neuen Cube erzeugt, ihn auf 0.5, 0.2, 0.5 skaliert und ihn waypoint genannt, auf ihn lege ich das Script Waypoint. Um auch den Wegpunkt vom Untergrund abzuheben habe ich diesmal ein blaues Material erzeugt und darauf gelegt.

Jetzt machen wir uns noch am Boxcollider dieses Wegpunktes zu schaffen, wir setzen das Häkchen bei „Is Trigger“ und die Größe des Colliders setzen wir auf 6 , 1 , 6.

Zu guter letzt verpassen wir dem Wegpunkt noch einen Tag, dazu legen wir einen neuen an und nennen ihn auch Waypoint.

Danach habe ich ein neuen Prefab erstellt, dieses nenne ich ebenfalls waypoint und ziehe den eben erstellten Würfel darauf. Damit haben wir das Objekt Waypoint vollständig.

So sieht das ganze aus:

 

bild2e.jpg

 

Anschließend duplizieren wir diesen Wegpunkt so oft das in regelmäßigen Abständen, bei mir ca. alle 4 Einheiten ein Wegpunkt platziert wird. Dort wo ein Wegpunkt innerhalb eines der Objekte liegen würde wird natürlich keiner erstellt.

Alle Wegpunkte sollten kurz über dem Boden liegen.

Die Szene sollte jetzt ungefähr so aussehen:

 

bild3kt.jpg

 

Im Moment können unsere Wegpunkte noch nicht wirklich viel aber dazu kommen wir jetzt.

Wir erstelle uns ein Empty Gameobject und nennen es z.B. waypointManager, diesem Gameobject ordnen wir nun alle Wegpunkte unter.

Dieser WaypointManager bekommt auch gleich ein Script welches alle Berechnungen für die Wegpunkte zu Spielbeginn ausführen wird.

Wenn ein Level sehr groß ist und du willst die Wegpunkte noch in Abschnitte unterteilen, z.B. Raum A, Raum B etc. dann kannst du weitere Empty Gameobject erstellen und die Wegpunkte diesen Unterordnen, wichtig ist nur das diese dann auch dem WaypointManager untergeordnet werden.

 

So jetzt sind unsere Wegpunkte schön geordnet und wir können uns daran machen dem waypointManager ein Script zu geben, dafür legen wir wieder ein neues Javascript Dokument an und nennen es WaypointManager.

 

Diesmal erstellen wir keine extra Klasse.

Ersteinmal legen wir eine neue Variable an die ich „maxDistanceBetweenWaypoints“ genannt habe, sie gibt an wie weit ein Wegpunkt vom anderen maximal entfernt sein darf um ein Nachbarwegpunkt von diesem zu werden.

 

var maxDistanceBetweenWaypoints:float = 6;

 

Ich hab hier den Wert auf 6 gesetzt damit auch diagonal Wegpunkte als Nachbarn in Frage kommen können, in eurem Projekt kann man diesen Wert dann so anpassen wie es am besten zu euren gewählten Abständen zwischen den Wegpunkten passt.

 

So jetzt kommen wir dazu die Wegpunkte unter dem WaypointManager zu erkennen und in das Array Waypoint.Waypoints zu werfen, also das static Array das später von überall erreichbar ist.

Jetzt kommt vielleicht die Frage auf warum sich die Wegpunkte nicht selbst in das Array werfen, in einer Awake Funktion. Das hatte ich auch zunächst gemacht, allerdings waren dann manche schon drin, andere aber nicht als die Nachbarwegpunkte kalkuliert wurden, dadruch gabs eben haufenweise Fehler.

 

Um diesen Schritt jetzt zu erledigen schreiben wir uns eine Rekursive Funktion, also eine Funktion die sich selbst aufruft solange sie nicht ans Ziel gekommen ist.

 

Ich nenne sie „CalculateWaypoints“ und sie empfängt einen Parameter und zwar ein Transformobjekt das ich parentTransform nenne.

 

function CalculateWaypoints(parentTransform:Transform)
{

for(var child:Transform in parentTransform)
{

	if(child.GetComponent(Waypoint))
	{

		var wP:Waypoint = child.GetComponent(Waypoint);
		Waypoint.Waypoints.Add(wP);

	}
	if(child.childCount > 0)
	{

		CalculateWaypoints(child);

	}

}

}

 

Wie man sieht wird für jedes Transformobjekt „child“ in parentTransform geschaut ob es die Componente Waypoint besitz, ist dies der Fall wird diese Componente in das static Array Waypoints der Klasse Waypoint geworfen.

In der nächsten if Anweisung wird geschaut ob sich unter derm Transformobjekt child weitere Objekte befinden, also ob es ein solches überobjekt zu besseren Anornung der Wegpunkte ist.

Ist dies der Fall, gibt es also weitere Transformobjekte unter child ruft sich die Funktion CalculateWaypoints selbst auf. Mit einer solchen rekursiven Funktion kann man also eine ganze Hierachie egal wie lang und egal wie verschachtelt durcharbeiten um an bestimmte Informationen zu kommen und dabei ist völlig egal ob man weiß wie tief die Hierachie ist.

 

So jetzt haben wir die Funktion geschrieben nun muss sie noch aufgerufen werden, dazu erstellen wir nun die Funktion Awake() und rufen als erstes in dieser die Funktion CalculateWaypoints auf.

 

function Awake()
{
Waypoint.Waypoints = new Array();
CalculateWaypoints(transform);
}

 

Der Funktion wurde die transform Componente des GameObjects übergeben auf dem das Script liegt, als dem waypointManager.

Damit befinden sich jetzt alle Wegpunkte im Array Waypoints.

In der Zeile oben drüber habe ich das Array Waypoints in Waypoint neu erstellt um zu verhindern das eventuell Wegpunkte aus einem zuvor geladen Level immer noch in dem Array liegen.

 

Jetzt geht’s daran die Verbindungen zwischen den Wegpunkten zu ermitteln, also festzustellen welche Nachbarwegpunkte zu einem Wegpunkt gehören.

Dazu erstellen wir eine weitere Funktion die ich „CalculateNeighbours“ genannt habe.

 

In dieser wird für jeden Wegpunkt zunächst geschaut welche anderen in der Nähe sind und als Nachbarn in Frage kommen können.

 

function CalculateNeighbours()
{

for(var waypoint:Waypoint in Waypoint.Waypoints)
{

	for(var neighbour:Waypoint in Waypoint.Waypoints)
	{

		if(neighbour!=waypoint)
		{

			var pos1:Vector3 = waypoint.transform.position;
			var pos2:Vector3 = neighbour.transform.position;
			var deltaL:float = Vector3.Distance(pos1,pos2);

			if(deltaL <=maxDistanceBetweenWaypoints)
			{


				//Mache etwas

			}

		}

	}

}

}

 

Also die erste For- Schleife läuft jeden Wegpunkt durch, die zweite wiederum jeden um zu schauen ob ein Nachbar zu dem Wegpunkt ermittelt werden kann. Dazu wird als erstes überprüft ob der gerade kontrollierte Wegpunkt nicht zufällig der Wegpunkt ist für den die überprüfung gerade durchgeführt wird, denn ein Wegpunkt kann sich ja schlecht selbst als Nachbarn haben.

 

if(neighbour!=waypoint)

 

In dieser if Anweisung wird dann als erstes die Entfernung zwischen beiden ermittelt, dazu habe ich 2 Vectoren angelegt denen ich die Positionen der zu den Wegpunkten gehörenden Transformobjekte übergebe.

Anschließend rechne ich über Vector3.Distance deltaL also die Distanz zwischen ihnen aus.

In der nächsten If Anweisung wir dann kontrolliert ob deltaL kleiner gleich der maximal erlaubeten Distanz „maxDistanceBetweenWaypoints“ ist. Ist dies der Fall kann weiter gemacht werden.

Jetzt muss über Raycasts geschaut werden ob eventuell Objekte zwischen ihnen liegen.

 

Also der folgende Code kommt an die Stelle von „//Mach was“.

 

var hits:RaycastHit[];
hits = Physics.RaycastAll(pos1,Vector3.Normalize(pos2-pos1),deltaL);

var isWayFree:boolean = true;

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

if(!hits[i].collider.isTrigger)
{

	isWayFree = false;
	break;
}

}


if(isWayFree)//wenn der weg frei ist ist es ein begebarer nachbar
{
waypoint.addNeighbour(neighbour);

}

 

Ich habe hier keine normalen Raycast gewählt da es bei meinem Spiel Objekte gibt die sich bewegen können, d.h. das es nicht unbedingt heißen muss das der Weg nicht frei ist wenn der Raycast auf einen Collider trifft. Genau dafür habe ich RaycastAll genommen. Dieser testet jetzt von pos1 aus in Richtung von pos2 auf die Entfernung deltaL auf Kollision. Die Variable „hits“ enthält dann alle getroffenen Objekte.

Dazu hab ich mir noch eine Boolesche Variable „isWayFree „ angelegt welche mir angibt ob der Weg nun frei ist oder nicht, am Anfang steht diese auf true.

Nun gehe ich in einer weiteren For- Schleife alle alle getroffenen Objekte durch und in der if- Anweisung darunter kann ich dann auf genau solche Ausnahmen eingehen. Im Moment steht dort nur „!hits.collider.isTrigger“, also wenn der getroffene Collider kein Trigger ist dann ist der Weg nicht frei, isWayFree wird dann auf false gesetzt und die For- Schleife abgebrochen über break.

In dieser If-Anweisung könnte man sich auch noch mehrer Ausnahmen reinschreiben, z.B.

 

 if(!hits[i].collider.isTrigger && hits[i].collider.tag != "Player")

 

So jetzt hätten wir den raycast gemacht in der nächsten If- Anweisung wird jetz nurnoch geschaut ob der Weg nun frei ist oder nicht, ist er frei dann wird der neighbour dem waypoint als Nachbar zugeordnet.

 

Damit sind unsere Wegpunkte vollständig berechnet wir müssen die Funktion CalculateNeigbours() jetzt nurnoch in der Awake Funktion unter CalculateWaypoints aufrufen.

 

Hier noch mal das ganze Script auf einen Blick:

 

var maxDistanceBetweenWaypoints:float = 5;

function Awake()
{
Waypoint.Waypoints = new Array();
CalculateWaypoints(transform);
CalculateNeighbours();
}

function CalculateWaypoints(parentTransform:Transform)
{

for(var child:Transform in parentTransform)
{

	if(child.GetComponent(Waypoint))
	{

		var wP:Waypoint = child.GetComponent(Waypoint);
		Waypoint.Waypoints.Add(wP);

	}
	if(child.childCount > 0)
	{

		CalculateWaypoints(child);

	}

}

}



function CalculateNeighbours()
{

for(var waypoint:Waypoint in Waypoint.Waypoints)
{

	for(var neighbour:Waypoint in Waypoint.Waypoints)
	{

		if(neighbour!=waypoint)
		{

			var pos1:Vector3 = waypoint.transform.position;
			var pos2:Vector3 = neighbour.transform.position;
			var deltaL:float = Vector3.Distance(pos1,pos2);

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

				var isWayFree:boolean = true;

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

					if(!hits[i].collider.isTrigger)
					{

						isWayFree = false;
						break;
					}

				}


				if(isWayFree)
				{
					waypoint.addNeighbour(neighbour);

				}

			}

		}

	}



}

}

 

 

Nun haben wir zwar alle Nachbarn zu jedem Wegpunkt berechnet aber davon sehen wir nichts, um dies jetzt noch zu machen müssen wir noch mal ins Script Waypoint.

Dort fügen wir noch folgende 2 Funktionen in die Klasse Waypoint ein:

 

function Awake()
{

transform.renderer.enabled = false;

}

function OnDrawGizmosSelected ()
{

Gizmos.color = Color (0,1,1,.5);
Gizmos.DrawCube (transform.position, Vector3 (0.5,0.2,0.5));

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

	for(var neighbour:Waypoint in waypointsInRange)
	{
		Gizmos.color = Color(1,0,0,1);
		Gizmos.DrawLine(transform.position,neighbour.transform.position);

	}

}

}

 

zunächst schalten wir in der Funktion Awake die Render Componente aus denn wir wollen im Spiel ja die Wegpunkte nicht sehen.

Damit wir aber im Editor wenn wir es wollen trotzdem den Wegpunkt als Würfel gezeigt bekommen und wir die Verbindungen zwischen den einzelnen Wegpunkten sehn kommt noch die Funktion OnDrawGizmosSelected ()

Hinein.

In dieser erzeugen wir einfach einmal einen Cube um die Position des Waypoints und wir zeiechnen zu jedem Nachbarwegpunkt eine rote Linie.

 

 

Wenn wir jetzt das Spiel starten und Gizmos anzeigen lassen sehen wir wenn wir im Inspektor den Waypointmanager ausgewählt haben die Verbindungen zwischen den einzelnen Wegpunkten.

Sollten die Verbindungen nicht optimal sein verschiebe noch mal die Wegpunkte oder ändere die maxDistanceBetweenWaypoints des WaypointManagers im Inspektor.

 

bild4g.jpg

 

Zum Schluss noch eine Anmerkung. Die Trigger um die Wegpunkte sollten immer so groß sein das zwischen den verschiedenen Triggern der Wegpunkt der Abstand maximal so groß ist wie der

Collider der kleinsten Figur. Denn wenn der Platz zwischen ihnen zu groß ist kann es durch einen dummen Zufall dazu kommen das eine Figur genau zwischen ihnen durchläuft und der aktuelle Wegpunkt der in dieser dann gespeichert wird ist garnicht mehr der in dessen Nähe er wirklich steht. Also am besten die größe des Triggers bei einem Verändern und dann durch Apply drücken auf alle anderen anwenden.

 

So damit wäre das Wegpunkt System fertig, jetzt fehlt nur noch die Umsetzung des A* Algorithmus in Unity und eine KI die das gesamte nutz.

Beides wird in Teil 3 und 4 behandelt.

 

-->Weiter zu Teil 3<--

 

Stephan

Link zu diesem Kommentar
Auf anderen Seiten teilen

Schön das es klappt, aber noch was zu den Triggern, die Abstände zwischen den Triggern sollten nicht zu groß sein am besten das fast kein Haar mehr dazwischen passt :)

Da muss ich sagen hab ich im Tut nicht sauber gearbeitet :P, zumindest sollten sie kleiner sein als der Collider der kleinsten Figur.

Ansonsten könnte eine Figur zufällig genau zwischen diesen hindurchlaufen und der aktelle Wegpunkt ist garnicht der bei dem er steht.

Also einfach bei einem Wegpunkt den Trigger verändern und Applay drücken damit sich die Größe auf alle anderen auswirkt.

 

Gruß Stephan

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ich denk mal morgen oder übermorgen.... weiß aber noch nicht was die KI können soll! Irgend welche Wünsche??

Aber nix zu komplexes es soll ja schön kurz und verständlich sein.

 

Soll die KI zu einem Spieler laufen per Pfadfindung oder ehern irgendwas wie in einem strategiespiel, Figur läuft da hin wo man hin drückt??

Link zu diesem Kommentar
Auf anderen Seiten teilen

also, für mich würd reichen wenn es eine kugel wär, die dahinläuft wo man hin klickt, ODER einfach, eine kugel die einem parcour von a nach b läuft :)

 

freu mich schon ;)

 

aja, ist das normal, wenn ich die scripte Pathfinder, Waypoint und Waypoint manager hab, zeigts mir das an:

 

Assets/Pathfinder.js(38,41): BCE0005: Unknown identifier: 'ReturnPathNodeWithLowestFValue'.

 

kann mir wer helfen? ^^

 

PS: nach vergrößern der variable MaxDistanceBetween siehts jetzt besser aus :)

post-295-064777400 1302438490_thumb.gif

Link zu diesem Kommentar
Auf anderen Seiten teilen

  • 1 year later...

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...