Генерация мира: Ландшафт и характеристики местности

Что нам стоит мир построить?

Задачи генерации целого мира в игре никогда не давала мне покоя. Полностью созданный мир на основе псевдо-случайных чисел делает опыт каждого игрока уникальным. Вообразите себе не только случайную карту мира, но и случайные квесты, случайные подземелья, случайных NPC. Абсолютно недетерминированный игровой процесс создает ощущение… магии.
 
Когда игра сама создает себя — это искусство, это волшебство. Никогда нельзя быть уверенным в том, что тебя будет поджидать в подземелье, какое задание ты получишь, что произойдет, если ты откажешься делать что-либо при разговоре с NPC.
 
В этом цикле статей я расскажу про генерацию карты мира, ландшафта, природных зон.
 
Интересно? Прошу под кат!

 

Введение

Создание карты мира можно разбить на несколько базовых задач:
  1. Генерация поверхности планеты
  2. Определение характеристик (температура, влажность, высота над уровнем моря) каждой точки на карте
  3. Распределение биомов
  4. Заполнение игрового слоя планеты разрушаемыми блоками (блоки земли, снега, воды, травы)
 
Детально поговорим про каждую основную задачу.
 

Генерация поверхности планеты

Когда я только начинал заниматься этой проблемой (>2 лет назад), на просторах сети было очень ограниченное количество статей, которые не давали рекомендаций к действию, а как то отдаленно описывали несформированные мысли по поводу тех или иных подходов к этой задаче. Поэтому, пришлось все придумывать самому. Описанный мною подход не претендует на уникальность, я бы даже не смог его назвать сейчас (с высоты полученного опыта за последние 2 года) эффективным способом генерации ландшафта. Но, он работает, работает стабильно, так что давайте рассмотрим его поближе.
 
Шум Перлина
Популярный способ генерации поверхности мира — использование шума Перлина.
Я использовал каноничный метод генерации шума Перлина, который можно с легкостью найти на просторах интернета. Приведу код класса, который отвечает у меня за генерцию шума:
 
 
Как можно заметить, он несильно отличается от примеров, представленных в интернете. Заметим, что я использую двумерный шум, так как планируется, что игра будет двумерная.

Центральный метод, который будет отвечать за генерацию шума для карты — это метод GenerateNoise(double x, double y, double factor, double persistence, double frequency, double amplitude).  Назначение параметров его сигнатуры достаточно очевидно, но часть из них выглядят весьма загадочно — что следует понимать содержательно под параметрами persistence, frequency, amplitude?

  • Persistence — это постоянность рельефности будущего ландшафта. Я использую значения, близкие к 1, чтобы получить более реалистичный ландшафт будущей карты мира.
  • Frequency — это частота колебаний шума. Содержательно этот параметр отвечает за то, насколько сильно рельеф будет «ломанным» (т.е. значение шума будет колебаться от минимума к максимуму). Для изломанной островной карты рекомендую использовать значение 0.4. Для карты, наиболее близкой к земной, рекомендую использовать значение 0.2.
  • Amplitude — амплитуда шума. Я использую значения, близкие к 1.
 
Рассмотрим примеры полученного ландшафта при использовании различных значений параметров.
 
Снимок шумаПараметры генерации шумаХарактер рельефа
ReliefPersistence = 0.9999f

ReliefFrequency = 0.01f

ReliefAmplitude = 0.9999f
Гладкий, не изломанный рельеф,
несколько ярковыраженных континентов,
не очень много островов.
ReliefPersistence = 0.9999f

ReliefFrequency = 0.02f

ReliefAmplitude = 0.8f
Изломанный рельеф,
карта как будто бы
состоит из множества островов.
ReliefPersistence = 0.9999f

ReliefFrequency = 0.04f

ReliefAmplitude = 0.9999f
Изломанный и раздробленный рельеф,
вся карта состоит из множества островов,
что больше напоминает
один континент с
кучей мелких водоемов.
ReliefPersistence = 0.5f

ReliefFrequency = 0.4f

ReliefAmplitude = 0.99999f
NO WAY


На полученных снимках шума самые светлые участки, которые имеют равномерный цвет — это суша, все остальное — скрыто под водой. При генерации карты мира я использовал еще один параметр — WaterLevel, который используется для отсечения значений шума выше заданного порога. Все, что выше заданного уровня воды — это плоская суша и окрашивается в равномерный серый цвет. Все, что ниже уровня воды — это ландшафт подводного мира. Чем темнее пиксель на карте, тем ниже относительно уровня моря эта точка ландшафта находится.

Что же, у нас есть сгенерированная карта ландшафта. Хотелось бы расположить биомы… Но для этого нам надо установить температуру, определить дальность от воды (иными словами — прибрежное или внутриконтинентальное расположение).

Определение характеристик местности

Что и как нам надо определить?
Для реалистичного расположения биомов на карте мира следует учитывать несколько критериев. В реальной жизни природные зоны формируются на основе температуры, влажности, континентального расположения, перепадов температуры в различные сезоны, количества осадков и т.д.
 
В игре не планируется динамическая смена погоды и времен года, поэтому определим список важных критериев, по которым будут располагаться биомы:
  • Средний показатель температуры
  • Дальность от воды
  • Высота относительно уровня моря
 
Высота относительно уровня моря у нас задана — это центрированная нормализованная величина шума Перлина. Дальность от воды (как и высота) — тоже определяется центрированной нормализованной величиной шума Перлина. Такое допущение обосновывается следующими факторами:
  • без отсечения значения шума Перлина местность приобретает исключительно горный характер. Содержательно это означает, что любая суша на планете — это некоторая пологая или крутая гора. Я использую отсечения выше уровня моря, чтобы добиться ровного ландшафта, но ничто не мешает хранить значение шума в данной точке
  • шум Перлина относительно равномерный, т.е. при удалении от некоторого условного водоема высота относительно уровня моря увеличивается «равномерно», что позволяет использовать эту величину в качестве меры удаленности от воды.
 
Осталось только для каждой точки определить температуру.
 
Формирование температурных изотерм
В качестве основы положим ряд ограничений на способ формирование температурных изотерм.
  • Самое жаркое место на планете — это экватор, т.е. середина карты
  • Самое холодное место — это полюса (низ и верх карты)
 
Казалось бы, определить линейную зависимость температуры точки карты относительно экватора и полюсов не составляет труда. Но тогда, характер температурного распределения будет, мягко говоря, нереалистичным. В реальном мире температура падает нелинейно относительно дальности расположения от экватора.
 
Мне понравился характер поведения функции плотность нормального распределения (распределения Гаусса). Она наиболее интересно показывает характер изменения температуры от экватора (значение функции в точке мат. ожидания) до полюсов (значения, близкие к 0). Характер поведения функции достаточно гибко настраивается при помощи параметра среднеквадратичного отклонения.
 
Дабы не быть голословным, приведу иллюстрацию
 
Графики функции плотности нормального распределения при разных параметрах.
 
В нашем случае в точке математического ожидания (параметр u) температура будет принимать максимальное значение — это и будет температура экватора. 
 
Чтобы температура уменьшалась равномерное, необходимо поиграться с параметром среднеквадратичного отклонения. Заметим, что он должен зависеть от ширины карты. В случае, если его сделать фиксированным, независимо от размера карты, температура будет распределяться одинаково и минимальное значение температуры будет установлено всегда на одном и том же расстоянии от экватора.
 
Функция для вычисления плотности вероятности в заданной точке x определяется по стандартной формуле:
 
 
В качестве u установим положение экватора по оси Y (середина карты). В качестве среднеквадратичного отклонения я эмперически подобрал следующее значение:
double sigma = (mapMiddle/2.5);
где mapMiddle — середина карты, т.е. половина от ширины карты.
 
Следует понимать, что в качестве аргумента x мы подставляем координату y, так как именно она отвечает за расположение точки на карте относительно экватора.
 
 
Таким образом, если точки на карте расположены на одной широте, значения их температурных показателей будут одинаковыми. Это не есть хорошо, так как карта будет выглядеть искусственно и деревянно. Добавим небольшой синусоидный «шум» к математическому ожиданию, чтобы сместить его по синусоиде относительно точки идеального экватора:
 мат_ожидание = координаты_экватора + (разброс * sin(x / (32 * pi)));
Параметр разброса будет определять величину плавания экватора, а делитель аргумента синуса — частоту колебаний.
 
Полученный результат будет достаточно гладким. Для внесения некоторой неоднородности я добавил небольшой равномерный шум к значению y при вычислении плотности в текущей точке. Содержательно, это означает, что при вычислении значения температуры в текущей точке на самом деле вычисляется температура в случайной точке в небольшом диапазоне относительно координаты y.
 
Посмотрим примеры температурного распределения на планете при разной длине интервала случайного разброса. Красным оттенком отмечены самые жаркие места (непосредственная близость к экватору), синим цветом — минимальные температуры. Переходы от красного к синему показывают понижение температуры при удалении от экватора.
 
 
Температурное распределениеОписание
Температурное распределение без добавления случайного шума к координате y при вычислении температуры и без синусоидного смещения экватора. Скучно, просто, неинтересно.
Температурное распределение без добавления случайного шума к координате y при вычислении температуры. Наблюдается характерное синусоидное смещение экватора, описанное выше. Температура расположена гладко и равномерно.
Добавлен небольшой шум к координате y. Диапазон шума [-1:1], изменения температурного распределения едва заметны и не вносят особого разнообразия.
Добавлен сильный шум к координате y. Диапазон шума [-10:10], изменения температурного распределения достаточно заметны и вносят сильное разнообразие в температурные значения относительно соседей. (Примечание: зернистость изображения — это не артефакт, это признак шума при вычислении температуры)
 
Подведем итоги.
 
Вычисление значения температуры для заданной точки на карте выполняется в несколько этапов.
 
 
  1. Вычисляем экватор карты (точка мат.ожидания) mapMiddle = map.Height / 2.0
  2. Вычисляем значения среднеквадратичного отклонения sigma = (mapMiddle/2.5)
  3. К текущей рассматриваемой точке y добавляем шум.
  4. Добавляем периодическое синусоидное смещение для экватора (смещаем мат. ожидание на циклическую величину)
  5. Вычисляем значение функции плотности.
  6. Нормализуем его (чтобы получить значение от 0 до 1), разделив на максимальное значение — в точке мат. ожидания, которое можно вычислить так: maxGausDistributionValue = Math.Exp(0) * (1.0 / (sigma * Math.Sqrt(2.0 * Math.PI)))
  7. Центрируем нормализованное значение — вычитаем из него 0.5 (для того, чтобы функция принимала значение в диапазоне от -0.5 до 0.5)
  8. Умножаем на глобальную амплитуду температуры (разницу между максимальной и минимальной температурой)
 
И проделываем все это для каждой точки на карте мира. вычисления выполняются достаточно быстро, а при правильном распараллеливании  - можно добиться еще больших показателей скорости вычисления.
 
Теперь нам надо расположить биомы… Но что такое биомы? Как их задать? Что нужно знать о них? Об этом мы поговорим в следующей статье.
 
Продолжение следует...
Источник: http://cheprogrammer.blogspot.ru/2016/02/map-generation-1.html
переходов: 216

Продолжать в таком же духе?

Похожие статьи

  • Еще раз немного про изометрию, перерасчет координат и вращение камеры
     Добрый день, уважаемые Коленковчане! В этой небольшой статье я хотел бы концентрированно и полностью раскрыть все секреты преобразования изометрических координат в экранные и...
  • Аудио-спектральный принтер
    Вы когда-нибудь слышали о скрытых посланиях в музыке? Я слышал. Больше всего меня заинтересовало, каким образом можно вставить изображение в трек, как в этих случаях. Я узнал,...
  • jSFXR
    -Всем привет! я jSFXR! -Что ты такое? -Я как SFXR, только яваскрипт -нононо! Ведь тебя можноисполЬЗОВАТЬ ПРЯМ В БРАУЗЕРЕ! -Конечно -А ну-ка иди сюда! Так я и сделал. И вот ...
  • synthWave — основной компонент звукогенератора bfxr версии 1.4.1
    Это пост о том, по каким принципам и в каком порядке генерируется звук в bfxr — популярном в среде инди-геймдевелоперов генераторе аудио, доступного на момент написания поста...
10 комментариев
Xitilon

В кои-то веки на Коленку пришёл человек, который поставил кат, и хорошо отформатировал сам пост (что составляет некоторую сложность с нашим редактором, увы). Я рад такому визиту, пост был интересен мне. Заодно посмотрел и блог по ссылке, любопытно.

У нас нет каких-то норм или уровней качества для публикации, поэтому, что называется, feel free. Один момент:

сиречь: эмперически

Тут первое слово — правильно, второе — не совсем.

Ещё, «сильный шум» в визуализации температур — практически не виден даже в том блоге, где картинки большие. Наверное имеет смысл привести участок в большом масштабе, и с большей контрастностью. Ну, это я так, просто заметил. Понятно что уже написанный пост для себя нет большого смысла править по сто раз, я в конце концов сам такие пишу (а также намного хуже).

denisbarrett

Большое спасибо за отзыв, поправил нехорошую формулировку!

Впредь буду более детально относиться к скриншотам)

Palets
Хотел плюсануть, но случайно поставил минус, виноват! Заебатый пост, жду когда про биомы будет.
Xitilon
А какую игру хотелось бы сделать с такой генерацией? Видимо, что-то вроде Цивилизации? Майнкрафт?
denisbarrett

Это очень сложный вопрос...

Много всяких идей перебродило в голове, у меня есть некоторая общая концепция — это полностью случайный мир. Случайный ландшафт, случайные города, случайные NPC, крово-родственные связи между NPC, симуляция жизни (упрощенная, но симуляция) и принятие решения ИИ конкретного NPC о добыче еды, либо о копании алмазов в шахтах на основе либо Марковских цепей, либо нейронный сетей Кохонена. NPC рождаются в семьях, растут, женятся, рожают детей, умирают. Наследуетя специализация от родителей (шахтер, охотник, стражник, повар, алхимик, заклинатель, кузнец), с течением жизни прокачивается. Этакий Симс с Рогаликом одном флаконе.

Так как мир состоит из блоков, каэжый из блоков можно разрушать, собирать, ставить другой и т.д.

Причем, я достаточно хорошо и ясно представляю себе, как все это делать, но времени и мотивации не хватает катастрофически.

Xitilon

Напомнило мне одну «игру» (я бы назвал это арт-объектом), где есть «бесконечный», наполняемый по мере открывания древовидный список, где вселенная состоит из трёх рукавов, дальше там космос, дальше планеты, животные, люди, у людей одежда, в одежде карманы, в карманах записки с генерируемыми надписями, или ещё какая ерунда, а всё это состоит из веществ, вещества из молекул, потом там уходит куда-то в микро-мир, а потом типа там ещё другая вселенная. Забыл как называется, в Гугле так и не нашёл.

Замах большой слишком, так игру не сделать. Да и будет ли это игра вовсе? Скорее похоже на небольшую научную работу — вижу много вычислений в описанном концепте, не вижу геймплея (это не плохо, просто не вижу).

Кроме того, Марковские цепи, да и даже обычные нейронные сети, имеют весьма ограниченное применение, по причинам в том числе производительности. Было бы конечно интересно увидеть это в действии, но прогнозы… весьма умеренные.

denisbarrett
Могу сказать даже больше — это и будет скорее некоторая научная работа, игра, в которой замкнутая динамическая популяционная система. Скорее всего, она самоуничтожится достаточно быстро, если будет возможность убивать у мирных людей убивать друг друга за еду и деньги)
Xitilon
если будет возможность убивать у мирных людей убивать друг друга за еду и деньги)
Что-то тут уже слишком много убивания! Точно самоуничтожится!
razzle_dazzle
Dwarf Fortress подходит?
shevtsov200
Если не Dwarf Fortress, то, может, Ultima Ratio Regum подойдёт.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.