Ищете хороший алгоритм создания карты мира [закрыто]

Я работаю над игрой типа Civilization, и я ищу хороший алгоритм для создания карт мира, подобных Земле. Я экспериментировал с несколькими альтернативами, но пока не нашел настоящего победителя.

Один из вариантов - создать карту высот с использованием шума Перлина и добавить воду на таком уровне, чтобы около 30% земли было сушей. Хотя шум Перлина (или аналогичные методы на основе фракталов) часто используется для ландшафта и является достаточно реалистичным, он не предлагает много способов контроля над числом, размером и положением получаемых континентов, что я хотел бы есть с точки зрения игрового процесса.

Второй вариант - начать с произвольно расположенного начального числа из одной плитки (я работаю над сеткой плиток), определить желаемый размер для континента и каждый ход добавлять плитку, которая по горизонтали или вертикали примыкает к существующему континенту, пока вы достигли желаемого размера. Повторите то же самое для других континентов. Этот метод является частью алгоритма, используемого в Civilization 4. Проблема в том, что после размещения первых нескольких континентов можно выбрать начальное местоположение, окруженное другими континентами и, следовательно, не подходящее для нового. Кроме того, он имеет тенденцию создавать континенты слишком близко друг к другу, что приводит к чему-то, что больше похоже на реку, чем на континенты.

Кто-нибудь знает хороший алгоритм для создания реалистичных континентов на сеточной карте, сохраняя при этом контроль над их количеством и относительными размерами?

Вы можете взять пример с природы и изменить свою вторую идею. После того, как вы сгенерируете свои континенты (которые примерно одинакового размера), заставьте их беспорядочно перемещаться, вращаться, сталкиваться, деформировать друг друга и дрейфовать друг от друга. (Примечание: возможно, это не самая простая вещь для реализации.)

Изменить: вот еще один способ сделать это, в комплекте с реализацией - Генерация полигональных карт для игр .

Я предлагаю вам вернуться и

1. Подумайте, что делает континенты "хорошими".
2. Напишите алгоритм, который отличит хорошую континентальную планировку от плохой.
3. Уточните алгоритм, чтобы вы могли количественно оценить, насколько хорош хороший макет.

Как только вы это сделаете, вы можете приступить к реализации алгоритма, который должен иметь следующую форму:

• Создавайте дрянные континенты, а затем улучшайте их.

Для улучшения вы можете попробовать всевозможные стандартные приемы оптимизации, будь то имитация отжига, генетическое программирование или что-то совершенно специальное , например, перемещение случайно выбранного граничного квадрата из любого места на континенте к краю, противоположному центру масс континента. Но главное - уметь написать программу, которая отличит хорошие континенты от плохих. Начните с рисованных континентов, а также ваших тестовых континентов, пока не получите то, что вам нравится.

Я написал что-то похожее на то, что вам нужно для автоматического клона Civilization 1. Для записи я написал это на VB.net, но поскольку вы ничего не упоминаете о языке или платформе в своем вопросе, я сохраню это абстрактно.

«Карта» указывает количество континентов, разницу в размерах континентов (например, 1.0 сохранит все континенты с одинаковой приблизительной площадью суши, уменьшение до 0,1 позволит континентам существовать с 1/10 массы самого большого континента), максимальную площадь суши (в процентах) для генерации и центрального смещения земли. «Семя» случайным образом распределяется по карте для каждого континента, взвешенное по направлению к центру карты в соответствии с центральным смещением (например, низкое смещение создает распределенные континенты, более похожие на Землю, тогда как высокое центральное смещение будет больше напоминать Пангея). Затем для каждой итерации роста «семена» назначают тайлы земли в соответствии с алгоритмом распределения (подробнее об этом позже), пока не будет достигнута максимальная площадь земли.

Алгоритм распределения земли может быть сколь угодно точным, но я нашел более интересные результаты, применяя различные генетические алгоритмы и бросая кости. «Игру жизни» Конвея действительно легко начать. Вам нужно будет добавить НЕКОТОРУЮ глобальную логику, чтобы избежать врастания континентов друг в друга, но по большей части вещи сами о себе позаботятся. Проблема, которую я обнаружил с более фрактальными подходами (что было моим первым желанием), заключалась в том, что результаты либо выглядели слишком шаблонно, либо приводили к слишком большому количеству сценариев, требующих хакерских обходных правил для получения результата, который все еще не казался достаточно динамичным. В зависимости от используемого алгоритма вы можете применить «размытие» к результату, чтобы исключить такие вещи, как обильные одноквадратные плитки океана и клетчатые береговые линии. В случае появления чего-то вроде континента в окружении нескольких других, которому некуда больше расти, переместите семя в новую точку на карте и продолжите прохождение роста. Да, это может означать, что иногда у вас оказывается больше континентов, чем планировалось, но если это действительно то, чего вы категорически не хотите, тогда еще один способ помочь избежать этого - смещать алгоритмы роста, чтобы они поддерживали рост в направлении с наименьшей близостью к другим. семена. В худшем случае (во всяком случае, на мой взгляд) вы можете пометить серию как недействительную, когда семени некуда расти и создать новую карту. Просто убедитесь, что вы установили максимальное количество попыток, чтобы, если указано что-то нереалистичное (например, уместить 50 равновзвешенных континентов на доске 10x10), он не тратит вечно на попытки найти правильное решение.

Я не могу поручиться за то, как это делают Civ и т. Д., И, конечно, не касается таких вещей, как климат, возраст земли и т. Д., Но, играя с алгоритмом роста семян, вы можете получить довольно интересные результаты, которые напоминают континенты, архипелаги и т. Д. используйте тот же подход для создания «органических» рек, горных хребтов и т. д.

Я создал что-то похожее на ваше первое изображение на JavaScript. Это не очень сложно, но работает:

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>

В статье о создании полигональной карты описывается пошаговая генерация карты без разбивки на полигоны Вороного.

Этот парень дает и все исходники. Это Flash (ActionScript 3 / ECMAScript), но его можно перенести на любой другой объектно-ориентированный язык.

Или попробуйте использовать алгоритмы, реализованные в каком-нибудь программном обеспечении фрактальной среды, таком как TerraJ

Просто подумайте о манжете здесь:

Выберите несколько начальных точек и назначьте каждой случайно выбранный (желаемый) размер. При желании вы можете создать отдельный размер для запланированных континентов и запланированных островов.

Оберните петлей элементы земли и там, где они еще не достигли запланированного размера, добавьте один квадрат. Но самое интересное - это взвесить шанс, что каждый соседний элемент будет единым целым. Некоторые предположения, которые могут влиять на:

1. Расстояние до ближайшего «другого» участка. Дальше лучше всего порождает обширные океанические пространства. Чем ближе, тем лучше узкие каналы. Вы должны решить, собираетесь ли вы также позволить битам сливаться.
2. Расстояние от семян. Чем ближе, тем лучше - компактные участки земли, чем дальше, тем лучше - долота с длинной нитью
3. Количество имеющихся прилегающих земельных участков. Если поставить вес в пользу множества прилегающих квадратов, у вас будет гладкое побережье, а если вы предпочтете несколько, то вы получите много бухт и полуостровов.
4. Наличие поблизости квадратов "ресурсов"? Зависит от правил игры, когда вы генерируете ресурсный квадрат и хотите ли вы упростить задачу.
5. Вы позволите битам приблизиться или соединиться с полюсами?
6. ??? не знаю что еще

Продолжайте до тех пор, пока все участки земли не достигнут запланированного размера или не перестанут расти по какой-либо причине.

Обратите внимание, что изменение параметра для этих весовых коэффициентов позволяет вам настроить тип создаваемого мира, что мне понравилось в некоторых цивилизациях.

Таким образом, вам нужно будет создать ландшафт для каждого бита отдельно.

Вы можете попробовать алгоритм ромбовидного квадрата или шум Перлина, чтобы создать что-то вроде карты высот. Затем присвойте значения диапазонов тому, что отображается на карте. Если ваша «высота» идет от 0 до 100, то сделайте 0-20 воды, 20-30 пляжей, 30-80 травы, 80-100 гор. Я думаю, что Notch сделал что-то похожее на это в миникрафте, но я не эксперт, я просто настроен на алмазный квадрат после того, как наконец заработал.

Думаю, здесь можно использовать подход в стиле «динамического программирования».

Сначала решайте небольшие проблемы и разумно комбинируйте решения для решения более серьезных проблем.

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" ;)

Было бы очень хорошо взглянуть на некоторые «Алгоритмы построения графиков»

• Силовые алгоритмы
• Генетический алгоритм построения графиков

Вы можете изменить их по своему усмотрению.

У меня была идея создания карты, аналогичной ответу тектонических плит. Это было примерно так:

1. проведите по квадратам сетки, получая каждый квадрат как «земельный» квадрат, если rnd <= 0,292 (фактический процент суши на планете Земля).
2. Перенесите каждый кусок земли на один квадрат к ближайшему большему соседу. Если соседи равноудалены, перейдите к большему блоку. Если куски одинакового размера, выберите один случайным образом.
3. если два квадрата земли соприкасаются, сгруппируйте их в кусок, с этого момента перемещая все квадраты как один.
4. повторите с шага 2. Остановитесь, когда все блоки будут подключены.

Это похоже на то, как гравитация работает в трехмерном пространстве. Это довольно сложно. Более простой алгоритм для ваших нужд будет работать следующим образом:

1. Поместите n квадратов стартовой земли в случайных положениях x, y и на приемлемом расстоянии друг от друга. Это семена ваших континентов. (Используйте теорему Пифагора, чтобы семена имели минимальное расстояние между собой и всеми остальными.)
2. создать квадрат суши из существующего квадрата суши в случайном направлении, если это направление - квадрат океана.
3. повторите шаг 2. Остановитесь, когда земельные участки заполнят 30% от общего размера карты.
4. если континенты расположены достаточно близко друг к другу, установите наземные мосты, чтобы имитировать эффект Панамы.
5. Добавляйте меньшие случайные острова по желанию для более естественного вида.
6. для каждого добавляемого вами дополнительного квадрата «острова» вырежьте квадраты внутренних морей и озер из континентов, используя тот же алгоритм в обратном порядке. Это сохранит процент земли на желаемом уровне.

Сообщите мне, как это работает. Сам никогда не пробовал.

PS. Я вижу, это похоже на то, что вы пробовали. За исключением того, что он устанавливает все семена сразу перед началом, поэтому континенты будут достаточно далеко друг от друга и остановятся, когда карта будет достаточно заполнена.

Я на самом деле не пробовал это, но это было вдохновлено ответом Дэвида Джонстона относительно тектонических плит. Я сам пробовал реализовать это в своем старом проекте Civ, и когда дело дошло до обработки столкновений, у меня появилась другая идея. Вместо того, чтобы напрямую генерировать плитки, каждый континент состоит из узлов. Распределите массу по каждому узлу, затем сгенерируйте серию континентов-капель, используя двухмерный метабаллический подход. Тектонику и дрейф континентов было бы до смешного легко «подделать», просто перемещая узлы. В зависимости от того, насколько сложным вы хотите заниматься, вы даже можете применить такие вещи, как токи, для управления движением узлов и создания горных хребтов, соответствующих перекрывающимся границам плит. Наверное, не стал бы так много добавлять в игровой процесс,

Хорошее объяснение метабаллов, если вы раньше с ними не работали:

http://www.gamedev.net/page/resources/_//feature/fprogramming/exploring-metaballs-and-isosurfaces-in-2d-r2556

Вот что я думаю, поскольку собираюсь реализовать что-то подобное, что у меня есть для игры, находящейся в разработке. :

Мир разделен на регионы. в зависимости от размера мира он определит, сколько регионов. В этом примере мы предположим, что мир среднего размера с 6 регионами. Каждая зона сетки разбивается на 9 зон сетки. эти зоны сетки разбиваются на 9 сеток каждая. (это не для движения персонажа, а просто для создания карты) Сетки предназначены для биомов, зоны сетки - для изгиба наземных объектов (континент против океана), а регионы - для общего климата. Сетки разбиваются на плитки.

Сгенерированным случайным образом регионам присваиваются логические наборы климатических параметров. Например, зоны сетки назначаются случайным образом; океан или суша. Сетки назначаются биомам случайным образом с модификаторами в зависимости от их зон сетки и климата: лес, пустыня, равнины, ледник, болото или вулканический. После того, как все эти основы назначены, пора объединить их вместе, используя функцию на основе случайных процентов, которая заполняет наборы плиток. Например; если у вас есть лесной биом, рядом с пустынным биомом, у вас есть алгоритм, который уменьшает вероятность того, что плитка будет «лесной», и увеличивает, что она будет «пустыней». Итак, примерно на полпути между ними вы увидите своего рода смешанный эффект, объединяющий два биома для несколько плавного перехода между ними. Переход от одной зоны сетки к другой, вероятно, потребует немного больше работы, чтобы обеспечить логические образования на суше. Как, например, биом из одной зоны сетки, который касается биома из другой, вместо простого процента переключения, основанного на близости. Например, есть 50 плиток от центра биома до края биома, то есть 50 плиток от края, которого он касается, до центра следующего биома. Логично, что это оставило бы 100% -ное изменение от одного биома к другому. По мере того, как плитки приближаются к границе двух биомов, процент сужается до 60% или около того. Я думаю, было бы неразумно давать слишком большую вероятность пересечения биомов далеко от границы, но вы захотите, чтобы граница была несколько смешанной. Для зон сетки процентное изменение будет более выраженным. Вместо того, чтобы упасть примерно до 60%, он упадет только до 80%. Затем необходимо будет выполнить вторичную проверку, чтобы убедиться, что в центре наземного биома рядом с океаном нет случайного водного тайла без какой-либо логики. Итак, либо соедините этот тайл воды с массой океана, чтобы создать канал для объяснения тайла воды, либо удалите его совсем. Землю в водном биоме легче объяснить, используя обнажения горных пород и тому подобное.

Ой, тупой, прости.

Я бы разместил фрактальный ландшафт в соответствии с некоторой компоновкой, которая, как вы знаете, «работает» (например, сетка 2x2, ромб и т.д., с некоторым дрожанием), но с гауссовым распределением демпфирования с пиками вниз к краям центров континентов. Установите уровень воды ниже, чтобы он был в основном на суше, пока не приблизитесь к краям.