Proceduralnie generuj regiony na wyspie

Obecnie mam wyspy, które wyglądają tak:

I chcę podzielić proceduralnie na regiony, takie jak to:

Jaki algorytm robi to, czego szukam? Czy masz sugestie, jak tworzyć spójne regiony, jak na dolnym zdjęciu? Twoja pomoc jest mile widziana.

W prawdziwym świecie te granice prowincji często będą podążać za cechami geologicznymi, takimi jak rzeki.

Więc może dobrym rozwiązaniem byłoby modelowanie geologii wyspy i wypadnięcie granic?

Red Blob Games ma kilka dobrych artykułów na ten temat, z ładnie wyglądającymi wynikami.

Jego podejście wydaje się obejmować teselację Voronoi i określa rzeki jako granice między komórkami.

Sprawdź inne artykuły na jego stronie, napisał dużo na temat generowania map .

Rozwiązałbym ten problem za pomocą dwóch przebiegów diagramów Voronoi:

First Pass: Partycjonowanie regionu

W pierwszym przejeździe wykorzystano by nieco rzadki rozkład punktów (tj. Odległość między punktami powinna być stosunkowo duża), aby z grubsza podzielić wyspę na regiony (patrz uwaga poniżej dotycząca generowania punktów). Następnie wygeneruj diagram Voronoi na podstawie tych punktów. To podzieli wyspę na regiony wielokątne wokół każdego punktu, jak pokazano poniżej:

Drugie przejście: Randomizacja granic

Teraz, gdy wyspa została podzielona na regiony, następnym krokiem jest „zgrubienie” granic między nimi. Aby to zrobić, wygeneruj nową warstwę punktów za pomocą bardziej zwartego rozkładu punktów (tj. Odległość między punktami powinna być mała) i ponownie użyj tych punktów, aby utworzyć kolejny diagram Voronoi. Następnie dla każdego mniejszego regionu przypisz go do większego regionu, sprawdzając jego punkt początkowy. Spowoduje to bardziej poszarpane granice między większymi poddziałami. Oto zbliżenie tego, co wygląda na obu diagramach Voronoi:

A oto ten sam obszar pokazujący tylko ostateczne granice:

Komentarze do generowania punktów

Jeśli chodzi o generowanie punktów, lubię stosować rozkład dysków Poissona , aby uzyskać względnie ładny i równomierny rozkład punktów. Inną powszechną opcją jest uzyskanie podobnie równomiernego rozkładu - użycie algorytmu Lloyda na zbiorze „regularnych” losowych punktów. LLoyd's jest łatwiejszy do kodowania, ale może zająć trochę prób i błędów, aby ustalić, ile przepustek jest wymaganych do uzyskania pożądanego wyniku.

Jednym z potencjalnych problemów związanych z tym podejściem jest to, że partycjonowanie pierwszego przejścia może generować bardzo małe regiony. Jeśli nie chcesz ich w końcowym wyniku, po prostu połączę je z losowym regionem sąsiadującym.

Uwagi końcowe

Ilustracje, które przedstawiłem, to obrazy rastrowe, ale ta technika działa również z reprezentacjami wielobocznymi / wektorowymi.

MineCraft robi to dobrze, a jego algorytm generacji światowej został dokładnie przeanalizowany i udokumentowany.

Istnieją różne opisy algorytmu, jeden z nich tutaj: https://github.com/UnknownShadow200/ClassiCube/wiki/Minecraft-Classic-map-generation-alameterm

Rdzeniem algorytmu jest generator szumów Perlina . Kontroluje to bezpośrednio wysokość (mniej więcej, ponieważ kolejny krok do wykopania jaskiń może również zmienić powierzchnię), a także generowanie biomu. Generator biomu jest prawdopodobnie tym, czego chcesz użyć do tworzenia obszarów.

(Stara wersja) jest udokumentowana , w zasadzie działa przy użyciu dwóch różnych generatorów hałasu Perlin, jednego do „temperatury”, jednego do „opadów”, a następnie wybierając biom z tych dwóch. Same zmienne (temperatura i opady) nie są tak naprawdę później używane w grze; na przykład na pustyniach nie ma deszczu, ale gra określa to na podstawie właściwości „pustyni”, a nie na podstawie pierwotnej wartości opadów.

Istnieją różne narzędzia online do generowania mapy biomów z losowych nasion, jednym z nich jest mineatlas.com . Sądzę, że wewnętrznie używają serwera Java, który korzysta z wewnętrznych klas samego MineCraft; Nie wiem, czy którykolwiek z ich kodów źródłowych jest dostępny bezpośrednio.

Typowy algorytm wykorzystywany na przykład przez Azgaar ( kod źródłowy ). Jest mniej więcej tak:

1. podziel swoją ziemię na mniejsze obszary, np. przez delauny triangulację lub komórki voronoi.
2. określ (losowo lub w inny sposób) „początkowe” lokalizacje dla swoich kultur, królestw, religii lub cokolwiek innego, co chcesz symulować.
3. określ (losowo lub w inny sposób) „czynnik wzrostu” dla każdego z nich. Im większa różnica w czynnikach wzrostu, tym mniej jednolita ostateczna mapa.
4. Teraz iteruj po swoich królestwach (itp.) I, w zależności od czynnika wzrostu, rozłóż je na otaczające, puste kafelki, aż cała mapa zostanie wypełniona.
5. Prawdopodobnie chcesz zakończyć nieco prostowanie granic, zmieniając komórki, które mają tylko jednego sąsiada we własnym kolorze, a poza tym są otoczone innym kolorem niż ten kolor.

Jeśli jesteś zainteresowany robieniem tego w formacie wektorowym, a nie w podejściu opartym na rastrze, jakiś czas temu napisałem post na blogu o prawie dokładnie tym.

http://blog.particracy.com/worlds-and-their-geography/

Chodzi o to, że zaczynasz od siatki (zwykle opartej na Voronoi) i rozwijasz regiony koncentrycznie z losowo zaszczepionych punktów, które są wystarczająco oddalone od siebie.

Cóż za zabawne pytanie :) To podejście jest trochę oparte na komórkach Vornoi, ale metryka odległości nie jest dość euklidesowa (użyłem mocy 1,5 zamiast 2,0) i ma w sobie trochę losowości. Może przeskakiwać nad wodą, co nie jest idealne.

Pobliskie regiony można łączyć ze sobą, aby uzyskać bardziej interesujące kształty, w tym celu użyłem N najbliższych sąsiadów, aby to ustalić.

Jeśli jesteś zainteresowany, mogę uzyskać więcej informacji i udostępnić kod Python.