Straßen- / Flusserzeugung auf 2d Gitterkarte

12

Dies ist eine neue Frage, aber hier ist sie:

Meine Karte ist ein 2D-Raster, und ich möchte Straßen und Flüsse erzeugen. Die Route vom Start- bis zum Endpunkt muss nicht die optimale Route in Bezug auf die Anzahl der Kacheln sein. Stattdessen sollten sie ein gewisses Maß an Zufälligkeit (Turns) aufweisen.

Gibt es einen Standardalgorithmus für solche Dinge?

Prost!

AKTUALISIEREN:

Dies ist das Ergebnis des Spielens mit Gewichten auf dem Gitter und der Anwendung eines Algorithmus für kürzeste Wege (Bellman-Ford) unter Verwendung der jgrapht-Bibliothek. Immerhin bin ich der Antwort von Donutz gefolgt.

http://pastebin.com/AGQGK5ik

Markos Fragkakis
quelle
Gibt es irgendwelche Hindernisse auf der Karte?
MichaelHouse
Der Fluss ist noch nicht das erste Hindernis, das gesetzt wird.
Markos Fragkakis

Antworten:

18

Sie können den optimalen Pfad mit A * erzeugen und ihn dann mit der Mittelpunktverschiebung verzerren.

Bildbeschreibung hier eingeben

Dadurch wird sichergestellt, dass Ihre Endpunkte erreicht werden, und Sie können die Zufälligkeit in hohem Maße steuern. Zum Beispiel würde ich Straßen nicht so zufällig ordnen wie Flüsse. Welche Intelligenz auch immer beim Bau von Straßen zum Tragen kommt, sie versucht in der Regel optimal zu sein.

Achten Sie darauf, dass Sie nach jeder Iteration überprüfen, ob auf Ihrer Karte Hindernisse vorhanden sind, die Sie nicht überwinden.

Eine andere Methode wäre, Perlin-Rauschen zu erzeugen, nachdem Sie den optimalen Pfad gefunden haben, und dann Ihre Punkte basierend auf dem erzeugten Rauschen zu verschieben. Verwenden Sie beispielsweise dieses Rauschen:

Bildbeschreibung hier eingeben

Dann zeige mit dem optimalen Pfad in rot und dem verschobenen Pfad in blau:

Bildbeschreibung hier eingeben

Beachten Sie, wie sich der verschobene Pfad in den dunkleren Bereichen des Rauschens "eingependelt" hat. Ebenso könnte ein Fluss durch ein Tal fließen.

Ein Vorteil der Perlin-Geräuschauswahl besteht darin, dass Sie Ihre Hindernisse berücksichtigen und im Rahmen des Algorithmus vermeiden können.

MichaelHouse
quelle
1
Wie kann man diesen Punkt basierend auf dem Rauschen verschieben?
Khoi
1
Dies hängt davon ab, wie Sie das Rauschen und die erzeugte Linie speichern. Sie können das nächstgelegene / niedrigste Rauschen senkrecht zur Linie zuerst in der Mitte, dann in den Mittelpunkten zwischen Mitte und Ende usw. finden.
MichaelHouse
3

Mit dem A * -Algorithmus können Sie auch Kacheln Werte zuweisen, die deren Eignung anzeigen. Zum Beispiel können Sie die niedrigsten Kostenwerte für Niedrigland für Flüsse, für Flachland (aber nicht für Sumpf) für Straßen zuweisen und basierend darauf generieren. Dies gibt Ihnen nicht die kürzeste Route, aber die effizienteste Route. Wenden Sie eine kleine Zufälligkeit auf Ihre Kachelwerte an und Sie können einige suboptimale Routen erhalten.

Donutz
quelle
2

Was ist, wenn die Höhe ein Faktor ist? Ich kann eine Höhenkarte mit Diamantquadrat-Algorithmus erstellen. Ich überlegte, ob ich jedem Plättchen etwas zufälliges Wasser hinzufügen und es dann durchlaufen und in niedrigere Lagen leiten sollte, bis sich alles gesetzt hatte, aber das würde sich verlangsamen und wahrscheinlich Seen bilden, keine Flüsse.

Ich dachte auch daran, Normalen für jede Fliese zu betrachten. Wenn 2 Normalen aufeinander zeigen, muss das ein Tal sein. In einem Tal würde sich Wasser ansammeln. Wenn sie in die gleiche Richtung oder voneinander weg zeigen, sammelt sich kein Wasser. Dies wäre wahrscheinlich schneller als die Iterationsmethode, würde aber möglicherweise keine Seen, sondern nur Flüsse ergeben. Ich musste damit herumspielen, um nicht zu verhindern, dass alle aufeinander zu zeigenden Kacheln in einen Fluss verwandelt wurden.

user137
quelle
Ich habe eines der Dokumente gelesen, in denen Sie jeder Kachel ein Gewicht hinzufügen können, und bestimmte Kacheln sind einfach unpassierbar.
Joe Plante