Was ist die am besten geeignete Lösung für die Wegfindung für eine sehr große prozedural generierte Umgebung?

Ich habe ziemlich viel gelesen, um die folgende Wahl zu treffen: Welche Wegfindungslösung sollte man in einem Spiel implementieren, in dem die Welt prozedural generiert wurde, von wirklich großen Dimensionen?

So sehe ich die Hauptlösungen und ihre Vor- und Nachteile:

1) Gitterbasierte Pfadfindung - Dies ist die einzige Option, für die keine Vorverarbeitung erforderlich wäre, was gut passt. Mit der Erweiterung der Welt wächst der verwendete Speicher jedoch exponentiell auf ein wahnsinniges Niveau. Dies kann in Form von Verarbeitungspfaden durch Lösungen wie den Block A * - oder Subgoal A * -Algorithmen erfolgen. Die Speichernutzung ist jedoch das schwer zu umgehende Problem.

2) navmesh - dies wäre aufgrund seiner Präzision, schnellen Pfadberechnung und geringen Speichernutzung sehr schön. Es kann jedoch eine obszöne Vorverarbeitungszeit dauern.

3) Sichtbarkeitsdiagramm - Diese Option benötigt auch eine hohe Vorverarbeitungszeit, obwohl sie durch die Verwendung schneller Vorverarbeitungsalgorithmen verringert werden kann. Dann ist die Pfadberechnung im Allgemeinen auch schnell. Die Speichernutzung kann jedoch je nach Konfiguration der prozeduralen Welt noch verrückter als gitterbasiert werden.

Was wäre also der beste Ansatz (andere, die nicht in dieser Liste aufgeführt sind, sind ebenfalls willkommen) für eine solche Situation? Gibt es Techniken oder Tricks, mit denen prozedurale unendliche Welten gehandhabt werden können?

Vorschläge, Ideen und Referenzen sind willkommen.

BEARBEITEN:

Um mehr Details zu geben, sollte man die Anwendung, von der ich spreche, als eine sehr sehr große Büroebene betrachten, in der Räume prodecuraly generiert werden. Der Algorithmus funktioniert wie folgt. Zunächst werden Räume platziert. Als nächstes Wände. Dann die Türen und später die Möbel / Hindernisse, die in jedem Raum gehen. Die Umgebung kann also sehr groß werden und viele Objekte enthalten, da neue Räume entstehen, sobald sich die Spieler der Grenze des bereits erzeugten Bereichs nähern. Dies bedeutet, dass es keine großen offenen Flächen ohne Hindernisse geben wird.

Angesichts der Tatsache, dass die Räume prozedural gebaut, Portale erstellt und dann gefüllt werden, habe ich einige Ideen.

A * funktioniert sehr gut in Navigationsnetzen und auch hierarchisch. Ich würde in Betracht ziehen, ein Wegfindungssystem aufzubauen, das auf zwei Ebenen funktioniert - erstens Raum für Raumebene und zweitens in jedem Raum von Portal zu Portal. Ich denke, Sie können dies während der Generierung zu einem erschwinglichen Preis tun. Sie müssen erst dann von Raum zu Raum gehen, wenn Sie ihn betreten. Daher ist er für Speicher- / CPU-Kosten sehr erschwinglich.

High Level A * kann durch Erstellen eines Diagramms für jedes Portal und jeden Raum erstellt werden - ein Raum ist der Knoten und der 'Pfad' oder Rand ist das Portal zu einem anderen Raum. Die Kosten für die Durchquerung haben einige Optionen - sie können beispielsweise vom Mittelpunkt des Raums zum Mittelpunkt des anderen Raums reichen. Oder Sie möchten bestimmte Kanten von Portal zu Portal mit realen Entfernungen erstellen, was meiner Meinung nach nützlicher ist. Auf diese Weise können Sie die Pfadfindung auf hoher Ebene von Raum A nach Raum B durchführen. Türen können geöffnet und geschlossen werden, wodurch bestimmte Pfade aktiviert oder deaktiviert werden. Dies ist für bestimmte Spieltypen hilfreich. Da es raum- / portalbasiert ist, sollte es ziemlich einfach und erschwinglich zu berechnen sein - nur Entfernungsberechnungen und Grafikbuchhaltung.

Der schwierigere Teil ist das niedrige Level A *, da es sich um ein polygonales Navigationsnetz handeln sollte. Wenn jeder Raum quadratisch ist, können Sie mit einem Polygon beginnen. Wenn Sie Hindernisse platzieren, subtrahieren Sie den belegten Bereich vom Polygon und machen Sie Löcher darin. Wenn alles fertig ist, möchten Sie es wieder in Dreiecke zerlegen und das Diagramm aufbauen. Ich denke nicht, dass das so langsam ist, wie du denkst. Der schwierige Teil besteht darin, das Schneiden von Polygonlöchern durchzuführen, was eine gute Menge an Buchhaltung für solche Dinge erfordert, aber es ist gut dokumentiert in Strukturen mit halben Kanten und etablierten Grafikbüchern für die Informatik. Sie können diese Generation auch träge in einem Hintergrunddiagramm ausführen, da Sie die A * -Ergebnisse dieses Levels erst dann benötigen, wenn sich jemand im Raum befindet. Das High-Level kümmert sich für Sie um die grundlegende Pfadplanung.

Ich weiß, dass ich die Erzeugung von Navigationsnetzen auf niedriger Ebene beschönigt habe, aber ich denke, es ist eines der Dinge, die Sie sich vorgenommen und gelöst haben, und dann ist es geschafft. Es gibt eine Reihe von Bibliotheken wie CGAL ( http://www.cgal.org ) und andere, die dieses Zeug können, aber um es wirklich schnell zum Laufen zu bringen, müssen Sie es möglicherweise selbst schreiben, damit Sie nur die Dinge haben, die Sie haben brauchen.

Alternativ können Sie jeden Raum zu einem Raster machen, und die Hindernisse füllen Teile des Rasters aus, und dann alle Standard-Rasterglättungsalgorithmen ausführen, aber ich mag Navmesh-Daten, da sie klein und schnell sind.

Hoffe das macht Sinn.

Ich werde einen Stich machen und einen hierarchischen Pfadfindungsalgorithmus wie HPA * empfehlen . Obwohl ich kein Experte für KI bin, bin ich ziemlich zuversichtlich, da Ihr Generator fast identisch mit dem in einem Spiel klingt, an dem ich arbeite , dh ich habe auch ein bisschen über dieses Problem nachgedacht.

HPA * (Hierarchical Path-Finding A *) ist eine Methode zur Optimierung von regulärem A *, indem zuerst die Karte in Bereiche gruppiert wird, die miteinander verbunden sind, und dann ein Diagramm dieser Cluster auf hoher Ebene erstellt wird. Bei der Pfadfindung wird A * (oder ein beliebiger Pfadfindungsalgorithmus) im übergeordneten Diagramm und dann in jedem der Cluster ausgeführt, die den besten übergeordneten Pfad bilden. Anscheinend wird es häufig in RTS-Spielen verwendet, in denen viele Einheiten in Echtzeit über eindeutige Pfade über eine große Karte navigieren müssen. Dies sollte Ihnen eine Vorstellung davon geben, wie effizient diese Methode ist.

Hier ist ein Bild von ihrem Papier; Das linke sind die Cluster mit Verbindungsknoten, und das rechte ist das übergeordnete Diagramm:

Zum Glück für Ihren Generator ist er aufgrund der von Ihnen platzierten Räume sehr gut für diesen Algorithmus geeignet: Dadurch erhalten Sie die Hälfte des Clusters kostenlos. Ihr übergeordnetes Diagramm besteht im Wesentlichen aus allen Türen Ihrer Räume. Was HPA * für Sie bedeutet, ist: Finden Sie die Reihe von Räumen / Türen, durch die ich gehen muss, und wie Sie durch jeden Raum in dieser Reihenfolge navigieren.

Noch ein paar nette Dinge über diesen Algorithmus:

• A * ist langsam, da es den vollständigen Pfad finden muss, bevor Ergebnisse zurückgegeben werden. Mit HPA * können Sie den übergeordneten Pfad sowie den Pfad für den ersten Raum finden, sodass Sie ihm sofort folgen und die Pfade für den Rest der Räume später verschieben können. Dadurch reagiert der Algorithmus.
• Sie können die Pfadfindungsergebnisse zwischen Türpaaren für jeden Raum zwischenspeichern, da Pfade, die in diesem Raum verlaufen, aber nicht beginnen oder enden, garantiert einem solchen Pfad folgen.
• Sie können mehrere Ebenen in dieser Hierarchie haben, obwohl dies nur für wirklich gigantische Karten nützlich ist.

Beachten Sie, dass HPA * nahezu optimal ist. Sie können leicht erkennen, warum, wenn Sie sich einen Raum mit so vielen Hindernissen vorstellen, dass es lange dauert, ihn zu überwinden. Aus dem gleichen Grund sollten Sie darauf achten, ob ein Raum über genügend Hindernisse verfügt, um ihn effektiv zu unterteilen. Behandeln Sie diesen Raum im übergeordneten Diagramm nicht als einzelnen Cluster.

Für einige andere mögliche Algorithmen können Sie diese Frage in cstheory.SE ausprobieren , in der eine Tonne davon aufgelistet ist.