- PVSM.RU - https://www.pvsm.ru -

Создаём свою Minecraft: генерация 3D-уровней из кубов

Создаём свою Minecraft: генерация 3D-уровней из кубов - 1

Частично из-за популярности Minecraft, в последнее время наблюдается рост интереса к идее игры, действие которой происходит в состоящем из кубов мире, построенном из 3D-рельефа и заполненного такими элементами, как пещеры, обрывы и так далее. Такой мир — идеальное применение для шума, сгенерированного в стиле моей библиотеки ANL. Данная статья возникла из обсуждений моих предыдущих попыток [1] реализации этой техники. С тех пор в структуре библиотеки появились незначительные изменения.

В предыдущих постах я рассказывал об использовании функций 3D-шума для реализации рельефа в стиле Minecraft. После этого библиотека немного эволюционировала, поэтому я решил вернуться к этой теме. Так как мне пришлось отвечать на множество вопросов по этой системе, я попытаюсь более подробно рассказать о задействованных концепциях. Чтобы базовые концепции были понятнее, я начну с идеи генерации 2D-рельефа, используемого в таких играх, как Terraria и King Arthur's Gold, а затем расширю систему до 3D-примеров наподобие Minecraft. Это позволит мне эффективнее демонстрировать концепции на примере изображений.

Эта система разрабатывалась с учётом следующей абстрактной цели: мы должны иметь возможность передать системе координату определённой точки или ячейки, и определить, какой тип блока должен находиться в этой локации. Мы хотим, чтобы система представляла собой «чёрный ящик»: передаём ей точку, возвращаем тип блока. Разумеется, это относится только к изначальной генерации мира. Блоки в подобных играх могут изменяться действиями игрока, и будет неудобно пытаться описать такие изменения при помощи такой же системы. Подобные изменения должны отслеживаться каким-то иным образом. Эта система генерирует изначальный мир, первозданный и нетронутый руками игрока и других персонажей.

Возможно, эта техника не подойдёт для моделирования таких систем, как трава или другие биологические сущности, учитывая то, что такие системы сами по себе являются сложными сущностями, которые не так легко моделировать неявным образом. То же самое относится к таким системам, как падающий снег, образование льда и т.д… Описанная в статье техника представляет собой неявный метод, т.е. такой, который может быть оценен в точке, и значение которого в заданной точке не зависит от окружающих значений. Биологические и другие типы систем для выполнения точной симуляции обычно должны учитывать окружающие значения. Например: сколько солнечного света падает на блок? Есть ли поблизости вода? На эти и другие вопросы нужно ответить для симуляции роста и распространения биологических систем, а также, в меньшей степени, других типов связанных с климатом систем. Также эта техника не подходит для моделирования воды. В этой системе отсутствует понятие потока, знание о механике жидкости или гравитации. Вода — это сложная тема, требующая множества сложных вычислений.

Итак, мы просто моделируем землю и камни. Нам нужна функция, которая сообщит, чем должна быть заданная локация: землёй, песком, воздухом, золотом, железом, углём и т.д… Но мы начнём с самого простого. Нам нужна функция, которая скажет, является ли блок сплошным или полым (заполненным воздухом). Эта функция должна симулировать окружающую нас землю. То есть небо находится наверху, земля — снизу. Итак, давайте возьмёмся за библейскую задачу, и отделим небо от земли. Для этого изучим функцию Gradient [2]. Функции Gradient передаётся отрезок прямой в N-мерном пространстве (т.е. в любом пространстве координат, будь то 2D, 3D, или выше), и она вычисляет поле градиента вдоль этого отрезка. Входящие координаты проецируются на этот отрезок и их значение градиента вычисляется в зависимости от того, где они лежат относительно конечных точек отрезка. Проецируемым точкам назначаются значения в интервале (-1,1). И это станет для нас хорошим началом. Мы можем задать функцию Gradient вдоль оси Y. В верхней части интервала мы сопоставим поле градиента с -1 (воздух), а в нижней — с 1 (земля).

terraintree=
{
	{name="ground_gradient", type="gradient", x1=0, x2=0, y1=0, y2=1}
}

(Вкратце объясню запись. Код примеров записан в виде таблицы объявлений Lua. Подробнее о формате можно прочитать в разделе про интеграции с Lua [3]. По сути, формат предназначен для парсинга специальным классом, считывающим объявления и превращающим их в деревья экземпляров модулей шума. Я предпочитаю этот формат более многословному пошаговому формату C++, потому что компактнее и чище. По-моему, исходный код получается более читаемым и сжатым, чем код на C++. По большей части объявления легко читаемы и понятны. Модули имеют названия, источники заданы именем или значением. Код на Lua, используемый для парсинга объявления таблицы, включён в исходники на случай, если вы захотите использовать эти объявления напрямую.)

В случае 2D функция Gradient получает отрезок прямой в виде (x1,x2, y1,y2), а в случае 3D формат расширен до (x1,x2, y1,y2, z1,z2). Точка, образованная (x1,y1), обозначает начало отрезка прямой, сопоставленное с 0. Точка, образованная (x2,y2) — это конец отрезка, сопоставленный с 1. То есть здесь мы сопоставляем отрезок прямой (0,1)->(0,0) с градиентом. Следовательно, градиент будет находиться между областями функции Y=1 и Y=0. То есть эта полоса образует размеры мира по Y. Любая часть мира будет находиться в этой полосе. Мы можем привязать любой регион по X (практически до бесконечности, но здесь нас ограничивает точность double), но всё интересное, т.е. поверхность земли, будет находиться в пределах этой полосы. Такое поведение можно изменить, но и в его пределах мы имеем большую степень гибкости. Просто не забывайте, что любые значения, которые находятся над или под этой полосой, скорее всего будут не интересными, потому что значения выше вероятнее всего будут воздухом, а значения ниже — землёй. (Как вы вскоре увидите, это заявление вполне может оказаться ошибочным.) Для большинства изображений в этой серии я буду сопоставлять квадратный регион, заданный квадратом (0,1)->(1,0) в 2D пространстве. Следовательно, в начале наш мир выглядит так:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 2

Пока ничего интересного; к тому же, это изображение не отвечает на вопрос «заданная точка сплошная или полая?». Чтобы ответить на этот вопрос, нам нужно применить Step Function [4] (кусочно-заданную функцию). Вместо плавного градиента нам нужно чёткое разделение, при котором все локации с одной стороны полые, а все локации с другой стороны — сплошные. В ANL это можно реализовать при помощи функции Select [5]. Функция Select получает две входящие функции или значения (в этом случае они будут равны «сплошному» (Solid) и «полому» (Open)), и выбирает из них на основании значения контрольной функции (в данном случае Gradient). Модуль Select имеет два дополнительных параметра, threshold и falloff, которые влияют на этот процесс. На данном этапе falloff нежелателен, поэтому мы сделаем его равным 0. Параметр threshold решает, где будет проходить разделительная линия между Solid и Open. Всё, что в функции Gradient будет больше этого значения, превратится в Solid, а всё, что меньше порога — в Open. Так как Gradient сопоставляет интервал со значениями от 0 и 1, логично будет расположить порог в 0.5. Так мы разделим пространство ровно пополам. Значение 1 будет сплошной локацией, а значение 0 — полой. То есть мы зададим функцию плоскости земли следующим образом:

terraintree=
{
	{name="ground_gradient",       type="gradient",       x1=0, x2=0, y1=0, y2=1},
	{name="ground_select",         type="select",         low=0, high=1, threshold=0.5, control="ground_gradient"}
}

Сопоставив ту же область функции, что и раньше, мы получим нечто подобное:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 3

Такая картина чётко отвечает на вопрос, является ли заданная точка сплошной или полой. Мы можем вызвать функцию с любой возможной координатой 2D-пространства, и её результат будет равен или 1, или 0, в зависимости от того, где находится точка относительно поверхности земли. Тем не менее, такая функция не особо интересна, это всего лишь плоская линия, протянувшаяся в бесконечность. Чтобы оживить картину, мы используем технику под названием «турбулентность» («turbulence»).

«Турбулентность» — это сложное обозначение концепции добавления значений к входящим координатам функции. Представьте, что мы вызываем показанную выше функцию земли с координатой (0,1). Она лежит над плоскостью земли, потому что при Y=1 градиент имеет значене 0, что меньше threshold = 0.5. То есть эта точка будет вычислена как Open. Но что если перед вызовом функции земли мы каким-то образом преобразуем эту точку? Допустим, вычтем из координаты Y случайное значение, например, 3. Мы вычитаем 3 и получаем координату (0,-2). Если теперь мы вызовем функцию земли для этой точки, то точка будет считаться сплошной, потому что Y=-2 лежит ниже сегмента Gradient, соответствующего 1. Внезапно полая точка (0,1) превращается в сплошную. У нас получится висящий в воздухе блок сплошного камня. Так можно сделать с любой точкой в функции, прибавляя или вычитая случайное число из координаты Y входящей точки до вызова функции ground_select. Вот изображение функции ground_select, показывающее это. Перед вызовом функции ground_select к координате Y каждой точки прибавляется значение в интервале (-0.25, 0.25).

Создаём свою Minecraft: генерация 3D-уровней из кубов - 4

Это уже интереснее, чем плоская линия, но не очень похоже на землю, потому что каждая точка перемещается на совершенно случайное значение, что создаёт хаотичный паттерн. Однако если мы используем непрерывную случайную функцию, например, Fractal [6] из библиотеки ANL, то вместо беспорядочного паттерна получим нечто более управляемое. Поэтому давайте подключим к плоскости земли фрактал и посмотрим, что получится.

terraintree=
{
	{name="ground_gradient",          type="gradient",           x1=0, x2=0, y1=0, y2=1},
	{name="ground_shape_fractal",     type="fractal",            fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=2},
	{name="ground_scale",             type="scaleoffset",        scale=0.5, offset=0, source="ground_shape_fractal"},
	{name="ground_perturb",           type="translatedomain",    source="ground_gradient", ty="ground_scale"},
	
	{name="ground_select",            type="select",             low=0, high=1, threshold=0.5, control="ground_perturb"}
}

Здесь стоит заметить пару аспектов. Во-первых, мы задаём модуль Fractal, и соединяем его цепочкой с модулем ScaleOffset [7]. Модуль ScaleOffset масштабирует выходные значения фрактала до более удобного уровня. Часть рельефа может быть горной и требовать большего масштаба, а другая часть — более плоской и с меньшим масштабом. О разных типах рельефа мы поговорим позже, а пока используем их для демонстрации. Выходные значения функции теперь дадут такую картину:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 5

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

Создаём свою Minecraft: генерация 3D-уровней из кубов - 6

На показанном выше изображении все чёрные точки имеют значение -0.25, а все белые — значение 0.25. То есть там, где фрактал чёрный, соответствующая точка функции земли будет смещена «вниз» на 0.25. (0.25 обозначает 1/4 экрана.) Так как одна точка может быть смещена ненамного, а другая точка над ней в пространстве может быть смещена больше, то возникает вероятность появления выступов скал и летающих островов. Выступы в природе вполне естественны, в отличие от летающих островов. (Если только мы не в фильме «Аватар».) Если в вашей игре нужен подобный фантастический ландшафт, то замечательно, но если вам нужна более реалистичная модель, то нам нужно немного настроить функцию фрактала. К счастью, это способна сделать функция ScaleDomain [8].

Мы хотим заставить функцию вести себя подобно функции карты высот. Представьте 2D-карту высот, где каждая точка карты обозначает высоту точки в решётке точек сетки, которые подняты вверх или опущены вниз. Белые значения карты обозначают высокие холмы, чёрные — низкие долины. Нам нужно похожее поведение, но чтобы добиться его, нужно по сути избавиться от одного из измерений. В случае карты высот мы создаём 3D-рельеф из 2D-карты высот. Аналогично, в случае 2D-рельефа нам нужна 1D-карта высот. Сделав так, чтобы все точки фрактала с одинаковой координатой Y имели одинаковое значение, мы можем сместить все точки с одинаковой координатой X на одинаковую величину, благодаря чему летающие острова исчезнут. Для этого можно использовать ScaleDomain, обнулив коэффициент scaley. То есть перед вызовом функции ground_shape_fractal мы вызываем ground_scale_y, чтобы присвоить координате y значение 0. Это гарантирует, что значение Y не будет влиять на выходные данные фрактала, по сути превратив его в функцию 1D-шума. Для этого мы внесём следующие изменения:

terraintree=
{
	{name="ground_gradient",          type="gradient",           x1=0, x2=0, y1=0, y2=1},
	{name="ground_shape_fractal",     type="fractal",            fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=2},
	{name="ground_scale",             type="scaleoffset",        scale=0.5, offset=0, source="ground_shape_fractal"},
	{name="ground_scale_y",           type="scaledomain",        source="ground_scale", scaley=0},
	{name="ground_perturb",           type="translatedomain",    source="ground_gradient", ty="ground_scale_y"},
	
	{name="ground_select",            type="select",             low=0, high=1, threshold=0.5, control="ground_perturb"}
}

Мы соединим функцию ScaleDomain в цепочку с ground_scale, а затем изменим исходные данные ground_perturb, чтобы они были функцией ScaleDomain. Это изменит фрактал, смещающий землю и превратит его в нечто подобное:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 7

Теперь если мы взглянем на выходные данные, то получим результат:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 8

Намного лучше. Летающие острова полностью исчезли, а рельеф больше напоминает горы и холмы. К сожалению, при этом мы потеряли выступы и обрывы. Теперь вся земля непрерывная и покатая. При желании можно исправить это несколькими способами.

Во-первых, можно использовать ещё одну функцию TranslateDomain [9], соединённую с ещё одной функцией Fractal [6]. Если мы применим к направлению по X небольшую величину фрактальной турбулентности, то сможем немного исказить края и поверхности гор, и этого возможно будет достаточно для образования обрывов и выступов. Давайте посмотрим на это в действии.

terraintree=
{
	{name="ground_gradient",          type="gradient",           x1=0, x2=0, y1=0, y2=1},
	{name="ground_shape_fractal",     type="fractal",            fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=2},
	{name="ground_scale",             type="scaleoffset",        scale=0.5, offset=0, source="ground_shape_fractal"},
	{name="ground_scale_y",           type="scaledomain",        source="ground_scale", scaley=0},
	{name="ground_perturb",           type="translatedomain",    source="ground_gradient", ty="ground_scale_y"},
	{name="ground_overhang_fractal",  type="fractal",            fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=2},
	{name="ground_overhang_scale",    type="scaleoffset",        source="ground_overhang_fractal", scale=0.2, offset=0},
	{name="ground_overhang_perturb",  type="translatedomain",    source="ground_perturb", tx="ground_overhang_scale"},
	
	{name="ground_select",            type="select",             low=0, high=1, threshold=0.5, control="ground_overhang_perturb"}
}

А вот результат:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 9

Второй способ: можно просто присвоить параметру scaley функции ground_scale_y значение больше 0. Если оставить небольшой масштаб по Y, то мы получим долю вариативности, однако чем больше будет масштаб, тем сильнее рельеф будет напоминать прежнюю версию без масштабирования.

Создаём свою Minecraft: генерация 3D-уровней из кубов - 10

Результаты выглядят намного интереснее, чем обычные покатые горы. Однако как бы ни интересны они были, игроку всё равно наскучит исследовать рельеф с одинаковым паттерном, растянувшийся на многие километры. Кроме того, такой рельеф будет очень нереалистичным. В реальном мире есть большая вариативность, повышающая интересность рельефа. Давайте посмотрим, что можно сделать, чтобы мир стало более разнообразным.

Взглянув на предыдущий пример кода, можно увидеть в нём определённый паттерн. У нас есть функция градиента, которая управляется функциями, придающими земле форму, после чего применяется кусочно-заданная функция и земля обретает заполненность. То есть усложнять рельеф логичнее будет на этапе придания земле формы. Вместо одного фрактала, смещающего по Y и другого, смещающего по X, мы можем добиться нужной степени сложности (с учётом производительности: каждый фрактал требует дополнительных вычислительных затрат, поэтому надо стараться быть консервативными.) Мы можем задать формы земли, представляющие собой горы, предгорья, плоские низины, пустоши, и т.д… и использовать выходные данные различных функций Select [5], объединённых в цепочки с низкочастотными фракталами, чтобы очертить области каждого типа. Итак, давайте посмотрим, как можно реализовать разные типы рельефа.

Чтобы проиллюстрировать принцип, мы выделим три типа рельефа: плоскогорья (плавные покатые холмы), горы и низины (по больше части плоские). Для переключения между ними мы используем систему на основе select и соединим их в сложное полотно. Итак, начинаем…

Предгорья:

С ними всё просто. Мы можем взять использованную выше схему, немного снизить амплитуду холмов, возможно, даже сделать их более субтрактивными, чем аддитивными. чтобы опустить средние высоты. Также мы можем снизить количество октав, чтобы сгладить их.

{name="lowland_shape_fractal",         type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=1},
{name="lowland_autocorrect",           type="autocorrect",      source="lowland_shape_fractal", low=0, high=1},
{name="lowland_scale",                 type="scaleoffset",      source="lowland_autocorrect", scale=0.2, offset=-0.25},
{name="lowland_y_scale",               type="scaledomain",      source="lowland_scale", scaley=0},
{name="lowland_terrain",               type="translatedomain",  source="ground_gradient", ty="lowland_y_scale"},

Плоскогорья:

С ними тоже всё просто. (На самом деле, ни один из этих типов рельефа не представляет трудностей.) Однако мы используем другой базис, чтобы сделать холмы похожими на дюны.

{name="highland_shape_fractal",        type="fractal",          fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=2},
{name="highland_autocorrect",          type="autocorrect",      source="highland_shape_fractal", low=0, high=1},
{name="highland_scale",                type="scaleoffset",      source="highland_autocorrect", scale=0.45, offset=0},
{name="highland_y_scale",              type="scaledomain",      source="highland_scale", scaley=0},
{name="highland_terrain",              type="translatedomain",  source="ground_gradient", ty="highland_y_scale"},

Горы:

{name="mountain_shape_fractal",        type="fractal",          fractaltype=anl.BILLOW, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=4, frequency=1},
{name="mountain_autocorrect",          type="autocorrect",      source="mountain_shape_fractal", low=0, high=1},
{name="mountain_scale",                type="scaleoffset",      source="mountain_autocorrect", scale=0.75, offset=0.25},
{name="mountain_y_scale",              type="scaledomain",      source="mountain_scale", scaley=0.1},
{name="mountain_terrain",              type="translatedomain",  source="ground_gradient", ty="mountain_y_scale"},

Разумеется, можно подойти к этому процессу ещё более творчески, но в целом паттерн будет таким. Мы выделяем характеристики типа рельефа и подбираем под них функции шума. Для всего этого действуют одинаковые принципы; основные различия заключаются масштабе. Теперь чтобы соединить их вместе, мы подготовим дополнительные фракталы, которые будут управлять функцией Select [5]. Затем мы объединим в цепочку модули Select для генерации всего рельефа.

{name="terrain_type_fractal",          type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=3, frequency=0.5},
{name="terrain_autocorrect",           type="autocorrect",      source="terrain_type_fractal", low=0, high=1},
{name="terrain_type_cache",            type="cache",            source="terrain_autocorrect"},
{name="highland_mountain_select",      type="select",           low="highland_terrain", high="mountain_terrain", control="terrain_type_cache", threshold=0.55, falloff=0.15},
{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},

Итак, здесь мы задаём три основных типа рельефа: lowlands, highlands и mountains. Используем один фрактал для выбора одного из них, чтобы присутствовали естественные переходы (lowlands->highlands->mountains). Затем используем ещё один фрактал для случайной вставки в карту пустошей (badlands). Вот как выглядит готовая цепочка модулей:

terraintree=
{
	{name="lowland_shape_fractal",         type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=1},
	{name="lowland_autocorrect",           type="autocorrect",      source="lowland_shape_fractal", low=0, high=1},
	{name="lowland_scale",                 type="scaleoffset",      source="lowland_autocorrect", scale=0.2, offset=-0.25},
	{name="lowland_y_scale",               type="scaledomain",      source="lowland_scale", scaley=0},
	{name="lowland_terrain",               type="translatedomain",  source="ground_gradient", ty="lowland_y_scale"},
	{name="ground_gradient",               type="gradient",           x1=0, x2=0, y1=0, y2=1},
	{name="highland_shape_fractal",        type="fractal",          fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=2},
	{name="highland_autocorrect",          type="autocorrect",      source="highland_shape_fractal", low=0, high=1},
	{name="highland_scale",                type="scaleoffset",      source="highland_autocorrect", scale=0.45, offset=0},
	{name="highland_y_scale",              type="scaledomain",      source="highland_scale", scaley=0},
	{name="highland_terrain",              type="translatedomain",  source="ground_gradient", ty="highland_y_scale"},

	{name="mountain_shape_fractal",        type="fractal",          fractaltype=anl.BILLOW, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=4, frequency=1},
	{name="mountain_autocorrect",          type="autocorrect",      source="mountain_shape_fractal", low=0, high=1},
	{name="mountain_scale",                type="scaleoffset",      source="mountain_autocorrect", scale=0.75, offset=0.25},
	{name="mountain_y_scale",              type="scaledomain",      source="mountain_scale", scaley=0.1},
	{name="mountain_terrain",              type="translatedomain",  source="ground_gradient", ty="mountain_y_scale"},

	{name="terrain_type_fractal",          type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=3, frequency=0.5},
	{name="terrain_autocorrect",           type="autocorrect",      source="terrain_type_fractal", low=0, high=1},
	{name="terrain_type_cache",            type="cache",            source="terrain_autocorrect"},
	{name="highland_mountain_select",      type="select",           low="highland_terrain", high="mountain_terrain", control="terrain_type_cache", threshold=0.55, falloff=0.15},
	{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},
	{name="ground_select",                 type="select",           low=0, high=1, threshold=0.5, control="highland_lowland_select"}
}

Вот несколько примеров получаемых рельефов:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 11

Создаём свою Minecraft: генерация 3D-уровней из кубов - 12

Создаём свою Minecraft: генерация 3D-уровней из кубов - 13

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

Для пещер я использую мультипликативную систему, применяемую к ground_select. То есть я создаю функцию, выводящую 1 или 0, и умножаю их на выходные данные ground_select. Благодаря этому полой становится любая точка функции, для которой значение функции пещер равно 0. То есть там, где я захочу получить пещеру, функция пещер должна возвратить 0, а там, где пещеры быть не должно, функция должна быть равна 1. Что касается формы пещер, я хочу основать систему пещер на основе 1-октавного Ridged Multifractal [6].

{name="cave_shape",               type="fractal",                fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=2},

В результате получится нечто такое:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 14

Если применить функцию Select [5] как кусочно-заданную функцию, как мы делали с градиентом земли, реализовав её так, чтобы нижняя часть порога select была равна 1 (нет пещеры), а верхняя часть равна 0 (есть пещера), то результат будет примерно выглядеть так:

{name="cave_shape",               type="fractal",                fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=2},
{name="cave_select",              type="select",                 low=1, high=0, control="cave_shape", threshold=0.8, falloff=0},

Результат:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 15

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

{name="cave_shape",               type="fractal",                fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=2},
{name="cave_select",              type="select",                 low=1, high=0, control="cave_shape", threshold=0.8, falloff=0},
{name="cave_perturb_fractal",     type="fractal",                fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=3},
{name="cave_perturb_scale",       type="scaleoffset",            source="cave_perturb_fractal", scale=0.25, offset=0},
{name="cave_perturb",             type="translatedomain",        source="cave_select", tx="cave_perturb_scale"},

Результат:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 16

Это слегка зашумливает пещеры и делает их не такими плавными. Давайте теперь посмотрим, что произойдёт, если применить пещеры к рельефу:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 17

Поэкспериментировав со значением threshold в cave_select, мы можем делать пещеры тоньше или толще. Но главное, что нам нужно попробовать — сделать так, чтобы пещеры не отъедали такие огромные фрагменты поверхностного рельефа. Для этого можно вернутся к функции highland_lowland_select, которая, как мы помним, является последней функцией рельефа, искажающей градиент земли. В этой функции полезно то, что она всё ещё является градиентом, увеличивающим значение при углублении функции в землю. Мы можем использовать градиент для ослабления функции пещер, чтобы пещеры увеличивались при углублении в землю. К счастью для нас, это ослабление можно реализовать просто умножением выходных данных функции highland_lowland_select на выходные данные cave_shape, а затем передать результат остальной цепочке функций. Далее мы внесём здесь важное изменение — добавим функцию Cache [10]. Функция кэширования сохраняет результат функции для заданной входящей координаты, и если функция вызывается повторно с той же координатой, она вернёт кэшированную копию, а не будет вычислять результат повторно. Это полезно в подобных ситуациях, когда одна сложная функция (highland_lowland_select) в цепочке функций вызывается несколько раз. Без кэша вся цепочка сложной функции при каждом вызове вычисляется заново. Чтобы добавить кэш, нам сначала нужно внести следующие изменения:

{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},
{name="highland_lowland_select_cache", type="cache",            source="highland_lowland_select"},
{name="ground_select",                 type="select",           low=0, high=1, threshold=0.5, control="highland_lowland_select_cache"},

Так мы добавили Cache, а затем перенаправили входные данные ground_select, чтобы они брались из кэша, а не напрямую из функции. Затем мы можем изменить код пещер, чтобы добавить ослабление:

{name="cave_shape",                    type="fractal",           fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=4},
{name="cave_attenuate_bias",           type="bias",              source="highland_lowland_select_cache", bias=0.45},
{name="cave_shape_attenuate",          type="combiner",          operation=anl.MULT, source_0="cave_shape", source_1="cave_attenuate_bias"},
{name="cave_perturb_fractal",          type="fractal",           fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=3},
{name="cave_perturb_scale",            type="scaleoffset",       source="cave_perturb_fractal", scale=0.5, offset=0},
{name="cave_perturb",                  type="translatedomain",   source="cave_shape_attenuate", tx="cave_perturb_scale"},
{name="cave_select",                   type="select",            low=1, high=0, control="cave_perturb", threshold=0.48, falloff=0},

Первым делом мы добавили функцию Bias [11]. Это сделано ради удобства, потому что позволяет нам настраивать интервал функции ослабления градиента. Затем добавлена функция cave_shape_attenuate, которая является Combiner [12] типа anl::MULT. Она умножает градиент на cave_shape. Затем результат этой операции передаётся функции cave_perturb. Результат выглядит примерно так:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 18

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

terraintree=
{
	{name="ground_gradient",               type="gradient",         x1=0, x2=0, y1=0, y2=1},
	
	{name="lowland_shape_fractal",         type="fractal",          fractaltype=anl.BILLOW, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=0.25},
	{name="lowland_autocorrect",           type="autocorrect",      source="lowland_shape_fractal", low=0, high=1},
	{name="lowland_scale",                 type="scaleoffset",      source="lowland_autocorrect", scale=0.125, offset=-0.45},
	{name="lowland_y_scale",               type="scaledomain",      source="lowland_scale", scaley=0},
	{name="lowland_terrain",               type="translatedomain",  source="ground_gradient", ty="lowland_y_scale"},
	
	{name="highland_shape_fractal",        type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=4, frequency=2},
	{name="highland_autocorrect",          type="autocorrect",      source="highland_shape_fractal", low=-1, high=1},
	{name="highland_scale",                type="scaleoffset",      source="highland_autocorrect", scale=0.25, offset=0},
	{name="highland_y_scale",              type="scaledomain",      source="highland_scale", scaley=0},
	{name="highland_terrain",              type="translatedomain",  source="ground_gradient", ty="highland_y_scale"},

	{name="mountain_shape_fractal",        type="fractal",          fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=8, frequency=1},
	{name="mountain_autocorrect",          type="autocorrect",      source="mountain_shape_fractal", low=-1, high=1},
	{name="mountain_scale",                type="scaleoffset",      source="mountain_autocorrect", scale=0.45, offset=0.15},
	{name="mountain_y_scale",              type="scaledomain",      source="mountain_scale", scaley=0.25},
	{name="mountain_terrain",              type="translatedomain",  source="ground_gradient", ty="mountain_y_scale"},

	{name="terrain_type_fractal",          type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=3, frequency=0.125},
	{name="terrain_autocorrect",           type="autocorrect",      source="terrain_type_fractal", low=0, high=1},
	{name="terrain_type_y_scale",          type="scaledomain",      source="terrain_autocorrect", scaley=0},
	{name="terrain_type_cache",            type="cache",            source="terrain_type_y_scale"},
	{name="highland_mountain_select",      type="select",           low="highland_terrain", high="mountain_terrain", control="terrain_type_cache", threshold=0.55, falloff=0.2},
	{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},
	{name="highland_lowland_select_cache", type="cache",            source="highland_lowland_select"},
	{name="ground_select",                 type="select",           low=0, high=1, threshold=0.5, control="highland_lowland_select_cache"},
	
	{name="cave_shape",                    type="fractal",           fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=4},
	{name="cave_attenuate_bias",           type="bias",              source="highland_lowland_select_cache", bias=0.45},
	{name="cave_shape_attenuate",          type="combiner",          operation=anl.MULT, source_0="cave_shape", source_1="cave_attenuate_bias"},
	{name="cave_perturb_fractal",          type="fractal",           fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=3},
	{name="cave_perturb_scale",            type="scaleoffset",       source="cave_perturb_fractal", scale=0.5, offset=0},
	{name="cave_perturb",                  type="translatedomain",   source="cave_shape_attenuate", tx="cave_perturb_scale"},
	{name="cave_select",                   type="select",            low=1, high=0, control="cave_perturb", threshold=0.48, falloff=0},
	
	{name="ground_cave_multiply",          type="combiner",          operation=anl.MULT, source_0="cave_select", source_1="ground_select"}
}

Вот примеры рандомизированных карт, полученных из этой функции:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 19

Создаём свою Minecraft: генерация 3D-уровней из кубов - 20

Создаём свою Minecraft: генерация 3D-уровней из кубов - 21

Теперь всё выглядит довольно неплохо. Все пещеры представляют собой довольно большие каверны глубоко под землёй, но ближе к поверхности они обычно превращаются в маленькие туннели. Это помогает создать атмосферу загадочности. Исследуя поверхность, вы обнаруживаете небольшой вход в пещеру. Куда она ведёт? Насколько глубоко простирается? Мы не можем этого знать, но в процессе изучения она начинает расширяться, превращаясь в обширную систему каверн, заполненных тьмой и опасностями. И лутом, конечно. Там всегда много лута.

Можно изменять эту систему множеством разных способов, получая различные результаты. Мы можем изменять параметры threshold для cave_select и параметры у cave_attenuate_bias, или заменять cave_attenuate_bias на другие функции, чтобы сопоставлять интервал градиента с иными значениями, лучше подходящими вашим потребностям. Также можно добавить ещё один фрактал, искажающий систему пещер по оси Y, чтобы устранить возможность появления неестественно плавных туннелей по оси X (вызванных тем, что форма пещер искажается только по X). Ещё можно добавить новый фрактал как дополнительный источник ослабления, задать третий источник для cave_shape_attenuate, масштабирующий ослабление на основе регионов, чтобы пещеры в некоторых областях располагались плотнее (допустим, в горах), а в других реже или вовсе отсутствовали. Этот региональный select можно создать из функции terrain_type_fractal, чтобы знать, где расположены области гор. Всё сводится просто к тому, чтобы продумать, чего вы хотите, разобраться в том, какое влияние разные функции будут оказывать на выходные данные, и поэкспериментировать с параметрами, пока не получите нужный результат. Это не точная наука, и часто к нужному эффекту можно прийти разными путями.

Недостатки

У этого метода генерации рельефа есть недостатки. Процесс генерации шума может быть довольно медленным. Важно по возможности уменьшать количество фракталов, количество октав тех фракталов, которые вы используете, и других медленных операций. Пытайтесь использовать фракталы многократно и кэшировать все функции, которые вызываются несколько раз. В этом примере я достаточно вольно пользовался фракталами, создав по одному для каждого из трёх типов рельефа. Воспользовавшись ScaleOffset [13] для изменения интервалов и взяв за основу для них всех один фрактал, я бы сэкономил много процессорного времени. В 2D всё не так плохо, но когда вы доберётесь до 3D и попробуете сопоставлять объёмы данных, время обработки сильно увеличится.

Переходим в 3D

Всё это здорово, если вы создаёте игру наподобие Terraria [14] или King Arthur's Gold [15], но что, если вам нужно нечто наподобие Minecraft [16] или Infiniminer [17]? Какие изменения нам нужно будет внести в цепочку функций? На самом деле, их не так много. Показанная выше функция почти без модификаций сработает и для 3D-рельефа. Вам достаточно будет сопоставить 3D-объём, используя 3D-вариации генератора, а также сопоставить ось Y с вертикальной осью объёма, а не 2D-областью. Однако всё-таки потребуется одно изменение, а именно, способ реализации пещер. Как вы видели, Ridged Multifractal отлично подходит для 2D-системы пещер, но в 3D он вырезает множество искривлённых оболочек, а не туннелей, и его влияние оказывается неверным. То есть в 3D необходимо задать два фрактала форм пещер, оба являются 1-октавным шумом Ridged Multifractal, но с разными seed. При помощи Select задаём им значения 1 или 0, и перемножаем их. Таким образом, в местах пересечения фракталов появится пещера, а всё остальное останется сплошным, и внешний вид туннелей станет более естественным, чем при использовании одного фрактала.

terraintree3d=
{
	{name="ground_gradient",               type="gradient",         x1=0, x2=0, y1=0, y2=1},
	
	{name="lowland_shape_fractal",         type="fractal",          fractaltype=anl.BILLOW, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=2, frequency=0.25},
	{name="lowland_autocorrect",           type="autocorrect",      source="lowland_shape_fractal", low=0, high=1},
	{name="lowland_scale",                 type="scaleoffset",      source="lowland_autocorrect", scale=0.125, offset=-0.45},
	{name="lowland_y_scale",               type="scaledomain",      source="lowland_scale", scaley=0},
	{name="lowland_terrain",               type="translatedomain",  source="ground_gradient", ty="lowland_y_scale"},
	
	{name="highland_shape_fractal",        type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=4, frequency=2},
	{name="highland_autocorrect",          type="autocorrect",      source="highland_shape_fractal", low=-1, high=1},
	{name="highland_scale",                type="scaleoffset",      source="highland_autocorrect", scale=0.25, offset=0},
	{name="highland_y_scale",              type="scaledomain",      source="highland_scale", scaley=0},
	{name="highland_terrain",              type="translatedomain",  source="ground_gradient", ty="highland_y_scale"},

	{name="mountain_shape_fractal",        type="fractal",          fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=8, frequency=1},
	{name="mountain_autocorrect",          type="autocorrect",      source="mountain_shape_fractal", low=-1, high=1},
	{name="mountain_scale",                type="scaleoffset",      source="mountain_autocorrect", scale=0.45, offset=0.15},
	{name="mountain_y_scale",              type="scaledomain",      source="mountain_scale", scaley=0.25},
	{name="mountain_terrain",              type="translatedomain",  source="ground_gradient", ty="mountain_y_scale"},

	{name="terrain_type_fractal",          type="fractal",          fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=3, frequency=0.125},
	{name="terrain_autocorrect",           type="autocorrect",      source="terrain_type_fractal", low=0, high=1},
	{name="terrain_type_y_scale",          type="scaledomain",      source="terrain_autocorrect", scaley=0},
	{name="terrain_type_cache",            type="cache",            source="terrain_type_y_scale"},
	{name="highland_mountain_select",      type="select",           low="highland_terrain", high="mountain_terrain", control="terrain_type_cache", threshold=0.55, falloff=0.2},
	{name="highland_lowland_select",       type="select",           low="lowland_terrain", high="highland_mountain_select", control="terrain_type_cache", threshold=0.25, falloff=0.15},
	{name="highland_lowland_select_cache", type="cache",            source="highland_lowland_select"},
	{name="ground_select",                 type="select",           low=0, high=1, threshold=0.5, control="highland_lowland_select_cache"},
	
	{name="cave_attenuate_bias",           type="bias",              source="highland_lowland_select_cache", bias=0.45},
	{name="cave_shape1",                   type="fractal",           fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=4},
	{name="cave_shape2",                   type="fractal",           fractaltype=anl.RIDGEDMULTI, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=1, frequency=4},
	{name="cave_shape_attenuate",         type="combiner",           operation=anl.MULT, source_0="cave_shape1", source_1="cave_attenuate_bias", source_2="cave_shape2"},             
	{name="cave_perturb_fractal",          type="fractal",           fractaltype=anl.FBM, basistype=anl.GRADIENT, interptype=anl.QUINTIC, octaves=6, frequency=3},
	{name="cave_perturb_scale",            type="scaleoffset",       source="cave_perturb_fractal", scale=0.5, offset=0},
	{name="cave_perturb",                  type="translatedomain",   source="cave_shape_attenuate", tx="cave_perturb_scale"},
	{name="cave_select",                   type="select",            low=1, high=0, control="cave_perturb", threshold=0.48, falloff=0},
	
	{name="ground_cave_multiply",          type="combiner",          operation=anl.MULT, source_0="cave_select", source_1="ground_select"}
}

Примеры результатов:

Создаём свою Minecraft: генерация 3D-уровней из кубов - 22

Создаём свою Minecraft: генерация 3D-уровней из кубов - 23

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

Автор: PatientZero

Источник [18]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/algoritmy/334354

Ссылки в тексте:

[1] попыток: http://www.gamedev.net/blog/33/entry-2227887-more-on-minecraft-type-world-gen

[2] Gradient: http://accidentalnoise.sourceforge.net/implicit.html#Gradient

[3] интеграции с Lua: http://accidentalnoise.sourceforge.net/lua.html

[4] Step Function: http://en.wikipedia.org/wiki/Step_function

[5] Select: http://accidentalnoise.sourceforge.net/implicit.html#Select

[6] Fractal: http://accidentalnoise.sourceforge.net/implicit.html#Fractal

[7] ScaleOffset: http://accidentalnoise.sourceforge.net/implicit.html#ScaleOffset

[8] ScaleDomain: http://accidentalnoise.sourceforge.net/implicit.html#ScaleDomain

[9] TranslateDomain: http://accidentalnoise.sourceforge.net/implicit.html#TranslateDomain

[10] Cache: http://accidentalnoise.sourceforge.net/implicit.html#Cache

[11] Bias: http://accidentalnoise.sourceforge.net/implicit.html#Bias

[12] Combiner: http://accidentalnoise.sourceforge.net/implicit.html#Combiner

[13] ScaleOffset: http://accidentalnoise.sourceforge.net/implicit.html#ScaleOfset

[14] Terraria: http://www.terraria.org/

[15] King Arthur's Gold: http://kag2d.com/

[16] Minecraft: http://www.minecraft.net/

[17] Infiniminer: http://thesiteformerlyknownas.zachtronicsindustries.com/?p=713

[18] Источник: https://habr.com/ru/post/472574/?utm_source=habrahabr&utm_medium=rss&utm_campaign=472574