Pracuję nad grą podobną do Civilization i szukam dobrego algorytmu do generowania map świata podobnych do Ziemi. Eksperymentowałem z kilkoma alternatywami, ale nie trafiłem jeszcze na prawdziwego zwycięzcę.
Jedną z opcji jest wygenerowanie mapy wysokości za pomocą szumu Perlina i dodanie wody na takim poziomie, aby około 30% powierzchni świata to ląd. Chociaż szum Perlina (lub podobne techniki oparte na fraktali) jest często używany w terenie i jest dość realistyczny, nie oferuje zbyt wiele w zakresie kontroli liczby, rozmiaru i położenia powstałych kontynentów, co chciałbym z perspektywy rozgrywki.
Drugą opcją jest rozpoczęcie od losowo umieszczonego ziarna z jednym kafelkiem (pracuję na siatce kafelków), określenie pożądanego rozmiaru kontynentu i dodawanie w każdej turze płytki, która jest poziomo lub pionowo przylegająca do istniejącego kontynentu, aż osiągnąłeś żądany rozmiar. Powtórz dla innych kontynentów. Ta technika jest częścią algorytmu używanego w Civilization 4. Problem polega na tym, że po umieszczeniu kilku pierwszych kontynentów można wybrać lokalizację startową, która jest otoczona przez inne kontynenty, a więc nie będzie pasować do nowego. Ma również tendencję do odradzania się kontynentów zbyt blisko siebie, co skutkuje czymś, co bardziej przypomina rzekę niż kontynenty.
Czy ktoś zna dobry algorytm generowania realistycznych kontynentów na mapie opartej na siatce, zachowując jednocześnie kontrolę nad ich liczbą i względnymi rozmiarami?
Odpowiedzi:
Możesz wziąć przykład z natury i zmodyfikować swój drugi pomysł. Po wygenerowaniu kontynentów (które są mniej więcej tej samej wielkości), spraw, aby losowo się poruszały i obracały, zderzały się, deformowały i oddalały od siebie. (Uwaga: może to nie być najłatwiejsza rzecz do wdrożenia).
Edycja: Oto inny sposób na zrobienie tego, wraz z implementacją - generowanie map wielokątnych dla gier .
źródło
Proponuję cofnąć się i
Gdy już to zrobisz, możesz zacząć wdrażać algorytm, który powinien mieć następujący kształt:
Aby ulepszyć, możesz wypróbować różnego rodzaju standardowe sztuczki optymalizacyjne, niezależnie od tego, czy jest to symulowane wyżarzanie, programowanie genetyczne, czy coś całkowicie ad hoc , na przykład przesunięcie losowo wybranego kwadratu krawędziowego z dowolnego miejsca na kontynencie do krawędzi przeciwnej do środka masy kontynentu. Ale kluczem do sukcesu jest napisanie programu, który odróżni dobre kontynenty od złych. Zacznij od ręcznie rysowanych kontynentów, a także kontynentów testowych, aż uzyskasz coś, co Ci się podoba.
źródło
Napisałem coś podobnego do tego, czego szukasz dla automatycznego klona Civilization 1 w stylu wygaszacza ekranu. Dla przypomnienia, napisałem to na VB.net, ale ponieważ nie wspominasz o języku ani platformie w swoim pytaniu, zatrzymam to abstrakcyjne.
„Mapa” określa liczbę kontynentów, zróżnicowanie wielkości kontynentów (np. 1,0 utrzymywałoby wszystkie kontynenty o tym samym przybliżonym obszarze lądowym, a do 0,1 pozwoliłoby istnieć kontynentom z 1/10 masy największego kontynentu), maksymalny obszar lądowy (w procentach) do wygenerowania i centralne odchylenie względem ziemi. „Ziarno” jest rozmieszczone losowo po mapie dla każdego kontynentu, ważone w kierunku środka mapy zgodnie z centralnym nastawieniem (np. Niskie odchylenie powoduje, że rozproszone kontynenty są bardziej podobne do Ziemi, gdzie wysokie centralne odchylenie będzie bardziej przypominać Pangea). Następnie dla każdej iteracji wzrostu „nasiona” przypisują kafelki terenu zgodnie z algorytmem dystrybucji (więcej o tym później), aż do osiągnięcia maksymalnej powierzchni lądu.
Algorytm rozmieszczenia terenu może być tak precyzyjny, jak chcesz, ale znalazłem bardziej interesujące wyniki, stosując różne algorytmy genetyczne i rzucając kostką. „Gra w życie” Conwaya jest naprawdę łatwa do rozpoczęcia. Będziesz musiał dodać NIEKTÓRE globalnie świadome logiki, aby uniknąć wzajemnego zrastania się kontynentów, ale w większości przypadków same zajmują się sobą. Problem, który znalazłem w przypadku podejść opartych na bardziej fraktali (co było moim pierwszym zamysłem), polegał na tym, że wyniki albo wyglądały na zbyt wzorzyste, albo prowadziły do zbyt wielu scenariuszy wymagających zasad obejścia opartych na hacky, aby uzyskać wynik, który wciąż nie był wystarczająco dynamiczny. W zależności od używanego algorytmu możesz zastosować „rozmywanie” wyniku, aby wyeliminować takie rzeczy, jak obfite jednokwadratowe kafelki oceanu i linie brzegowe w kratkę. W przypadku pojawienia się czegoś w rodzaju kontynentu otoczonego przez kilka innych i nie mającego miejsca na rozwój, przenieś nasiona do nowego punktu na mapie i kontynuuj etapy wzrostu. Tak, może to oznaczać, że czasami kończy się na większej liczbie kontynentów niż planowano, ale jeśli naprawdę jest to coś, czego zdecydowanie nie chcesz, to innym sposobem na uniknięcie tego jest odchylenie algorytmów wzrostu, tak aby faworyzowały wzrost w kierunku, w którym najmniej blisko do innych. posiew. W najgorszym przypadku (w każdym razie moim zdaniem) możesz oznaczyć serię jako nieważną, gdy ziarno nie ma już miejsca na wzrost i wygenerowanie nowej mapy. Po prostu upewnij się, że ustawiłeś maksymalną liczbę prób, więc jeśli określono coś nierealistycznego (np. Dopasowanie 50 kontynentów o parzystej wadze na planszy 10x10), nie spędza wieczności na próbach znalezienia prawidłowego rozwiązania.
Nie mogę ręczyć za to, jak robi to Civ itp. I oczywiście nie obejmuje takich rzeczy, jak klimat, wiek lądowy itp., Ale bawiąc się algorytmem wzrostu nasion, można uzyskać całkiem interesujące wyniki, które przypominają kontynenty, archipelagi itp. zastosuj to samo podejście do produkcji rzek, pasm górskich, które wyglądają na „organiczne”.
źródło
Stworzyłem coś podobnego do twojego pierwszego obrazu w JavaScript. To nie jest super wyrafinowane, ale działa:
http://jsfiddle.net/AyexeM/zMZ9y/
źródło
Artykuł o generowaniu map poligonalnych opisuje krok po kroku generowanie map, eliminując wielokąty Woronoja.
Ten gość podał też wszystkie kody źródłowe. Jest to Flash (ActionScript 3 / ECMAScript), ale można go przenieść na dowolny inny język obiektowy
Lub spróbuj użyć algorytmów zaimplementowanych w niektórych programach środowiska fraktalnego, takich jak TerraJ
źródło
Po prostu myślę o mankiecie tutaj:
Wybierz punkty początkowe i przypisz każdemu losowo wylosowany (oczekiwany) rozmiar. Jeśli chcesz, możesz zachować osobne losowanie rozmiarów dla planowanych kontynentów i planowanych wysp.
Pętla nad elementami lądu, a tam, gdzie nie są jeszcze w planowanym rozmiarze, dodaj jeden kwadrat. Ale fajną częścią jest rozważenie szansy, że każdy sąsiedni element będzie tym jedynym. Kilka sugestii, które mogą mieć znaczenie:
Kontynuuj, aż wszystkie masy lądowe osiągną planowany rozmiar lub z jakiegoś powodu nie będą już mogły rosnąć.
Zwróć uwagę, że dostosowanie parametru do tych współczynników wagi pozwala dostroić rodzaj generowanego świata, co jest cechą, którą lubiłem w niektórych cywilizacjach.
W ten sposób będziesz musiał generować teren dla każdego bitu osobno.
źródło
Możesz wypróbować algorytm kwadratu diamentowego lub szum Perlina, aby wygenerować coś w rodzaju mapy wysokości. Następnie przypisz wartości zakresów do tego, co pojawia się na mapie. Jeśli Twój „wzrost” wynosi od 0 do 100, zrób 0 - 20 wody, 20 - 30 plaż, 30 - 80 traw, 80 - 100 gór. Myślę, że notch zrobił coś podobnego do tego w minicraftach, ale nie jestem ekspertem, jestem po prostu nastawiony na diamentowy kwadrat po tym, jak w końcu zaczął działać.
źródło
Myślę, że można tu zastosować podejście w stylu „programowania dynamicznego”.
Bardzo dobrze będzie przyjrzeć się niektórym „Algorytmom układu wykresów”
Możesz je zmodyfikować, aby dostosować je do swoich potrzeb.
źródło
Miałem pomysł na stworzenie mapy podobnej do odpowiedzi płyt tektonicznych. To wyglądało mniej więcej tak:
Jest to podobne do działania grawitacji w przestrzeni 3D. To dość skomplikowane. Prostszy algorytm dla twoich potrzeb działałby w następujący sposób:
Daj mi znać, jak to działa. Sam nigdy tego nie próbowałem.
PS. Widzę, że jest to podobne do tego, co próbowałeś. Z wyjątkiem tego, że ustawia wszystkie nasiona naraz, przed rozpoczęciem, więc kontynenty będą wystarczająco daleko od siebie i zatrzymają się, gdy mapa zostanie wystarczająco wypełniona.
źródło
Właściwie tego nie próbowałem, ale zainspirowała mnie odpowiedź Davida Johnstone'a dotycząca płyt tektonicznych. Próbowałem to wdrożyć samodzielnie w moim starym projekcie Civ, a kiedy przyszło do radzenia sobie z kolizjami, miałem inny pomysł. Zamiast bezpośrednio generować kafelki, każdy kontynent składa się z węzłów. Rozłóż masę na każdy węzeł, a następnie wygeneruj serię kontynentów typu „blob” przy użyciu metody 2D metaballi. Tektonikę i dryf kontynentów byłoby śmiesznie łatwo „udawać”, po prostu przesuwając węzły. W zależności od tego, jak skomplikowane chcesz jechać, możesz nawet zastosować takie rzeczy, jak prądy, aby poradzić sobie z ruchem węzłów i wygenerować pasma górskie, które odpowiadają nakładającym się granicom płyt. Prawdopodobnie nie dodałby tak dużo do rozgrywki,
Dobre wyjaśnienie metaballów, jeśli wcześniej z nimi nie pracowałeś:
http://www.gamedev.net/page/resources/_//feature/fprogramming/exploring-metaballs-and-isosurfaces-in-2d-r2556
źródło
Oto, o czym myślę, ponieważ mam zamiar zaimplementować coś takiego, co mam do gry w fazie rozwoju. :
Świat podzielony na regiony. w zależności od wielkości świata określi, ile regionów. W tym przykładzie przyjmiemy średni świat z 6 regionami. Każda strefa siatki dzieli się na 9 stref siatki. te strefy siatki dzielą się na 9 sieci każda. (nie dotyczy to ruchu postaci, ale jedynie tworzenia map) Siatki są przeznaczone dla biomów, strefy siatki są dla obiektów lądowych (kontynent kontra ocean), a regiony dla ogólnego klimatu. Siatki rozpadają się na płytki.
Regiony generowane losowo otrzymują przypisane logiczne zestawy klimatyczne. Na przykład strefy siatki są losowo przypisywane; ocean lub ląd. Siatkom przypisywane są losowo biomy z modyfikatorami w oparciu o ich strefy siatki i klimat, są to lasy, pustynie, równiny, lodowce, bagna lub wulkan. Po przypisaniu wszystkich tych podstaw, nadszedł czas, aby połączyć je ze sobą, używając losowej funkcji procentowej, która wypełnia zestawy kafelków. Na przykład; jeśli masz biom leśny, obok biomu pustynnego, masz algorytm, który zmniejsza prawdopodobieństwo, że dachówka będzie „leśna”, a zwiększy, że będzie „pustynna”. Tak więc, mniej więcej w połowie między nimi, zobaczysz rodzaj mieszanego efektu łączącego dwa biomy, aby wyłączyć nieco płynne przejście między nimi. Przejście z jednej strefy siatki do drugiej prawdopodobnie wymagałoby trochę więcej pracy, aby zapewnić logiczne formacje lądu, na przykład biom z jednej strefy sieci, która styka się z biomem z innej, zamiast prostego procentu przełączania opartego na bliskości. Na przykład istnieje 50 kafelków od środka biomu do krawędzi biomu, co oznacza, że jest ich 50 od krawędzi, z którą styka się do środka następnego biomu. Logicznie rzecz biorąc, pozostawiłoby to 100% zmianę z jednego biomu do drugiego. Więc gdy płytki zbliżają się do granicy dwóch biomów, procent zmniejsza się do około 60%. Myślę, że nierozsądne byłoby dawanie zbyt dużego prawdopodobieństwa przekroczenia biomów daleko od granicy, ale chcesz, aby granica była nieco wymieszana. W przypadku stref siatki zmiana procentowa będzie znacznie wyraźniejsza. Zamiast procentowego spadku do około 60%, spadłby tylko do około 80%. Następnie należałoby przeprowadzić kontrolę wtórną, aby upewnić się, że nie ma przypadkowej płytki wody pośrodku biomu lądowego obok oceanu bez jakiejś logiki. Więc albo połącz tę płytkę z wodą z masą oceanu, aby utworzyć kanał, aby wyjaśnić płytkę z wodą, lub usuń ją całkowicie. Teren w biomie opartym na wodzie jest łatwiejszy do wyjaśnienia za pomocą wychodni skalnych i tym podobnych.
Och, trochę głupi, przepraszam.
źródło
Umieszczałbym teren fraktalny zgodnie z pewnym układem, o którym wiesz, że "działa" (np. Siatka 2x2, romb itp., Z pewnymi jitterem), ale z rozkładem Gaussa tłumiącym szczyty w dół w kierunku krawędzi centrów kontynentu. Ustaw poziom wody niżej, tak aby w większości był lądem, aż zbliżysz się do krawędzi.
źródło