Wegfindung auf einer unebenen Planetenoberfläche

16

Meine Frage ist, was der beste Ansatz wäre, um auf einer unebenen Planetenoberfläche nach Wegen zu suchen.


Hintergrundinformation

Ich habe einen Planeten aus einer Verschiebung erstellt, die 6 sphärische projizierte Ebenen abbildet. Die Ebenen bildeten zunächst einen Würfel, bevor sie in eine Kugelform projiziert wurden.

Bildbeschreibung hier eingeben

Ich frage mich, ob es möglich ist, jede "Kugel projizierte Würfelfläche" als Gitter zu verwenden und einen einfachen A * -Algorithmus zu verwenden, um die bestmögliche Route zu finden. Ich möchte auch, dass die Verschiebungshöhe berücksichtigt wird, damit der Pfad das Steigen vermeidet Berge usw. (Ich denke, dies wäre nur eine Heuristik innerhalb des A * -Algorithmus.) Eine weitere Überlegung ist, dass ich Planetenbewegung erreicht habe , indem ich die Physik-Engine von Unity3d nutze, um die Schwerkraft auf den Mittelpunkt des Planeten anzuwenden. Würde meine vorgeschlagene Lösung erfordern, dass die Bewegung der Wirkstoffe unabhängig von der Gravitationsphysik gesteuert wird?

Um meine Frage besser formulieren zu können, ist dies mein aktueller Planetenkörper:

Bildbeschreibung hier eingeben

Caius Eugene
quelle
2
Dieses Video von Planetary Annihilation könnte Sie interessieren . Sie scheinen dasselbe zu tun, als würden Sie die Welt von einem Würfel umhüllen und einen Pfad finden. Es ist keine wirkliche Antwort, aber Sie können sehen, dass sie A * zusammen mit einigen anderen Strategien zur Optimierung der Wegfindung auf einer Kugel verwenden. Das Wegfindungsbit beginnt um 24:30 Uhr .
MichaelHouse
@Byte56 Danke für diesen Link, wirklich interessante Herangehensweise an die Kosten, ich kann es kaum erwarten, das Spiel zu sehen, wenn es fertig ist!
Caius Eugene

Antworten:

12

Anscheinend haben Sie Ihre eigene Frage bereits beantwortet. Ein * ist wahrscheinlich der beste Ansatz. Ja, natürlich kann es so verwendet werden, wie Sie es beschreiben, einschließlich der Höhenangaben, um Berge zu vermeiden. Solange Sie auf Informationen zu einem Raster auf der Oberfläche Ihrer Welt zugreifen können, können Sie diese nicht in der A * -Heuristik verwenden.

Schließlich verwechseln Sie die Suche nach Pfaden mit der Suche nach Pfaden am Ende Ihrer Frage. Bei der Pfadsuche spielt die Schwerkraft keine Rolle, es sei denn, Sie fügen sie als Heuristik hinzu. Da Sie sich auf der Oberfläche eines Planeten befinden, ist die Schwerkraft über die gesamte Oberfläche im Wesentlichen gleich. Viele Spiele haben Schwerkraft zusammen mit Bewegung, ich sehe keinen Grund, warum Sie nicht können.

Grundsätzlich wollen wir von rot nach blau abbilden, um auf einer Kugel genauso zu sein wie auf einem Würfel.

Bildbeschreibung hier eingeben

Da A * häufig Nachbarn zu seinem aktuellen Knoten abruft, können Sie auf einfache Weise eine Reihe von Funktionen zum Abrufen benachbarter Knoten erstellen. Zum Beispiel getXPlus(), getXMinus(), getZPlus()und so weiter. Diese Funktionen übernehmen den aktuellen Knoten und geben den Knoten in der durch den Funktionsnamen angegebenen Richtung zurück.

Meistens können diese Funktionen nur einen Wert inkrementieren und an den Kanten ausgeführt werden, die sich ändern.

Sie möchten die Oberfläche Ihres Würfels einem 2D-Koordinatensystem zuordnen. Wie auch immer Sie dies tun, sie müssen sich nicht aneinanderreihen, sondern geben jedem Rasterplatz eine eindeutige X-, Y-Koordinate.

Wenn Sie sich nun an einer Kante befinden und den angrenzenden Gitterbereich erhalten, müssen Sie nicht nur die Koordinaten erhöhen. Wir müssen herausfinden, zu welchem ​​Gesicht wir uns bewegen und zu den Koordinaten dieses Gesichts wechseln.

Wenn Sie hier beispielsweise die XPlus-Koordinate abrufen, werden sowohl die X- als auch die Y-Koordinate geändert, da wir auf einer neuen Fläche in einen neuen Rasterraum wechseln. Die grüne Linie repräsentiert eine Kante zwischen zwei Flächen.

Bildbeschreibung hier eingeben

Da es sich nur um globale Koordinaten handelt, ist es möglicherweise einfacher, ein internes lokales Koordinatensystem mit einer dritten Dimension zu verwenden, die die Würfelfläche darstellt, auf der Sie sich gerade befinden.

In beiden Fällen müssen Sie für jeden Rasterraum auf der Fläche des Cubes eine eindeutige Koordinate haben. Das Verfahren zwischen ihnen hängt davon ab, wie Sie das Koordinatensystem implementieren. Sie müssen wissen, wo diese Koordinate auch auf die Oberfläche der Kugel abgebildet wird.

All dies sollte irgendwann weggezogen werden, damit Sie nicht einmal darüber Bescheid wissen.

MichaelHouse
quelle
Prost für die Antwort. Ich denke, ich kämpfe damit, dass jedes Flugzeug ein isoliertes Gitter ist. Haben Sie Vorschläge (oder weitere Informationen) zum Umgang mit den Nähten? Ich schätze, ich werde meinen "Würfel" mathematisch aufklappen, alle Gitter kombinieren und den Pfad anhand dieses Datensatzes berechnen.
Caius Eugene
Wirklich, es sind nur die Kanten, um die Sie sich sorgen müssen. Das lässt sich leicht durch eine Wrapper-Funktion lösen (Einwickeln Ihres Cubes in eine Wrapper-Funktion, die Ihre Welt einwickelt ...). Sie können den Würfel in eine flache Oberfläche abstrahieren, die sich umhüllt. Erstellen Sie Funktionen zum Abrufen des angrenzenden Rasterraums. Mit getXPlus () wird das Raster in der XPlus-Richtung abgerufen. Es spielt keine Rolle, ob es sich an der Grenze zwischen Flächen befindet. Die Funktion wechselt nur die Flächen und gibt die entsprechenden Rasterinformationen zurück.
MichaelHouse
Die einzige Ungenauigkeit bei der Pfadfindung auf dem gefalteten Würfel besteht darin, dass die Scheitelpunkte schief sind und die Kanten daher unterschiedliche Längen haben. Es ist möglich, dass die resultierenden Pfade dadurch nicht merklich verändert werden und Sie die Längen einfach berücksichtigen können.
Danijar
1
Das Wichtigste, was hier zu verstehen ist, ist, dass A * nicht unbedingt in einem Flugzeug operiert. es arbeitet mit einem Graphen. Obwohl innerhalb jeder Würfelfläche die Knoten in einem Raster angeordnet und verbunden sind, gibt es auch Knotenverbindungen über die Kanten des Würfels.
Jmegaffin
1
@Byte56 Danke für die großartige Antwort, ich habe angefangen, eine Lösung zu implementieren, aber ich bin ein bisschen blockiert. Vielleicht habe ich falsch verstanden. Ich habe eine Frage zu stackoverflow gestellt, da ich das Gefühl hatte, dass es sich eher um ein Mathematik- / Programmierproblem handelt. Stackoverflow.com/questions/16089074/…
Caius Eugene