Prozedurale Fluss- oder Straßenerzeugung für unendliches Gelände

28

Ich sollte Wege sagen, keine Straßen, da ich eher mittelalterlich denke. Auch nicht auf der Suche nach Realismus. Die Antwort, nach der ich suche, wird darin bestehen, in die Form zu passen, die ich beschreibe, und nicht in den Realismus.

Ich suche nach einer Methode, um prozedurale Straßen / Flüsse auf kurvige Weise zu erzeugen, aber ich möchte dies für ein System mit unendlichem Gelände tun. Genau wie Perlin-Rauschen Blobs erzeugt, möchte ich Liniensegmente mit zufälliger Länge (möglicherweise mit unendlicher Länge) erzeugen.

Ich bin mir dessen bewusst Strategien wie die vorgeschlagene Antwort gefunden hier , aber es ist auf einer festgelegten Start- und Endpunkt an die Arbeit angewiesen ist , ich habe keine festgelegten Start- und Endpunkt haben. Ich möchte in der Lage sein, eine Funktion einfach mit beliebigen Koordinaten aufzurufen und zurückgeben zu lassen, ob die spezifischen Koordinaten Teil des Flusses / der Straße sind.

Ich möchte nicht, dass Terrain im Voraus generiert wird. Dazu gehört eine Höhenkarte (wie sie für Regensimulationen oder ähnliches verwendet wird). Ich möchte auch keinen Start- / Endpunkt benötigen.

Gibt es einen solchen Algorithmus oder eine Änderung an einem Rauschalgorithmus, die jemand kennt, um das zu erreichen, was ich zu erklären versuche?

Der nächste Punkt, zu dem ich bisher gekommen bin, sind mehrfach gekämmte Fraktale, wenn ich den Namen richtig verwende. Ich nehme nur den absoluten Wert von Wertrauschen (vorausgesetzt, es wird auf -1 bis +1 skaliert) und setze einen Schwellenwert. Mein Hauptproblem dabei ist, dass sich die Linien viel zu oft überlappen, meistens kreisförmig sind, manchmal zu großen Seen zusammenlaufen, was ordentlich, aber unerwünscht ist, und oftmals die Dicke der Linien zu stark variiert.

Hier ist ein Bild von dem, was ich bisher in 2D habe, aber mit einer sehr hohen Frequenz, um mehr Details zu zeigen:

Bildbeschreibung hier eingeben

Mythen
quelle
Da Flüsse "fließen", kann es leicht sein, Flüsse zu bestimmen, indem Sie einfach Lärm verwenden, um den Ursprungspunkt zu bestimmen. Danach können Sie einfach Ihre Höhenkartendaten verwenden, um den Pfad zu bestimmen.
Krieg
straßen könnten allerdings etwas anspruchsvoller sein, ich dachte darüber nach, straßen auf der grundlage der nutzung zu bauen, wenn ein spieler / alle spieler regelmäßig über ein gelände gehen, wird es zu einem weg.
Krieg
1
@ user19142 OK, dann kein Duplikat. Sie können einen gewissen Nutzen aus dieser Frage / Antwort finden auch: gamedev.stackexchange.com/questions/53400/... Und ich werde die bisherigen Links wieder schließen als „related“ gamedev.stackexchange.com/questions/45403/... gamedev. stackexchange.com/questions/29044/... gamedev.stackexchange.com/questions/31263/...
Michael
4
Ich denke, Straßen werden nicht sehr glaubwürdig sein, wenn sie mit Lärm erzeugt werden. Straßen entstehen durch Intelligenz statt durch Physik und Zeit. Obwohl sie sich manchmal ähneln, sind sie so unterschiedlich, dass Sie wahrscheinlich nicht denselben Algorithmus für beide verwenden können.
MichaelHouse
1
Die Straßen in diesem Projekt waren Höhenlinien, die bestimmten Höhen folgten, sodass Sie sie möglicherweise lokal generieren konnten. Es funktionierte dort aber die Höhenkarten wurden nicht mit Perlinrauschen erzeugt.
amitp

Antworten:

11

Nur meine Idee, dies zu archivieren, ohne (viel) Vorberechnung und die Möglichkeit für eine unendliche Welt.

Das erste Element des Algorithmus ist die Verwendung von Voronoi-Diagrammen . Sie unterteilen Ihre Welt in Gitter, jedes Gitter hat eine Adresse in der Form (xgrid, ygrid). Für jede Zelle, in der Sie Straßen erstellen müssen, fügen Sie die Variablen xgrid und ygrid in eine Hash-Funktion ein, die eine Zahl CellSeed zurückgibt . Sie verwenden CellSeed als Startwert für einen Zufallszahlengenerator, der die Koordinaten der Punkte für das Voronoi-Diagramm generiert.

Jetzt müssen Sie die Kanten des Diagramms und die Knoten suchen, an denen mehrere Kanten kollidieren. Sie können die Informationen auch in einem Diagramm speichern, um den Zugriff zu vereinfachen.

Nach diesem Schritt können Sie gültige Pfade durch das Netzwerk suchen.

Für gültige Pfade können Sie jetzt die Straßen erstellen (sie haben scharfe Kanten).

Hinweis : Sie müssen auch die Koordinaten des Voronio-Diagramms für alle Nachbarzellen generieren, damit Sie keine Ränder an den Zellenrändern haben.

Wenn Sie keine scharfen Kanten möchten, können Sie den Mittelpunkt jeder Verbindung berechnen und die Richtung als Tangente für eine Bezier-Interpolation zwischen zwei Kanten im Diagramm verwenden.

Über die Verwendung von Voronoi-Diagrammen

Um stadtähnliche Straßenstrukturen zu archivieren, können die Punkte der Pseudozufallsfunktion in einem Raster ausgerichtet werden, sodass die Wege rechteckig sind.

Für mehr kreisähnliche Straßen müssen die Punkte ungeordneter sein.

Diagramm aus Wikipedia

Über die Pseudo-Zufallsfunktion werden die Positionen der Punkte für die Voronoi-Diagramme generiert

Dies kann eine normale Zufallsfunktion oder eine Hammersley-Menge für eine gleichmäßigere, nicht klumpige Verteilung der Punkte sein.

Quonux
quelle
Haben Sie Beispiele für Hash-Funktionen? Ich habe das gleiche Ziel (unendliche Welt, in der Voronoi für Straßen verwendet wird), aber ich kann anscheinend nicht verstehen, wie das gemacht werden soll. Jede voronoi lib, die ich finden kann, erwartet Koordinaten eines Begrenzungsrahmens, der den Zweck sofort zunichte macht.
BotskoNet
Nein, die Hash-Funktion dient nur dazu, der Zelle einen Startseed zuzuweisen. Kann etwas so Triviales sein wie x * prime1 + y * prime2 + z * prime3. Wenn die Primzahlen ungleich und idealerweise groß sind, sollten Sie hier mit 64-Bit-Ganzzahlen / ohne Vorzeichen rechnen. Es ist kein Problem, wenn die Bibliothek einen Begrenzungsrahmen verwendet, da Sie für jede Zelle nur alle Punkte in der Zelle plus alle Punkte der Nachbarzellen (die 8 Nachbarzellen sind) berücksichtigen müssen.
Quonux
Sie werden wahrscheinlich auf Präzisionsprobleme mit einfacher Genauigkeit stoßen, wenn die Bibliothek einfache Genauigkeit verwendet oder wenn Sie einfache Genauigkeit verwenden. Um das Problem zu umgehen, wenn die lib nur einfache Genauigkeit verwendet und Sie nicht wie folgt vorgehen: Subtrahieren Sie vor dem Konvertieren der Positionen in einfache Genauigkeit die globale Position der mittleren Zelle von ihnen, und setzen Sie diese als floats in die lib und transformieren Sie dann die Ergebnisse zurück.
Quonux
Ich habe diesen Algorithmus eigentlich nie implementiert, aber die Hash-Funktion kann tatsächlich trivial sein.
Quonux
8

Für die Erstellung von Straßen (und Städten) ist das beste Papier, das ich gefunden habe, das folgende:

Prozedurale Modellierung von Städten von Y Parish und P Müller

Dies nutzt das L-System und kann US- und EU-Straßenmuster erzeugen. Wenn Sie keine Straßen für eine ganze Stadt generieren möchten, können Sie nur die Hauptstraßen generieren. Es kann eine Höhenkarte, eine Wasserkarte und eine Bevölkerungsdichtekarte eingegeben werden.

Rak
quelle
+1 nur weil ich das Papier mochte. Passte wirklich nicht dazu, wie ich versuchen wollte, die Straßen / Wege / Flüsse zu generieren, während ich das Gelände dynamisch generierte.
Mythics
6

http://vterrain.org/Culture/Roads/ Im Abschnitt "Generieren von 3D-Straßen" finden Sie einige Informationen zur Straßengenerierung .

Das Problem bei Straßen ist, dass sie Landmarken verbinden (obwohl sie häufig dem Gelände folgen, anstatt direkt von A nach B zu gehen).

Persönlich würde ich das Terrain generieren, dann Flüsse platzieren (möglicherweise mithilfe von Erosion, siehe http://vterrain.org/Water/ Abschnitt "Hydrogeologie") und dann Städte an Orten platzieren, an denen dies sinnvoll ist (z. B. in der Nähe eines Flusses oder eines anderen Flusses) Wasserquelle oder an einem Ort, an dem Wasser mithilfe von Aquädukten oder Wassertürmen und -rohren transportiert werden kann) und schließlich Straßen zwischen Städten entstehen.

Um die Verwendung in einer prozeduralen Welt zu vereinfachen, können Sie auf dem Terrain Zwischenpunkte erstellen, an denen bei der Erstellung an dieser Stelle am wahrscheinlichsten Straßen verlaufen, und dann die Zwischenpunkte verbinden, wenn an dieser Stelle tatsächlich eine Straße erstellt wird.

Exilyth
quelle
4

Erstens sind Flüsse und Straßen sehr unterschiedlich. Straßen tendieren dazu, Isolinien zu folgen (gleiche / ähnliche Höhe) - der Grund dafür ist, dass es viel einfacher ist, auf Straßen zu fahren, die nicht viel ansteigen oder abfallen. Flüsse hingegen verlaufen senkrecht zu Isolinien / Isoklinen (bergab). Flüsse bilden sich in Becken (Ansammlungen von Bergen, die alle nach unten in ein bestimmtes Tal fließen) und neigen dazu, baumartige Strukturen zu bilden. Außerdem verlaufen Straßen häufig senkrecht zu Flüssen, um logische Brücken zu bilden. Am besten erzeugen Sie zuerst Flüsse und dann logische Straßen (dh Straßen zwischen Städten). Ich habe leider keine Zeit, näher darauf einzugehen, aber ich hoffe, das bringt Sie auf den richtigen Weg.

Es mag naheliegend erscheinen, aber schauen Sie sich Google Maps für verschiedene Geländearten und Straßen an. Sie werden ein besseres Gefühl dafür bekommen, wie sie aussehen sollten.

Gavan Woolery
quelle
1
Ich habe die Frage noch einmal geändert, um besser zu verstehen, dass ich nicht annähernd so sehr an Realismus interessiert bin wie an der Art und Weise, wie der Algorithmus funktionieren müsste. Trotzdem schätze ich die Antwort vor allem für einige der verwendeten Begriffe. Versuchen Sie, sich mein Verlangen eher als unendliche Kringel mit zufälliger Länge vorzustellen, die mit minimalen Daten erzeugt werden können (wie eine Höhenkarte).
Mythics