Wie können Buchten und Meerengen in einer prozedural generierten Karte ermittelt werden?

40

Ich habe eine prozedural erzeugte Karte mit Voronoi-Zellen, mit einem definierten Meeresspiegel und einer glaubwürdigen Höhenkarte.

Strom

Bisher konnte ich bestimmte geografische Merkmale erfolgreich kennzeichnen: Land, Meer, Seen, Flüsse, Flussmündungen, Zusammenflüsse, Berge und Biome. Zu den Biomes zählen Tundra, boreale Wälder, Wiesen und gemäßigte Wälder. Es gibt dort auch ein paar andere Biome, aber für meine Zwecke sind sie momentan nicht wichtig.

Ich würde gerne Buchten und Meerengen als nächstes bezeichnen, aber ich weiß nicht, wie ich das richtig machen soll. Eine Bucht ist ein versenktes Küstengewässer, das direkt mit dem Ozean verbunden ist.

Eine Meerenge ist eine natürlich geformte, schmale Wasserstraße, die zwei Teile des Ozeans verbindet. Grundsätzlich dort, wo sich zwei Landstücke fast berühren und es auf beiden Seiten Ozean gibt. Wird auch als "Kanal" bezeichnet.

Zum Ermitteln von Features kann ich jedes Feature nach Typ wie folgt durchlaufen:

for each (var feature:Object in geography.getFeaturesByType(Geography.LAND))
  // loop through lands
  for each (var cell:Cell in feature.cells)
  // loop through cells
    for each (var neighbor:Cell in cell.neighbors)
    // loop through a cell's neighbors
      trace(neighbor.hasFeatureType(Geography.LAND));
Olin Kirkland
quelle
8
Ich empfehle einen BaySian-Klassifikator.
Akkumulation
1
@Akkumulation Ist das ein Wortspiel auf "bay" oder ist das ein seriöser Vorschlag? In letzterem Fall sollten Sie eine angemessene Antwort schreiben.
Philipp
Ich bin mir zu 99% sicher, dass er einen Witz macht.
Olin Kirkland

Antworten:

29

Die Art und Weise, wie Dragons Abound Buchten identifiziert, besteht darin, entlang der Küste zu gehen und zwei Stellen an der Küste zu finden, an denen der Abstand zwischen den Stellen in gerader Linie geringer ist als der Abstand zwischen den Stellen entlang der Küste. Dies ist die Verkrümmung der Küste zwischen den beiden Punkten. Durch Auswahl einer Sinuositätsgrenze und von Grenzen für den geradlinigen Abstand zwischen den Punkten können Sie schmale tiefe Buchten, breite flache Buchten usw. identifizieren.

In diesem Bild zeigen die roten und violetten Punkte die beiden Kandidatenpunkte, und die grüne Linie ist die Küstenlinie zwischen den Punkten. Die Sinuosität ist das Verhältnis dieser beiden Längen:

Beispiel einer Bucht

Alternativ können Sie zwei Punkte an der Küste auswählen und ein Polygon erstellen, indem Sie die beiden Punkte und die Küstenlinie zwischen den beiden Punkten verbinden (dh die grüne Linie oben vom roten Punkt zum violetten Punkt verbinden). Messen Sie die Fläche dieses Polygons. Eine Bucht hat eine größere Fläche als eine Nicht-Bucht.

Nach meiner Erfahrung war eine Kombination dieser beiden Maßnahmen am besten geeignet, um zuverlässig zu identifizieren, was die Menschen als Buchten betrachten.

Beachten Sie, dass dies auch Punkte erkennt. Um nur Buchten zu finden, müssen Sie überprüfen, ob das "Innere" der Bucht Wasser und kein Land enthält. Eine schnelle und einfache Möglichkeit, dies zu tun, besteht darin, den Mittelpunkt der Linie zwischen den beiden Punkten zu überprüfen, um festzustellen, ob es sich um Wasser handelt. (Dies kann getäuscht werden, ist aber im Allgemeinen ausreichend.)

Ein verwandtes Problem besteht darin, die "Mündung" der Bucht zu identifizieren - dh die beste Wahl für die beiden Punkte, die die Öffnung zur Bucht markieren. In der Regel haben Sie eine Reihe von Kandidaten für den "Mund". In der obigen Beispielkarte können Sie die Mündung dieser Bucht weiter hinein- oder herausschieben. Im Allgemeinen spielt es wahrscheinlich keine große Rolle, aber eine Heuristik, die einigermaßen gut funktioniert, ist die Minimierung des geradlinigen Abstands über den Mund.

Ich habe noch keine Meerengen geschafft, aber ich habe die Absicht, Punkte entlang der Küste zu überprüfen, um den nächstgelegenen Punkt an einer anderen Küste zu finden. Wenn dies unter einer festgelegten Grenze liegt, ist es eine Meerenge.

Dr. Pain
quelle
3
Ich hätte wissen sollen, dass Drachen im Überfluss die Antworten haben, die ich brauche.
Olin Kirkland
48

Im Folgenden finden Sie eine ungefähre Vorstellung davon, wie Sie mithilfe von Bildverarbeitungstransformationen die relevanten Funktionen isolieren können:

  1. Wenden Sie eine Überflutungsfüllung aus einer Ozeanzelle an, um eine Maske aus allen Ozeanzellen zu erstellen. Je nachdem, wie Ihre Flüsse eingerichtet sind, benötigen Sie möglicherweise ein zusätzliches Höhen- oder Freiraumkriterium, um zu verhindern, dass die Ozeanmaske ins Landesinnere fließt. ;)

    Ozean-Maske

  2. Wenden Sie eine lokale Glättung am Rand dieser Maske an, wobei die Verbundenheit / Topologie gleich bleibt, aber kleine verrauschte Küstenlinienelemente geglättet werden, die ablenken können. So können wir uns auf große Buchten über winzigen Einlässen konzentrieren. Sie können die Breite Ihres Filterkerns / die Anzahl der Iterationen verwenden, um die Skala der Features, die Sie beibehalten, genau zu steuern.

    Hier habe ich einige Male einen Medianfilter angewendet. Zellularautomaten sind eine weitere beliebte Methode, um glatte Formen von einer verrauschten Eingabe zu entfernen.

    Geglättete Küste

  3. Verwandeln Sie die Maske in ein Distanzfeld, in dem jede Zelle ihre Distanz von der geglätteten Küste speichert.

    Entfernungsfeld

Jetzt sehen wir einige vielversprechende Feature-Highlights. In einem signierten Distanzfeld erscheinen sowohl Buchten als auch Meerengen als scharfe Grate, wobei die Distanz zu den Seiten abfällt. Wir können einen Kantenerkennungsfilter verwenden, um diese Kanten auszublenden:

Kanten hervorgehoben

Sie können dann zwischen Buchten und Meerengen unterscheiden, indem Sie dem Grat folgen, um die Konnektivität zu bestimmen. Eine Bucht ist ein Grat, der in Richtung Küste verläuft und immer flacher (vom Land entfernt) wird, bis er in einem Punkt endet. Eine Meerenge ist ein Grat, der eine Fernregion mit einer anderen Fernregion verbindet und auf dem Weg durch eine Fernregion verläuft.

Eine andere Möglichkeit besteht darin, jeder Insel eine ID zuzuweisen (Suche verbundener Komponenten). Wenn Sie dann Ihr Entfernungsfeld erstellen, geben Sie die "nächste Insel-ID" entlang der Entfernungsgrenze weiter. Eine Bucht oder ein Einlass ist dann ein Grat in Wasser neben derselben Landmasse auf beiden Seiten, während ein Kanal ein Grat ist, der Wasser neben zwei verschiedenen Landmassen trennt.

Sie können Mindest- und Höchstwerte für den Abstand zum Ufer oder die Länge des Firsts festlegen, um zu steuern, welche Features zu kennzeichnen sind, wenn Sie beispielsweise übermäßig enge / breite Meerengen ausschließen müssen.

DMGregory
quelle
9
Dies sieht sehr cool aus und könnte möglicherweise erheblich beschleunigt werden, wenn Sie direkt die Zellstruktur verwenden, um die verschiedenen Schritte und nicht die grafische Darstellung anzuwenden!
Quentin
7
Der zweite Ansatz (Zuweisen einer ID für jede Landmasse und Unterscheidung, ob es sich um dieselbe Landmasse auf beiden Seiten des Gewässers handelt) scheint am einfachsten zu sein.
Monty Harder,
Die "Landmass ID" ist auf jeden Fall eine gute Idee, da Sie sie auch in der Kartenbeschriftung benötigen, um Inselnamen zu generieren.
MSalters
6

Grundsätzlich müssen Sie darüber nachdenken, was Sie genau mit einer Bucht oder Meerenge meinen und warum Sie sie unterscheiden möchten (dient dies zur AI-Berechnung oder zur Kennzeichnung von Orientierungspunkten oder etwas anderem?). Probieren Sie ein paar Definitionen aus, um die zu finden, die Ihnen am besten gefällt. Formulieren Sie dann Bedingungen, um Ihre Voronoi-Zellen zu überprüfen. Ein paar Vorschläge:

Bucht

  • Jede Ozeanzelle, die nur mit einer anderen Ozeanzelle verbunden ist
  • ODER: Jede Ozeanzelle, die mit mehr Land als Ozeanzellen verbunden ist, wobei alle Ozeanzellen nebeneinander liegen
  • ODER: Wie oben, jedoch mit einem Kriterium basierend auf der Grenzlänge (z. B. doppelt so viel Land wie Wassergrenze)

Straße

  • Jede Ozeanzelle, die genau zwei Ozeanzellen verbindet, die nicht nebeneinander liegen
  • ODER: Jede Ozeanzelle, die mit zwei Landzellen verbunden ist, die nicht zur selben Landmasse gehören (Sie müssen zuerst herausfinden, welche Landzellen verbunden sind, und jeder Landmasse IDs zuweisen).
  • ODER: Marschieren Sie um die Grenze und zählen Sie Land / Wasser- und Wasser / Land-Übergänge. Sie benötigen mindestens zwei von jedem.
  • Abhängig von Ihrer Methode und dem, was Sie mit den Kategorien tun möchten, möchten Sie möglicherweise Meerengen beseitigen, die nur zu einer Bucht führen, oder sie stattdessen als Bucht kennzeichnen.
Autolykos
quelle
2
Wenn eine Meerenge zu einer Bucht führt, können diese beiden zusammen als Fjord bezeichnet werden.
Philipp
1
Wenn die Zellen im Verhältnis zur Größe einer Bucht / Meerenge klein sind, müssen Sie diese möglicherweise weitergeben, um Zellen außerhalb der unmittelbar benachbarten Nachbarn zu betrachten.
DMGregory
Ja, die Skalierung ist ein kleines Problem und wirkt sich darauf aus, wie Sie Dinge definieren und "Zellen" deklarieren. Betrachten Sie eine Karte von Kanada und vergleichen Sie Folgendes: die Hudson Bay, die James Bay, den Golf von St. Lawrence und die Bay of Fundy. Wie wenden Sie diese Regeln zuverlässig an, um die gewünschten verwandten Namen zu erhalten? - Gibt es eine "Straße" zwischen Neufundland und Nova Scotia?
TheLuckless