Быстрое и плавное смешение биомов игровой карты

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

Определяемся с нужным результатом

Для реализации эффективного смешения биомов нам необходимо создать для каждой точки мира определённые данные. Чтобы смешение можно было использовать во множестве различных ситуаций, я решил создать значения весов, соответствующие влиянию каждого биома на конкретную координату. Например, где-то внутри переходной зоны между двумя биомами алгоритм смешения может выдавать на выходе веса {Forest: 0.6, Plains: 0.4}. Если наша цель заключается в вычислении веса рельефа, то мы можем сложить взвешенные высоты биомов следующим образом: Forest.GetHeight(...) * 0.6 + Plains.GetHeight(...) * 0.4. Также можно будет реализовать слияние трёх (или более) биомов в углах: {Forest: 0.55, Plains: 0.24, Mountains: 0.21}, или находиться целиком внутри одного биома: {Plains: 1.0}.

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


Плавный переход между двумя биомами


Переход со скачком и границей


Переход в месте, где сумма весов не равна единице

Существует множество способов форматирования данных, передающих одинаковую информацию. Я опишу выбранный мной формат ниже.

Способы и проблемы

Простой алгоритм смешения может состоять из генерации карты биома в полном разрешении и в выполнении размытия (например, гауссова) для создания весов смешения. Для этого можно начать с того, что заполнить достаточно большую поверхность карты генерируемого мира. Если мир генерируется частями или фрагментами, то здесь можно использовать кэширование, чтобы не генерировать много раз одни и те же области. После этого нужно взять окружность вокруг каждого столбца или координаты пикселя, для которой генерируется рельеф. На карте биома это будет выглядеть так, как будто мы собираемся считать количество ячеек каждого биома, попавших внутрь окружности. Но мы будем не прибавлять каждый раз, а добавлять число, уменьшающееся с увеличением расстояния. Для этого можно использовать формулу max(0, radius^2 - dx^2 - dy^2)^2. Она создаёт круглый «холм», как в фильтре Гаусса, но с приближением к конечному радиусу он плавно снижается до нуля. Чтобы сумма весов биомов была равна единице, каждое из значений нужно умножить на величину, обратную итоговой сумме. Так как итоговая сумма является константой, обратную величину можно вычислить заранее.

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


Веса смешения биомов относительно центральной точки

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

Некоторые генераторы обходят эту проблему, генерируя всё на сетке меньшего разрешения, а затем выполняя интерполяцию между пробелами. Это решает проблему скорости, но не позволяет создавать на границах никакого углового разнообразия ниже масштаба сетки. Границы становятся привязанными к краям сетки, потому что у нас есть данные только для её углов. Кроме того, если используется только простая линейная интерполяция (lerp), это создаёт регулярно повторяющиеся границы. Такие проблемы становятся особенно заметны, когда границы пытаются передать детали, для которых сетка имеет слишком низкое разрешение. Minecraft является примером использования такой стратегии. Я планирую написать серию статей, в которой предложу и реализую усовершенствования многих техник, которые используются в Minecraft. А пока я буду рассматривать тему смешения биомов отдельно, вне связи с какой-либо конкретной игрой.


Пример линейной интерполяции в увеличенном масштабе


Граница в Mineraft, из-за интерполяции демонстрирующая повороты в форме сетки

Решаем обе проблемы

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

В своём решении я заменил сетку случайно распределёнными точками данных. Затем я выполнил смешение между точками при помощи нормализованной разреженной свёртки.

Распределяем точки

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


Сетка без флуктуаций


Направления векторов флуктуации


Подвергнутые флуктуации точки

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


Базовый радиус без дополнения в наихудшем случае


Радиус с дополнением той же области

Находим точки

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


Шестиугольные слои поиска

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


layerSearchBound = (r*f + m + j)/d


Окружность, содержащая фрагмент. Формула получает вид ((r + r_c)*f + m + j)/d

Нормализованная разреженная свёртка

Каждая точка с флуктуацией выполняет сэмплирование биома в своём местоположении. Чтобы сгенерировать по этим данным смешение, используется процесс, похожий на описанное выше размытие по Гауссу. Сначала формула задаёт вес, который каждая точка данных должна внести в соответствующий биом. Здесь я снова использую max(0, radius^2 - dx^2 - dy^2)^2. Однако поскольку новые точки распределены так, что их мало и они далеко друг от друга, общий вес на координату становится очень непоследовательным. Чтобы скорректировать это, необходимо вычислять итоговую сумму и обратное ей значение динамически, а потом умножать на него веса. После использования этапа нормализации результат снова будет соответствовать требованию к сумме.


Итоговый вес до нормализации: ~10,2 млрд


Общий вес до нормализации: ~681 млн

Результаты

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

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


r_p=16, f=0.04


r_p=16, f=0.08


r_p=32, f=0.04


r_p=32, f=0.08

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

Сравнение

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

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


Несплошное смешение, r_p≈11.6, f≈0.095; исходное изображение


Простое смешение; r=24; исходное изображение


Смешение на сетке с Lerp; r=24, interval=8; исходное изображение


Свёрточное смешение на сетке; r=24, interval=8; исходное изображение

Как и ожидалось, простое смешение (в полном разрешении) создаёт самые плавные результаты. Несплошное смешение добавляет неотъемлемый аспект шума на границах, однако важно, что он не вносит заметного углового искажения. Сетка с lerp имеет самые заметные паттерны сетки. Свёрточное смешение на сетке создаёт плавные результаты, однако кривые притягиваются к направлениям сетки.

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


Смешение на сетке с Lerp; r=24, interval=4; исходное изображение


Свёрточное смешение на сетке; r=24, interval=4; исходное изображение


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

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

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

Пример карты высот

Рендеринг цветов со смешением может быть полезным сам по себе, но он не демонстрирует нам, как это будет выглядеть на реальном рельефе. Я назначил каждому биому собственную формулу карты высот на основе шума OpenSimplex2S, а затем выполнил смешение между ними при помощи системы разреженного смешивателя биомов.


Карта биомов со смешением в качестве примера карт высот (r_p=32, f=0.04)


Карта высот, сгенерированная смешением карт высот биомов


Карта высот, отрендеренная в 3D-режиме WorldPainter

Производительность

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


Исходный бенчмарк. Размер фрагментов 16x16. Указано время исполнения в наносекундах на координату.

Это уже демонстрирует чёткие различия между временем исполнения каждого из случаев. Однако есть очень простая оптимизация, которая позволяет улучшить ситуацию.

Оптимизация

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


Фрагменты, которые не подвергаются смешению, затемнены.

Вот обновлённые метрики производительности. Ради честности измерений я добавил оптимизацию во всех четырёх случаях.


Оптимизированные системы. Размер фрагментов 16x16. Указано время исполнения в наносекундах на координату.

Применение этой оптимизации обеспечивает рост производительности в случае разреженной системы до 36%. Системы полного разрешения и сетки со свёрткой имеют чуть меньший рост (максимум ~29% и ~34%), а сетка с lerp демонстрирует наименьший рост (максимум ~14%).

При таких значениях параметров разреженное смешение не так быстро, как сетка со свёрткой или сетка с lerp. Однако оно гораздо быстрее смешения в полном разрешении («простого» смешения). Эта разница становится особенно заметной при использовании низких частот сэмплирования точек — эта опция недоступна для простого случая смешения.

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

Система с линейной интерполяцией всегда самая быстрая. Однако её артефакты сетки настолько заметны, что скорость не оправдывает её использования. Можно попробовать интервал сетки 2, что выглядит намного лучше, чем 4, но это увеличивает показанное выше время исполнения до 594,905 (r=24) и 2025,882 (r=48). Такие результаты легко превзойти при разреженном смешении.

Размер фрагментов

Представленные выше метрики сгенерированы с фрагментами размером 16x16. Если увеличить их до 32x32, то производительность меняется следующим образом:


Оптимизированные системы. Размер фрагментов 32x32. Указано время исполнения в наносекундах на координату.

Любопытно, что lerp выполняется чуть быстрее, а другие системы проявили себя чуть хуже. Размер фрагмента может и не зависеть от пользователя, но он имеет влияние. Я точно не знаю, можно ли это связать с более удобным использованием кэша, запросами точек, распределением памяти и т.д.

Последние примечания о производительности

Так как генерация выполняется только в 2D, а в генерации рельефа могут присутствовать и другие этапы (например, 3D-шум, расстановка объектов), то стоит рассмотреть это в контексте производительности всего генератора. Если вы не сможете усовершенствовать похожим образом другие части генератора, то процентные улучшения отдельных частей могут привести к искажению картины общего процентного ускорения. Разреженное смешение не такое быстрое, как lerp, но оно намного быстрее, чем смешение с полным разрешением. Кроме того, оно больше соответствует времени исполнения обычных формул карт высот, состоящих из множества вычислений шума по ~20-100 нс каждое (на моей машине), и уже быстрее того, чего можно ожидать от оптимизированных 3D-карт шума (полного расширения).

Шумные границы (плохо это или хорошо)

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

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


Вывод функции обратного вызова


Разреженное смешение


Заново пересчитанная карта биомов

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

Обобщённость методики

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

• Размещение структур или объектов
• Неравномерная интерполяция
• Имитация эрозии
• Сам шум Вороного
• Другой шум, использующий распределённые точки

Дальнейшая разработка

Я рассказал о многих аспектах, возникающих при использовании такого смешения. Однако ради краткости я и не упомянул о множестве других аспектов. Возможно, я исследую их в будущем.

• Генерация карты с настраиваемыми биомами
• Подстройка результата под границы высот биомов (например, суши/воды на уровне моря)
• Предотвращение пересечения границ биомов на побережьях
• Переменная ширина смешения
• Другие способы интерполяции сетки, кроме lerp
• Быстрая линейная интерполяция на сетке с флуктуацией
• Сравнение внешнего вида и производительности сетки квадратов с флуктуациями
• Смешение сетки треугольников без флуктуаций
• Обобщение системы до 3D

Код

Код выложен в следующий репозиторий: KdotJPG/Scattered-Biome-Blender.

Смешение выполняется в классе ScatteredBiomeBlender. ScatteredBiomeBlender генерирует всё смешение для запрошенного фрагмента и выводит его в структуре данных наподобие связанного списка. Каждый узел обозначает конкретный биом и перечисляет веса координат каждого фрагмента в массиве. Также он содержит ссылку на следующий элемент, если он является последним, то значение равно null. В этом формате объём данных растёт пропорционально количеству биомов; кроме того, он позволяет не создавать отдельные экземпляры для каждой координаты.

Использование ScatteredBiomeBlender заключается в хранении экземпляра, который применяется вызовом генерации каждого фрагмента и в итерациях по возвращаемым им узлам LinkedBiomeWeightMap. Он спроектирован специально для работы квадратными фрагментами и квадратными пикселями/вокселями, но может быть реализован и для других форм на тех же принципах.

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

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

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