Generuj równe regiony na mapie heksadecymalnej

Biorąc na przykład dużą mapę heksów (X przez Y), jak mogę podzielić ją na N regionów połączonych heksów, aby symulować kraje?

Celem jest wygenerowanie mapy heksadecymalnej, która wygląda jak mapa rzeczywista z krajami o różnych kształtach, ale jednakowych rozmiarach.

Czy próbowałeś algorytmu Lloyda ? Procedura jest dość prosta i wygeneruje dość regularnie wyglądające regiony (w zależności od liczby uruchomionych iteracji).

1. Aby rozpocząć, ułóż mapę pustymi heksami.
2. Wybierz losowo N heksów. Będą one stanowić „środek masy” dla każdego kraju.
3. Oznacz każdy heks centralnym heksem, który jest najbliżej ( Schemat Voronoi ). Kraj i to zbiór wszystkich heksów najbliższych i-tego centralnego heksa .
4. Oblicz nowy środek masy dla każdego kraju.
5. Powtórz kroki 3 i 4 tyle razy, ile chcesz wygładzić wygenerowane regiony.

Nie musisz długo biegać, aby stworzyć ładnie wyglądającą mapę. Ten przykład wymagał tylko trzech iteracji.

Jeden prosty sposób, w jaki możesz spróbować.

1. Losowo wybierz nheksy. Każdy utworzy grupę.
2. Dla każdej grupy spróbuj rozwinąć początkowy heks w losowym kierunku.
3. Jeśli wszystkie heksy wokół wybranego heksa są zajęte, oznacz jako dotknięte, zmień heks.
4. Powtarzaj, aż każda grupa będzie miała długość 20 heksów lub nie będzie już miejsca na rozwinięcie (wszystkie heksy stuknięte).

Nie testowałem, ale powinno to wygenerować Wyspy i nieco unikać długich cienkich aparatów ortodontycznych. Ponadto, najprawdopodobniej będą granice sąsiadów, ale niekoniecznie każda z nich będzie się stykać z innymi, gęstość zależeć będzie od wartości n.
Niektóre grupy mogą być również opanowane przez inne i osiągać rozmiar mniejszy niż 20, możesz zapewnić powiększoną przestrzeń, odradzając początkowe heksy w minimalnej odległości od siebie.
Przetestuj i popraw w razie potrzeby.


Ponadto, niezwiązany z tym problemem, ale bardzo, bardzo przydatny do pracy z hexami, odwiedź tę stronę: http://www.redblobgames.com/grids/hexagons/#basics
Gromadzi całą masę informacji hex w jednym miejscu z niezły wygląd.

Zdecydowanie uważam, że jakiś rodzaj struktury wykresu to umożliwi. Zasadniczo utwórz krawędź między dwoma węzłami Hex, jeśli są one obok siebie, aby zasymulować całą mapę. Nie jestem jednak pewien dokładnego algorytmu generowania „kraju” na tej mapie. Chodzi o to, że w zależności od tego, jak chcesz, aby kraj wyglądał, potrzebujesz różnych algorytmów.

Z czubka mojej głowy zaleciłbym wybranie punktu i stamtąd na zewnątrz, wybranie losowej płytki w twoim „kraju rozwijającym się”, który ma sąsiadującą płytkę, która nie jest częścią tego kraju.

Wzorzec strategii może być wykorzystany do przełączania algorytmów w zależności od tego, jaki typ kraju chcesz. http://en.wikipedia.org/wiki/Strategy_pattern tzn. czy chcesz wąskiego wybrzeża jak Chile? A może chcesz coś bardziej okrągłego i zamkniętego?

Właściwości wykresu mogą również pozwalać ci dostosować to, jak ma wyglądać „kraj” końca: http://en.wikipedia.org/wiki/Eccentricity_(graph_theory)

Chcesz dużego kraju? Ulepsz właściwości wykresu i zmuś wygenerowany kraj (który jest tylko wykresem) do uzyskania właściwości, które nadadzą mu „wygląd”, jaki chcesz.

Wreszcie wykresy będą również bardzo przydatne do określania granic między krajami. Możesz zbudować wykres, który ma połączenie między dwoma węzłami, jeśli kraje graniczą ze sobą. Może to być przydatne do pewnego rodzaju partycjonowania w grze i pozwoli ci ewentualnie zoptymalizować pewne rzeczy w dalszym rozwoju.

Jedna mała uwaga: mówisz, że „wygląda jak prawdziwa mapa z krajami o różnych kształtach, ale jednakowych rozmiarach), ale„ rzeczywiste ”kraje mają bardzo różne rozmiary nawet w niektórych regionach - nawet„ duże ”kraje Europy mogą się znacznie różnić, np. Francja jest ponad dwa razy większa niż Włochy. To powiedziawszy, oczywiście istnieją regiony rozgrywki, które starają się zachować mniej więcej takie same rozmiary - pamiętaj, że niewielka różnorodność jest prawdopodobnie dobrą rzeczą!

Moje początkowe podejście do problemu polegałoby na „ewoluowaniu” (a nie „rozwijaniu”) waszych regionów:

• Zacznij od pewnego konkretnego podziału mapy na fragmenty o mniej więcej równej wielkości liniami prostymi (na przykład, jeśli chcesz 6 krajów, możesz podzielić mapę na trzy poziome wycinki, a następnie podzielić każdy z tych wycinków „na przekątnej” na dwie części). Jest to oczywiście łatwe do wykonania programowo, zwłaszcza, że ​​nie musi być bardzo dokładne (w rzeczywistości prawdopodobnie nie powinno być bardzo dokładne).
• Wykonaj wstępne przejście do podziału, budując „granicową” strukturę danych: zestaw heksów, które mają sąsiadów należących obecnie do innego kraju. Byłby to również dobry moment na zliczenie liczby heksów w każdym kraju.

Teraz, tak długo, jak chcesz, uruchom następujący pseudokod:

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;
}

Utrzyma to przybliżoną równowagę między wielkością dowolnych dwóch sąsiednich krajów, a kontrola „rozłączenia” (którą można wykonać za pomocą prostego algorytmu wypełniania powodzi) gwarantuje, że żaden kraj nigdy nie rozpadnie się na kawałki. Aktualizowanie listy granic jest operacją o stałym czasie - zmieniony hex oczywiście zawsze będzie na granicy, i możesz po prostu sprawdzić jego sześciu sąsiadów, aby sprawdzić, czy któryś z nich stał się komórką graniczną (ponieważ jego sąsiad jest teraz w inny kraj) lub przestał być komórką graniczną (ponieważ jego sąsiad jest teraz w tym samym kraju), modyfikując odpowiednio zestaw granic.

Aby ulepszyć to podejście, możesz nawet ustawić warunek, który hex zmienić nieco, losowo - zamiast zawsze „równoważyć” oba kraje, zawsze możesz dokonać zamiany z pewnym prawdopodobieństwem, a nawet stopniowo zmniejszyć to prawdopodobieństwo ponad czas (podobny do procesu chłodzenia w algorytmie symulowanego wyżarzania ), aby zacząć wymuszać, aby były mniej więcej tego samego rozmiaru.

Pamiętaj, że nie gwarantuje to, że wszystkie obszary mają dokładnie taki sam rozmiar (co jest niemożliwe, chyba że N i tak idealnie podzieli rozmiar siatki), a nawet nie zagwarantuje, że wszystkie kraje znajdują się w zasięgu jednego heksa od siebie; to powinno gwarantować (run na tyle iteracji), że każdy kraj nie więcej niż jeden hex większy lub mniejszy niż każdy z jego bezpośrednimi sąsiadami jest, choć.