Инь-Янь консолидация для процедурной генерации границ
Способ процедурной генерации граничного перехода от одной среды к другой, которые заданы на какой-либо регулярной решетке точек в квадрате или равностороннем треугольнике. Допускает обобщение на произвольные фигуры, а также на любые тайловые покрытия.
При генерации пространственных сред может возникать ситуация, когда требуется сделать границу двух или более сред, заданных на некотором упорядоченном множестве точек (решетке), причем, переход между ними должен быть постепенным. Эта «постепенность» может быть передана градиентным переходом, и тогда каждая точка решетки должна содержать величины, задающие пропорции сред. Или может быть предана способом, который мы рассмотрим в этом материале подробнее. В примерах здесь рассматриваем 2d среды, то есть только двумерные решетки.
Нас интересует способ, который создает у границ сред регионы со средами, в которые происходит переход, причем в самих этих регионах могут содержаться подрегионы с иными средами. В этом случае, в каждой точке решетки будет задана только одна среда. В принципе, возможна произвольная вложенность сред друг в друга, отсюда и название метода Инь-Янь консолидация. Обоснованность использования термина консолидация станет ясна позже.
Такой подход может, например, быть использован для процедурной генерации планетарных биомов, передавая земное поведение биомов при переходе от сплошного леса к сплошной степи и т. п.
Чтобы поиграться с кодом для генерации некоторых из приведённых здесь диаграмм, требуется Wolfram Mathematica. Бесплатный Wolfram Player может быть использован только для просмотра.
Также замечу, что здесь часто упоминаются методы создания фрактальных поверхностей. Эта тема сама по себе обширна и много где освещается. Поэтому я не буду останавливаться на ней в этой небольшой статье.
❯ Предварительные замечания
Распространённым является подход, основанный на генерации шума (noise mesh), заданного на решетке: можно считать, что величина шума задает третью координату и вместе с координатами точек решетки определяет некоторую поверхность в 3d пространстве. Таким шумом может быть, например, дробное Броуновское движение (fBm) или фрактал построенный методом срединного смещения (midpoint displacement). Далее, в зависимости от требуемого количества сред и их местоположения, строят одну или несколько разделяющих поверхностей. Значения на поверхностях сравнивают со значениями шума и на основании этого определяют среду в каждой точке решетки. Так, если сред только две, то достаточно одной разделяющей поверхности и, если значение шума в точке больше значения на разделяющей поверхности, то в этой точке будет первая среда, в противном случае будет вторая среда.
Манипулировать конечным результатом здесь можно тремя параметрами:
- Выбор вида шума (базисной функции для fBm) и выбор фрактальной размерности;
- Преобразование шума после его получения (постпроцессинг);
- Выбор разделяющих поверхностей.
К недостаткам этого метода можно отнести относительную сложность реализации, особенно для количества сред больше двух. Так же большинство известных алгоритмов для генерации шума работает только на квадратной решетке. При тайловой генерации на основе fBm шума требуется сохранять направления векторов на границе тайлов.
В предлагаемом ниже методе легко делать смешение четырех сред на квадратной решетке и трех на треугольной решетке. При тайловой генерации на границе тайлов требуется сохранять только значения сред: одно значение на точку, а соседние тайлы должны использовать эти значения и не менять их.
❯ Квадратный тайл
Начинаем с первоначального распределения точек. Строим произвольную разделяющую поверхность между горизонтальными плоскостями z=0 и z=1. Будем называть ее поверхностью, задающую начальное распределение. В примерах ниже поверхность везде задается функцией ArcTan (x), параметризованной таким образом, чтобы она принимала значение 0 и 1 на границах области определения, но функция может быть и любой другой.
Для присутствия трех или четырех сред требуется еще одна разделяющая поверхность, которая может быть задана функцией от оставшейся координаты y. Далее, в каждой точке решетки квадрата определяем случайную величину на отрезке [0,1]. Сравнивая эту величину со значениями разделяющих поверхностей, мы определяем значение среды s в этой точке. Для всего квадрата картина выглядит следующим образом.
Такого рода распределение может выглядеть череcчур хаотично. Поэтому попытаемся некоторым образом консолидировать отдельные точки (отсюда слово консолидация в названии метода). Для этого мы должны пробежать все точки квадрата и поменять их значения в зависимости от значений сред s1,…, sn в других точках квадрата, которые назовем родительскими (origin). Для данного примера используется обход точек как для метода срединного смещения создания фрактальной поверхности, только обход точек должен осуществляться в обратном порядке. При этом родительские точки располагаются на тех же местах. Значения в родительских точках комбинируются, и результирующее значение присваивается текущей точке решетки.
Процедура выбора родительских точек, на самом деле, может быть самой разной. Способ комбинирования значений в них называется функцией консолидацииf (s1,…, sn)→s.
В этом примере функция консолидации возвращает значение среды, которая чаще всего встречается в родительских точках. Процесс консолидации может быть повторен неограниченное количество раз, до тех пор, пока распределение точек нас не устроит. После еще одного повторения мы получим:
Выбранная функция консолидации хотя и обеспечивает постоянное «уплотнение» распределения, но имеет недостаток, а именно — появляются отдельно стоящие точки, выстраивающиеся в ряд. Если просто убрать такие точки, то можем получить следующее распределение:
Случай смешивания четырех сред показан в заголовке статьи.
❯ Недерминированный обход квадрата
В следующем примере попробуем поменять обход точек на случайный, то есть будем делать полную перестановку в списке точек для обхода при каждой итерации. Родительскими точками будем считать все непосредственно окружающие точки, а результат функции консолидации это наиболее часто встречающееся значение сред в родительских точках. Применяя данную процедуру консолидации, получим следующую последовательность результатов.
Как видим, распределение получилось сразу более «плотным».
❯ Треугольный тайл
Похожую процедуру можно осуществить и в равностороннем треугольнике. Применяем процесс консолидации и конце убираем отдельно стоящие точки сред.
❯ Обобщения и выводы
Манипулировать конечным результатом в приведенном методе можно следующими параметрами:
- Выбор поверхности задающей начальное «хаотическое» распределение;
- Метод обхода точек решетки;
- Выбор родительских точек;
- Выбор функции консолидации;
- Количество итераций.
Возможно задействование и бОльшего количества сред. Для этого потребуется, чтобы была величина определенная в каждой точке решетки, например, заданная какой-либо функцией h (x, y)→t. Тогда имея еще одну функцию g (s, t)→s, возвращающую значение некоторой среды, можно с помощью композиции g (s, h (x, y))→s получить новое значение среды в точке (x, y) имеющей первоначальную среду s в этой точке (например, ту, что получается в результате начального «хаотического» распределения).
Процесс консолидации можно использовать на распределении имеющем произвольное количество сред. Ко всему прочему, консолидировать можно и распределения полученные другими способами как, например, выше упомянутым способом fBm шума.
На практике с биомами это может использоваться для получения изменений биомов с высотой. Здесь в соответствующей функции g (s, t) первый аргумент — это значение биома расположенного на уровне моря, а вторым аргументом служит высота над уровнем моря.
Еще одно важное свойство, — это возможность делать консолидацию не в «правильной» фигуре. И действительно, нигде в описании метода правильность фигуры не подразумевается, а только существование регулярной решетки в ней. Более того, фигура может быть вообще произвольной формы, нужно только чтобы выбор родительских точек был корректно определен для всех точек при их обходе.
Количество итерациий тоже влияет на результат. Обычно можно ожидать, что чем их больше, тем более «плотное» распределение получится, но это не общее правило.
И здесь еще одно обобщение — дробная консолидация, когда на последней итерации проходится только некоторая доля точек фигуры. Таким образом, количество итераций — это рациональное число.
Возможно, захочется почитать и это:
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩
