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

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

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

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

Плюсы:

Минусы:

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

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

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

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

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

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

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

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

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

Плюсы:

Минусы:

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

Плюсы:

Минусы:

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

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

Плюсы:

Минусы:

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

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

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

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

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

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

Плюсы:

Минусы:

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

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

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

ЗАКЛЮЧЕНИЕ

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

#процедурнаягенерация