[Перевод] Как происходит генерация мира Minecraft

image


Задумывались ли вы когда-нибудь, сколько на нашей планете песчинок? По грубым оценкам, более 7 квинтиллионов! Это 7 с 18 нулями. И всё-таки это даже меньше половины количества уникальных миров в Minecraft. Как же Minecraft и другим похожим играм удаётся создавать такие сложные, красивые, однако полностью процедурные миры? В этой статье я расскажу, как игра генерирует свои миры, от самой высокой горы до самой глубокой пещеры.
Для многих из вас Minecraft может быть первой (а может быть, и единственной) игрой, в которой миры не творятся вручную дизайнером уровней, а создаются процедурно.

Однако первой игрой с процедурно сгенерированным миром является «Elite», первая версия которой вышла для компьютера BBC Micro в 1984 году. Это прапрадед относительно новой «Elite: Dangerous», выпущенной в 2014 году.

c7f04cc94c4545f45157673cdfe5ad09.gif


Автоматическая генерация новых миров может казаться привлекательным способом ленивого создания бесконечного контента для игры. Однако на самом деле всё наоборот! Чтобы научить машину тому, как выглядит хороший уровень… нужно быть очень хорошим программистом и дизайнером уровней.

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

Пусть эти алгоритмы и случайны, однако они детерминированы. Это значит, что при наличии одинаковых исходных условий (одинакового seed) они всегда дают одинаковые результаты. И именно благодаря этому каждый мир Minecraft можно воссоздать по его seed. А поскольку сами seed хранятся как 64-битные числа, то существует 18,4 квинтиллиона уникальных значений, которые можно создать.

В No Man«s Sky тоже используются 64-битные seed, и это объясняет, почему в этой игре тоже 18,4 квинтиллиона уникальных планет.

«Rogue» (1980 год)


Но как случайные числа (по сути, получаемые «бросанием кубиков» компьютером) могут создавать миры? Наверно, для объяснения нужно начать с чего-то меньшего, чем Minecraft. Добро пожаловать в «Dungeons of Doom».

Выпущенная в 1980 году игра «Rogue» считается первой графической адвенчурой, она стала главным источником вдохновения для разработчиков тысяч игр в жанре dungeon crawler, выпущенных за последующие десятилетия.

Minecraft тоже позаимствовала многие характеристики, сделавшие Rogue знаменитой, и генерация процедурных подземелий для исследований — лишь одна из них.

Rogue обычно называют первой «графической» адвенчурой, и она определённо была, по крайней мере, одной из первых.

Как же Rogue создавала свои «Dungeons of Doom» (подземелья рока) в 1980 году? Каждый уровень разделялся на сетку 3 на 3, а в каждую ячейку помещалась случайная комната.

803e70f8a103cf07bcdbed820d1ef847.jpg


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

В Rogue также могли появляться тупики, потайные двери и даже комнаты монстров! И всё это было реализовано примерно в девяти тысячах строках кода и более чем трёхстах функциях! …307, если точнее! Для сравнения: в Minecraft 1.18 насчитывается более 52 тысяч функций, находящихся примерно в 4200 файлах!

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

Исходный код Rogue
Оригинальный исходный код «Rogue» можно найти в проекте Decoded: Rogue, где Mai Zure провёл тщательный разбор каждого файла. Основная часть кода была написана до появления стандарта ANSI C, что объясняет присутствие большого количества того, что не стоит считать антипаттернами.

Например, авторы использовали макросы для создания циклов until:

#define until(expr) while(!(expr))

И как будто этого недостаточно, они ещё и заменили ключевые слова C case и default на when и otherwise:
#define when           break;case
#define otherwise      break;default

Недавно я говорил об этом в Twitter, что привело к интересному обсуждению:
Когда вы почувствуете вину из-за написанного вами кода, то просто вспомните, что в исходном коде «Rogue» были макросы для переопределения ключевых слов switch.

#define when break; case
#define otherwise break; default

ryclfhsh45jvzib9gvcw0n3flty.png

4gxgn98ktutlcxarf2gxxlccue0.png

Кодинг «Rogue» в 1980-х, должно быть, сильно походил на игру в рогалик. pic.twitter.com/HbAJbwqlBP— Alan Zucconi (@AlanZucconi) December 18, 2020

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


Исходный код Minecraft
Строго говоря, исходный код Minecraft никогда не публиковался. Однако учитывая, что основная версия игры написана на Java, её достаточно легко декомпилировать. Mojang была толерантна и поддерживала эту практику, поскольку она помогала создать сообщество моддеров.

Если вам любопытно узнать больше об исходном коде Minecraft, то стоит изучить MCP Reborn — Mod Coder Pack, предназначенный для создания модифицированных клиентов и исследования их внутренней работы.


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

И было неправильным говорить об истории Minecraft без упоминания игры, которая стала источником вдохновения её разработчика: «Infiniminer».

Поначалу кажется, что это игра про добычу полезных ископаемых, в которой две команды соревнуются в сборе наибольшего количества руды, золота и алмазов. Но «Infinimer» был не только про добычу ресурсов, но и про создание; не только своей базы, но и историй.

Легко заметить, что игра стала непосредственным источником вдохновения для разработки Minecraft: блоки, кирка, пещеры и лавовые озёра, золото и алмазы, небо и пустота! Даже TNT! В параллельной Вселенной Minecraft могла бы выглядеть так.

Хотя каждая карта «Infiniminer» далеко не бесконечна, все они и в самом деле генерируется процедурно. Всё начинается с цельного блока земли, в котором отрисовывается множество рудных жил. Каждая начинается в случайной точке, и при каждой итерации жила движется в случайном направлении. Эта техника называется «случайным блужданием» (random walk).

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

Такой подход может показаться простым, может, даже слишком, однако это очень похоже на то, как работала Minecraft в первые девять месяцев своей разработки. В своей самой первой версии, в то время называвшейся «Cave Game», каждый мир состоял всего из 256 блоков в ширину и 64 в высоту.

Чтобы реализовать мечту о безграничном мире Minecraft, потребовалось девять месяцев. И реализована она была при помощи очень простого трюка: каждый раз, когда игрок забирался слишком далеко, создавался новый «фрагмент» мира.

Благодаря этому каждый мир был ограничен ПО: например, на 32-битной системе это примерно расстояние в 4,3 миллиарда блоков от точки создания игрока.

Но постойте, прежде чем вы начнёте паковать рюкзак, знайте, что на самом деле так далеко забраться невозможно! Игроки ограничены площадью 60 000 000 на 60 000 000 блоков. По сравнению с бесконечностью кажется, что это не очень много. Однако это всё равно в семь раз больше, чем поверхность Земли. Примерно в половину размера Нептуна!

e21c513d2560b3f2efdfe0df4f2318bf.png


Но даже при этом «больше» не всегда означает «лучше». Ни одна версия Minecraft не даёт игрокам никакой новой геймплейной механики в масштабе больше 25000 блоков. Хотя вблизи мир выглядит богатым и разнообразным, но чем дальше мы отходим, тем сильнее начинает проявляться паттерн. Рано или поздно каждый достаточно большой фрагмент мира будет неотличим от любого другого. В таком масштабе мир Minecraft изотропен, почти как наша Вселенная при максимальном масштабе. Это даёт нам понимание об «истинном» масштабе, в котором в неё нужно играть. И, следовательно, о масштабе, в котором должна по-настоящему работать генерация мира.

2a57ed76729ebba346a2f7c6d137ad3e.png


2048 блоков

d03c177a4119ef96cee2a151dcbc4be1.png


8192 блока

9e1ccfa29e04771d64d5621d643dd31a.png


32768 блоков

fcd197b3cc0e96ce60bfbe9793cedf34.png


131072 блока

ba9ac09b89e55fb0cad622df6aacb2d5.png


524288 блоков

ee003f24c28bef95856f4a278bb82cbc.png


2097152 блока

Как генерировать карты биомов?
Minecraft позволяет игрокам рендерить карты мира при помощи стола картографа. Однако она может иметь ограниченное разрешение. Если вы хотите генерировать крупные карты биомов, то лучше всего использовать одну из множества утилит, созданных сообществом моддеров. Две лучшие Java-библиотеки — это BiomeUtils автора KaptainWutax и SeedFinding/mc_biome_java автора hube12. Для более новых версий Minecraft ещё одна библиотека на C — это Cubitect/cubiomes.

Это инструменты, которые можно использовать для сэмплирования биома любого мира в любой точке. Именно так сгенерированы карты из этой статьи.


Теперь вы видите, что все современные карты Minecraft выглядят «пятнистыми»: это вызвано тем, что каждый цвет представляет отдельный «биом»: область со своими географическими особенностями: растительностью, животными, зданиями и природными условиями.

Спустя девять месяцев после обновления, добавившего «бесконечность», в версии Alpha 1.2.0, больше известной как «Halloween Update», появилось десять таких биомов.

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

В ранних версиях Minecraft использовались три такие карты шума. Одна — для определения высоты рельефа, две другие — для температуры и осадков.

И именно сочетание последних двух определяло биом области.

Высокая температура и низкая влажность? Пустынный биом!

Низкая температура и низкая влажность? Биом тундры!

…и так далее.

c5f28cb8874e865510f5b4a6e28f8ff7.png


Это сработало, потому что карты температуры и осадков были достаточно плавными, поэтому между биомами присутствовали переходы. Это значило, что редко можно было встретить лес по соседству, допустим, с саванной.

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

Существенно переделали эту систему в Beta 1.8: «Adventure Update».

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

Однако избавление от Далёких земель стало лишь побочным эффектом более глубоких изменений. В «Adventure Update» появился совершенно новый генератор рельефа!

Опытные игроки помнят, что в ту эпоху миры имели очень отчётливый стиль. Они были довольно «континентальными»: большие острова, разделённые ещё более обширным океаном.

Всё полностью изменилось в Minecraft 1.7.2, больше известной как «The Update that Changed the World». И это обновление действительно изменило довольно многое! Например, сильно уменьшился размер океанов.

За три года Mojang существенно изменила способ генерации миров. Причём дважды! И это достаточно сильно повлияло на все старые серверы, например, на знаменитый 2b2t — старейший анархический сервер Minecraft. FitMC записал очень интересное видео, демонстрирующее, как такое простое изменение, вроде апгрейда на новую версию, навсегда изменило и так уже неспокойную ситуацию на 2b2t.

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

И хотя в Minecraft 1.18 кое-что изменилось, миры, которые вы годами исследовали, строили, любили и теряли… были созданы одним и тем же алгоритмом.

И, думаю, вы пришли сюда затем, чтобы узнать, как же он работает на самом деле.

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

Хм, наверно, это не самый эффективный способ объяснения работы алгоритма.

Может быть, стоит показать на примерах?


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

Во второй фазе генерации мира происходит работа с рельефом, она разбита на три этапа.

На первом создаётся базовый контур при помощи карты биомов, определяющей высоту, которую может иметь каждая область. В результате получается сплошной бесплодный ландшафт, полностью состоящий из камня, на котором каждый пустой блок ниже $y=62$ превращается в воду.

На последующем этапе все каменные блоки на поверхности заменяются типом, соответствующим их биому. Травой в случае равнин, песком для пустынь, гравием для океанов, и так далее. Также на этом этапе генерируется слой коренной породы. Любопытно, что в Java Edition её паттерн не зависит от seed мира и одинаков для каждого мира Minecraft.

На третьем этапе из камня вырезаются пещеры и ущелья.

f121a4ce862baca59f6b58febe378b4e.png


b114fbfd7cd50e043f0fefba0dfe21d1.png


Третья фаза заполняет мир оставшимися элементами. Сначала размещаются такие постройки, как деревни, крепости и океанические монументы, затем идут декоративные элементы наподобие деревьев и травы. Также в этой фазе в мир добавляются рудные жилы, и этот процесс схож с используемым в «Infiniminer».

Давайте подробнее рассмотрим, как работает каждая фаза…

Карта биомов


Генерация карты биомов — самая критически важная фаза, потому что она служит чертежом для создания всего остального мира.

Карта создаётся последовательностью довольно простых операций, называемых «слоями», наложенными друг поверх друга. Каждый слой получает карту биомов с предыдущего слоя, добавляет деталей и передаёт её следующему.

6a8a33de41ee3dd2fa9c1e4467e79399.png


Миры Minecraft создаются при помощи не одного, а целых четырёх наборов слоёв.

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

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

Разумеется, у Minecraft нет кубика D10, однако она может «бросать» случайные числа при помощи так называемого квадратичного конгруэнтного генератора.

Внутри исходного кода это называется Island Layer, потому что каждый отдельный пиксель этой карты шума будет шаблоном, из которого возникают континенты. На самом деле, каждый пиксель соответствует 4096 игровым блокам.

Чем глубже мы опускаемся по слоям биомов, тем детализированней становится карта. Это возможно благодаря слоям масштабирования (zoom), которые в два раза увеличивают разрешение, с которым будут работать последующие слои.

Например, если пиксель из Island layer соответствует 4096 блокам, то каждый добавленный после масштабирования пиксель будет иметь в игре размер 2048 блоков.

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

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

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

Если выполнять этот слой снова и снова, то мы увидим, что он не всегда обеспечивает одинаковый результат. Даже слои добавляют случайности!

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

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

Основная часть формы суши создаётся попеременным использованием слоёв AddIsland и Zoom. Это позволяет создавать в мире уникальные элементы в различных разрешениях.

Области океанов


Форма океана в основном задаётся двумя слоями.

Первый был добавлен в «Adventure Update», чтобы сделать мир менее «континентальным» и более «взаимосвязанным». В коде Minecraft это в буквальном смысле называется Remove Too Much Ocean («убираем слишком большое количество океана»).

Все области океана, окружённые океаном, имеют вероятность 50% превращения в сушу.

450973f0b38631c55093ddd65582027a.png


f3771bc74386cc0d0215e05d69a5c1db.png


Это не только создаёт более фрагментированные побережья, но и изменяет соотношение суши к воде с 27% до более чем 50%.

Следующий слой из основного набора помечает все области океана, окружённые другим океаном, как «глубокие». Позже это приведёт к созданию биомов мелководья и глубоководья.

Температуры и биомы


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

Сначала каждой точке суши случайно назначается температура: Warm (тёплая), Cold (холодная) или Freezing (морозная) в пропорциях 4, 1 и 1.

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

Любая тёплая суша по соседству с холодной или морозной превратится в умеренную. А морозная суша рядом с тёплой или умеренной превратится в холодную.

В конечном итоге эти температуры являются основным фактором определения того, каким биомом станет конкретный фрагмент суши. Например, тёплые области имеют вероятность 50% превращения в пустыню, 33% в саванну, а оставшиеся 17% — в равнины.

Аналогичным образом умеренные, холодные и морозные области имеют определённые вероятности превращения в умеренный, холодный и морозный биомы (леса, тайгу и ледяные равнины).

Варианты биомов


На этом этапе ландшафт уже выглядит знакомым, но ему недостаёт вариативности в отдельных биомах. Чтобы исправить это, в данном слое имеется небольшая вероятность превращения биома в его «холмистый» вариант. Например, он может превратить пустыню в пустынные холмы, лес в лесистые холмы, а саванну в плато.

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

a9236893270505bb71e3d2d607c9f7b9.png


424003228ccc226e2d18048144716fc6.png


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

Обычно каждый слой работает с картой локально, игнорируя общую картину. А при наличии такого количества шагов сложно гарантировать гармоничное смешение между биомами.

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

b778cb74d739c8f659f852e92589f4ed.png


d0fc21c3889898f0635719a1712b6db1.png


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

25d655ed0a64b9d729dd272c1a5aafdc.png


fa5f87c4425dffee07a6be7f40338b4a.png


Редкие биомы


Особого упоминания заслуживают редкие биомы, поскольку их генерация выполняется немного иначе. Кроме назначения температур слой климата имеет вероятность 1/13 пометить область как «особую».

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

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

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

Легендарные грибные острова создаются схожим образом. Каждый блок океана, окружённый водой, имеет вероятность 1/100 превращения в грибное поле. Отвечающий за это слой находится довольно высоко, поэтому грибные острова обычно довольно большие и однородные.

Это один из редчайших биомов в Minecraft, единственный, где естественным образом не создаются враждебные мобы.

Слои создания рек


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

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

8a11d27bd1bbcfeeebf5cdb0007d38a2.png


fee9d8d1593d9b5ac9dcd789486faf54.png


Затем они сглаживаются фильтром низких частот, чтобы устранить любые зазоры или грубые края, и передаются в основной набор слоёв через River Mixer Layer.

8d5de4f1349294423e695d54988d8f11.png


794a2eeddceb36c4663cba932bcc9b76.png


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

Набор слоёв температуры океана


Последний элемент, задействованный в генерации биомов — это набор слоёв температуры океана. Он добавляет вариативности океану, который за исключением мелководья и глубоководья не имеет других отличительных черт.

Этот набор слоёв при помощи шума Перлина создаёт собственную карту температур. Это очень популярный алгоритм для создания процедурных карт шума, который был разработан в 1982 году, но не для игры, а для фильма «Трон».

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

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

Существуют ли альтернативы шуму Перлина?
С момента публикации статьи о шуме Перлина в 1985 году он стал очень популярен во всех медиа, где в той или иной форме присутствует процедурная генерация. Он настолько известен, что в большинстве движков имеется собственная реализация шума Перлина, например, Mathf.PerlinNoise движка Unity (документация) или Noise Texture Node в Blender.

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

37f45d7c184e1cd49ceb3e0cd68da079.png

Из-за этого созданные при помощи шума Перлина ландшафты обычно бывают очень «квадратными» и в них часто присутствуют выровненные по сетке элементы, раскрывающие происхождение шума, использованного при их создании.

Некоторые разработчики предупреждают, что не стоит во всём полагаться на шум Перлина как на первый, а иногда и единственный тип шума для творчества. Если вы хотите узнать об интересных альтернативах, не имеющих недостатков шума Перлина, то крайне рекомендую прочитать статью The Perlin Problem: Moving Past Square Noise.

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


b92aa13f202c79e7b42d8ba6ce7c0823.png


После завершения генерации карта увеличивается в масштабе и вливается в полный набор слоёв при помощи OceanMixer Layer. Это наконец создаёт биомы в областях океана, которые могут быть тёплыми, тепловатыми, холодными и замёрзшими.

36d8a3853bb69da0979d3c4c7fb6c520.png


0b0aa832be55d6188bff4c0916242c47.png


Самый последний этап — увеличение масштаба карты ещё два раза. Это выполняется не традиционными слоями Zoom, которые мы видели раньше, а при помощи другой техники, которая ещё сильнее разрушает края между разными биомами.

После этого у нас на руках остаётся готовая карта биомов, в которой каждый пиксель соответствует реальному блоку игры.

0a0ab88c40138de9ae4cf14598db97d1.png


И мы готовы двигаться к следующей фазе!

Высота рельефа


Во второй фазе, разбитой на три этапа, генерация мира занимается рельефом.

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

Первый из трёх этапов генерации рельефа Minecraft определённо требует подробного объяснения.

Minecraft создаёт сложный и интересный рельеф при помощи техники под названием «фрактальный шум броуновского движения»: это ещё одно название карты шума.

Фрактальный шум создаётся сложением нескольких карт шума Перлина, сэмплируемых с разным масштабом. Каждая новая (называемая октавой) имеет в два раза большее разрешение по сравнению с предыдущей, но её вклад также снижается вдвое.

Фрактальный шум известен тем, что создаёт правдоподобно выглядящие рельефы. И он работает, потому что добавляет разную степень детализации в разных масштабах. Именно это мы и наблюдаем в реальных рельефах.

Minecraft запросто могла бы сэмплировать фрактальную карту в каждой координате $\left(x, z\right)$, чтобы получить высоты рельефа. Однако алгоритмы игры работают иначе!

Так как же Minecraft получает высоту рельефа? Она начинает с самой вершины мира, в координате $y=255$, и начинает двигаться вниз, вычисляя значение фрактального шума для каждой конкретной координаты $\left(x,y,z\right)$ вдоль этого виртуального столбца. Первая координата $y$, для которой фрактальный шум равен или больше нуля, становится окончательной высотой рельефа в координате $\left(x, z\right)$.

d7b91f30fb6ae706e5e058d2235263a2.png


В ранних девлогах объяснялось, зачем нужен этот процесс: мы должны интерпретировать «значение шума как «плотность» — всё меньше нуля будет считаться воздухом, а всё, что больше или равно нулю, будет землёй».

В том же самом посте также говорится о том, насколько вычислительно затратен этот процесс. Поэтому ради оптимизации эту карту фрактального шума сэмплируют с меньшим разрешением: мир разделён на «ячейки» размером 4×8x4 блоков каждая.

Если точнее, в Minecraft не используется единая карта фрактального шума: на самом деле их три! Причина этого проста: эти карты замечательны, но довольно однородны. Благодаря использованию двух карт, инициализированных с разными параметрами и смешанными согласно третьей карте шума, Minecraft позволяет добавлять ещё более интересные и естественно выглядящие вариации рельефа.

Но и это ещё не всё! В ранних версиях Minecraft биомы и карта высот рельефа не зависели друг от друга. Однако начиная с Beta 1.8 и далее карта биома напрямую влияет на генерацию рельефа, модулируя максимальную высоту каждого биома.

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

d2227333a117ae52b1e3009874622313.png


Строго говоря, в генерации рельефа задействовано ещё как минимум две карты шума. Карта «шума глубин» добавляет вариативности для компенсации того, что интерполяция между ячейками сглаживает мелкие детали. А карта «шума поверхности» определяет, сколько блоков камня нужно заменить стандартным блоком в каждом биоме.

И, вероятно, существует ещё с десяток других карт, используемых в мелких де

© Habrahabr.ru