Erzeugen Sie gleiche Regionen in einer hexadezimalen Karte

13

Wie kann ich zum Beispiel eine große (X x Y) Hex-Karte in N Regionen verbundener Hex-Felder unterteilen, um Länder zu simulieren?

Ziel ist es, eine hexadezimale Karte zu erstellen, die wie eine reale Karte mit Ländern mit unterschiedlichen Formen und gleicher Größe aussieht.

MadCatPT
quelle

Antworten:

13

Haben Sie Lloyd's Algorithmus ausprobiert ? Die Prozedur ist ziemlich einfach und generiert ziemlich regelmäßig aussehende Bereiche (abhängig von der Anzahl der Iterationen, die Sie ausführen).

  1. Kacheln Sie die Karte mit leeren Feldern, um zu beginnen.
  2. Wähle N Felder nach dem Zufallsprinzip. Diese repräsentieren den "Massenschwerpunkt" für jedes Land.
  3. Kennzeichnen Sie jedes Hex mit dem mittleren Hex, dem es am nächsten liegt ( Voronoi-Diagramm ). Land i ist die Menge aller Felder , die dem i-ten mittleren Feld am nächsten liegen .
  4. Berechnen Sie den neuen Schwerpunkt für jedes Land.
  5. Wiederholen Sie die Schritte 3 und 4 so oft, wie Sie die erzeugten Bereiche glätten möchten.

Sie müssen nicht lange laufen, um eine gut aussehende Karte zu erstellen. In diesem Beispiel waren nur drei Iterationen erforderlich.

Michael Kristofik
quelle
Sehr schön und +1 für ein spezielles Beispiel, aber ich würde mir ein bisschen Sorgen machen, dass diese ein bisschen zu regelmäßig sind! Trotzdem sehen die Ergebnisse besonders in dieser Größenordnung wirklich großartig aus, und es ist auch eine hervorragende Möglichkeit, andere Methoden zu verwenden.
Steven Stadnicki
1
Mein Beispiel wurde von einem Blogbeitrag über die Generierung von Polygonkarten inspiriert . Der Autor fügte Rauschen an den Rändern jeder Region hinzu, um ein gezackteres Aussehen zu erzielen (scrollen Sie nach unten, um es zu sehen). Sie müssten viel mehr Verhexungen verwenden als ich, um dies zu einer praktikablen Option zu machen, aber es ist auf jeden Fall machbar.
Michael Kristofik
3

Eine einfache Möglichkeit, die Sie versuchen könnten.

  1. Wähle zufällig nSechsecke aus. Jeder startet eine Gruppe.
  2. Versuchen Sie für jede Gruppe, das Anfangsfeld in eine zufällige Richtung zu erweitern.
  3. Wenn alle Felder um das gewählte Feld besetzt sind, markieren Sie es als getappt, und ändern Sie das Feld.
  4. Wiederholen Sie diesen Vorgang, bis jede Gruppe 20 Sechsecke lang ist oder keinen Platz mehr zum Erweitern hat (alle Sechsecke werden getappt).

Ich habe nicht getestet, aber dies sollte Inseln erzeugen und lange dünne Zahnspangen etwas vermeiden. Höchstwahrscheinlich wird es auch Nachbarn geben, aber nicht notwendigerweise wird jeder in Kontakt mit dem anderen sein, diese Dichte wird vom Wert von abhängen n.
Einige Gruppen können auch von anderen in die Enge getrieben werden und eine Größe von weniger als 20 erreichen. Sie können den gewachsenen Platz sicherstellen, indem Sie die Startfelder in einem Mindestabstand voneinander platzieren.
Testen und optimieren Sie nach Bedarf.


Besuchen Sie auch diese Seite, die nicht mit diesem Problem zusammenhängt, aber sehr, sehr nützlich für die Arbeit mit Verhexungen ist: http://www.redblobgames.com/grids/hexagons/#basics
Sie aggregiert eine ganze Reihe von Verhexungsinformationen an einem einzigen Ort mit ein schönes bild.

petervaz
quelle
Sollte wahrscheinlich einen Mechaniker für Gruppe A einschließen, der Knoten für Gruppe B gibt, wenn Gruppe B an Gruppe A grenzt und keinen anderen Ort hat. Solange Gruppe A freien Raum hat, um die verlorenen Knoten zu ersetzen. Dann ist es egal, wo sie angefangen haben. Da wirkt das irgendwie wie ein "Rückzug".
MichaelHouse
Ich denke, ich beginne ein Land zu einer Zeit, bilde zuerst die Eckgruppen, dann geben die Randgruppen, was ich will. Ich werde es versuchen, wenn ich nach Hause komme.
MadCatPT
@Byte56 Ja, ich habe mir während des Mittagessens tatsächlich so etwas ein bisschen überlegt. Wenn die Gruppe in einer Ecke nirgends wachsen kann, nimmt sie einfach ein Feld einer anderen Gruppe und lässt diese Gruppe bei der nächsten Iteration einen leeren Platz finden. Es sollte jedoch eine gewisse Sicherheit bieten, um zu vermeiden, dass sich zwei in die Enge getriebene Gruppen unendlich gegenseitig schikanieren.
Petervaz
Echte Länder haben oft Grenzen an Flüssen oder Bergen. Wenn Sie in eine zufällige Richtung expandieren, können Sie versuchen, die Wahrscheinlichkeit einer Expansion zu verringern, wenn sich das nächste Hex auf der anderen Seite eines Flusses oder eines Bergrückens befindet.
amitp
@amitp Wenn das OP erwartet hätte, dass diese Faktoren berücksichtigt werden, hätte er sie wahrscheinlich erwähnt. Ich gehe nicht davon aus, nur innerhalb der ursprünglichen Prämissen zu arbeiten.
Petervaz
2

Ich denke definitiv, dass eine Art Graphstruktur dies ermöglichen würde. Erstellen Sie grundsätzlich eine Kante zwischen zwei Hex-Knoten, wenn diese nebeneinander liegen, um die gesamte Karte zu simulieren. Ich bin mir jedoch nicht sicher, mit welchem ​​Algorithmus ein "Land" auf dieser Karte erstellt werden soll. Die Sache ist, je nachdem, wie Sie das Land "aussehen" möchten, würden Sie verschiedene Algorithmen benötigen.

Aus dem Kopf heraus würde ich empfehlen, einen Punkt auszuwählen und von dort nach außen zu gehen, indem ich ein zufälliges Plättchen in Ihrem "Anbauland" auswähle, das ein benachbartes Plättchen enthält, das nicht Teil des Landes ist.

Ein Strategiemuster könnte verwendet werden, um Algorithmen auszutauschen, je nachdem, welche Art von Land Sie sehen möchten. http://en.wikipedia.org/wiki/Strategy_pattern dh möchtest du ein schlankes Küstenland wie Chile? Oder möchten Sie etwas, das runder und geschlossener ist?

Mit den Diagrammeigenschaften können Sie auch festlegen, wie das Endland aussehen soll: http://en.wikipedia.org/wiki/Eccentricity_(graph_theory)

Willst du ein großes Land? Passen Sie die Diagrammeigenschaften an und zwingen Sie das generierte Land (das nur ein Diagramm ist), die gewünschten Eigenschaften zu erhalten.

Zu guter Letzt sind Grafiken auch sehr nützlich, um Grenzen zwischen Ländern zu definieren. Sie können ein Diagramm erstellen, das eine Verbindung zwischen zwei Knoten hat, wenn die Länder aneinander grenzen. Dies kann für eine Art von Partitionierung in Ihrem Spiel nützlich sein und ermöglicht Ihnen möglicherweise, bestimmte Dinge in der Entwicklung weiter zu optimieren.

Dean Knight
quelle
2

Eine kleine Anmerkung: Sie sagen "sieht aus wie eine reale Karte mit Ländern unterschiedlicher Formen, aber gleicher Größe", aber "reale" Länder sind auch in bestimmten Regionen sehr unterschiedlich groß - selbst die "großen" Länder Europas können sehr unterschiedlich sein. Frankreich ist mehr als doppelt so groß wie Italien. Trotzdem gibt es natürlich Spielregionen, in denen man versuchen kann, die Größe in etwa gleich zu halten - beachten Sie jedoch, dass eine kleine Variation hier wahrscheinlich eine gute Sache ist!

Meine anfängliche Herangehensweise an das Problem wäre, Ihre Regionen zu "entwickeln" (anstatt zu "wachsen"):

  • Beginnen Sie mit einer konkreten Unterteilung der Karte in ungefähr gleich große Abschnitte durch gerade Linien (wenn Sie beispielsweise 6 Länder möchten, können Sie die Karte in drei horizontale Abschnitte unterteilen und dann jeden dieser Abschnitte "auf der Diagonale" teilen. in zwei Teile teilen). Dies ist offensichtlich programmgesteuert einfach zu bewerkstelligen, zumal es nicht sehr genau sein muss (in der Tat sollte es wahrscheinlich nicht sehr genau sein).
  • Führen Sie einen ersten Durchlauf der Division durch und erstellen Sie eine Datenstruktur für die Begrenzung: eine Reihe von Feldern, deren Nachbarn derzeit zu einem anderen Land gehören. Dies wäre auch ein guter Zeitpunkt, um die Anzahl der Felder in jedem Land zu bestimmen.

Führen Sie nun den folgenden Pseudocode aus, solange Sie möchten:

Pick a random hex A from the boundary list;
Pick a random neighbor B of this hex from a different country;
if (A's country has more hexes than B's country has) {
  change hex A to belong to B's country;
} else if (B's country has more hexes than A's country has) {
  change hex B to belong to A's country;
} else {
  flip a coin to decide which to change;
}
if ( the changed hex's old country has become disconnected ) {
  undo and reject this move;
} else {
  update the boundary list around the changed hex and its neighbors;
}

Auf diese Weise wird ein grobes Gleichgewicht zwischen der Größe zweier benachbarter Länder aufrechterhalten, und die Überprüfung der Trennung (die mit einem einfachen Algorithmus für die Überflutung durchgeführt werden kann) stellt sicher, dass kein Land jemals in Teile zerbricht. Das Aktualisieren der Grenzliste ist eine Operation mit konstanter Zeit - das geänderte Hex befindet sich offensichtlich immer noch an der Grenze, und Sie können einfach die sechs Nachbarn überprüfen, um festzustellen, ob einer von ihnen zu einer Grenzzelle geworden ist (da sich der Nachbar jetzt in befindet ein anderes Land) oder wurde keine Grenzzelle mehr (weil sich die Nachbarn jetzt im selben Land befinden), und änderte den Grenzsatz nach Bedarf.

Für eine Verfeinerung dieses Ansatzes können Sie sogar die Bedingung, welche Verhexung sich ändern soll, etwas zufällig festlegen - anstatt die beiden Länder immer "auszugleichen", können Sie den Swap immer mit einer bestimmten Wahrscheinlichkeit abschließen und diese Wahrscheinlichkeit sogar allmählich verringern Zeit (ähnlich dem Abkühlungsprozess in einem Simulated Annealing- Algorithmus), um zu erzwingen, dass sie ungefähr dieselbe Größe haben.

Beachten Sie, dass dies nicht garantiert, dass alle Gebiete genau die gleiche Größe haben (was unmöglich ist, wenn N Ihre Gittergröße nicht perfekt aufteilt), und nicht einmal garantiert, dass sich alle Länder innerhalb eines Sechsecks voneinander im Gebiet befinden. Es sollte jedoch garantieren (für genügend Iterationen ausführen), dass jedes Land nicht mehr als ein Feld größer oder kleiner als jeder seiner unmittelbaren Nachbarn ist.

Steven Stadnicki
quelle