Navigation Meshes
Obwohl der Begriff Navigation Mesh sehr viele Interpretationen offen lässt, hat er sich vor allem für eine Art der Darstellung des begehbaren Bereiches einer statischen Welt durchgesetzt, und zwar für eine die auf Dreiecken basiert. Wie uns die Computergrafik lehrt, kann man jede beliebige Oberfläche, und vor allem jedes beliebige Polygon in viele oder (zum Glück meistens) wenige Dreiecke zerlegen. Für alle nicht flug- und tauchfähigen Wesen reicht eine Oberfläche auch aus um den begehbaren Bereich eines Wesens darzustellen und somit auch um diverse Pathfinding-Algorithmen anzuwenden. Navigation Meshes dienen somit zur Repräsentation des begehbaren Bereiches einer allgemeinen 3D-Welt von einem Wesen welches sich primär auf einer 2-dimensionalen Oberfläche bewegt.
Inhaltsverzeichnis
Datenstruktur
Die Datenstruktur für ein Navigation Mesh sieht sehr ähnlich aus wie die Datenstruktur für ein 3D-Objekt welches wir rendern möchten. Der größte Unterschied besteht darin, dass wir hier sehr stark an den Verbindungen zwischen den einzelnen Dreiecken interessiert sind, welche uns bei der Darstellung üblicherweise eher egal sind. Wir definieren also eine Dreiecks-Struktur welche folgende Daten beinhaltet:
- Die 3 Eckpunkte des Dreiecks
- Verweise auf die Nachbardreiecke (üblicherweise 0 bis 3 an der Zahl)
Da man des öfteren auch Abfragen benötigen wird, wo man ein Dreieck zu einer bestimmten Position finden möchte, kann man diese des weiteren durch verschiedenste Raumunterteilungstechniken (wie beispielsweise Octrees) optimieren.
Anwendung
Die Verwendung von Navigation Meshes ist verhältnismäßig trivial.
Finden eines Weges
Für das finden eines Weges benötigen wir einen Start- und einen Zielknoten, sowie einen Graphen (aus Knoten mit Verbindungen bestehend). Ein Knoten ist hierbei ein Dreieck die Verbindungen sind die Nachbardreiecke. Wenn diese vorhanden sind, so können wir mit einem beliebigen Suchalgorithmus (wie beispielsweise A-Stern) unsere Welt nach einem Weg durchsuchen. Den Start-Knoten kennen wir üblicherweise, da der Start-Knoten meist die eigene Position ist wo wir laufend das Dreieck auf dem wir uns befinden aktualisieren. Beim Zielknoten kann dies bereits etwas komplizierter werden, denn hier müssen wir uns gegebenenfalls ein Ziel-Dreieck heraussuchen.
Positionsangabe -> Knoten (Dreieck)
Da wir Positionsangaben üblicherweise im 3-dimensionalen Raum angeben, und Navigation Meshes nur eine 2-dimensionale Oberfläche definieren, stoßen wir hier bereits auf ein kleines Problem: angenommen wir haben ein zweistöckiges Haus und wir wollen das richtige Dreieck finden zu dem eine 3D-Positionsangabe passt, so reicht es nicht zwingendermaßen aus zu prüfen, ob der Punkt unter oder über einem Dreieck ist um zu wissen in welchem Stock wir uns befinden. Möglicherweise gab es eine kleine Bodenrille die wir bei unserem (eher mit grober Auflösung behafteten) Navigation Mesh nicht beachtet haben, aber es könnte auch sein, dass sich das gesuchte Objekt an der Decke des Erdgeschosses befindet. Eine verhältnismäßig einfache Lösung wäre hier, dass wir voraussetzen, dass sich die Oberfläche des Navigation Meshes niemals über einem begehbaren Punkt befindet, und wenn möglich natürlich auch niemals unterhalb der Decke des darunterliegenden Bereiches.
Nebeneffekt: Kollisionsabfragen
Pathfinding (also das wofür wir Navigation Meshes verwenden) findet sehr häufig bei NPCs (Non player characters) - also Computergegnern - Anwendung. Wenn wir nun die begehbare Oberfläche (siehe Navigation mesh Generierung) so einschränken, dass ein NPC niemals an eine Wand stoßen kann und sich wenn möglich auch niemals den Kopf an der Decke anstoßen kann, so können wir auf Kollisionsabfragen für diesen NPC (mit der statischen) Umgebung verzichten, da er niemals einen Bereich betreten wird, wo er mit einem Objekt kollidieren könnte.
Die begehbare Oberfläche
Eines der größeren Probleme bei Naviagation Meshes besteht darin, zu definieren welche Bereiche begehbar sind und welche nicht begehbar sind. Die auftretenden Fragestellungen sind hierbei:
- Wie nahe kann ein NPC an eine Wand gehen? Handelt es sich um eine Maus oder um einen Dinosaurier?
- Wie hoch muss die Decke sein damit der Bereich als begehbar gilt? Wiederum die Maus verglichen mit dem Dinosaurier.
- Erstellen wir das Navigation Mesh so, dass der NPC springen kann oder so, dass er sich bereits ducken muss?
- Welche Höhenunterschiede kann der NPC bezwingen? Kann er wie eine Katze einen Meter hoch springen (wodurch ggf. sogar mehr als 3 Nachbardreiecke je Knoten nötig wären) oder hat er bereits Probleme eine Treppe hoch zu steigen?
- Wie steile Wände kann der NPC hoch steigen? Ist es eine Spinne die an Wänden hoch krabbelt?
- Wie tiefes Wasser ist für diesen NPC begehbar? Kann der NPC vielleicht sogar schwimmen?
Diese (und ähnliche) Unterscheidungen erfordern üblicherweise starke Kompromisse bei der Verwendung von Navigation Meshes für unterschiedlichste Arten von NPCs. Entweder man benötigt ein eigenes Naviagtion Mesh für viele unterschiedliche Kategorien von Lebewesen, oder aber (im Extremfall) kann ein Dinosaurier die gleichen Bereiche betreten wie eine Maus.
Es kann somit empfehlenswert sein, bei einem Dreieck (also einem Knoten) zusätzlich noch einige Werte anzugeben:
- minimale, maximale oder durchschnittliche Höhe
- exakte Höhe je Eckpunkt (Vorsicht: unter Umständen kann die minimale Höhe des Dreiecks dennoch niedriger liegen wenn die Decke in Bezug auf dieses Dreieck Unregelmäßigkeiten aufweist)
- Steigung
- Wassertiefe
- ...
Man kann natürlich auch parameter bei Verbindungen zwischen Dreiecken angeben, was beispielsweise bei der erforderlichen Sprunghöhe sinnvoll wäre.
Diese zusätzlichen Daten erfordern natürlich einen zusätzlichen Rechenaufwand zur Laufzeit (ist ein Knoten wirklich begehbar für mich) ermöglichen jedoch das schnelle erkennen, ob ein NPC klettern, springen oder kriechen muss um einen Knoten zu errechen (bzw. um sich darin fortzubwegen).
Bei der Betrachtung der begehbaren Oberfläche haben wir vorausgesetzt, dass eine Kraft existiert die uns am Boden (also auf einer 2-dimensionalen Oberfläche) hält. Im Bezug auf unsere Spinne die an den Wänden hoch krabbelt, ist dies ihr eigenes Haltevermögen. Das Abseilen einer Spinne (welches volumetrische Navigation Meshes erfordern würde) wurde nicht beachtet.
Wenn wir also unser Navigation Mesh bilden wollen, so haben wir eine Defintion von "begehbar". Zumeist hängt diese Definition mit der Gravitationskraft zusammen, also jener Kraft die uns daran hindert auf den Wänden herum zu spazieren. Wenn wir nun ein 3D-Objekt haben, von dem wir wissen wo oben und unten ist (also in welche Richtung die Graviation wirkt) und kein Dreieck von einem anderen geschnitten wird (also der Boden besteht nicht nur aus einem Rechteck sondern wird an den Wänden unterteilt), so können wir verhältnismäßig einfach alle Dreiecke bestimmen, welche eine Steigung besitzen welche wir als begehbar definieren. Die Steigung wird hierbei durch den Winkel zwischen Normalvektor des Dreiecks und dem Richtungsvektor der Gravitation bestimmt. Die Höhe welche ein bestimmter Punkt besitzt lässt sich ebenfalls bestimmen, wenn wir alle Dreiecke eines 3D-Objektes untersuchen. Ein allgemeines 3D-Objekt (wo es nicht zwingend der Fall ist, dass kein Dreieck von einem andren geschnitten wird) können wir mit einem BSP-Baum entsprechend unterteilen, obwohl hier häufig mehr Dreiecke entstehen als notwendig.
Üblicherweise empfiehlt sich bei generierten Navigation Meshes eine Nachbearbeitung durch einen Menschen, zum einen deshalb weil häufig Dreiecke zu einem größeren Zusammengefasst werden können, aber zum anderen auch weil "unsinnige" Bereiche als begehbar definiert werden (beispielsweise wird kaum jemand auf das Dach eines Hauses steigen, es sei denn es ist erwünscht).
Es ist natürlich ein verhältnismäßig aufwändiges Verfahren alle (in Hinsicht auf Begehbarkeit) gewünschten Eigenschaften eines (allgemeinen) 3D-Objektes zu untersuchen, aber da dieser Prozess nicht während der Laufzeit statt findet und somit wenig optimiert werden muss, sind diese Berechnungen ebenfalls nicht allzu schwierig.
Bisher wurden zwar auf unterschiedliche Arten von NPCs etwas eingegangen jedoch nicht darauf, wie man dynamische Objekte in einer Welt welche durch Navigation Meshes dargestellt wird beachten könnte.
Spezielle Verbindungsstücke (Tür, Lift, ...)
Spezielle Verbindungstücke wie Türen, Fenster, Lifte, (mehr oder weniger magische-) Portale, Transporter, ... können verhältnismäßig einfach in ein Navigation Mesh eingebaut werden. Zu den Verbindung von 2 Dreiecken - oder in die Dreiecke selbst - kann man Informationen einfügen welche angeben ob diese Verbindung überschritten (bzw. dieses Dreieck betreten) werden kann oder nicht, sowie auch die nötigen Handlungen (wie Tür öffnen, klettern, springen, Knopf drücken, ...) angeben.
Lediglich die bereits geöffnete Tür, oder das geöffnete Fenster (welche einen "unvorhergesehenen" Bereich des Navigation Meshes blockieren, obwohl sie dafür einen anderen Teil frei geben) fallen unter die Kategorie der "Blockierenden Objekte".
Blockierende Objekte
Wenn man jedoch Objekte so positionieren kann, dass ein Weg blockiert wird, so wird es schon etwas komplizierter. Die performance mäßig beste Datenstruktur dafür wäre üblicherweise, dass man für jedes Dreieck eine Liste der Objekte speichert die sich auf diesem Dreieck befinden. Da ein Objekt häufig mehrere Dreiecke berührt ist dies aufgrund der Redundanz und vom Speicherbedarf her jedoch üblicherweise nicht die optimale Lösung.
Begehbar oder nicht begehbar
Meistens ist es nicht wünschenswert ein Dreieck als nicht begehbar zu markieren sobald sich ein blockierendes Objekt darauf befindet, da wir damit im Unterschied zu Tile basierten Vorgehensweisen sehr schnell aufgrund eines winzigen Objektes einen ganzen Korridor versperren, es sei denn wir unterteilen unsere Welt in sehr viele kleine Dreiecke, worunter vor allem der Speicherbedarf und hin und wieder auch die Performance leidet (siehe: "Positionsangabe -> Knoten (Dreieck)" ). Häufig empfiehlt es sich jedoch auch nicht, jedes Dreieck auf dem sich Objekte befinden auf seine Begehbarkeit für einen konkreten NPC zu überprüfen, da dies eine verhältnismäßig komplexe Abfrage ist. Wir könnten beim einfügen und entfernen eines Objektes prüfen, ob dieses Dreieck noch als begehbar bewertet werden soll oder nicht, jedoch haben wir hier zur Laufzeit(!) die unter "Die begehbare Oberfläche" betrachteten Probleme zu beachten. Eine hohe Anzahl von dynamische Objekten (und vor allem häufiges hinzufügen und entfernen davon) ist somit bei Navigation Meshes nicht sonderlich ratsam.
Zusätzlich müssen wir uns ggf. noch Sorgen darüber machen, ob auch alle Verbindungen noch gültig sind. Beispeilsweise ein großer Stein der die Tür blockiert muss nicht zwangsläufig ein gesamtes Dreieck blockieren, sondern kann auch "nur" die Verbindung zum Durchgang versperren.
Kollisionsabfragen mit dynamischen Objekten
Wir erinnern uns: mit einem Navigation Mesh müssen wir uns über Kollisionsabfragen keine Sorgen mehr machen. Für dynamische Objekte trifft dies allerdings nicht zu. Hier ist es (performance mäßig) allerdings von enormen Vorteil, wenn alle Objekte welche dieses Dreieck berühren in einer Liste dieses Dreiecks gespeichert werden. Wenn wir sehr große Dreiecke im Navigation Mesh haben, so kann es sich sogar lohnen in diesem Dreieck die Objekte durch diverse Raumunterteilungstechniken (wie beispielsweise einem Octree) zu trennen.
Für Volumetrische Aktionsräume (also Pathfinding in der Luft, im Wasser als Taucher oder im All) sind Navigation Meshes nur begrenzt brauchbar. Im Endeffekt muss eine Reduzierung auf ein oder mehrere 2D-Oberflächen durchführbar sein, was beim fliegen und beim tauchen noch möglich ist, aber spätestens im All stoßen Navigation Meshes an ihre Grenzen. Obwohl auch eine 3D-Variante von Navigation Meshes denkbar wäre (mittels 3-seitigen Pyramiden), empfehlen sich üblicherweise stattdessen andere Repräsentationen der Welt.
