Шум Перлина: математика и генерация мира No Man's Sky

Формулы, октавы и производные.

На конференции GDC 2017 выступил Шон Мюррей (Sean Murray), создатель No Man's Sky — игры c процедурной генерацией контента. Он рассказал, как это работает на конкретных математических примерах.

​DTF публикует пересказ выступления.

Мюррей начинал в студии Criterion, сейчас принадлежащей EA. Тогда она славилась своими движками и технологиями. В основном Мюррей писал код. Потом он трудился над Burnout Paradise и Black, получившими (особенно за графику) хорошие отзывы.

Отдельно стоит упомянуть, что Мюррей участвовал в создании движка Renderware — он использовался в GTA, Call of Duty, Bully и других проектах. Разработчик даже оставил в них что-то вроде «авторской подписи»: баг, из-за которого у персонажей при определённых условиях отваливались руки.

По мнению Шона, движок игры определяет её дизайн. Сам выбор «мотора» — первый шаг в геймдизайне. К началу разработки No Man’s Sky Мюррей успел поучаствовать в создании семи игровых движков, так что и для неё решил сделать собственный.

Поначалу работа над No Man’s Sky была для него просто увлечением. Но существовавшие игровые движки казались слишком скучными, и он захотел сделать нечто принципиально новое.

No Man’s Sky перестала быть хобби после выхода первого трейлера. На момент выпуска видео игра настолько отличалась от всего, что было на рынке, что разработчикам было негде искать примеры решения проблем.

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

В No Man’s Sky нельзя ничего «запечь» или рассчитать заранее. Простой пример: в любой другой игре, чтобы поставить маркер на крышу здания, достаточно расположить на карте строение, создать маркер и переместить его. А в No Man’s Sky движок должен учитывать изгиб планеты, иначе здание может оказаться под землёй или на другом её конце. Затем нужно разместить маркер на горизонте, потому что иначе его не будет видно. При этом ось Y не обозначает «высоту», поскольку планета — это реальный физический объект, так что нужно высчитывать тангенсы и касательные, а также расстояние до полюса планеты.

Итак, маркер на нужной высоте. Но что, если его нужно поставить на другую планету? Или, что ещё хуже, на её обратную сторону? А если между планетой игрока и планетой с маркером окажется ещё одна? Маркер должен всегда быть на горизонте и менять своё положение с изменением точки обзора.

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

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

Но Мюррею нравится работать со всеми этими проблемами. No Man’s Sky стала идеальным полем экспериментов для человека, которому наскучила стандартная разработка движков.

No Man’s Sky — одновременно большая и маленькая игра. Во время релиза объём билда, скачиваемого в Steam, составлял всего два гигабайта, полтора из которых ушло на аудиоматериалы. Движок, отвечающий за весь мир игры, «весил» примерно 300 мегабайт. Отчасти из-за низкого объёма исходных файлов Мюррей считает процедурную генерацию очень перспективной сферой для веб-игр.

Проект разрабатывала небольшая команда — в среднем над ним единовременно работало шесть человек.

Сначала генерируется шум, то есть части ландшафта, население планет и так далее. Затем это превращается в воксели и полигонизируется, после чего рендерится и обсчитывается физически.

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

Впервые Мюррей попытался решить эту проблему, скопировав Minecraft (популярный подход в то время). Он использовал тот же метод генерации мира: трилинейное фильтрованное поле шума Перлина низкой плотности.

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

Вместо такого:

Мюррей хотел сделать нечто подобное:

Ему были нужны реалистичные формы и высокий уровень детализации.

Вторым решением были поля из шума высокой плотности — они используются в Space Engine. Результат выглядит привычно. Вот, например, рендер из Terrengine:

Всё, что изображено на картинке, это шум Перлина. Обычно именно такие примеры из портфолио присылают те, кто хочет занять должность в команде No Man’s Sky. Вроде бы похоже на горы, а вроде бы и нет.

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

Затем Мюррей попробовал DEM Data Trainer — данные о высоте реального ландшафта, на основе которых можно было задавать переменные для более реалистичного распределения шума.

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

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

Поэтому Мюррей перешёл к методу, который назвал Uber Noise — в нём он объединил все упомянутые практики, которые пробовал в течение трёх-четырёх лет.

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

Методом Перлина пользуются все. Он работает так: берётся случайный шум, а затем из него создаются градиенты и формы. В итоге он принимает форму, напоминающую цепь гор и обрывов. Шум когезионный и фрактальный.

Затем слои шума с разной частотой и амплитудой накладываются друг на друга.

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

В зависимости от того, какой ландшафт необходим, можно использовать разные методы генерации шума. Например, с помощью функции 0f-abs создаются такие формы:

На схеме выглядит как волосы Барта Симпсона, но в 3D с текстурами получается вполне реалистичный ландшафт. Если добавить Terrengine или Worldbuilder, выйдет убедительный «альпийский» пейзаж.

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

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

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

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

Выглядит куда интереснее (особенно для игрока). Стоит помнить, что на картинках выше изображён только один уровень шума, а в No Man’s Sky их генерируется множество, при этом данные из одного используются для других.

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

На картинке выше был обычный шум Перлина. Теперь к нему добавлена ещё одна функция.

И ещё одна.

Уже напоминает фотографию ландшафта с воздуха.

Вот увеличенный вариант.

Видны участки, похожие на реки, долины и так далее. В No Man’s Sky они создаются с помощью именно этой технологии.

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

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

Функция для Uber Noise. Каждый из её параметров контролируется отдельно и задаётся на основе данных от предыдущего слоя шума.

С помощью параметров выше можно копировать внешний вид, например, тектонической или ледниковой эрозии. Всё, что нужно сделать — изменить амплитуду производной.

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

На этой картинке форма слева получилась как раз из-за акцентирования менее заметных октав шума.

А на этой так возникли каньоны.

С помощью Uber Noise создаётся необычный, разнообразный и реалистичный ландшафт, что делает процесс исследования планет интереснее.

На этом изображении всего один уровень Uber Noise. Внизу и слева — результат деформации области значений. Вдали заметно, что ландшафт меняется: горы становятся не такими высокими и менее округлыми.

Полностью протестировать No Man’s Sky было невозможно, ведь нельзя предсказать, как будет генерироваться вселенная. Каждый игрок исследует собственный мир, и разработчики в принципе не могут знать, каким он будет — только догадываться.

Поэтому в конце продакшена они постарались протестировать количество вариантов вселенных, которое равнялось примерному количеству игроков. В качестве примера были взяты игры, которые вышли в Steam до этого — Inside с тремя тысячами игроков одновременно и Far Cry Primal с 14 тысячами.

Прогнозы им не помогли. В No Man’s Sky на ПК и PS4 одновременно играло 500 тысяч человек, и у каждого создавалась собственная вселенная. В итоге количество ошибок было вполне обычным, сравнимым с предыдущими играми Мюррея вроде Burnout — примерно один процент. На момент выхода Foundation, первого дополнения к No Man’s Sky, ошибок стало ещё меньше (примерно полпроцента) при миллионе игроков.

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

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