Jak podzielić siatkę heksów równomiernie między n graczy?

Tworzę prostą grę opartą na siatce heksadecymalnej i chcę, aby mapa była równo podzielona między graczy. Mapa jest tworzona losowo i chcę, aby gracze mieli mniej więcej taką samą liczbę komórek i stosunkowo małe obszary. Na przykład, jeśli na mapie jest czterech graczy i 80 komórek, każdy z graczy miałby około 20 komórek (nie musi być precyzyjny). Ponadto każdy gracz powinien mieć nie więcej niż cztery sąsiednie komórki. Oznacza to, że podczas generowania mapy największe „fragmenty” nie mogą być większe niż cztery komórki.

Wiem, że nie zawsze jest to możliwe dla dwóch lub trzech graczy (ponieważ przypomina to problem „kolorowania mapy”) i nie mam nic przeciwko robieniu innych rozwiązań (takich jak tworzenie map rozwiązujących problem). Ale jak dla czterech do ośmiu graczy, jak podejść do tego problemu?

Oto co bym zrobił:

1. Przypisz wszystkie komórki losowym graczom. Na dużych mapach powinno być bardzo prawdopodobne, że wszyscy gracze wygenerują całkiem parzystą liczbę kafelków, na mniejszych mapach prawdopodobnie będziesz musiał wprowadzić pewne poprawki.
2. Rozbij kawałki, które są zbyt duże. Najłatwiej jest wziąć wszystkie płytki w kawałki i ponownie przypisać każdą płytkę losowo.
3. W przypadku niezrównoważonej liczby komórek (np. Gracz A ma 24 komórki, gracz B ma 16), przypisz kilka komórek z nadreprezentowanych graczy do niedostatecznie reprezentowanych graczy.
4. Sprawdź ponownie, czy nie ma kawałków. Jeśli krok 3 wprowadził nowe fragmenty, wróć do kroku 2. Jeśli nie, ładna mapa!

Zakładając, że masz w sumie mapę heksadecynalną nkomórek i pgraczy, p <= nnajlepszym sposobem na rozwiązanie tego problemu jest dystrybucja typu round-robin za pomocą automatów komórkowych (CA).

Inicjalizacja

Losowo (i / lub przy użyciu niektórych lub innych metod heurystycznych, takich jak odległość od centrum mapy) wybierz komórkę początkową dla każdego gracza. Ponieważ p <= nnie powinno to stanowić problemu.

Automaty komórkowe

Potrzebujesz pełnej łączności między komórkami heksadecymalnymi. Sugerowałbym tablicę 6 sąsiadów na komórkę:

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

Zastosowanie tablic o stałym rozmiarze pozwala istnieć pojęcie kierunków topograficznych między komórkami, czego nie byłoby w przypadku listy lub wektora. Polecam to, ponieważ może to ułatwić pewne operacje nawigacyjne.

Możesz także przechowywać mapę heksadecymalną w układzie 2D z przesunięciami na wiersz. Może to być jednak nieco mniej intuicyjne niż przechowywanie sąsiedniej tablicy na komórkę, tylko ze względu na geometryczne przesunięcie w każdym innym rzędzie.

Upewnij się, że każda komórka jest podłączona do wszystkiego, co jest sąsiadem. Możesz zrobić ten wiersz po rzędzie, komórka po komórce podczas generowania pełnej mapy heksadecymalnej. PS Jeśli ostatecznie chcesz uzyskać mapę heksadecymalną, która nie jest prostokątna, możesz po prostu usunąć pojedyncze komórki i odniesienia do tych komórek, aby utworzyć ujemne przestrzenie, umożliwiając utworzenie konturu mapy organicznej.

Round-robin Distribution

Pseudo kod:

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

Algorytm ten da każdemu graczowi szansę na powiększenie swojego terytorium o jeden, w sposób okrągły, pod warunkiem, że na terytorium gracza nadal znajduje się ważna przestrzeń do uprawy. Jeśli pewne gracze są zablokowane rośnie dalej, algorytm będzie mimo to nadal rosnąć terytoria graczy, którzy nie mają jeszcze ważne miejsca rośnie. Możesz z łatwością ograniczyć każdego gracza do tej samej liczby komórek, jak tylko jedna z nich osiągnie limit, ale powinno to być na tyle łatwe, abyś mógł się zorientować, jeśli chcesz.

Zapewni to maksymalne rozmiary „terytoriów macierzystych” dla każdego gracza. Jeśli chcesz mieć dodatkowo terytoria wyspiarskie, w celu wypełnienia limitu liczby komórek dla tego gracza, gdy graczowi zabraknie miejsca na rozwój, możesz wybrać nową komórkę początkową z neutralnej listy komórek i stamtąd kontynuuj ten sam proces „wzrostu”. W ten sposób uzyskasz spójne zestawy wysp dla każdego gracza, a nie losowy hałas.

Innym podejściem byłoby zacząć od dystrybucji, która jest „sprawiedliwa”, ale regularna, a następnie użyć metody podobnej do Symulowanego wyżarzania, aby rozbić regularność bez utraty uczciwości:

• Zacznij od przypisania kolorów do wszystkich komórek siatki w regularnym wzorze (np. Powtarzaj wzór „123412341234” w pierwszym rzędzie, a następnie „341234123412” w następnym itd.). Może to prowadzić do nierównomiernego rozmieszczenia kolorów, jeśli twoja mapa jest szczególnie słabo ukształtowana, ale przypuszczam, że zaczynasz od stałej mapy, więc powinieneś być w stanie znaleźć jakieś equidistributed regularne farbowanie niego.
• Następnie powtórz następujące kroki dla dowolnej liczby kroków (nie ma prawdziwego kryterium „doneness”, więc eksperymentowanie powie ci, jaka jest minimalna rozsądna liczba kroków):
  • Wybierz losowo dwa elementy siatki
  • Jeśli mają ten sam kolor, spróbuj ponownie (nie ma sensu inaczej, ponieważ wtedy zamiana nie będzie możliwa. Masz tylko 1/4 szansy na trafienie tego samego koloru i 1/16 szansy na trafienie tego samego koloru dwa razy z rzędu, więc nigdy nie powinieneś próbować za dużo)
  • Tymczasowo zamień kolory tych dwóch elementów
  • Przetestuj rozmiary nowo utworzonych regionów w lokalizacjach elementów po zamianie:
    • wykonaj proste wypełnienie zalewowe na zewnątrz z nowego miejsca każdego elementu, aby określić, jak duży obszar tego koloru zrobiłby zamiana.
  • Jeśli jeden z tych dwóch regionów jest większy niż próg, cofnij tymczasową zamianę; w przeciwnym razie „sfinalizuj” zamianę kolorów dwóch elementów.

Kluczem tutaj jest to, że zamiana dwóch punktów oznacza, że ​​nigdy nie wyważasz kolorów, a także test, który wykonujesz przed sfinalizowaniem zamiany, gwarantuje, że nigdy nie utworzysz zbyt dużych regionów. Jeśli masz jakieś sposoby wyświetlania siatki, możesz nawet zwizualizować ten proces, aby zobaczyć, jak „buduje” swoje regiony poprzez powtarzające się zamiany.

Nawiasem mówiąc, jeśli nie możesz zacząć od równomiernego regularnego kolorowania, powinieneś być w stanie zrobić coś podobnego do równomiernego rozbarwienia: podczas gdy twoje zabarwienie nie jest równomierne, wybierz element losowo; następnie, jeśli jest to jeden z nadmiernie reprezentowanych kolorów, tymczasowo ustaw jego kolor na jeden z niedostatecznie reprezentowanych kolorów, a następnie sprawdź, czy nie tworzy on zbyt dużego obszaru nowego koloru.