Pfadnetzwerke in Unity: KI-Wegfindung mit C# implementieren

Einführung in Pfadnetzwerke für die Spielnavigation

In der modernen Spieleentwicklung ist die künstliche Intelligenz (KI) von Gegnern oder NPCs ein zentrales Element. Eine der wichtigsten Aufgaben ist die Wegfindung (Pathfinding) – die Fähigkeit eines Agenten, sich durch eine virtuelle Umgebung zu bewegen, ohne mit Hindernissen zu kollidieren. Während Raster-basierte Ansätze oft zu viele Zellen und unzugängliche Bereiche erzeugen, bieten Pfadnetzwerke (Path Networks) eine elegante Lösung: Sie diskretisieren den kontinuierlichen Raum in wenige Knoten und Kanten, erlauben dem Agenten aber, sich frei zwischen diesen Knoten zu bewegen. Dieses Tutorial zeigt dir, wie du ein solches Pfadnetzwerk in Unity mit C# implementierst – exakt abgestimmt auf typische Aufgaben aus dem Studium der Spielentwicklung.

Grundlagen: Was ist ein Pfadnetzwerk?

Ein Pfadnetzwerk besteht aus Pfadknoten (Path Nodes) und Kanten (Edges). Eine Kante zwischen zwei Knoten A und B existiert nur, wenn:

Kein Hindernis oder keine Begrenzungswand die direkte Sichtlinie blockiert.
Ausreichend Platz auf beiden Seiten der Kante vorhanden ist, sodass ein Agent (mit einem bestimmten Radius) entlang der Linie navigieren kann, ohne mit Hindernissen zu kollidieren.
Beide Knoten innerhalb der navigierbaren Fläche und außerhalb von Hindernissen liegen.

Kanten sind ungerichtet: Wenn es eine Kante von A nach B gibt, muss es auch eine von B nach A geben. Zudem darf keine Kante zu sich selbst führen, und Duplikate sind zu vermeiden. Klingt einfach? Die Herausforderung liegt in der effizienten Überprüfung dieser Bedingungen, besonders bei vielen Knoten und komplexen Polygon-Hindernissen.

Projektaufbau und Vorbereitung

In der typischen Unity-Aufgabe (z.B. aus einem Kurs wie CS7632) erhältst du eine Szene mit vordefinierten Pfadknoten und Hindernissen. Deine Aufgabe ist es, die Methode Create() in der Datei CreatePathNetwork.cs zu implementieren. Die Methode erhält Parameter wie den Ursprung und die Größe der navigierbaren Fläche, eine Liste von Hindernissen (als Polygone), den Agentenradius sowie die Pfadknoten. Dein Code muss die Liste der gültigen Kanten (pathEdges) befüllen.

Wichtige Unity-Konzepte

Bevor wir loslegen, stelle sicher, dass du mit folgenden Konzepten vertraut bist:

Vector2: Repräsentiert 2D-Punkte.
Polygon-Klasse: Stellt Hindernisse dar; bietet Methoden wie getPoints() (Float-Koordinaten) und getIntegerPoints() (skaliert mit Faktor 1000).
DistanceToLineSegment(): Berechnet den Abstand eines Punktes zu einer Linie – essentiell für die Kollisionserkennung.

Algorithmus zur Kantengenerierung

Der Kern deiner Implementierung ist die Überprüfung jeder möglichen Kante zwischen allen Knotenpaaren. Hier ein strukturierter Ansatz:

Schleife über alle Knotenpaare (i, j) mit i < j (um Duplikate zu vermeiden).
Prüfe Sichtlinie: Stelle fest, ob die direkte Linie zwischen Knoten i und j von einem Hindernis oder der Begrenzung geschnitten wird. Nutze hierfür die Polygon-Schnittpunkttests.
Prüfe ausreichenden Abstand: Für jedes Hindernis muss der Abstand des Agenten (Mittelpunkt) zur Kante größer oder gleich dem Agentenradius sein. Berechne dazu den minimalen Abstand der Kante zu jedem Hindernispunkt (oder besser: zum Hindernis als Ganzes).
Prüfe Knotenposition: Stelle sicher, dass beide Knoten innerhalb der Begrenzung und außerhalb aller Hindernisse liegen.
Füge Kante hinzu: Wenn alle Bedingungen erfüllt sind, füge die Kante sowohl in der Liste von Knoten i als auch von Knoten j hinzu (ungerichtet).

Beispiel: Kollisionserkennung mit DistanceToLineSegment

float distance = DistanceToLineSegment(point, lineStart, lineEnd);
if (distance < agentRadius) {
    // Kollision – Kante ungültig
}

Beachte: Der Test muss für jeden Punkt jedes Hindernisses durchgeführt werden. Bei vielen Hindernissen kann dies rechenintensiv sein – optimiere durch räumliche Partitionierung (z.B. Grid oder Quadtree), falls nötig.

Erweiterung: Points of Visibility (PoV)

Ein optionaler, aber lehrreicher Zusatz ist die Generierung von Pfadknoten mittels des Points-of-Visibility (PoV)-Algorithmus. Hierbei werden Knoten automatisch an den Eckpunkten von Hindernissen platziert, und zwar in einem Abstand, der zwischen minPoVDist und maxPoVDist liegt. Die Idee: Von jedem solchen Punkt aus sind die angrenzenden Bereiche gut einsehbar, was die Navigation erleichtert. Die Implementierung erfordert zusätzliche geometrische Berechnungen (Winkelhalbierende, Versatz entlang der Normalen).

Praktische Tipps und Fallstricke

Randfälle testen: Deine Lösung sollte mit einer leeren Knotenliste, einem einzelnen Knoten oder mehreren Knoten am selben Ort umgehen können.
Performance: Für eine Szene mit 100 Knoten und 10 Hindernissen (mit je 10 Punkten) ergeben sich ca. 4950 Kantenprüfungen. Jede Prüfung iteriert über alle Hindernispunkte – das sind 4950 * 100 = 495.000 Distanzberechnungen. Das ist in Unity meist akzeptabel, aber für größere Szenen solltest du optimieren.
Debugging: Nutze Unitys Debug.DrawLine(), um Kanten visuell darzustellen. So siehst du sofort, ob deine Logik korrekt ist.

Trend-Verbindung: Pfadnetzwerke in aktuellen Spielen

Pfadnetzwerke sind nicht nur theoretisch relevant – sie werden in vielen populären Spielen eingesetzt. Denk an Battle Royale-Titel wie Fortnite oder PUBG, wo KI-Gegner (Bots) sich intelligent durch die Umgebung bewegen müssen. Auch in Open-World-Spielen wie The Legend of Zelda: Tears of the Kingdom oder GTA VI (das 2026 noch immer im Gespräch ist) kommen ähnliche Techniken zum Einsatz. Sogar KI-Assistenten in Apps wie Google Maps nutzen verwandte Konzepte für die Routenplanung – allerdings in 2D mit Straßennetzen.

Zusammenfassung

In diesem Tutorial hast du gelernt, wie ein Pfadnetzwerk in Unity aufgebaut wird, welche geometrischen Prüfungen nötig sind und wie du typische Fehler vermeidest. Die Implementierung der Create()-Methode ist eine hervorragende Übung, um dein Verständnis von KI, Kollisionserkennung und Datenstrukturen zu vertiefen. Viel Erfolg bei deiner Hausarbeit!