Erzeugen Sie prozedural Regionen auf der Insel

29

Ich habe derzeit Inseln, die so aussehen:

Insel

Und ich möchte es prozedural in folgende Regionen unterteilen:

Insel mit Regionen

Welcher Algorithmus macht was ich suche? Haben Sie Vorschläge, wie Sie kohärente Regionen wie im unteren Bild erstellen können? Deine Hilfe wird wertgeschätzt.

domisum
quelle
Wie sind Sie überhaupt auf dieses Inselbild gekommen? Haben Sie es erstellt und wenn ja, wie haben Sie es erreicht?
Vaillancourt
Ich habe es von einem Online-Kartengenerator erhalten.
Domisum
Entschuldigung für die Verzögerung bei der Aktualisierung meiner Antwort - es dauerte länger als ursprünglich geplant nach Hause zu kommen. Ich habe ein paar Illustrationen und Links hinzugefügt.
Pikalek
Wenn Sie dies von einem Online-Generator erhalten haben, sollten Sie sich den Fantasy Map Generator von Azgaar ansehen . Es hat Regionen und Namen mit anpassbaren Parametern, und WB.SE lässt grüßen. Es ist ein Github, so dass Sie möglicherweise ihren Code überprüfen können.
Anoplexie - Wiedereinsetzung von Monica

Antworten:

40

In der realen Welt folgen diese Provinzgrenzen häufig geologischen Merkmalen wie Flüssen.

Ein guter Ansatz wäre es also, die Geologie der Insel zu modellieren und die Grenzen herauszufallen.

Red Blob Games hat einige gute Artikel zu diesem Thema mit gut aussehenden Ergebnissen.

Sein Ansatz scheint die Verwendung der Voronoi-Tessellation zu beinhalten und die Flüsse als die Grenzen zwischen den Zellen zu definieren.

Schauen Sie sich die anderen Artikel auf seiner Website an, er hat viel über das Thema Kartengenerierung geschrieben .

Insel

Bram
quelle
3
Beachten Sie, dass in der realen Welt politische oder administrative Abteilungen manchmal auch willkürliche Abteilungen haben, normalerweise gerade Linien (z. B. entlang von Breiten- / Längengraden, Linien zwischen Berggipfeln usw.).
Pablo H
2
@PabloH Guter Punkt, obwohl gerade Grenzen postmediales Phänomen der Kolonialzeit zu sein scheinen. Aber da wir die Einstellung des OP-Problems nicht kennen, könnte es relevant sein
Sentry,
27

Ich würde dieses Problem mit zwei Durchgängen von Voronoi-Diagrammen lösen:

Erster Durchgang: Region Partitioning

Der erste Durchgang würde eine etwas spärliche Punkteverteilung verwenden (dh der Abstand zwischen den Punkten sollte relativ groß sein), um die Insel grob in Regionen zu unterteilen (siehe den Hinweis zur Punktgenerierung weiter unten). Erstellen Sie als nächstes ein Voronoi-Diagramm auf der Grundlage dieser Punkte. Dies unterteilt die Insel in polygonale Regionen um jeden Punkt, wie unten gezeigt:

Bildbeschreibung hier eingeben

Zweiter Durchgang: Randomisierung

Nachdem die Insel nun in Regionen unterteilt wurde, besteht der nächste Schritt darin, die Grenzen zwischen ihnen zu "verschärfen". Erstellen Sie dazu eine neue Ebene von Punkten mit einer kompakteren Punkteverteilung (dh der Abstand zwischen den Punkten sollte klein sein) und verwenden Sie diese Punkte erneut, um ein weiteres Voronoi-Diagramm zu erstellen. Ordnen Sie es als Nächstes für jede kleinere Region einer größeren Region zu, indem Sie den Startpunkt überprüfen. Dies führt zu zackigeren Grenzen zwischen den größeren Unterteilungen. Hier ist eine Nahaufnahme davon, wie es mit beiden Voronoi-Diagrammen aussieht:

Bildbeschreibung hier eingeben

Und hier ist derselbe Bereich, der nur die letzten Grenzen zeigt:

Bildbeschreibung hier eingeben

Kommentare zu Point Generation

In Bezug auf die Punktgenerierung verwende ich gerne eine Poisson-Verteilung , um eine relativ schöne und gleichmäßige Punkteverteilung zu erzielen. Die andere gebräuchliche Option für eine ähnlich gleichmäßige Verteilung ist die Verwendung des Lloyd-Algorithmus für eine Reihe von "regulären" Zufallspunkten. LLoyd's ist einfacher zu codieren, kann jedoch mit einigem Aufwand ermittelt werden, wie viele Durchgänge erforderlich sind, um das gewünschte Ergebnis zu erzielen.

Ein mögliches Problem bei diesem Ansatz besteht darin, dass die Partitionierung im ersten Durchgang einige sehr kleine Bereiche erzeugen kann. Wenn Sie sie nicht in Ihrem Endergebnis haben möchten, würde ich sie einfach mit einer zufälligen angrenzenden Region zusammenführen.

Schlussbemerkungen

Die Illustrationen, die ich zur Verfügung gestellt habe, sind Rasterbilder, aber diese Technik funktioniert auch mit polygonalen / vektordarstellungen.

Pikalek
quelle
1
Für prozedurale Grundrisse ist dies das, was ich tue, mache ein Voronoi-Diagramm von Punkten innerhalb der Region (der Insel), konstruiere ein Gitter (es muss nicht rechteckig sein, in deinem Fall ein deformiertes Gitter), das dieselbe Region einschließt. Berechnen Sie dann die booleschen Schnittpunkte des Gitters und des Voronoi, berechnen Sie die Flächen und ordnen Sie sie einem Datenbaum (Liste mit Listen, gezackten Arrays usw.) zu, je nachdem, welche Datenstruktur Sie bevorzugen. Sie erhalten einige fehlende Zellen, aber Sie können Ihr aussortiertes Gitter mit dem Original vergleichen, um Ihren Baum zu finden und ihm neu zuzuordnen.
Felipe Gutierrez
Sie haben Bilder hinzugefügt! Genau das tue ich für einen anderen Zweck
Felipe Gutierrez
4

MineCraft macht das gut und sein Algorithmus zur Welterzeugung wurde gründlich analysiert und dokumentiert.

Es gibt verschiedene Beschreibungen des Algorithmus, eine davon hier: https://github.com/UnknownShadow200/ClassiCube/wiki/Minecraft-Classic-map-generation-algorithm

Der Kern des Algorithmus ist ein Perlin-Rauschgenerator . Dies steuert die Höhe direkt (mehr oder weniger, da der nachfolgende Schritt zum Herausschneiden von Höhlen auch die Oberfläche verändern kann) sowie die Erzeugung von Biomen. So etwas wie der Biome-Generator ist wahrscheinlich das, was Sie zum Erstellen Ihrer Bereiche verwenden möchten.

(Eine alte Version davon) ist dokumentiert , im Grunde funktioniert es, indem zwei verschiedene Perlin Noise-Generatoren verwendet werden, einer für "Temperatur", einer für "Niederschlag", und dann das Biom aus diesen beiden ausgewählt wird. Die Variablen selbst (Temperatur und Niederschlag) werden später im Spiel nicht wirklich verwendet. Wüsten haben zum Beispiel keinen Regen, aber das Spiel bestimmt dies anhand der "Wüste" -Eigenschaft, nicht anhand des ursprünglichen Niederschlagswerts.

Es gibt verschiedene Online-Tools, um eine Biom-Karte aus einem zufälligen Samen zu generieren . Eines davon ist mineatlas.com . Ich vermute, dass sie intern einen Java-Server verwenden, der die internen Klassen von MineCraft selbst verwendet; Ich weiß nicht, ob der Quellcode direkt verfügbar ist.

Guntram Blohm unterstützt Monica
quelle
4

Ein typischer Algorithmus, der beispielsweise von Azgaar ( Quellcode ) verwendet wird. Ist ungefähr so:

  1. Teilen Sie Ihre Landmasse in kleinere Bereiche auf, z. B. durch delauny Triangulation oder Voronoi-Zellen.
  2. Bestimmen Sie (zufällig oder auf andere Weise) "Startorte" für Ihre Kulturen, Bereiche, Religionen oder was auch immer Sie simulieren möchten.
  3. Bestimmen Sie (zufällig oder auf andere Weise) einen "Wachstumsfaktor" für jeden von ihnen. Je mehr unterschiedliche Wachstumsfaktoren Sie haben, desto weniger einheitlich ist Ihre endgültige Karte.
  4. Nun iterieren Sie über Ihre Bereiche (usw.) und verteilen sie je nach Wachstumsfaktor auf leere Kacheln in der Umgebung, bis die gesamte Karte gefüllt ist.
  5. Wahrscheinlich möchten Sie die Ränder ein wenig glätten, indem Sie Zellen vertauschen, die nur einen Nachbarn in ihrer eigenen Farbe haben und ansonsten von einem anderen als dieser Farbe umgeben sind.
Tom
quelle
3

Wenn Sie daran interessiert sind, dies eher im Vektorformat als in rasterbasierten Ansätzen zu tun, habe ich vor einiger Zeit einen Blog-Beitrag darüber geschrieben.

http://blog.particracy.com/worlds-and-their-geography/

Die Idee ist, dass Sie mit einem Netz beginnen (normalerweise auf Voronoi-Basis) und die Regionen konzentrisch aus zufällig gesetzten Punkten wachsen lassen, die einen ausreichenden Abstand voneinander haben.

Wouter Lievens
quelle
2

Was für eine lustige Frage :) Dieser Ansatz basiert auf Vornoi-Zellen, aber die Entfernungsmetrik ist nicht ganz euklidisch (ich habe die Potenz von 1,5 anstelle von 2,0 verwendet) und enthält eine gewisse Zufälligkeit. Es kann über das Wasser springen, was nicht ideal ist.

Nahe gelegene Regionen können zusammengeführt werden, um interessantere Formen zu erhalten. Hier habe ich die N nächsten Nachbarn verwendet, um dies zu bestimmen.

Wenn Sie interessiert sind, kann ich auf weitere Details eingehen und den Python-Code weitergeben.

Karte 1 Karte 2

NikoNyrh
quelle