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.
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:
Antworten:
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.
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.
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.
quelle