Wie verteilt man das Hex-Gitter gleichmäßig auf n Spieler?

15

Ich mache ein einfaches Hex-Grid-basiertes Spiel und möchte, dass die Karte gleichmäßig unter den Spielern aufgeteilt wird. Die Karte wird zufällig erstellt, und ich möchte, dass die Spieler ungefähr die gleiche Anzahl von Zellen mit relativ kleinen Flächen haben. Wenn sich beispielsweise vier Spieler und 80 Zellen auf der Karte befinden, hat jeder der Spieler ungefähr 20 Zellen (es muss nicht genau auf den Punkt genau sein). Jeder Spieler sollte nicht mehr als vier benachbarte Zellen haben. Das heißt, wenn die Karte generiert wird, können die größten "Stücke" nicht mehr als vier Zellen pro Stück sein.

Ich weiß, dass dies nicht immer für zwei oder drei Spieler möglich ist (da dies dem Problem "Färben der Karte" ähnelt), und ich bin damit einverstanden, andere Lösungen für diese zu finden (z. B. Karten zu erstellen, die das Problem lösen). Aber wie könnte ich für vier bis acht Spieler dieses Problem angehen?

Manabreak
quelle
Zelluläre Automaten sind ein einfacher Weg, ähnlich wie dieser: Eine einfache Karte, vier Biome und wie man sie verteilt
MichaelHouse

Antworten:

3

Das würde ich tun:

  1. Ordnen Sie alle Zellen zufälligen Spielern zu. Auf großen Karten sollte dies sehr wahrscheinlich eine ziemlich gerade Anzahl von Kacheln für alle Spieler ergeben. Auf kleineren Karten müssen Sie wahrscheinlich einige Korrekturen vornehmen.
  2. Brechen Sie zu große Stücke auf. Am einfachsten ist es, alle Kacheln in Stücken zu nehmen und sie wieder nach dem Zufallsprinzip zuzuweisen.
  3. Bei einer unausgeglichenen Anzahl von Zellen (z. B. Spieler A hat 24 Zellen, Spieler B hat 16) weisen Sie ein paar Zellen von überrepräsentierten Spielern zu unterrepräsentierten Spielern zu.
  4. Überprüfen Sie erneut, ob Brocken vorhanden sind. Wenn Schritt 3 neue Chunks eingeführt hat, gehen Sie zurück zu Schritt 2. Wenn nicht, schöne Karte!
Junuxx
quelle
PS Ich glaube nicht, dass dieses Problem jemals unmöglich ist, das Problem mit der Kartenfärbung ist ganz anders (zum einen ist es umgekehrt, Formen-> Farben anstelle von Farben-> Kachelzuweisungen).
Junuxx
Ich mag diesen Ansatz ein bisschen, aber gibt es keine Möglichkeit, dass er für eine lange Zeit läuft und versucht, die Flächengrößen auszugleichen?
Manabreak
1
@manabreak: Ich habe etwas gemacht , um es auszuprobieren. Mit einer kleinen Änderung in Schritt 2 (Neuzuweisung durch Durchlaufen aller Spieler anstelle einer Neuzuweisung nach dem Zufallsprinzip) funktioniert es recht gut. Ich werde versuchen, es aufzuschreiben, wenn ich Zeit habe.
Junuxx
1
Das sieht genau so aus, wie ich gesucht habe. :)
Manabreak
1

Angenommen, Sie haben eine Hexmap von nZellen insgesamt und von pSpielern, bei denen dies p <= nam besten durch Round-Robin-Verteilung über zellulare Automaten (CA) gelöst werden kann .

Initialisierung

Wählen Sie nach dem Zufallsprinzip (und / oder unter Verwendung irgendeiner oder anderer Heuristik, z. B. Entfernung vom Kartenmittelpunkt) eine Startzelle für jeden Spieler. Da p <= nsollte dies kein Problem sein.

Zelluläre Automaten

Sie benötigen vollständige Konnektivität zwischen Ihren Hex-Zellen. Ich würde ein Array mit 6 Nachbarn pro Zelle vorschlagen:

class Cell
{
   //... other members...
   Cell[6] neighbours = new Cell[6];
}

Durch die Verwendung von Arrays mit fester Größe kann das Konzept der topografischen Richtungen zwischen Zellen erstellt werden, die in einer Liste oder einem Vektor nicht vorhanden sind. Ich empfehle dies, da es bestimmte Navigationsoperationen erleichtern kann.

Sie können Ihre Hexmap auch in einem 2D-Array mit Offsets pro Zeile speichern. Dies ist jedoch möglicherweise etwas weniger intuitiv als das Speichern eines Nachbar-Arrays pro Zelle, nur aufgrund des geometrischen Versatzes in jeder zweiten Zeile.

Stellen Sie sicher, dass jede Zelle mit allem verbunden ist, was ein Nachbar ist. Sie können dies Zeile für Zeile und Zelle für Zelle tun, während Sie die vollständige Hexmap generieren. PS Wenn Sie letztendlich eine nicht rechteckig begrenzte Hexmap möchten, können Sie einfach einzelne Zellen und Verweise auf diese Zellen entfernen, um negative Leerzeichen zu bilden, sodass Sie einen organischen Kartenumriss erstellen können.

Round-Robin-Verteilung

Pseudocode:

count number of neutral cells in entire map, minus those starting cells taken by players
while neutral cells remain (or while true)
   for each player
      if player has not yet reached expected territory size in cells
         for each cell already constituting this player's territory
           if territory can grow by one cell into a neutral neighbour
              grow into neighbour
              reduce neutral cell count for entire map by one
              if no more neutral cells remain in map
                 break out of outermost while loop immediately
              else
                 continue to next player immediately
begin game

Dieser Algorithmus gibt jedem Spieler die Möglichkeit, sein Territorium in einem Round-Robin-Verfahren um eins zu vergrößern, vorausgesetzt, das Territorium des Spielers verfügt noch über einen gültigen Erweiterungsbereich. Wenn bestimmte Spieler daran gehindert werden, weiter zu wachsen, vergrößert der Algorithmus trotzdem weiterhin das Territorium der Spieler, die noch über gültigen Wachstumsraum verfügen. Sie könnten jeden Spieler leicht auf die gleiche Anzahl von Zellen beschränken, sobald eine von ihnen ein Limit erreicht, aber das sollte leicht genug für Sie sein, um es herauszufinden, falls dies gewünscht wird.

Dies wird für jeden Spieler "Heimatgebiete" von maximaler Größe bereitstellen. Wenn Sie zusätzlich "Inselgebiete" haben möchten, um die Zellenzahlquote für diesen Spieler zu erfüllen, können Sie, sobald ein Spieler nicht mehr über genügend lokalen Speicherplatz verfügt, eine neue Startzelle aus der Liste der neutralen Zellen auswählen und Fahren Sie von dort aus mit demselben "Wachstumsprozess" fort. Auf diese Weise erhalten Sie für jeden Spieler eine ansehnlich große, zusammenhängende Inselgruppe und kein zufälliges Rauschen.

Ingenieur
quelle
Obwohl Sie eine hervorragende Dokumentation und einen Pseudocode für Ihren Algorithmus bereitstellen, bin ich mir nicht sicher, ob dies mit den Fragen des Fragestellers übereinstimmt. In der Frage wird erwähnt, dass "die größten" Blöcke nicht mehr als vier Zellen umfassen dürfen, während Ihr Algorithmus eine möglichst große zusammenhängende Gruppe erstellt.
17.
@ fnord Nein, das tut es nicht. Sie haben meine Antwort nicht richtig gelesen. Ich habe den Pseudocode explizit begrenzt: "Wenn der Spieler die erwartete Gebietsgröße in den Zellen noch nicht erreicht hat". Bitte entfernen Sie Ihre Ablehnung. Sie können den Änderungsverlauf der Frage jederzeit überprüfen, um sich davon zu überzeugen, dass dies bereits vor Ihrem Kommentar und Ihrer Ablehnung der Fall war.
Ingenieur
In der Frage wird gefragt, ob "nicht mehr als vier benachbarte Zellen" vorhanden sind und jeder Benutzer einen erwarteten Teil der Karte haben soll. Dies impliziert für mich, dass wir uns eher darum bemühen, wie Risikospiele die Karte für alle Spieler nach dem Zufallsprinzip aufteilen. Ihre Antwort unterteilt die Karte in "Heimatgebiete mit maximaler Größe". Ihr Algorithmus stoppt zwar, wenn das erwartete Gebietsgrößenlimit erreicht ist, aber ich sehe keine Möglichkeit für diesen Spieler, neue "Inseln" zu erhalten, obwohl Sie es in einem späteren Text erwähnen.
17.
@fnord Deine Logik ist fehlerhaft. In Ihrem letzten Satz geben Sie zu, dass mein Algorithmus bei der Größe der Insel stoppt n, und widersprechen sich dann selbst, indem Sie sagen, dass Sie "keinen Weg sehen", und ich "erwähne [wie man Inseln bekommt] im späteren Text". Habe ich oder habe ich die Frage nicht beantwortet? Dieser verallgemeinerte Algorithmus kann verwendet werden, um entweder Zellen zu streuen (durch Beschränkung nauf 1) oder Inseln zu erzeugen (durch Setzen von n> 1). Sie haben also in einem einzigen Algorithmus nicht nur die Möglichkeit zu streuen, sondern auch zu gruppieren. Wie beantwortet dies nicht die Frage des OP? Wie ist es eines Downvotes wert?
Ingenieur
Ich würde meinen Kommentar oben bearbeiten, aber es ist zu spät. "Ich sehe keinen Weg in Ihrem Algorithmus ". Sie erwähnen das Konzept jedoch in einem späteren Text.
17.
0

Ein anderer Ansatz wäre, mit einer Verteilung zu beginnen, die "fair", aber regelmäßig ist, und dann einen Ansatz zu verwenden, der dem simulierten Glühen ähnelt, um die Regelmäßigkeit zu unterbrechen, ohne die Fairness zu verlieren:

  • Weisen Sie zunächst allen Zellen Ihres Rasters in einem regelmäßigen Muster Farben zu (z. B. mit einem sich wiederholenden Muster "123412341234" in der ersten Zeile, gefolgt von "341234123412" in der nächsten usw.). Dies kann zu einer ungleichmäßigen Verteilung der Farben führen , wenn Sie Ihre Karte besonders schlecht geformt, aber ich bin die Annahme , dass Sie mit einer festen Karte fangen, so dass Sie sollten in der Lage zu finden , einige gleichmäßig verteilen regelmäßige Färbung davon.
  • Wiederholen Sie dann das Folgende für so viele Schritte, wie Sie möchten (es gibt kein echtes Kriterium für den Gargrad, sodass Sie durch Experimentieren feststellen können, wie viele Schritte mindestens angemessen sind):
    • Wähle zwei Elemente des Gitters nach dem Zufallsprinzip aus
    • Wenn sie die gleiche Farbe haben, versuchen Sie es erneut (es hat sonst keinen Sinn, da das Austauschen dann ein No-Op ist. Sie haben nur eine 1/4-Chance, die gleiche Farbe zu treffen, und eine 1/16-Chance, die gleiche Farbe zu treffen zweimal hintereinander, so dass Sie nie zu viel wiederholen müssen)
    • Tauschen Sie vorläufig die Farben dieser beiden Elemente aus
    • Testen Sie die Größe der neu gebildeten Bereiche an den Positionen der Elemente nach dem Tausch:
      • Füllen Sie jedes Element an der neuen Stelle mit einer einfachen Überflutung nach außen, um zu bestimmen, wie groß ein Bereich dieser Farbe sein würde, den der Tausch ergeben würde.
    • Wenn eine dieser beiden Regionen größer als Ihr Schwellenwert ist, machen Sie den vorläufigen Swap rückgängig. Andernfalls stellen Sie den Austausch der Farben der beiden Elemente fertig.

Das Wichtigste dabei ist, dass Sie durch das Vertauschen von zwei Punkten die Farben niemals aus dem Gleichgewicht bringen. Ebenso wird durch den Test, den Sie vor Abschluss des Austauschs durchführen, sichergestellt, dass Sie niemals zu große Bereiche erstellen. Wenn Sie die Möglichkeit haben, Ihr Raster anzuzeigen, können Sie diesen Vorgang sogar visualisieren, um zu beobachten, wie es seine Regionen durch die wiederholten Auslagerungen "aufbaut".

Wenn Sie übrigens nicht mit einer gleichverteilten regulären Färbung beginnen können, sollten Sie dennoch in der Lage sein, etwas Ähnliches zu tun, um die Färbung gleich zu verteilen: Während Ihre Färbung nicht gleichverteilt ist, wählen Sie ein Element nach dem Zufallsprinzip aus; Wenn es sich dann um eine der überrepräsentierten Farben handelt, stellen Sie die Farbe vorläufig auf eine der unterrepräsentierten Farben ein und stellen Sie dann sicher, dass kein zu großer Bereich der neuen Farbe erstellt wird.

Steven Stadnicki
quelle
Stochastische Ansätze sind ineffizient. Für einen Ansatz wie meinen, der überlegte Schritte ausführt, nähert sich die Laufzeit O (n) für n Kartenzellen. Für Ihren Algorithmus ist es O (n * m), wobei m die Anzahl der gewünschten Zellen pro Insel ist (tatsächlich für jede potenzielle Insel). Immer am besten für Algorithmen, die eine leicht abschätzbare Laufzeit haben. Anstatt eine willkürlich generierte Karte zu reparieren, ist es besser, eine Karte zu erstellen, die in n Schritten nicht kaputt oder willkürlich ist. Auf diese Weise wird ein kontrollierter, effizienter Prozess aufrechterhalten.
Ingenieur