Pathfinding

[Plagiatus]

Pathfinding

So, nachdem ich mich jetzt lange und ausführlich damit beschäftigt habe, sind hier meine Erkenntnisse und Vorschläge:

Pathfinding is hoch individuell und projektspezifisch. Daher müssen generische Lösungen entweder sehr simpel sein, damit auf ihnen aufgebaut werden kann, oder sehr komplex, damit sie möglichst viele Anwendungsfälle abdecken. Auch gibt es viele verschiedene Möglichkeiten das ganze zu implementieren und parametrisieren, manche davon mehr aufwändig und andere weniger.

Daher also meine Vorschläge:

• Ich würde gerne zwei Ansätze implementieren:
  • Waypoints
  • Realtiv einfaches "NavMesh"
• Diese haben grundsätzlich unterschiedliche Anwendungsfälle, daher die zwei unterschiedlichen Implementationen.

Waypoints

Ein vergleichweise simples System welches die Erstellung von Wegpunkten in der Szene ermöglicht. Diese Wegpunkte können dann miteinander verbunden werden, um so die Navigation von einem beliebigen Punkt zu einem anderen beliebigen Punkt zu ermöglichen. So weit so einfach, hier sind einige Überlegungen dazu, wie diese Funktionalität erweitert werden kann:

• Wegpunkt-Gruppierungen
  • Die Wegpunkte werden in Gruppen eingeteilt. Nur wenn ein Wegpunkt mindestens zu einem anderen Wegpunkt in der gleichen Gruppe eine Verbindung hat, gilt dieser als valide.
  • Wegpunkte können zu einem Wegpunkt einer anderen Gruppe verbunden werden. Dies erlaubt so hoffentlich eine längere Navigation, selbst über Gruppen hinaus. (Anwendungsfall: Mehrere Detailebenen in den Wegpunkten, z.B. über einen Szenenwechsel hinweg, eine Minimap o.ä.)
  • Alternativ könnte eine "Detailebene" implementiert werden, diese ist allerdings glaube ich nicht so frei einsetzbar wie eine Gruppierung.
  • Die gesamte Idee ist allerdings vielleicht auch so schon etwas weit gedacht - wer einen Szenenwechsel haben möchte bei erreichen eines bestimmten Wegpunktes der sollte das wahrscheinlich besser selbst implementieren. Die Wegpunkte könnten (wenn diese die Navigation übernehmen) ein dementsprechendes Eventsystem beinhalten.
• Nicht-lineare Verbindungen
  • Splines, im besonderen Bezierkurven würden sich anbieten, damit die Bewegung nicht nur linear verläuft sondern auch Kurven gehen kann
• Automatische Navigation einer Node entlang der Wegpunkte zum Zielpunkt
  • Manipulation der Skalierung (Größe, Geschwindigkeit) entlang der Navigation
  • enweder absolut oder über physics

"Nav Mesh"

Vorneweg, die Implementierung welche mir vorschwebt ist in der Komplexität sehr reduziert um hoffentlich sowohl mir als auch dem Anwender die Nutzung ultimativ zu erleichtern. Sie ist nicht zu vergleichen mit den Fähigkeiten die z.B. das NavMesh in Unity aufweist. Daher auch der Name in Anführungszeichen, da es sich dabei nicht wirklich um ein ausgereiftes NavMesh handlen würde. Der Hauptgrund, da bin ich ehrlich, für diese "vereinfachte" Variante ist, dass ich mir nicht zutraue, in vertretbarer Zeit ein dynamisches NavMesh, welches am besten noch live und dynamisch sich an die Gegebenheiten anpasst und generierten Polygonen sich aufbaut, überhaupt geschweige denn besonders performant umzusetzen.

Ich stelle mir das wie folgt vor:

• Man definiert eine Größe für den (2D, rechteckigen) zu navigierenden Bereich
• Man definiert eine Größe der begehbaren Zonen
• Der Bereich wird daraufhin in diese Zonen eingeteilt
• In jeder Zone wird einmal beim baking gecheckt, ob eine Zone begehbar ist oder nicht. Dies wird dadurch geprüft, ob in einer gewissen (konfigurierbaren) Höhe über der Zone kein Hindernis / Objekt (Collider) ist.
• Alle Zonen welche sich eine Seite teilen, gelten als miteinander verbunden und können somit begangen werden.
  

So ist innerhalb einer Zone die Bewegung trivial (einfach linear von Punkt zu Punkt) und zwischen Zonen kann letztendlich ein kaum modifizierter A* Algorithmus angewandt werden. Auch diese Methode kann entweder den berechneten Pfad ausspucken oder ggf. die Bewegung direkt selbst übernehmen.

Mögliche Erweiterungen:

• Zonen können sich zu größeren Zonen zusammenfassen für eine schnellere Berechnung da weniger Zonen bedacht werden müssen. (Überlegung: Diese Zonen müssen evtl das gleiche Seitenverhältnis beibehalten wie die kleinen Zonen. Oder in anderen Worten, sie müssen auf jeder Seite die gleiche Menge an Zonen haben. Eventuell löst oder wenigstens verringert das die Probleme welche sonst beim stringpulling (s.u.) auftauchen können.)

• Zonen können mit Attributen (z.B. "giftig") oder Kosten versehen werden um das Pathfinding zu beeinflussen (z.B. nur Agenten welche "giftresistenz" haben gehen freiwillig durch diese Zone, oder wenn ein Umweg eine kostenintensivere Zone vermeidet)

• Die einzelnen Zonen können sporadisch erneut prüfen, ob sie noch begehbar sind, statt nur beim baking (potenzieller Konflikt mit den zusammenfassenden Zonen)

• Das Pathfinding zwischen Zonen kann verbessert werden indem man statt der einfach zu entwickelnden "Mitte-zu-Mitte über Mitte der gemeinsamen Kante" Bewegung die Bewegung durch beliebige Punkte zulässt.

  • Nachdem A* die benötigten Zellen ausgemacht hat, können wir nun einen "String Pulling" Algorithmus (z.B. Simple Stupid Funnel Algorithm) anwenden, um diesen optimierten Pfad zu finden
    
    

• Hinzufügen eines "Steering" Algorithmus, welcher Hindernisse in der Geometrie umgehen kann.

Was es NICHT beinhaltet:

• Multiagent Pathfinding
• Automatische Meshkreation über Bereiche welche nicht rechteckig und flach sind
  • besonders nicht über die vorhandene Geometrie eines Levels.
• Feingranulare Hinderniserkennung und -umgehung
• Reaktion auf sich ändernde Umgebungsbedingungen

Auf diese Weise kann man immernoch mit etwas manuellem Aufwand relativ komplexe Bewegungsmöglichkeiten erstellen, ohne dass das Mesh alles selbst automatisiert abdecken muss.

Feedback und Diskussion

Ich poste das ganze hier nicht nur, um meine Gedanken zu sortieren, sondern vorallem um Feedback zu erhalten und andere Sichtweisen und Ideen zu hören. Habe ich etwas wichtiges vergessen? Sollte ich doch lieber ein "richtiges" NavMesh implementieren weil das eigentlich so schwierig nicht sein sollte? Mache ich mir zu viel Aufwand für etwas das am Ende vielleicht sowieso niemand nutzt und sollte daher lieber nur eines von beiden Implementieren? usw.

Also, lasst mich gerne an euren Gedanken teilhaben und lasst uns diskutieren wie wir das am besten Umsetzen können.

[plojo]

Muss das NavMesh zwingend rechteckig sein? Und du sagst, es muss flach sein, wie ist das gemeint? Es sollte doch schon möglich sein, dass in einer 3D-Szene z.B. auch Treppen hinauf navigiert werden kann. Ich fände es besser, wenn wir nur eine Lösung implementieren. Für mich hört sich ein NavMesh sinnvoller an, da es die Funktionalität von denn Waypoints doch eigentlich beinhaltet, oder?

[Plagiatus]

Mit "flach" meine ich, dass ein Mesh nur zweidimensional sein darf, also keine gewölbten Flächen abdecken würde. Das würde natürlich bedeuten, dass irgendwie ein schönes, nicht flaches Terrain nicht funktionieren würde.

Und ja, das Nav-Mesh soll zwingend rechteckig sein, da die innere Aufteilung nach meinem Vorschlag auch in rechtecken (oder sogar quadraten) passieren würde. Allerdings kann man ja mehrere Nav-Meshes anlegen, solange diese eine gemeinsame Kante mit einem anderen NavMesh haben würden die als verbunden erkannt werden. So kannst du z.B. auch eine Rampe (Treppe ist etwas schwieriger, aber Treppen sind sowieso immer überraschend schwierig) anlegen welche zwei NavMeshes auf unterschiedlichen Ebenen miteinander verbindet, solange jeweils eine Kante mit der anderen verbunden ist.

In meinen Augen deckt das NavMesh nicht zwingend die Waypoints ab. Mit Waypoints kann man spezielle Punkte definieren und genau festlegen, wie man zu ihnen hin kommt, während man bei einem NavMesh einen (oder mehrere) Bereiche festlegt, auf denen man sich dynamich bewegen kann. Das NavMesh gibt also mehr Freiheiten was die Bewegung angeht, welche ggf nicht gewünscht sind.

[JirkaDellOro]

Das Waypoint-System ist besonders sinnvoll für z.B. Adventure-Games, insbesondere 2D-Adventures mit einer 3D-Anmutung. Durch Zusatzinfo an den Wegpunkten können Figuren und ihre Bewegung auch entsprechend skaliert werden.

[JirkaDellOro]

Ein solches System, dass auch im Editor erscheint, hatte ich mal rudimentär für Alida implementiert, siehe https://github.com/KohlerAl/Thesis bzw. https://kohleral.github.io/Thesis/

[plojo]

Aber man kann doch trotzdem mit einem NavMesh die Waypoints nachahmen, indem man sein NavMesh halt einfach aus engen Pfaden aufbaut (eher wie ein Spinnennetz) anstelle von großen Flächen. Wenn man nur Rechtecke verwenden kann, ist das natürlich nicht so praktisch. Ist es denn viel schwieriger, ein auf Dreiecken basierendes NavMesh zu implementieren?

[Plagiatus]

Ein NavMesh für etwas zu verwenden das auch mit einem Waypoint system gut zu lösen wäre ist ein bisschen so wie mit Kanonen auf Tauben zu schießen - geht schon, ist aber overkill. Ein NavMesh ist ein deutlich komplexeres System, sowohl für den Nutzer beim setup als auch für die Engine zum berechnen. Daher würde ich beides bereitstellen.

Einen beliebigen Polygon Bereich in Dreiecke zu zerschneiden ist weniger das Problem, und auch die Navigation durch diese Dreiecke sollte keine Probleme machen sondern exakt so funktionieren wie bei den Rechtecken. Ich bin mir nur vorallem nicht sicher, wie ich in solch einem Fall eine möglichst gute Hinderniserkennung machen können soll, so dass die Dreiecke möglichst gut um die Hindernisse herum gelegt werden. Mein Google-Fu scheint auch nicht stark genug zu sein, da ich dazu bisher auch noch keine Hilfestellungen im Netz finden konnte.

Außerdem muss man sich dann auch überlegen, wie man diese Bereiche definiert, wenn nicht über eine simple Rechteckige Auswahl.

Randnotiz: Wenn man das ganze über Dreiecke aufbaut, dann könnte man sich überlegen, letztendlich jedes existierende Mesh als Grundlage für die Navigation nutzen zu können. Allerdings kommen dann wieder weitere Überlegungen ins Spiel wie "Kletterfähigkeiten" (wie steil kann ein Agent den Berg hoch laufen?) oder "wo ist eigentlich oben und ist das überhaupt wichtig?" welche es immer schwieriger machen ein allgemeines NavMesh zu entwickeln ohne es übermäßig zu verkomplizieren.

[Plagiatus]

Um das ganze in Dreiecke aufzubauen könnte man das oben genannte Verfahren anwenden: Aufteilung der Fläche in ein kleinrasteriges Gitter / Zonen, check jeder Zone auf Begehbarkeit, auf Basis dieser Flächen die gesamte begehbare Fläche aufbauen und dann in Dreiecke aufteilen.

[Plagiatus]

Aber jetzt, da ich auch bei der Gizmoimplementierung die ich für die NavMesh Implementierung haben wollte, auf Hürden stoße, setze ich mich zunächst an die hoffentlich leichtere Umsetzung der Wegpunkte.

Gibt es noch Vorschläge und Feedback zu der konkreten Implementation dieser? Besonders auch zu den Vorschlägen Zwecks Gruppierungsmöglichkeiten, Splines und autonomer Bewegung.

[JirkaDellOro]

Wegen dem Handling im Editor kannst Du dich vielleicht schon am Beispiel oben etwas orientieren. Hast Du mal reingeschaut? Ich habe dafür damals einiges bezüglich Listendarstellung angepasst.