Как генерируются миры — описание подходов для создания процедурных локаций в играх

Краткое знакомство с алгоритмом планирования, а также с симуляционным и функциональным подходами.

Инди-разработчик Руне Сковбо Йохансен в 2015 году опубликовал в своём блоге подробное описание разных подходов к процедурной генерации окружения в играх. Автор рассказал, чем друг от друга отличаются симуляционный и функциональный подходы, а также алгоритм планирования. Мы выбрали из текста главное.

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

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

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

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

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

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

Для игр с псевдо-бесконечным миром, таких как Minecraft и No Man's Sky, важно отсутствие зависимостей от соседних точек — по крайней мере, для генерации ландшафта. Поскольку мир генерируется кусками на лету, у конкретной точки может не быть нужных соседей, так как они ещё не сгенерированы.

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

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

В Minecraft, например, рельеф вычисляется при помощи функционального метода. А освещение затем симулируется в соответствии с имеющейся контекстной информацией о геометрии мира.

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

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

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

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

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

Чаще всего алгоритм планирования применяется для подземелий, а не для игр с псевдо-бесконечными мирами. Но и это возможно: для этого потребуется алгоритм планирования, который умеет работать с большими масштабами — он нужен для создания общего дизайна мира. Затем остальные алгоритмы создадут отдельные части окружения, которые соединятся вместе.

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

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

#опыт #левелдизайн