Привет, Хабр! Обратите внимание, Распродажа «Чёрная Пятница» от издательства «Питер» скоро закончится.
Поговорим о том, как в известных играх, например, Minecraft и Terraria, из ничего генерируются бесконечные и разнообразные миры. Пост снабжен подробными примерами кода.
Почти любому из нас доводилось хотя бы раз играть в такую игру, в которой автоматически генерируется ландшафт. Подобные игры по-настоящему сильно стимулируют пользователя продолжать игру, постоянно подбрасывая ему новые ситуации.
Если вы – разработчик и любите уделять внимание деталям, то, вероятно, задумывались, а как генерируются такие бесконечные миры. Несмотря на всю их сложную структуру, вся такая генерация сводится к тщательно настроенной случайной составляющей.
Что такое процедурная генерация миров?
Процедурная генерация – это метод создания данных при помощи алгоритма, а не вручную. В случае с компьютерными играми такой метод применяется для генерации миров и их деталей без обязательного вмешательства разработчика. Данная техника широко используется в таких играх как Minecraft, Terraria или No Man’s Sky, в основе которых лежат открытые миры. Пользователь может как ему угодно исследовать такие миры и взаимодействовать с ними.
Процедурная генерация миров принципиально превосходит генерацию, выполняемую вручную – поскольку на разработку требуется меньше времени и меньше расходов. Размеры загружаемых файлов обычно удается существенно уменьшить, поскольку при поставке в игре отсутствуют огромные заранее построенные карты. Более того, обычно внедряются без труда, как только доведена до конца разработка движка, отвечающего за генерацию миров.
Теперь перейдем к технической части посмотрим, как на самом деле устроен этот процесс. Я покажу вам, как сгенерировать двумерный мир.
Код для примеров я решил написать при помощи Processing — это графическая библиотека и IDE на основе языка Java. Я выбрал Processing из соображений простоты, но вы можете воспользоваться любой технологией, которая вам удобна. В конце статьи я оставлю ссылку на GitHub-репозиторий, где выложен весь исходный код.
Обратите внимание: в примерах я использую файловое расширение .java, чтобы код хорошо раскрашивался. На самом деле у всех этих файлов расширение .pde.
Что такое шум, и почему он так важен?
Всем нам известна концепция «шум» — обычно так называют беспорядочные раздражающие звуки. Теперь давайте познакомимся с численным шумом. Он состоит из множества точек, на значения которых влияют значения окружающих точек.
Факт взаимосвязанности этих значений друг с другом – ключевой аспект генерации миров, поскольку логично ожидать, что участки, расположенные рядом, будут выглядеть похоже, а не по-разному. Например, не предполагаешь, что посреди неба тебе может встретиться река.
Из всех типов шумов особенно часто используется шум Перлина, названный так в честь его создателя, Кена Перлина. Шум Перлина позволяет генерировать псевдослучайные органические паттерны для любого количества измерений.
Я не буду подробно разбирать математику, лежащую в основе этого алгоритма, поскольку во многих языках программирования предусмотрены встроенные функции для этой цели. В любом случае, если вы хотите подробнее познакомиться с этой темой, вот полное объяснение.
Карты шумов и как они используются
Карты шумов – это графические представления шума в заданном n-мерном регионе пространства, обычно в 2D- или 3D-играх. В случае процедурной генерации они представляют конкретную характеристику мира, например, высоту, температуру, влажность и т.д.
Каждая точка на карте определяет конкретное значение в финальном произведении. Рассмотрим, как можно сгенерировать карту шума – в данном случае для высот ландшафта – на языке Processing:
// масштаб определяет, насколько детализирована будет сгенерированная карта
float scale = 0.005f;
// Максимальная высота, которая может быть на ландшафте. В Minecraft она равна 255.
static final int MAX_HEIGHT = 255;
// xPos и yPos – это актуальные координаты мира
int xPos = 0;
int yPos = 0;
final int[][] generateHeight()
{
// создаем 2D-массив, в котором будет содержаться карта шумов для высот мира.
// "width" и "height" – это встроенные переменные, представляющие, соответственно, ширину и высоту окна
int heightMap[][] = new int[width][height];
for (int x = 0; x != width; x++)
{
for (int y = 0; y != height; y++)
{
// сгенерировать шум Перлина на основе координат x,y
// умножение координат на масштаб влияет на детализацию сгенерированной карты
// функция noise() возвращает число в диапазоне от 0 до 1
float value = noise((x + xPos) * scale, (y + yPos) * scale);
// выразить на карте сгенерированный шум между 0 и MAX_HEIGTH, затем округлить
int h = round(map(value, 0f, 1f, 0, MAX_HEIGHT));
// наконец, установить высоту актуальной точки на карте
heightMap[x][y] = h;
}
}
return heightMap;
}Код для генерации двумерной карты шумов по высоте.
Как вы, вероятно, уже догадались, также можно генерировать сразу много карт шумов для каждой характеристики, которой должен обладать наш мир. Предыдущее изображение шума было сгенерировано при помощи именно этой функции.
Итак, какие еще характеристики должны быть у мира? Я решил остановиться на температуре и влажности. Процесс генерации этих карт похож на тот, что мы уже рассмотрели выше.
Вся разница в том, что влажность в конкретной точке также зависит от температуры в этой точке, а на температуру влияет и высота ландшафта – все это совершенно логично. Например, в реальном мире температура на высоте 3000 м обычно ниже, чем на уровне моря.
// TEMPERATURE_SCALE определяет, насколько детализирована должна быть карта температур.
float TEMPERTURE_SCALE = 0.001f;
int DEFAULT_TEMPERATURE = 20;
// TEMPERATURE_INCREMENT определяет, насколько температура меняется в зависимости от высоты.
float TEMPERATURE_INCREMENT = 0.3f
// Функция принимает карту высот в качестве параметра, поскольку температура связана с ней.
final float[][] generateTemperatureMap(int[][] heightMap)
{
// Сначала создадим 2d-массив, в котором будем хранить карту температур
float temperatureMap[][] = new float[width][height];
for (int x = 0; x != width; x++)
{
for (int y = 0; y != height; y++)
{
// Получим шум Перлина в заданной точке с координатами x,y.
// Умножим координаты на масштаб, чтобы определить, насколько детализированной должна быть карта.
// Наконец, умножим на 100 и вычтем 50, чтобы подогнать температуру под конкретный диапазон.
// Второй шаг полностью специфичен для данной реализации и не является общим правилом.
float temperatureNoise = noise(x * TEMPERATURE_SCALE, y * TEMPERATURE_SCALE) * 100 - 50;
// Вычислить изменение температуры на основе того, какова высота точки
// Как видите, степень влияния высоты на температуру зависит от константы TEMPERATURE_INCREMENT.
float temperatureFromAltitude = DEFAULT_TEMPERATURE - abs(heightMap[x][y] - MAX_TEMPERATURE_HEIGHT) * TEMPERATURE_INCREMENTe;
// Вычислить финальную температуру и сохранить ее на карте.
temperatureMap[x][y] = temperatureNoise + temperatureFromAltitude;
}
}
return temperatureMap;
}
// HUMIDITY_SCALE определяет, насколько детализирована должна быть карта влажности.
float HUMIDITY_SCALE = 0.003f;
// HUMIDITY_TEMPERATURE определяет, насколько температура влияет на влажность.
float HUMIDITY_TEMPERATURE = 1.3f;
// Константы, зависящие от реализации.
float HUMIDITY_HIGH_TEMP = 23f;
float HUMIDITY_LOW_TEMP = 2f;
// Функция принимает карту температур в качестве параметра, поскольку влажность связана с ней.
final float[][] generateHumidityMap(float[][] temperatureMap)
{
// создадим 2d-массив, в котором будем хранить карту влажности.
float humidityMap[][] = new float[width][height];
for (int x = 0; x != width; x++)
{
for (int y = 0; y != height; y++)
{
// Как и в случае с картой температур, сгенерируем шум Перлина в заданной точке при заданном масштабе.
float humidityNoise = noise(x * HUMIDITY_SCALE, y * HUMIDITY_SCALE) * 100 - 50;
// Корректировки, зависящие от реализации и определяющие, как температура будет влиять на влажность в заданной точке.
float humidityFromTemperature = 0f;
if (temperatureMap[x][y] > HUMIDTY_HIGH_TEMP)
humidityFromTemperature = temperatureMap[x][y] * 2 - HUMIDITY_HIGH_TEMP;
else if (temperatureMap[x][y] < HUMIDITY_LOW_TEMP)
humidityFromTemperature = HUMIDITY_LOW_TEMP;
else
humidityFromTemperature = temperatureMap[x][y]
// Вычисляем окончательную влажность.
// Константа HUMIDITY_TEMPERATURE определяет, насколько температура влияет на влажность.
humidityMap[x][y] = humidityNoise + humidityFromTemperature * HUMIDITY_TEMPERATURE;
}
}
return humidityMap;
}Код для генерации двумерных карт шумов, описывающих температуру и влажность.
О биомах и о том, как они определяются
Для начала выясним, что же такое биом? Согласно National Geographic, биом – это обширная область, характеризующаяся определенной флорой, почвами, климатом и фауной. Как вытекает из этого определения, биом характеризуется конкретным набором характеристик, которые можно сгенерировать на основе карт шумов. Остается соотнести эти значения с разными биомами в зависимости от того, какие характеристики они должны иметь.
Чтобы прояснить этот процесс, рассмотрим конкретный пример: саванны. Это относительно низкая равнина. В саванне растет высокая трава, поэтому этот ландшафт не должен быть засушливым, а также не должен промерзать.
Настройка этих значений – обязанность программиста, и такая настройка полностью зависит от реализации. Процесс поиска наилучших значений связан с генерацией различных миров со слегка отличающимися друг от друга параметрами, после чего вы выбираете те результаты, которые вам наиболее понравятся.
В моем примере я предполагаю, что диапазон высот в саванне должен быть в диапазоне от 135 и 169 – это значения, к которым я пришел методом проб и ошибок. Кроме того, полагаю, что температура должна быть в диапазоне от 0 до 50, влажность – также в диапазоне от 0 до 50.
Примечание: эти значения выражены не в метрах, градусах или процентах. Это просто числа, означающие конкретные координаты на соответствующей карте.
Для удобства давайте создадим на Processing классы Range и Biome:
// Класс, представляющий диапазон чисел (напр. от 0 до 50)
class Range
{
public final float min;
public final float max;
public Range(float min, float max)
{
this.min = min;
this.max = max;
}
// Возвращает, входит ли заданное значение в диапазон
public boolean fits(float value)
{
return min <= value && value <= max;
}
};
// Класс, представляющий биом в мире
class Biome
{
public final String name;
public final Range heightRange;
public final Range tempRange;
public final Range humidityRange;
// col – это цвет, в котором представлен биом
public final color col;
public Biome(String name, Range heightRange, Range tempRange, Range humidityRange, color col)
{
this.name = name;
this.heightRange = heightRange;
this.tempRange = tempRange;
this.humidityRange = humidityRange;
this.col = col;
}
};Классы Range и Biome.
Теперь мы можем представить саванны как объект (и то же касается других биомов) и хранить их в массиве, который станет нашим списком биомов:
final Biome[] biomes = new Biome[]
{
// имя высота температура влажность цвет
new Biome("Abyss", new Range(0, 39), new Range(-10, 50), new Range(-10, Float.MAX_VALUE), #090140),
new Biome("Ocean", new Range(40, 129), new Range(-10, 50), new Range(-10, Float.MAX_VALUE), #2107D8),
new Biome("IceLands", new Range(0, 170), new Range(-Float.MAX_VALUE, 0), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), #75FCF2),
new Biome("Shore", new Range(130, 135), new Range(0, 50), new Range(-Float.MAX_VALUE, 50), #C7CE00),
new Biome("SnowyShore", new Range(130, 135), new Range(-Float.MAX_VALUE, 0), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), #EDFCA8),
new Biome("Plains", new Range(135, 169), new Range(0, 50), new Range(0, 50), #40D115),
new Biome("FireLands", new Range(135, 169), new Range(50, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, 30), #E57307),
new Biome("Forest", new Range(140, 169), new Range(0, 25), new Range(5, 30), #128B03),
new Biome("Tundra", new Range(140, 169), new Range(-10, 0), new Range(5, Float.MAX_VALUE), #745F4E),
new Biome("Desert", new Range(135, 169), new Range(30, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, 5), #CBB848),
new Biome("GrassyHills", new Range(160, 189), new Range(5, 25), new Range(5, 30), #2E7612),
new Biome("ForestyHills", new Range(160, 189), new Range(5, 30), new Range(0, 30), #1B5504),
new Biome("MuddyHills", new Range(170, 189), new Range(0, 40), new Range(0, 50), #984319),
new Biome("DryHills", new Range(140, 189), new Range(10, 40), new Range(-Float.MAX_VALUE, 0), #C6950A),
new Biome("SnowyHills", new Range(170, 189), new Range(-Float.MAX_VALUE, 0), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), #1FA27C),
new Biome("DesertDunes", new Range(170, 189), new Range(30, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, 0), #7E7109),
new Biome("Volcano", new Range(170, MAX_HEIGHT), new Range(30, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, 35), #AF1109),
new Biome("RockyMountains", new Range(180, MAX_HEIGHT), new Range(-Float.MAX_VALUE, 30), new Range(-Float.MAX_VALUE, 40), #43100D),
new Biome("IceMountains", new Range(180, MAX_HEIGHT), new Range(-Float.MAX_VALUE, 0), new Range(5, Float.MAX_VALUE), #5B6A63),
new Biome("Swamp", new Range(130, 170), new Range(0, 35), new Range(40, Float.MAX_VALUE), #052403),
new Biome("RainForest", new Range(140, 180), new Range(30, 40), new Range(40, Float.MAX_VALUE), #324B28),
new Biome("DryLands", new Range(0, 150), new Range(0, 40), new Range(-Float.MAX_VALUE, 0), #834C10),
new Biome("Savannah", new Range(135, 169), new Range(20, 50), new Range(-10, 10), #767618),
new Biome("GeyserLand", new Range(130, 170), new Range(40, Float.MAX_VALUE), new Range(40, Float.MAX_VALUE), #3A3B55),
// Если значения точки не соответствуют ни одному из ранее фигурировавших биомов, ей присваивается особый биом "None"
new Biome("None", new Range(0, MAX_HEIGHT), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), new Range(-Float.MAX_VALUE, Float.MAX_VALUE), #E513C3),
};Массив биомов с их свойствами.
Как только определен список биомов мира, приходит время создавать карту биомов.
Карта биомов, как и те карты, о которых мы говорили выше – это множество точек, каждой из которых присвоены конкретные значения. В данном случае, значение координат x,y – это биом, лучше всего соответствующий параметрам данной точки на картах шума.
В качестве пояснения рассмотрим другой пример. Допустим, в координатах x,y карты высоты, температуры и влажности имеют значения 140, 25 и 25 соответственно. Поскольку все эти значения вписываются в заданный для саванны диапазон высот 135–169 и диапазон 0–50, соответствующий температуре и влажности, биом с такими координатами должен относиться к саванне.
Теперь, чтобы не проверять вручную, какой набор значений какому биому соответствует, давайте напишем для этого следующую функцию:
// Сгенерировать 2d-карту объекта Biome
final Biome[][] generateBiomes(int[][] heightMap, float[][] temperatureMap, float[][] humidityMap)
{
// 2d-массив, содержащий карту биома
Biome[][] biomeMap = new Biome[width][height];
// Перебрать все точки на карте
for (int x = 0; x != width; ++)
{
for (int y = 0; y != height; y++)
{
// Перебрать биомы и посмотреть, какой из них соответствует значениям для
for (Biome biome : biomes)
{
if (biome.heightRange.fits(h))
{
if (biome.tempRange.fits(temp))
{
if (biome.humidityRange.fits(humidity))
{
biomeMap[x][y] = biome;
}
}
}
}
}
}
return biomeMap;
}Конечно же, это не самый эффективный способ определения биома, но я старался оставить код максимально простым.
Как только каждой из точек присвоен нужный биом, переходим к созданию графического представления. Именно для этого используется свойство color класса Biome.
Напишем на Processing функцию, которая отрисовывает на экране готовую карту:
// Функция, отрисовывающая карту биома на экране
final void drawMap()
{
// Перебираем экранные координаты x,y
for (int x = 0; x != width; x++)
{
for (int y = 0; y != height; y++)
{
// Получаем на основании карты цвет биома
color col = biomeMap[x][y].col;
// Устанавливаем цвет штриха
stroke(col);
// Ставим на экране точку заданного цвета в координатах x,y
point(x, y);
}
}
}Вот какой рисунок получается в результате:
Случайные начальные значения
Случайные начальные значения – это просто числа, используемые для инициализации генератора псевдослучайных значений. Первое псевдослучайное значение генерируется из начального, и все последующие значения в случайной последовательности зависят от него.
Начальные значения полезны в тех случаях, когда нужна предсказуемость результатов. Фактически, все сгенерированные последовательности псевдослучайных чисел, выведенные из одного и того же начального значения, гарантированно будут равны.
Таким образом, если вы подыщете по-настоящему красивый мир, который хотите сохранить и использовать для игры, то можете просто сохранить его случайное начальное значение. Более того, если бы вы хотели передать кому-то этот мир, то вам не потребовалась бы широченная полоса передачи данных; достаточно было бы послать начальное число.
В Processing можно конкретно указать случайное начальное значение для функции noise() при помощи встроенной функции noiseSeed(). Она принимает в качестве значения число (случайное начальное значение) и не возвращает ничего.
int mySeed = 54;
noiseSeed(mySeed);Все карты, сгенерированные из этого начального значения, будут выглядеть совершенно одинаково, при условии, что код генерации мира останется неизменным.
Дальнейшие советы по генерации миров
Чтобы реализовать в игре процедурную генерацию миров, попробуйте разделить мир на фрагменты, чтобы загружать только нужные ресурсы.
Для перемещения по миру нужно двигать координаты x,y в направлении движения. Функции шумов будут генерировать значения шумов (и, следовательно, карты) в соответствии с новой позицией.
Вот снимок проекта, на основе которого написана эта статья. Видно, как генерируется ландшафт, пока вы движетесь по миру.
Демо-версия процедурной генерации миров с изменением координат.
Если вам будет интересно, загляните в репозиторий на GitHub по этому проекту. Заранее предупреждаю, что код не самый качественный, поскольку здесь я хотел создать всего лишь прототип Minecraft-подобной игры, которую сейчас разрабатываю.
Надеюсь, статья вам понравилась, и вы узнали что-то новое о том, как в играх генерируются миры.