Использование диаграмм Вороного и большого количества шума Perlin/Simplex

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

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

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

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

Определения и ограничения

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

  • Мир трехмерный, дискретный (состоящий из блоков единичного размера), ограниченный по оси Z точками 0 и 255 и неограниченный по осям X и Y.
  • Мир содержит биомы, каждый из которых охватывает большие горизонтальные области, определяющие характер пространства, занимаемого биомом.
  • В мире есть реки, озера и океаны.

Каждый мир определяется семенем. Одно и то же семя всегда будет генерировать один и тот же мир.

Создание миров

Чтобы упростить процесс генерации, мы разделим наш мир на куски. Каждый фрагмент будет занимать пространство размером 1024×1024×256 блоков.

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

Границы биомов

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

Диаграмма Вороного

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

Мы можем сделать это для каждой точки на плоскости xy, чтобы получить диаграмму Вороного для этих трех точек.

Хотя этот метод работает, он мучительно медленный, особенно когда количество точек велико.

В Python у scipy.spatial есть класс Voronoi, который более эффективно вычисляет диаграммы Вороного и предоставляет нам больше информации о диаграмме.

scipy.spatial с Voronoi возвращает список вершин, областей и ребер, которые будут полезны позже.

Эти дополнительные точки помогают сформировать так называемую тесселяцию Делоне.

Алгоритм релаксации Ллойда

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

Если мы используем такую ​​функцию, как random из numpy.random, для создания нескольких точек и расчета диаграммы Вороного, мы получим следующие результаты:

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

Это более заметно, когда мы уменьшаем масштаб (или увеличиваем количество точек):

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

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

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

Центроид многоугольника является средним значением его вершин.

Это диаграмма Вороного с точками ячеек, выделенными синим и центроидами ячеек, выделенными красным.

Затем мы можем снова и снова заменять точки ячеек (синие) центроидами ячеек (красные).

Это дает более привлекательные случайные точки.

Perlin/Simplex Noise: зачем нам это нужно?

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

Можно подумать об использовании random , и это будет иметь смысл.

Мы собираемся сгенерировать случайное число от 0 до 255 для каждого блока на плоскости xy в нашем мире.

Это дает следующий результат:

Что ж, это больше похоже на QR-код, чем на мир Minecraft.

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

Чтобы преодолеть эту проблему, мы собираемся использовать шум Перлина.

Шум Перлина был изобретен Кеном Перлином в 1983 году. В отличие от обычного случайного шума, он имеет структуру. Это выглядит ближе к случайным закономерностям, встречающимся в природе (облака, распространение леса).

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

Мы будем использовать реализацию симплексного шума в Python под названием noise. (модуль Python).

У нас есть 4 переменные для игры: масштаб, октавы, постоянство, лакунарность. Я не буду объяснять, что каждый из них делает, но я оставлю вас с этими GIF-файлами, которые я сделал, чтобы вы сами поняли это.

Возвращаемые значения шума находятся в диапазоне от -1 до 1.

Регулярность ячеек — Размывание границ

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

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

Для этого нам нужны две карты шума, одна для смещения по оси X, а другая по оси Y.

Мы можем контролировать зашумленность границ, умножая шум (значения от -1 до 1) на постоянную длину.

Выбор биомов

Minecraft имеет более 60 различных биомов. Каждый с разными свойствами. Теперь, когда мы разделили наш мир на ячейки, мы должны назначить биом каждой клетке. Для этого мы будем использовать шум Перлина.

График температура–осадки

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

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

Карты температуры и осадков

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

Выравнивание гистограммы

Если мы воспользуемся приведенными выше картами температуры и осадков, мы столкнемся с проблемой. Значения, основанные на шуме Перлина, неодинаковы. Значений, близких к 0, больше, чем значений, близких к -1 или 1. Это различает биомы, которые находятся на краях графика температуры и осадков.

Чтобы лучше понять эту неравномерность, я построил 1D-гистограммы и изумительно выглядящую 2D-гистограмму карт температуры и осадков.

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

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

Выровненная гистограмма плоская.

Поскольку мы уравнивали температуру и осадки по отдельности, двумерная гистограмма не является полностью плоской.

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

Теперь мы можем контролировать, насколько уравновешены наши значения.

Ячейки усреднения

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

Теперь в каждой ячейке есть температура и количество осадков в диапазоне от -1 до 1.

Квантование

Чтобы упростить работу со значениями температуры и осадков, мы преобразуем их в целые числа. Мы будем использовать np.uint8 в качестве типа данных для хранения этих значений.

Чтобы преобразовать значения на приведенных выше картах, мы сопоставим их с [0, 255] и округлим значение до ближайшего целого числа.

Квантование не меняет внешний вид температуры и осадков.

Теперь мы можем определить наш график температуры и осадков с помощью изображения 256 × 256.

Карта биомов

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

Карта высот

Каждая точка в нашем 2-мерном мире имеет возвышение (высоту). Для создания карты высот мы будем использовать карту шума.

Используя эту карту высот (со значениями от -1 до 1), мы можем создать маску длины. Значения выше 0 относятся к суше, а значения ниже 0 — к морю.

Комбинируя это с изображением, созданным ранее:

Чтобы визуализировать высоту, мы добавим на карту затенение.

Пока результаты выглядят многообещающе. Но высота не зависит от биома. Нам нужно изменить карту высот в каждом биоме. Мы добьемся этого, применив функцию к карте высот.

Детали карты высот

Мы будем использовать 2 карты высот с разным уровнем детализации. Это делается путем изменения количества октав в шуме Перлина.

Вот наши 2 карты высот:

Фильтры карты высот

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

Идея применения фильтров будет вдохновлена ​​кривыми Photoshop. Мы будем использовать Кубические кривые Безье, чтобы определить функцию, которую мы применим к карте высот.

Вот несколько примеров фильтров:

Мы создадим и настроим фильтр для каждого биома.

Чтобы применить эти фильтры к нашей карте высот, мы будем использовать маски. Маска — это карта, содержащая 1 в областях определенного биома и 0 в других областях.

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

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

Окончательные результаты карты высот в 3D

Мы можем использовать Blender для рендеринга этих карт в 3D. Мы будем использовать карту высот в модификаторе смещения в Blender.

Реки и озера

Границы

Мы добавим реки между границами биомов. Во-первых, нам нужно рассчитать границы между биомами.

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

Применение этой техники к нашей карте биома дает следующие результаты.

Мы можем контролировать размер рек, изменяя размер блока, содержащего соседей.

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

Реки также будут ограничены средними и низкими высотами.

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

Вот сравнение речной маски с размытой и замаскированной речной маской.

Мы будем использовать эту карту, чтобы «вырезать» реки на карте высот.

Деревья и растительность

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

Мы будем генерировать наборы деревьев с разной плотностью в зависимости от биома.

Мы объединим набор деревьев с масками биома и маской земли, которые обсуждались ранее, чтобы заполнить биомы деревьями. Каждый биом имеет разную плотность и, конечно же, разные типы деревьев.

Мои навыки Blender не позволяют мне визуализировать карту в 3D с деревьями :(.

Исходный код

Вот блокнот Jupyter, содержащий все шаги в статье в коде.

Внимание! Код очень запутанный и недокументированный.

Заключение

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

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

Вдохновение

Я был вдохновлен многими статьями, когда писал свою. Если вам понравилась эта статья, то вы обязательно захотите прочитать и эти:

Вы также можете ознакомиться с моей предыдущей статьей Моделирование трафика в Python, в которой рассказывается, как процедурно генерировать данные о трафике.