Процедурная генерация и с чем ее едят

Закончив становление магистром, наконец мои руки дошли до старой и так любимой мною темы - процедурная генерация. В данном материале я постараюсь рассмотреть возможные варианты процедурной генерации ландшафтов, ну или по простому - “Как создать карту для моей игры, и чтобы каждый раз было что-то новое”. Рассмотрим начальные вещи используемые для процедурной генерации, как их реализовывать и как они работают. Ну, начнем.

Может сгенерироваться что-то подобное
Может сгенерироваться что-то подобное

АЛГОРИТМЫ-АЛКОРИТМЫ

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

КЛЕТОЧНЫЕ АВТОМАТЫ. Муравей Лэнгтона

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

Плюсы:

  • Простота разработки
  • Легкость изменения (написание своих правил)

Минусы:

  • Скорость работы
  • Различные артефакты
  • Сложно реализуемая высота
  • Похожесть

Из всех существующих алгоритмов, больше всего подходит Муравей Лэнгтона и его модификации. Принцип работы прост:

  • Муравей делает шаг
  • Проверяет метку клетки и инвертирует ее
  • В зависимости от цвета делает поворот влево или вправо

Различные модификации изменяют лишь действия движения после определения метки. Также возможно изменить метку, добавив вариативность ( условно вместо 0 и 1, будет 0, 1, … , n , где n - любое целое число). Получаемые ландшафты после использования муравья имеют некоторые недостатки, которые можно легко решить.

Карта построенная муравьем Лэнгтона.
Карта построенная муравьем Лэнгтона.

Как можно заметить, внутри сгенерированной области полно пустых клеток. Данная проблема решается использованием дополнительной сетки, значения которой не инвертируются в обратную сторону, т.е. 0 переходит в 1 , но 1 не может перейти в 0. Либо же это решается морфологическими операциями компьютерного зрения: наращиванием и сжатием ( dilation and erosion).

НАРАЩИВАНИЕ И СЖАТИЕ

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

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

Применение операции Erosion.
Применение операции Erosion.

Dilation - операция наращивания. В алгоритме также как и в случае сжатия используется заданная маска. Проверяется каждая точка, и если она является активной (в случае клеточного автомата это 1), то точки, которые покрывает маска, становятся активными.

Применение операции Dilation.
Применение операции Dilation.

В обоих случаях использовалась маска:

[[ 1, 1, 1],
[ 1, 1, 1],
[ 1, 1, 1]].

АЛГОРИТМ РАЗРАСТАНИЯ

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

Плюсы:

  • Простота разработки
  • Легкость изменения

Минусы:

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

УМНЫЕ КЛЕТКИ

Умные клетки или произвольное разрастание. Алгоритм который написал я сам (может кто-то еще такое писал, но я не искал, и писал опираясь на клеточные автоматы). Данный алгоритм создает клетку “организма”, объект который может передвигаться во все стороны с приоритетом в нахождении клеток “пищи”. Такие клетки, совершая свои шаги, строят путь, помечая каждую клетку как пройденную. При перемещении на клетку пищи, создается еще один “организм”, который совершает аналогичные действия. Стартовой расположение “организмов” и “еды” выбирается случайно.

Плюсы:

  • Простота разработки
  • Легкость изменения

Минусы:

  • Скорость работы
  • Сложно реализуемая высота
  • Похожесть

ДИАГРАММА ВОРОНОГО

Диаграмма Вороного или же Мозаика Вороного, алгоритм построения многоугольных зон. На мой взгляд самый оптимальный способ реализации Мозаики Вороного это алгоритм Форчуна. Подробный разбор этого алгоритма лучше описать в отдельной статье, так что если понравится, могу взяться и за это. Коротко же алгоритм случайно расставляет точки. Затем создается движущаяся прямая, которая по достижению точки создает перпендикулярную прямую к ней, которая затем превращается в растущую параболу. Сама парабола заканчивает свой рост, когда сталкивается с другой подобной параболой.

Созданная диаграмма Вороного.
Созданная диаграмма Вороного.

Также существует алгоритм релаксации Ллойда, которые усредняет ячейки Вороного.

Плюсы:

  • Легкость настройки
  • Интересные зоны

Минусы:

  • Сложно реализуемая высота
  • Невозможно использовать сразу без дополнительных изменений

ШУМЫ

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

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

  • Задать случайные единичные градиенты (направление роста)
  • Вычислить скалярные произведения
  • Интерполировать(сгладить) полученные скаляры
Созданный шум классический Перлина.
Созданный шум классический Перлина.

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

А вот тут уже моя магия сделала работу
А вот тут уже моя магия сделала работу

Симплекс шум является более гладким вариантом Шума Перлина.

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

  • Задать векторные градиенты (направление роста) в узлах решетки
  • Разбить пространство на сетку симплексов (n-мерные треугольники)
  • Вычислить скалярное произведение между углом симплекса и вектором
  • Интерполировать (сгладить) функции затухания скалярных произведений
Симплекс шум, тоже Перлина.
Симплекс шум, тоже Перлина.

Ну а вот полученные результаты генераций, цвета клетки зависит от ее значения.

Плюсы:

  • Разнообразие
  • Сгенерированные высоты
  • Скорость (по сравнению со многими клеточными автоматами)

Минусы:

  • Средняя сложность создания

ВЫСОТЫ И РЕГИОНЫ

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

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

Реки это важно!

Небольшое дополнение от меня. Чтобы получившиеся карты были немного естественнее, я добавил реки. Для их построения использовался слегка модифицированный алгоритм А*. Выбиралась случайная точка из которой строился наикратчайший путь к ближайшей воде. Если вы хотите упростить, то можно создать отдельный граф, вершины которых пометить как высоту точки нахождения, и после этого по данному графу строить реки. Но тогда будьте готовы, что ваши реки будут идти вверх по скале. Если для расширения рек вы решите использовать симуляцию эрозии почвы, будьте готовы к тому, что появятся различные артефакты, которые будут выглядеть не очень приемлемо. Чтобы их устранить можно использовать описанные выше методы Erosion и Dilation. Для улучшения построения рек можно модифицировать обычный алгоритм А*, добавив начальный запас воды, который будет тратиться на каждый шаг подъема. Таким образом будут появляться небольшие озерца, перед тем как река снова продолжит течение вниз.

ЗАКЛЮЧЕНИЕ

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

143143
31 комментарий
333 ₽

Нужно больше статей про разработку.

6
Ответить

Посмотри как работает процедурка в Дварф Фортресс. Она не стремится сгенерировать ландшафт за один проход. А генеррует его "послойно"

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

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

Чем больше сущностей тем лучше контроль над финальным результатом и более "естественный" вид будет иметь

9
Ответить

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

3
Ответить

Комментарий недоступен

7
Ответить

В Ноу Мэнс Скае планеты с тропическим и райскими биомами часто так и выглядят с высоты.

4
Ответить

И это отвратительно. Шцм перлина имеет очень узнаваемый визуальный шаблон.

6
Ответить