Недавно я посмотрел видео Себастьяна Лаге о симуляции эрозии, но в его решении генерируется двухмерная карта высот. В то же время я играл в Satisfactory, наслаждаясь красивым рельефом, однако этот рельеф был тщательно спроектирован вручную. Можно ли сгенерировать подобный разнообразный рельеф процедурно? Я решил попробовать.

Скриншот красивого рельефа Satisfactory.

Первая попытка

Я хотел реализовать систему с возможностью генерации нависающих скал и пещер, вероятно, даже красивых арок из Satisfactory. Следовательно, двухмерной карты высот мне будет недостаточно. Поэтому вместо неё я решил использовать 3D-сетку, каждая ячейка которой является числом от 0 до 1, представляющим объём осадочного материала в данном кубе. После генерации сетки результат должен рендериться при помощи marching cubes.

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


Результат работы алгоритма 1: по крайней мере, недостатка в выступах нет.

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

Алгоритм 2

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

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

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


Рельеф, сгенерированный алгоритмом 2. Синяя линия — это дождевая капля. Цветами обозначена разная твёрдость.

Изменения оправдали себя. Теперь рельеф намного плавнее и более плоский. Однако при этом он стал скучным. В нём больше нет никаких интересных особенностей наподобие пещер. Нет крутых склонов гор. Мы даже не можем чётко увидеть путь движения воды. Возникла пара столовых гор, то есть 3D-природа алгоритма проявляется. Мне необходимо найти баланс между реализмом и интересностью.

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

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

Алгоритм 3

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

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


Результат алгоритма 3, на этот раз цветом обозначена крутизна склонов.

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

Окончательный алгоритм

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

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

Также я добавил деревья, цветы и траву, чтобы всё выглядело немного интереснее:


Рельеф с деревьями и травой.

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

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

Дальнейшие дополнения

Хотя меня вполне устраивает результат, если рельеф действительно будут использовать в игре, то требуется дополнительная работа.

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

Главное преимущество Satisfactory заключается в том, что все отдельные биомы имеют радикально отличающуюся геометрию. Требуются равнины, горы, острова, пустыни, болота и многое другое. Поэтому генератор должен быть настраиваемым, чтобы можно было генерировать множество уникальных типов рельефа. Эти разные типы должны иметь возможность плавного соединения. Разумеется, при этом водораздел и реки могут проходить через множество типов рельефа.

Несмотря на усовершествования в версии алгоритма 4, край карты по-прежнему уродлив. На данный момент я моделирую край как отвесную скалу бесконечной глубины, но это ли нам нужно? Возможно, лучше считать участок островом, окружённым океаном. При этом вода будет падать не ниже уровня моря. Возможно, даже получится симулировать эрозию, создаваемую волнами, чтобы получить реалистичные побережья и лагуны.

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