[Перевод] Воссоздаем Minecraft-подобную генерацию мира на Python
…используя диаграммы Вороного и много шумов Перлина и симплексных шумов
Прим. переводчика: стоит отметить, что непосредственно в Minecraft используются отличные от описанных ниже подходов — игра не использует диаграммы Вороного, а кроме двумерных шумов применяет также и трёхмерные (что, в частности, позволяет генерировать не только карту высот, но и пещеры)
Изображение автора.
Minecraft, самая продаваемая игра в мире, наиболее известная своими пикселизированными блоками и бесконечными мирами, содержит потрясающий процедурный генератор ландшафта — с пещерами, водоемами, и даже различными биомами.
Процедурная генерация является важной частью компьютерной графики — она используется в основном в играх и в фильмах. Она помогает создавать случайные структуры, не вызывающие ощущения «машинного» стиля.
Также процедурная генерация играет важную роль в машинном обучении. Она позволяет генерировать такие данные, которые сложно собрать. Обучение моделей машинного обучения требует огромных датасетов, которые может быть затруднительно собирать и подготавливать. Генерацию данных процедурным образом можно легко адаптировать к требуемому типу данных.
В детстве мне нравилось играть в Minecraft, и мне всегда было интересно, как эта игра генерирует бесконечные миры. В данной я статье я попытаюсь воссоздать это на Python.
Прим. переводчика. Осторожно, в статье много иллюстраций (в том числе анимированных)
Определения и ограничения
Для начала, определимся с тем, как будет генерироваться наш мир.
Мир является трёхмерным, дискретным (состоящим из блоков единичного размера), ограниченным по оси z в диапазоне от
0до255и неограниченным по осям x и y.Мир содержит биомы, каждый из которых охватывает большую площадь по горизонтали, и которые определяют характер местности в занимаемом биомом пространстве.
Мир содержит реки, озёра и океаны.
Каждый мир определяется зерном (англ. seed). Одно и то же значение зерна всегда приводит к генерации одного и того же мира.
Генерация миров
Чанк. Изображение автора.
Чтобы упростить процесс генерации, мы разделим наш мира на чанки (англ. chunk — ячейка, кусок). Каждый чанк занимает пространство размером 1024×1024×256 блоков.
Каждый чанк генерируется отдельно. Это поможет нам сохранять и загружать мир, а также упростит задачу генерации мира по частям.
Прим. переводчика. В Minecraft также используется разбиение пространства на чанки, однако они имеют значительно меньшие размеры — 16×16x256 блоков (16×16x384 — начиная с версии 1.18)
Границы биомов
Первое, что нам нужно сделать — разделить мир на ячейки в плоскости xy, каждая из которых будет принадлежать определённому биому. Каждой ячейке мы назначим точку, обозначающую её центр.
Диаграмма Вороного
Диаграмма Вороного поможет нам разбить мир на ячейки по заданному множеству точек. Основная идея диаграмм Вороного заключается в том, что каждая точка плоскости принадлежит той ячейке, центр которой находится к ней ближе всего.
Движущаяся точка окрашивается в цвет ближайшей к ней неподвижной точки. Изображение автора.
Мы можем проделать это для каждой точки плоскости xy, чтобы построить диаграмму Вороного для этих трёх точек.
Анимированная диаграмма Вороного для 3 точек. Изображение автора.
Хотя такой подход и работает, он очень медленный, особенно когда количество точек велико.
Анимированная диаграмма для 20 точек. Изображение автора.
В Python модуль scipy.spatial содержит класс Voronoi, который строит диаграммы Вороного более эффективно и предоставляет больше информации о диаграмме.
Диаграмма Вороного, построенная с помощью scipy.spatial. Изображение автора.
Класс 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.
Рендер карты высот с окрашиванием в зависимости от биома.
Сделано при помощи Blender. Изображение автора.Рендер карты высот с окрашиванием в зависимости от биома.
Сделано при помощи Blender. Изображение автора.Рендер карты высот с окрашиванием в зависимости от биома.
Сделано при помощи Blender. Изображение автора.
Реки и озера
Границы
Добавим реки на границах между биомами. Во-первых, нам понадобится вычислить границы между биомами.
Для этой цели мы переберём все точки на карте. Если у некоторой точки все её соседи принадлежат тому же биому, то она не лежит на границе. Если среди её соседей больше одного типа биома, то она является частью границы.
Иллюстрация пограничного пикселя. Изображение автора.Пример границы. Изображение автора.
Примения этот подход к нашей карте биомов, получим следующие результаты.
Карта биомов (слева) и рек (справа). Изображение автора.
Можно управлять шириной рек, изменяя размер окрестности, содержащей соседние точки.
Реки различной ширины. Изображение автора.
Будем использовать 2 различных разновидности рек: биомные реки и ячеечные реки. Биомные реки широкие и размещаются на границах биомов, в то время как ячеечные реки меньше и размещаются на границах ячеек. Затем используем маску суши, чтобы ограничить реки сушей.
Реки также будут ограничены лишь средней и низкой высотой над уровнем моря.
Реки. Изображение автора.
Прим. переводчика. Честно говоря, на мой взгляд, тут у автора получилось что-то очень странное в отношении рек.
Используем эту маску рек чтобы изменить карту высот. Размоем эту маску рек, а затем применим исходную маску рек к полученному результату. Таким образом получится карта с большими значениями в серединах рек, которые плавно уменьшаются к берегам.
Вот сравнение маски рек с размытой и маскированной маской рек.
Маска рек. Изображение автора.Боковое сечение маски рек. Изображение автора.
Используем эту карту, чтобы «прорезать» реки в карте высот.
Карта биомов (слева) и карта биомов с реками (справа). Изображение автора.
Деревья и растительность
Чтобы добавить деревья на нашу карту, используем алгоритм релаксации Ллойда, описанный ранее. Этот метод сэмплирования помогает генерировать случайные точки, разнесённые друг от друга.
Прим. переводчика: для получения равномерно разнесённых точек также неплохо подходит алгоритм дискового сэмплирования Пуассона (Poisson Disc Sampling)
Случайно выбранные точки (слева), релаксированные точки (справа). Изображение автора.
Будем создавать множества деревьев различной плотности в зависимости от биома.
Различные уровни плотности деревьев. Изображение автора.
Скомбинируем множество деревьев с масками биомов и маской суши, чтобы заполнить биомы деревьями. Каждый биом имеет различную плотность и, разумеется, различные типы деревьев.
Карта биомов с деревьями. Изображение автора.
Мои навыки владения Блендером не позволяют мне визуализировать карту с деревьями в 3D:(
Исходный код
Вот ссылка на Jupyter-ноутбук, содержащий все описанные в статье шаги в виде кода.
Предупреждение: Код очень запутанный и незадокументированный.
Заключение
Процедурная генерация является мощным инструментом в компьютерной графике. Она позволяет сгенерированному контенту выглядеть случайным, но в то же время художественным и структурированным. Как было сказано ранее, это можно использовать в машинном обучении для создания датасетов, покрывающих те области, которые дорого или затруднительно покрыть с помощью данных, собранных в реальном мире.
Эта статья была лишь забавным проектом, над которым я хотел поработать уже больше года. В нём ещё многого не хватает. Например, мне нужно создавать пещеры под землёй, деревни, а также придумать алгоритм, способный бесшовно соединять соседние чанки.
Источники вдохновения
Я вдохновлялся многими статьями, когда писал мою. Если вам понравилась эта статья, то вам определённо захочется прочитать и эти тоже:
