NavMesh, A* und Flow Field: 200 Agenten ohne Stau bewegen

Zweihundert Agenten vor einem einzigen Tor

Ende des letzten Jahres arbeitete ich an einer Belagerungsszene: ein einziges Burgtor und 200 NavMeshAgent-Instanzen, die darauf zuliefen. Navigation in der Spiele-KI bricht genau in solchen Szenen zusammen. Die Aufnahme, die QA an den Nightly Build hängte, fror immer an derselben Stelle ein: fünfzehn Meter vor dem Tor rieben sich rund sechzig Agenten aneinander und zitterten, einige liefen rückwärts. In den ersten zehn Sekunden schafften es nur etwa vierzig in den Hof hinter dem Tor.

Die Frame-Zeit lag bei 11 ms, solange die Agenten weit entfernt waren, und stieg auf 26 ms, sobald sie sich dem Tor näherten. Mein erster Verdacht war, dass A* explodiert sei. Der Profiler sah das anders: NavMesh.CalculatePath summierte sich auf 3,2 ms, während das interne Update von NavMeshAgent bei 9,8 ms lag. Der Engpass steckte also nicht in der Suche, sondern in der Arbeit, die jeder Agent in jedem Frame erledigt.

Zwei getrennte Probleme zeigten sich gleichzeitig und wurden für eines gehalten: die Kosten der globalen Wegberechnung und das Verhalten der Agenten zueinander. Jede Diskussion, die beides unter eine Überschrift packt, läuft ins Leere, weil die Lösungen an völlig verschiedenen Stellen liegen. Solange man sie nicht trennt, sieht man nie, welcher Regler welche Zahl bewegt hat. Bei uns begann die Trennung mit einer Gewohnheit: die Zeile für die Suche und die Zeile für das Agenten-Update im Profiler getrennt zu verfolgen.

Worauf die NavMesh wirklich schaut

Eine NavMesh ist ein Dreiecksnetz, das aus der begehbaren Oberfläche der Szene gebacken und von jeder Kante um den Agentenradius nach innen gezogen wird. Die Fläche, auf der ein Agent laufen kann, ist also nicht der Boden, den man im Viewport sieht. Kommt ein Report über feststeckende Agenten herein, macht man zuerst das Mesh im Navigation-Fenster sichtbar und misst, wie viele Zentimeter Durchgang an der Türschwelle tatsächlich übrig bleiben. Bei der voreingestellten Voxel Size von 0,166 m habe ich mehr als einmal beobachtet, wie in engen Ecken einzelne Polygone verschwinden.

Unsere Toröffnung war 1,6 m breit, der Agent Radius 0,5 m: übrig blieb eine einzige Spur von 0,6 m, ein Agent passt hindurch, zwei nicht. Den Radius auf 0,35 zu senken sah nach der einfachen Lösung aus, ließ die Agenten aber auf der ganzen Karte in Wände clippen. Die richtige Änderung war, das Tor im Level auf 2,4 m zu verbreitern. Der Agentenradius ist keine kosmetische Einstellung, sondern die Basiseinheit der gesamten Navigation.

Die zweite klassische Falle ist ein Ziel, das außerhalb des Mesh liegt. SetDestination gibt dann false zurück und niemand prüft den Rückgabewert, oder der Pfad kommt als NavMeshPathStatus.PathPartial an, der Agent läuft zum nächstgelegenen erreichbaren Punkt und wartet dort. Von außen liest sich das als "steckt fest". Jedes Ziel mit NavMesh.SamplePosition in einem Radius von 2 m auf das Mesh zu schnappen, hat die meisten dieser Reports erledigt. Dieselbe Prüfung gehört an die Spawn-Punkte; ein Agent, der außerhalb des Mesh geboren wird, ist ab dem ersten Frame verloren.

Unstetigkeiten wie Treppen, Lücken und Durchgänge brauchen Off-Mesh-Links. Von Hand platzierte OffMeshLink-Komponenten verhalten sich deutlich vorhersehbarer als automatisch erzeugte. Bei den voreingestellten Kosten von 1.0 versuchten 140 unserer 200 Agenten, sich durch eine einzige Lücke von 1,2 m zu quetschen; costOverride auf 5.0 schob die meisten auf die längere, aber offene Route. Halten Sie beide Enden eines Links auf dem Mesh; ein Link, dessen eines Ende in der Luft hängt, wird stillschweigend ignoriert.

Die Kosten von A* und hierarchisches Pathfinding

Die Kosten von A* Pathfinding wachsen mit der Zahl der expandierten Knoten. Auf einer NavMesh mit 41.000 Polygonen dauerte eine Anfrage von einem Ende der Karte zum anderen 0,35 ms. Zweihundert Agenten, die im selben Frame fragen, wären 70 ms, aber einen solchen Ruckler bekommt man nie zu sehen: Unity stellt die Anfragen in eine Queue, der Pfad trifft drei oder vier Frames später ein, und die Agenten laufen währenddessen weiter in die alte Richtung. Das Symptom ist kein Stocken, sondern eine verspätete Kurve.

Hierarchical Pathfinding halbiert diese Kosten gleich zweimal. Man teilt die Karte in Regionen und schreibt die Übergänge zwischen ihnen als Portale in einen Graphen; die Suche läuft zuerst auf einem groben Graphen mit 30-40 Knoten (0,02 ms), danach läuft ein detailliertes A* nur bis zum nächsten Portal. Unsere durchschnittliche Anfrage fiel von 0,35 ms auf 0,06 ms, und ein vollständiger Agentenpfad wurde nie wieder in einem Zug berechnet. Der grobe Graph entsteht einmal beim Bake und wird zur Laufzeit nur aktualisiert, wenn ein dynamisches Hindernis ein Portal schließt.

Die Alternative, die wir probiert und wieder verworfen haben, war ein gemeinsamer Path Cache. Wir rundeten Ziele auf Zellen von 4 m und gaben jedem Agenten, der zur selben Zelle wollte, denselben Pfad. Gegen statische Ziele lag die Trefferquote bei 70 %, bei der Verfolgung des Spielers fiel sie auf 18 %, und die Logik zum Invalidieren fraß mehr, als der Cache einbrachte. Wir haben den Code gelöscht. Das Teilen von Pfaden lohnt sich nur dort, wo das Ziel über Dutzende Frames stillhält.

Ein einziges Flow Field für die ganze Menge

Wenn 200 Agenten dasselbe Ziel haben, ergeben 200 getrennte Suchen keinen Sinn. Ein Flow Field lässt eine einzige Kostenausbreitung rückwärts vom Ziel laufen und schreibt anschließend in jede Zelle einen Richtungsvektor, der auf den günstigsten Nachbarn zeigt. Unseres war ein Grid von 128x128 bei 0,5 m pro Zelle, ein vollständiger Rebuild dauerte 4,1 ms. Die Ausbreitung füllt alle Zellen in einem Durchgang, die Kosten sind also völlig unabhängig davon, wie viele Agenten unterwegs sind.

Entscheidend ist, dass diese 4,1 ms nur anfallen, wenn sich die Zielzelle ändert, und nicht in jedem Frame. Während der Spieler lief, passierte das drei- bis viermal pro Sekunde, also grob 14 ms pro Sekunde. Die Kosten pro Agent schrumpfen auf zwei bilineare Samples: 0,004 ms, über 200 Agenten 0,8 ms. Dieselbe Menge kostete über hierarchisches A* 12 ms.

Die Grenze ist scharf: Jedes weitere Ziel bedeutet ein weiteres Feld. Ab drei oder vier Zielen überholen Speicher- und Rebuild-Kosten das A*. Wir sind deshalb hybrid geblieben: benannte NPCs und Boss-Agenten laufen über A*, die Crowd-Simulation über das Flow Field. Beide stehen auf denselben NavMesh-Dreiecken, nur die Quelle der Richtung unterscheidet sich. Die Unterscheidung steckt im Code in einem einzigen bool, und ein Designer kann sie am Prefab umschalten.

Local Avoidance ist keine globale Navigation

RVO und das davon abgeleitete ORCA tun genau eines: Jeder Agent liest Position und Geschwindigkeit seiner Nachbarn, schneidet die zu einer Kollision führenden Geschwindigkeiten über Halbebenen weg und wählt aus dem Rest das, was seiner bevorzugten Geschwindigkeit am nächsten kommt. Der Horizont reicht ein bis zwei Sekunden weit, und von der Geometrie des Levels weiß das Verfahren nichts. Es ist eine Richtungskorrektur, keine Navigation. Lässt man einen Agenten damit allein, bringt RVO ihn nie ans Ziel.

Deshalb ist es von Anfang an falsch, von Local Avoidance eine globale Lösung zu erwarten. An einer U-förmigen Hofmauer drückt RVO den Agenten gegen die Wand, und zwei frontal aufeinandertreffende Agenten verklemmen sich. obstacleAvoidanceType auf HighQuality zu setzen behebt das nicht; es frisst nur 6,2 der 9,8 ms über 200 Agenten. Der Wechsel auf Good brachte das auf 3,9 ms, ohne dass auf Kameradistanz ein Unterschied sichtbar gewesen wäre.

Der eigentliche Gewinn lag im Feld avoidancePriority. Solange alle Agenten auf dem Standardwert 50 stehen, bleibt die Lage symmetrisch und niemand weicht aus. Eine zufällige Priorität zwischen 0 und 99 beim Spawn senkte den Stau vor dem Tor von 4,2 Sekunden auf 1,1 Sekunden. Es war eine Änderung von einer einzigen Zeile.

Dynamische Hindernisse und das Budget für Path Requests

Dynamische Hindernisse laufen über NavMeshObstacle mit Carving, aber Carving backt die Tile bei jeder Bewegung neu. Mit 12 rollenden Fässern in der Szene sahen wir regelmäßige Spikes von 5,8 ms. carvingMoveThreshold auf 0,5 m anzuheben und carveOnlyStationary zu aktivieren brachte dieselbe Szene auf 0,9 ms. Machen Sie nie etwas dauerhaft Bewegtes zum Hindernis; das ist Sache der Local Avoidance.

Der Budget-Teil ist einfach: Legen Sie die Zahl der vollständigen Path Requests pro Frame fest. Bei uns sind es 12. Die Agenten fragen in einem Intervall von 0,45 Sekunden plus einem zufälligen Versatz von 0-0,15 Sekunden, denn ohne diesen Jitter legt die Spawn-Welle jede Anfrage in denselben Frame. Ist das Budget voll, wird die Anfrage nicht verworfen, sondern rutscht in den nächsten Frame, und niemand merkt es, weil der Agent inzwischen auf seinem bestehenden Pfad weiterläuft. Messen Sie dieses Budget auf der Zielhardware; die 12, die wir auf Konsole nutzen, liegen auf dem Desktop bequem bei 30.

In dieser Szene fiel die gesamte Frame-Zeit von 26 ms auf 13,4 ms und der Anteil des Pathfindings von 13 ms auf 2,1 ms, und der billigste Gewinn darin war die einzeilige Änderung an der Priorität. Ordnen Sie die Arbeit so: zuerst die NavMesh-Geometrie mit eigenen Augen prüfen, dann ein Request-Budget pro Frame einziehen, dann die Menge auf ein Flow Field umstellen, und erst ganz zum Schluss die Einstellungen der Local Avoidance anfassen. In umgekehrter Reihenfolge verschwinden Stunden in ORCA-Parametern, während der 0,6 Meter breite Durchgang genau dort bleibt, wo er war. Ändern Sie keine Einstellung, die Sie nicht gemessen haben; jede Zahl hier stammt aus dem Profiler, keine aus einer Vermutung.