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

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

Задачи генерации целого мира в игре никогда не давала мне покоя. Полностью созданный мир на основе псевдо-случайных чисел делает опыт каждого игрока уникальным. Вообразите себе не только случайную карту мира, но и случайные квесты, случайные подземелья, случайных 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. Умножаем на глобальную амплитуду температуры (разницу между максимальной и минимальной температурой)

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

Теперь нам надо расположить биомы... Но что такое биомы? Как их задать? Что нужно знать о них? Об этом мы поговорим в следующей статье.

Продолжение следует...