Navigation Meshes, Pfadkorridore und lokale Kollisionsvermeidung

Eine Route ist keine Bewegung

Eine erfolgreiche Pfadabfrage heisst nicht, dass ein Agent jede vom Spiel verlangte Bewegung auch ausführen kann. Die Navigation beschreibt, wo Fortbewegung erlaubt ist, die Steuerung (Steering) wählt die unmittelbare Richtung, und die Fortbewegung (Locomotion) setzt diese Wahl um. Diese Zuständigkeiten sollten getrennt untersucht werden, bevor ein Mesh wiederholt neu aufgebaut wird, um ein Bewegungsproblem zu lösen.

Korridore und Kollisionsvermeidung

Detour stellt einen Pfad als Polygonkorridor dar, der sich anpassen kann, wenn sich Agent und Ziel bewegen. Lokale Aktualisierungen sind begrenzt und können eine Neuplanung erfordern. [1] Die lokale Kollisionsvermeidung (Avoidance) passt die aktuelle Geschwindigkeit an, um Nachbarn auszuweichen. Godot trennt seinen Avoidance-Raum ausdrücklich von Navigation Meshes und von der Physikkollision; ein Avoidance-Radius beschreibt den Avoidance-Körper. [2]

Durchgerechnetes Beispiel

Angenommen sei ein beispielhafter kreisförmiger Agent mit Radius 0.3 m, der sich einer 0.5 m breiten Tür nähert. Sein Durchmesser beträgt 0.6 m, die physische Öffnung ist also zu schmal, auch wenn ein Pfad entlang der Mittellinie hindurchführt. Andere Steering-Prioritäten können den fehlenden Platz nicht schaffen. Die Navigationsrepräsentation muss zu den Bewegungsmassen des Agenten und dem erforderlichen Spielraum passen.

Wird die Tür auf 0.9 m verbreitert, passt ein solcher Agent geometrisch hindurch, zwei Agenten können jedoch nicht nebeneinander passieren, da ihre Durchmesser zusammen 1.2 m ergeben, noch ohne Spielraum. Nähern sich Agenten aus entgegengesetzten Richtungen, können lokale Geschwindigkeitsanpassungen sie blockieren. Eine Reservierung, eine Vorrangregel oder eine alternative Route ist eine Lösung für diesen Engpass auf Gameplay-Ebene. Sie sollte explizit umgesetzt werden und nicht in einem wachsenden Avoidance-Radius versteckt sein.

Praktisches Vorgehen

Radius, Höhe, Neigung und Stufenfähigkeit des Agenten sind zusammen mit den Einstellungen für den Navigationsaufbau festzulegen. Zuerst wird eine Route ohne Hindernisse getestet. Danach werden die gewählten Polygone, das Steering-Ziel, die bevorzugte Geschwindigkeit, das Ergebnis der Avoidance und die tatsächliche Verschiebung in unterschiedlichen Farben visualisiert.

Die tatsächliche Bewegung ist in den Zustand der Pfadverfolgung zurückzuführen. Es ist festzulegen, wann eine veränderte Tür, ein entferntes Polygon, ein Teleport oder anhaltend fehlender Fortschritt eine Routenprüfung oder Neuplanung auslöst. Ein gewünschtes Ziel kann auf eine erreichbare Fläche projiziert werden; dabei ist zu melden, ob der Agent das gewünschte Ziel erreicht hat oder nur diesen Ersatz.

Grenzen und Diagnose

Avoidance garantiert keinen globalen Fortschritt, löst nicht jedes Gedränge und repariert keine Route durch einen blockierten Korridor. Umgekehrt kann eine teure Neuplanung in jedem Frame einen Fehler in Steering oder Locomotion verdecken. Kosten der Routenabfrage, Kosten der Avoidance, Wartezeit und Abschluss sind getrennt zu erfassen.

Getestet werden sollten enge Durchgänge mit Gegenverkehr, bewegliche Ziele, gemischte Agentengrössen und dynamische Sperrungen. Kollisionsgeometrie, Navigationsfreiraum und Avoidance-Abmessungen sind bewusst konsistent zu halten, ohne anzunehmen, dass es sich um dieselbe Einstellung handelt. Verlangt das Spiel Warteschlangen oder Vorrang, ist diese Regel explizit umzusetzen und in den Debugging-Werkzeugen sichtbar zu machen.

Quellen

[1] Path corridor reference — Recast Navigation contributors.

[2] Using NavigationAgents — Godot Engine documentation.