Процедурная генерация

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


Рисунок 1: небольшой водопад.

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

• Результаты должны выглядеть естественными.
• Алгоритм должен быть простым.
• Алгоритм должен быть быстрым.
• Алгоритм должен симулировать гидравлическую эрозию, вызываемую осадками и реками.

Различные подходы

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

• Эрозия симулируется отслеживанием местонахождения воды для каждой позиции на рельефе. Для окружения создаётся сетка (или 2D-массив), в котором для каждой ячейки хранятся уровни воды и давления. При обновлении давления определяют, куда будет течь вода. В процессе течения вода перемещает осадочные породы.
• Эрозия симулируется бросанием на рельеф множества частиц, имитирующих капли дождя. Затем частицы перемещаются по склонам рельефа. Они могут переносить с собой осадочные породы или отлагать их.

Рисунок 2: остров после выполнения симуляции эрозии.

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

Снежки

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

Ниже представлен полный алгоритм эрозии (на Javascript). В этом коде для выполнения эрозии используется объект heightMap. Эту карту высот можно считывать и выполнять в неё запись, а функцию sampleNormal можно применять для получения нормали поверхности. Это 3D-вектор, указывающий вверх перпендикулярно рельефу, поэтому его можно использовать для определения направления и крутизны склона.

/** * Let a snowball erode the height map * @param {Number} x The X coordinate to start at * @param {Number} y The Y coordinate to start at */trace = function(x, y) {  const ox = (random.getFloat() * 2 - 1) * radius; // The X offset  const oy = (random.getFloat() * 2 - 1) * radius; // The Y offset  let sediment = 0; // The amount of carried sediment  let xp = x; // The previous X position  let yp = y; // The previous Y position  let vx = 0; // The horizontal velocity  let vy = 0; // The vertical velocity  for (let i = 0; i < maxIterations; ++i) {    // Get the surface normal of the terrain at the current location    const surfaceNormal = heightMap.sampleNormal(x + ox, y + oy);    // If the terrain is flat, stop simulating, the snowball cannot roll any further    if (surfaceNormal.y === 1)      break;    // Calculate the deposition and erosion rate    const deposit = sediment * depositionRate * surfaceNormal.y;    const erosion = erosionRate * (1 - surfaceNormal.y) * Math.min(1, i * iterationScale);    // Change the sediment on the place this snowball came from    heightMap.change(xp, yp, deposit - erosion);    sediment += erosion - deposit;    vx = friction * vx + surfaceNormal.x * speed;    vy = friction * vy + surfaceNormal.z * speed;    xp = x;    yp = y;    x += vx;    y += vy;  }};// Simulate 50000 snowballsconst snowballs = 50000;for (let i = 0; i < snowballs; ++i)  trace(    random.getFloat() * width,    random.getFloat() * height);// Blur the height map to smooth out the effectsheightMap.blur();

У алгоритма есть несколько примечательных свойств:

• Переменные ox и oy кодируют смещение снежка. Они используются для считывания склона рельефа с определённым смещением, чтобы сделать движение снежка чуть более грубым, позволяя снизить схождение путей снежков.
• Когда нормаль поверхности указывает ровно вверх (то есть когда значение y этой нормали равно единице), снежок останавливается. На практике это означает, что снежок достиг края симулируемой площади или морского дна, где симуляция завершается. Так как в этих областях ничего не происходит, симуляция эрозии там будет пустой тратой вычислительной мощи.
• При изменении величины осадочных пород снежок изменяет карту высот в своей предыдущей позиции, а не в текущей. Эрозия и отложение происходят в предыдущей позиции, чтобы снежки не закапывались в рельеф.
• После завершения симуляции эрозии к карте высот применяется размытие по Гауссу. Так как карта высот в этих примерах имеет низкое разрешение, требуется размытие, чтобы поверхности оставались визуально гладкими.

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

Результаты

Рисунок 3: результаты алгоритма эрозии.

После применения описанного выше алгоритма с различным количеством снежков мы получаем результаты, отрендеренные на рисунке 3. Алгоритм работает в браузере, а его исходный код можно найти на GitHub. При нажатии на пробел генерируется новый остров. Начальный материал для симуляции показан на первом изображении рисунка 3. Форма острова сгенерирована при помощи алгоритма, очень похожего на тот, который я использовал в примерах рельефа для послойного рендеринга вокселей. Хотя форма имеет отдельные детали и хребты, она очень гладкая и не содержит следов гидравлической эрозии.

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

На третьем изображении показан тот же остров после падения 50 000 снежков. По сравнению с предыдущим изображением не образовалось никаких новых деталей, хотя особенности рельефа стали более выраженными.

На последнем изображении показан остров после падения 100 000 снежков. Очевидно, что этого слишком много: хребты становятся очень глубокими, а побережье очень неровным. Кроме того, результаты выглядят менее реалистично. Долины вырезают очень резкие особенности рельефа, которые самостоятельно уничтожатся вследствие эрозии.

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

Заключение

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

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

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

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

Приложение: рендеринг прибрежных волн

Рисунок 4: рендеринг прибрежных волн.

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

На рисунке 4 этапы создания анимации волн:

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

Эта анимация демонстрирует этапы рисунка 4 в реальном времени.

Binding of Isaac и её ремейк Binding Of Isaac: Rebirth одни из самых любимых для меня игр. Они относятся к жанру roguelite twin stick shooter и очень похожи на Enter the Gungeon.

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

Хоть мне и пришлось провести декомпиляцию, а также освежить свои покрывшиеся пылью знания о Flash (когда-то я написал собственный декомпилятор Actionscript), мне ещё и очень повезло: разработчик Isaac Флориан Химсл и один из основных разработчиков Rebirth Саймон Парзер с радостью ответили на мои вопросы. На самом деле, Флориан даже недавно записал видео с описанием алгоритма. На его канале можно также узнать подробности разработки его новой игры Squid Invaders.

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

Базовый алгоритм

Разработчики Isaac активно вдохновлялись играми серии Zelda в 2D и генерировали карты, похожие на их подземелья.


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

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

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

План этажа

Isaac генерируется на сетке размером 98. Для удобства ячейки обозначаются числами единицами обозначают позицию по X, десятками позицию по Y. Это означает, что можно двигаться вверх, вниз, влево и вправо, просто прибавляя +10, -10, +1 и -1. Ячейки с позицией по X, равной 0, не используются (всегда пусты), и это значит, что большей части кода не нужно беспокоиться о границах карты. То есть верхняя левая ячейка карты имеет обозначение 01, а нижняя правая 79.

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

Сначала по формуле random(2) + 5 + level * 2.6 определяется количество комнат. Т.е. уровни начинаются с 7 или 8 комнат, и каждый раз увеличиваются на 2 или 3 комнаты.

Затем игра помещает начальную комнату (ячейка 35) в очередь. Далее она циклически обходит очередь. Для каждой ячейки в очереди она циклически обходит 4 основных направления и делает следующее:

• Определяет соседнюю ячейку, прибавляя к текущей ячейке +10/-10/+1/-1.
• Если соседняя ячейка уже занята, то игра ничего не делает.
• Если сама соседняя ячейка имеет более одного заполненного соседа, то игра ничего не делает.
• Если на уровне уже достаточно комнат, игра ничего не делает.
• Игра ничего не делает с вероятностью в 50%.
• В противном случае игра помечает соседнюю ячейку как содержащую комнату, и добавляет её в очередь.

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

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

Так как описанный выше алгоритм начинается с единственной комнаты и многократно расширяется наружу, он, по сути, является исследованием в ширину (breadth first exploration). Ограничение, не позволяющее добавить комнату, если уже есть два соседа, разделяет комнаты на отдельные коридоры, которые никогда не объединяются в петли.

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

Особые комнаты

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

Затем указывается положение секретной комнаты. Эти комнаты добавляются в план этажа; они являются одними из немногих исключений из правила, запрещающего располагать комнаты рядом с несколькими уже существующими. На самом деле, алгоритм наоборот, предпочитает их размещать их так. Генератор случайным образом ищет пустую ячейку, находящуюся рядом с не менее чем тремя комнатами и не рядом с любой из конечных комнат. Если он не находит её спустя 300 попыток, то слегка ослабляет критерий поиска, а после 600 попыток ослабляет его ещё больше. Эта процедура гарантирует, что секретная комната всегда будет размещена на уровне, но обычно они зажаты рядом с перекрёстками, то есть рядом с ними всегда много комнат.

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

Обычные комнаты

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

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

Для обычных комнат существует три пула: лёгкий, средний и сложный. Первый этап главы выбирает из простых и средних комнат, а второй из средних и сложных. Первая глава (Basement) содержит в пулах 174 обычных комнат. Альтернативные главы, например, Cellar, которая случайным образом может заменить Basement, имеют немного отличающийся набор комнат.

Проклятие лабиринта

Одна из самых интересных дополнительных особенностей кода это карты двойного размера. Они создаются случайно и только для некоторых режимов испытаний. Кроме очевидного удвоения количества особых комнат и двух соседних комнат с боссами они имеют и множество мелких деталей:

• На 80% больше обычных комнат (максимум 45)
• Для особых комнат используются только 6 дальних конечных комнат
• Уровни выбирают комнаты из пулов простых, средних и сложных комнат.
• В план этажа случайно добавляются дополнительные обычные комнаты с логикой размещения, как у секретных комнат.

Демо

Я создал на Javascript упрощённый пример генератора, чтобы можно было с ним поэкспериментировать. Полный код можно найти здесь, а работающий пример в оригинале статьи.

Rebirth

Binding of Isaac: Rebirth это ремейк оригинального Binding of Isaac, созданный компанией Nicalis, которая в то время была известна своими портами VVVVV и Cave Story. Игру портировали на C++ и переделали все звуки и графику. За годы существования игра получила множество DLC, добавивших новых предметов и врагов к и так уже достаточно впечатляющему списку оригинала.

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


С полным набором DLC (на момент написания статьи это Afterbirth+) в игре есть 11 больших комнат: 22, 21, L-образные и узкие коридоры в разных вариантах поворота.


Типичная L-образная комната, в три раза больше обычной комнаты. Она была реализована Саймоном Парзером благодаря аккуратной модификации исходного кода Химсла.

Вместо обхода в цикле всех направлений алгоритм обходит все выходы из комнаты. В комнате размером 22 их может быть до восьми.

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

Если для комнаты не хватает пространства, то алгоритм пытается вставить другого кандидата. При успешной вставке больших комнат есть вероятность 95%, что они будут удалены из пула.

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

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


В Isaac пропасти обычно пересекать невозможно

Вывод

Генератор уровней Isaac не самый сложный из тех, которые я видел, но несмотря на такой малый объём кода, работает он невероятно хорошо. Вероятно, именно поэтому его так часто пытаются воссоздать. Его простота позволяет вносить изменения и расширения, и мы видим это на примере Rebirth. Невероятный результат.

Также можно заметить, что эта игра продолжает тенденцию, в соответствии с которой план этажа генерируется отдельно от деталей комнаты. В своих статьях о Diablo 1 [перевод на Хабре] и Enter the Gungeon [перевод на Хабре] я говорил, почему такой подход может быть очень мощным.

При декомпиляции кода я не нашёл каких-то особо интересных подробностей. Самое интересное, о чём я могу сказать расположение комнаты сокровищ хранится в переменной с именем boner вероятно, сокращение от Bonus Room. Также в коде присутствуют тонкости относительно незначительных побочных эффектов различных предметов, но эту тему я оставлю анализаторам.

Далее вы можете посмотреть серию видео Химсла о внутреннем устройстве игры или даже сыграть в Isaac и увидеть все уровни вживую. Я слышал, что новый DLC Repentance выйдет в этом году. Также я рекомендую сыграть в другие игры главного дизайнера Эдмунда Макмиллена (особенно в Super Meat Boy).