...используя диаграммы Вороного и много шумов Перлина/симплексных шумов
Прим. переводчика: стоит отметить, что непосредственно в Minecraft используются отличные от описанных ниже подходов — игра не использует диаграммы Вороного, а кроме двумерных шумов применяет также и трёхмерные (что, в частности, позволяет генерировать не только карту высот, но и пещеры)
Minecraft, самая продаваемая игра в мире, наиболее известная своими пикселизированными блоками и бесконечными мирами, содержит потрясающий процедурный генератор ландшафта — с пещерами, водоёмами, и даже различными биомами.
Процедурная генерация является важной частью компьютерной графики — она используется в основном в играх и в фильмах. Она помогает создавать случайные структуры, не вызывающие ощущения «машинного» стиля.
Также процедурная генерация играет важную роль в машинном обучении. Она позволяет генерировать такие данные, которые сложно собрать. Обучение моделей машинного обучения требует огромных датасетов, которые может быть затруднительно собирать и подготавливать. Генерацию данных процедурным образом можно легко адаптировать к требуемому типу данных.
В детстве мне нравилось играть в Minecraft, и мне всегда было интересно, как эта игра генерирует бесконечные миры. В данной статье я попытаюсь воссоздать это на Python.
Определения и ограничения
Для начала, определимся с тем, как будет генерироваться наш мир.
Мир является трёхмерным, дискретным (состоящим из блоков единичного размера), ограниченным по оси z в диапазоне от
0до255и неограниченным по осям x и y.Мир содержит биомы, каждый из которых охватывает большую площадь по горизонтали, и которые определяют характер местности в занимаемом биомом пространстве.
Мир содержит реки, озёра и океаны.
Каждый мир определяется зерном (англ. seed). Одно и то же значение зерна всегда приводит к генерации одного и того же мира.
Генерация миров
Чтобы упростить процесс генерации, мы разделим наш мира на чанки (англ. chunk — ячейка, кусок). Каждый чанк занимает пространство размером 1024×1024×256 блоков.
Каждый чанк генерируется отдельно. Это поможет нам сохранять и загружать мир, а также упростит задачу генерации мира по частям.
Прим. переводчика. В Minecraft также используется разбиение пространства на чанки, однако они имеют значительно меньшие размеры — 16x16x256 блоков (16x16x384 — начиная с версии 1.18)
Границы биомов
Первое, что нам нужно сделать — разделить мир на ячейки в плоскости xy, каждая из которых будет принадлежать определённому биому. Каждой ячейке мы назначим точку, обозначающую её центр.
Диаграмма Вороного
Диаграмма Вороного поможет нам разбить мир на ячейки по заданному множеству точек. Основная идея диаграмм Вороного заключается в том, что каждая точка плоскости принадлежит той ячейке, центр которой находится к ней ближе всего.
Мы можем проделать это для каждой точки плоскости xy, чтобы построить диаграмму Вороного для этих трёх точек.
Хотя такой подход и работает, он очень медленный, особенно когда количество точек велико.
В Python модуль scipy.spatial содержит класс Voronoi, который строит диаграммы Вороного более эффективно и предоставляет больше информации о диаграмме.
Класс Voronoi в scipy.spatial возвращает список вершин, регионов и рёбер, что будет полезно на следующих этапах.
Эти дополнительные точки помогают сформировать так называемую тесселяцию Делоне (прим. переводчика: также её часто называют триангуляцией Делоне).
Алгоритм релаксации Ллойда
Теперь нам необходимо сгенерировать случайные точки, которые станут центрами ячеек.
Если мы используем функцию наподобие random из модуля numpy.random, чтобы сформировать множество точек, и построим по ним диаграмму Вороного, то получим следующий результат:
Как вы могли заметить, некоторые точки оказались слишком близко друг к другу. Это называется кластеризацией. Желательно, чтобы ячейки были распределены более равномерно.
Этот эффект становится более заметен, если мы уменьшим масштаб (или увеличим число точек):
Чтобы решить эту проблему, нам необходимо распределить точки дальше друг от друга.
Одним из способов решения этой проблемы является алгоритм релаксации Ллойда, который использует диаграмму Вороного, построенную по исходным точкам.
Идея алгоритма Ллойда заключается в том, чтобы построить диаграмму Вороного, а затем переместить каждую точку в центроид (геометрический центр) соответствующей ей ячейки. Данный процесс может быть повторён несколько раз.
Центроидом многоугольника является среднее от всех его вершин.
Вот диаграмма Вороного, в которой исходные точки отмечены синим цветом, а центроиды ячеек — красным.
Далее мы можем заменить исходные точки (синие) центроидами (красными), и повторять этот процесс снова и снова.
Это позволяет получить более привлекательное распределение случайных точек.
Шум Перлина/симплексный шум: зачем он нужен?
Чтобы построить случайный ландшафт, нам необходимо сгенерировать свойства, которые будут меняться случайным образом в пространстве — такие свойства, как высота, температура или количество осадков.
Первое, что приходит на ум — воспользоваться функцией random, и это логично.
Попробуем сгенерировать случайное число в диапазоне от 0 до 255, для каждого блока в плоскости xy в нашем мире.
Это приведёт нас к следующему результату:
Что ж, это больше похоже на QR-код, нежели на мир в Minecraft.
Проблема заключается в том, что наши случайные величины не имеют под собой связной структуры. Каждое значение генерируется независимо и не имеет ничего общего с соседними.
Чтобы решить эту проблему, применим шум Перлина.
Шум Перлина был изобретён Кеном Перлином в 1983 году. В отличие от обычного случайного шума, он обладает внутренней структурой. Он больше похож на случайные паттерны, встречающиеся в природе (облака, распределение лесов).
Симплексный шум был также создан самим Кеном Перлином. Он имеет много преимуществ по сравнению с шумом Перлина. В наши дни шум Перлина и симплексный шум повсеместно используются в процедурной генерации.
Мы будем использовать реализацию симплексного шума на Python из модуля noise.
Нам доступно 4 переменных, с которыми можно поиграть: scale (масштаб), octaves (число октав), persistence (персистентность), lacunarity (лакунарность). Я не буду объяснять, за что отвечает каждая из них, но предоставлю вам следующие гифки, которые я сделал, чтобы самому разобраться в этом.
Шум Перлина с различными параметрами. Изображения автора.
Возвращаемые значения шума лежат в диапазоне от -1 до 1.
«Правильность» ячеек — размываем границы
Несмотря на то, что сгенерированные для ячеек точки неплохо разнесены друг от друга, сами ячейки выглядят почти как правильные многоугольники.
Для устранения этого недостатка будем использовать шум Перлина. Для каждой точки мы выберем случайную точку поблизости и присвоим текущей точке вновь выбранную.
Для этого нам понадобится две карты шума, одна — для смещений по оси x, другая для оси y.
Мы можем управлять зашумлённостью границ, умножая значение шума (в диапазоне от -1 до 1) на некоторую константную длину.
Выбор биомов
В Minecraft представлено более 60 различных биомов, каждый со своими различными свойствами. Теперь, когда наш мир разбит на ячейки, нам необходимо присвоить биом каждой из них. Для этой цели мы будем использовать шум Перлина.
График температуры-осадков
Определим биомы, основываясь на двух параметрах: температуре и количестве осадков, используя график температуры-осадков. Так биомы обычно определяются в биологии окружающей среды.
Вдохновляясь этой диаграммой, спроектируем наш собственный график температуры-осадков.
Карты температуры и осадков
Теперь назначим каждой ячейке температуру и количество осадков, используя шум Перлина. Сгенерируем две карты, каждая из которых содержит значения шума для всех блоков в нашем чанке.
Выравнивание гистограмм
Если мы будем использовать приведённые выше карты температур и количества осадков, мы столкнёмся с проблемой. Значения, основанные на шуме Перлина, распределены не равномерно. Среди них больше значений, близких к 0, нежели значений, близких к -1 или 1. Это снижает число биомов, которые находятся на краях графика температур-осадков.
Чтобы лучше понять эту неравномерность, я построил одномерную гистограмму и потрясающую двумерную гистограмму карт температуры и количества осадков.
Как можно видеть, значения по краям дискриминированы. Чтобы устранить этот недостаток, выровняем наши значения.
Выравнивание гистограммы используется, чтобы скорректировать экспозицию изображений. По этой причине я использовал функцию exposure из модуля skimage.
Выровненная гистограмма становится плоской:
Поскольку мы выравнивали температуру и количество осадков независимо друг от друга, двумерная гистограмма не является полностью плоской.
Возможно, мы не хотим полностью сглаживать наши гистограммы. Чтобы иметь возможность управлять степенью сглаженности гистограмм, мы можем смешивать невыровненные значения с выровненными в некоторой пропорции.
Теперь мы можем управлять тем, насколько выровнены наши значения.
Усреднение значений внутри ячеек
Теперь каждая ячейка содержит значения температуры и количества осадков в диапазоне от -1 до 1.
Квантование
Чтобы упростить работу со значениями температуры и количества осадков, преобразуем их в целые числа. Будем использовать np.uint8 в качестве типа данных для хранения этих значений.
Чтобы преобразовать значения карт, представленных выше, отобразим их на интервал [0, 255], и округлим к ближайшему целому.
Квантование не меняет то, как выглядит температура и количество осадков.
Теперь мы можем определить наш график температуры-осадков в виде изображения размером 256×256 пикселей:
Карта биомов
Мы можем назначить каждой ячейке биом, используя график температуры-осадков, карту температур и карту осадков. Выполнив это для каждой ячейки, мы получим следующий результат:
Карта высот
Каждая точка нашего двумерного мира имеет высоту. Чтобы построить карту высот, мы будем использовать карту шума.
Используя эту карту высот (со значениями от -1 до 1), мы можем построить маску суши. Значения выше 0 становятся сушей, а ниже 0 — морем.
Совместим эту маску с изображением выше:
Чтобы визуализировать высоту, добавим затенение на карту:
Пока что результаты выглядят многообещающе. Но сейчас высота не зависит от биома. Нам следует менять карту высот внутри каждого биома. Чтобы достичь этой цели, мы будем применять некоторую функцию к карте высот.
Детализированная карта высот
Будем теперь использовать 2 карты высот с различной степенью детализации. Для этого будем использовать различное число октав в шуме Перлина.
Вот две наших карты высот:
Фильтрация карты высот
Мы будем работать с картой высот на суше (значения высоты в диапазоне от 0 до 1). Каждый биом будет использовать комбинацию двух карт высот (размытой и резкой) — и затем применять фильтр (функцию) к результату.
Идея применения фильтров основывается на инструменте Кривые (Curves) в Photoshop. Используем кубические кривые Безье, чтобы определить функцию, которую мы применим к карте высот.
Вот некоторые примеры фильтров:
Создадим и настроим фильтр для каждого биома.
Чтобы применить эти фильтры к нашей карте высот, мы будем использовать маски. Маска это карта, содержащая 1 в областях, принадлежащих некоторому биому, и 0 в остальных областях.
Если мы будем использовать жёсткую маску, у нас будут огромные перепады высот (на границах биомов — прим. переводчика). Поэтому применим размытие к маскам перед использованием. Также удалим океан с этой карты (умножив её на маску суши), чтобы применить фильтры только к суше.
Применим фильтры каждого биома к карте высот, пользуясь масками выше. Получим следующие результаты:
Итоговые результаты в 3D
Используя Blender, мы можем отрендерить эти карты в 3D. Используем карту высот в модификаторе "Displace" в Blender.
Реки и озера
Границы
Добавим реки на границах между биомами. Во-первых, нам понадобится вычислить границы между биомами.
Для этой цели мы переберём все точки на карте. Если у некоторой точки все её соседи принадлежат тому же биому, то она не лежит на границе. Если среди её соседей больше одного типа биома, то она является частью границы.
Применяя этот подход к нашей карте биомов, получим следующие результаты.
Можно управлять шириной рек, изменяя размер окрестности, содержащей соседние точки.
Будем использовать 2 различных разновидности рек: биомные реки и ячеечные реки. Биомные реки широкие и размещаются на границах биомов, в то время как ячеечные реки меньше и размещаются на границах ячеек. Затем используем маску суши, чтобы ограничить реки сушей.
Реки также будут ограничены лишь средней и низкой высотой над уровнем моря.
Прим. переводчика. Честно говоря, на мой взгляд, тут у автора получилось что-то очень странное в отношении рек.
Используем эту маску рек чтобы изменить карту высот. Размоем эту маску рек, а затем применим исходную маску рек к полученному результату. Таким образом получится карта с большими значениями в серединах рек, которые плавно уменьшаются к берегам.
Вот сравнение маски рек с размытой и маскированной маской рек.
Используем эту карту, чтобы «прорезать» реки в карте высот.
Деревья и растительность
Чтобы добавить деревья на нашу карту, используем алгоритм релаксации Ллойда, описанный ранее. Этот метод сэмплирования помогает генерировать случайные точки, разнесённые друг от друга.
Прим. переводчика: для получения равномерно разнесённых точек также неплохо подходит алгоритм сэмплирования диском Пуассона (Poisson Disc Sampling)
UPD: Пользователь @BigObfuscator в комментариях также рекомендует использовать для этой цели последовательность Халтона или пластическую последовательность.
Будем создавать множества деревьев различной плотности в зависимости от биома.
Скомбинируем множество деревьев с масками биомов и маской суши, чтобы заполнить биомы деревьями. Каждый биом имеет различную плотность и, разумеется, различные типы деревьев.
Мои навыки владения Блендером не позволяют мне визуализировать карту с деревьями в 3D :(
Исходный код
Вот ссылка на Jupyter-ноутбук, содержащий все описанные в статье шаги в виде кода.
Предупреждение: Код очень запутанный и незадокументированный.
Заключение
Процедурная генерация является мощным инструментом в компьютерной графике. Она позволяет сгенерированному контенту выглядеть случайным, но в то же время художественным и структурированным. Как было сказано ранее, это можно использовать в машинном обучении для создания датасетов, покрывающих те области, которые дорого или затруднительно покрыть с помощью данных, собранных в реальном мире.
Эта статья была лишь забавным проектом, над которым я хотел поработать уже больше года. В нём ещё многого не хватает. Например, мне нужно создавать пещеры под землёй, деревни, а также придумать алгоритм, способный бесшовно соединять соседние чанки.
Источники вдохновения
Я вдохновлялся многими статьями, когда писал мою. Если вам понравилась эта статья, то вам определённо захочется прочитать и эти тоже:
