Erzeugen Sie gleiche Regionen in einer hexadezimalen Karte

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.

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.

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.

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.

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.