Szukam dobrego algorytmu generowania mapy świata [zamknięte]

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?

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 .

Proponuję cofnąć się i

1. Pomyśl o tym, co wyróżnia „dobre” kontynenty.
2. Napisz algorytm, który może odróżnić dobry układ kontynentów od złego.
3. Doprecyzuj algorytm, aby móc oszacować, jak dobry jest dobry układ.

Gdy już to zrobisz, możesz zacząć wdrażać algorytm, który powinien mieć następujący kształt:

• Generuj kiepskie kontynenty, a następnie ulepszaj je.

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.

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”.

Stworzyłem coś podobnego do twojego pierwszego obrazu w JavaScript. To nie jest super wyrafinowane, ale działa:

http://jsfiddle.net/AyexeM/zMZ9y/

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Untitled Document</title>

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script>
<style type="text/css">
    #stage{
        font-family: Courier New, monospace;
    }
    span{
        display: none;
    }
    .tile{
        float:left;
        height:10px;
        width:10px;
    }
    .water{
        background-color: #55F;
    }
    .earth{
        background-color: #273;
    }
</style>
</head>

<body>


<div id="stage">

</div>

<script type="text/javascript">

var tileArray = new Array();
var probabilityModifier = 0;
var mapWidth=135;
var mapheight=65;
var tileSize=10;

var landMassAmount=2; // scale of 1 to 5
var landMassSize=3; // scale of 1 to 5


$('#stage').css('width',(mapWidth*tileSize)+'px');


for (var i = 0; i < mapWidth*mapheight; i++) {

    var probability = 0;
    var probabilityModifier = 0;

    if (i<(mapWidth*2)||i%mapWidth<2||i%mapWidth>(mapWidth-3)||i>(mapWidth*mapheight)-((mapWidth*2)+1)){

        // make the edges of the map water
        probability=0;
    }
    else {

        probability = 15 + landMassAmount;

        if (i>(mapWidth*2)+2){

            // Conform the tile upwards and to the left to its surroundings 
            var conformity =
                (tileArray[i-mapWidth-1]==(tileArray[i-(mapWidth*2)-1]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-mapWidth]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-1]))+
                (tileArray[i-mapWidth-1]==(tileArray[i-mapWidth-2]));

            if (conformity<2)
            {
                tileArray[i-mapWidth-1]=!tileArray[i-mapWidth-1];
            }
        }

        // get the probability of what type of tile this would be based on its surroundings 
        probabilityModifier = (tileArray[i-1]+tileArray[i-mapWidth]+tileArray[i-mapWidth+1])*(19+(landMassSize*1.4));
    }

    rndm=(Math.random()*101);
    tileArray[i]=(rndm<(probability+probabilityModifier));

}

for (var i = 0; i < tileArray.length; i++) {
    if (tileArray[i]){
        $('#stage').append('<div class="tile earth '+i+'"> </div>');
    }
    else{
        $('#stage').append('<div class="tile water '+i+'"> </div>');
    }
}

</script>

</body>
</html>

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

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:

1. Odległość do najbliższego „innego” lądu. Co więcej, lepiej generuje szerokie przestrzenie oceaniczne. Bliżej jest lepiej tworzy wąskie kanały. Musisz zdecydować, czy pozwolisz, aby bity również się scalały.
2. Odległość od nasion. Bliżej jest lepiej oznacza zwarte masy lądowe, dalej jest lepiej oznacza długie nawleczone bity
3. Liczba przyległych placów ziemi. Ważenie na korzyść wielu sąsiednich kwadratów daje gładkie wybrzeże, a preferowanie kilku daje dużo wlotów i półwyspów.
4. Czy w pobliżu znajdują się kwadraty „zasobów”? Zależy od zasad gry, kiedy generujesz kwadrat zasobów i czy chcesz to ułatwić.
5. Czy pozwolisz bitom zbliżyć się do biegunów lub połączyć się z nimi?
6. ??? nie wiem co jeszcze

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.

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ć.

Myślę, że można tu zastosować podejście w stylu „programowania dynamicznego”.

Najpierw rozwiązuj małe problemy i inteligentnie łącz rozwiązania, aby rozwiązać większy problem.

A1= [elliptical rectangular random ... ]// list of continents with area A1 approx. 
A2= [elliptical rectangular random ... ]// list of continents with area A2 approx.
A3= [elliptical rectangular random ... ]// list of continents with area A3 approx.
...
An= [elliptical rectangular random ... ]// list of continents with area An approx.

// note that elliptical is approximately elliptical in shape and same for the other shapes.

Choose one/more randomly from each of the lists (An).

Now you have control over number and area of continents.

You can use genetic algorithm for positioning them 
as you see "fit" ;)

Bardzo dobrze będzie przyjrzeć się niektórym „Algorytmom układu wykresów”

• Algorytmy oparte na sile
• Algorytm genetyczny dla układu grafów

Możesz je zmodyfikować, aby dostosować je do swoich potrzeb.

Miałem pomysł na stworzenie mapy podobnej do odpowiedzi płyt tektonicznych. To wyglądało mniej więcej tak:

1. przeciągnij przez kwadraty siatki, dając każdemu kwadratowi kwadrat „ziemi”, jeśli rnd <= 0,292 (rzeczywisty procent suchego lądu na planecie Ziemia).
2. Przenieś każdy kawałek ziemi o jeden kwadrat w kierunku najbliższego, większego sąsiada. Jeśli sąsiedzi są w równej odległości, idź w kierunku większego kawałka. Jeśli kawałki są tego samego rozmiaru, wybierz jeden losowo.
3. jeśli dwa pola ziemi się zetkną, zgrupuj je w kawałku, przesuwając od teraz wszystkie kwadraty jako jeden.
4. Powtórz od kroku 2. Zatrzymaj, gdy wszystkie fragmenty zostaną połączone.

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:

1. Upuść n pól startowych w losowych pozycjach x, y i dopuszczalnych odległościach od siebie. To nasiona dla waszych kontynentów. (Użyj twierdzenia Pitagorasa, aby upewnić się, że nasiona mają minimalną odległość między sobą a wszystkimi innymi.)
2. odradzaj kwadrat lądowy z istniejącego kwadratu lądowego w losowym kierunku, jeśli jest to kwadrat oceanu.
3. powtórz krok 2. Zatrzymaj się, gdy pola lądu zajmą 30% całkowitego rozmiaru mapy.
4. jeśli kontynenty są wystarczająco blisko siebie, w razie potrzeby upuść mosty lądowe, aby zasymulować efekt panamy.
5. W razie potrzeby upuść mniejsze, przypadkowe wyspy, aby uzyskać bardziej naturalny wygląd.
6. dla każdego dodatkowego kwadratu „wyspy”, który dodasz, wytnij morza śródlądowe i pola jezior z kontynentów, używając tego samego algorytmu w odwrotnej kolejności. Pozwoli to utrzymać żądaną wartość procentową ziemi.

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.

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

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.

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.