НАВИГАЦИЯ ИГРЫ

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

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

Как всё началось

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

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

Black

По мнению Шона, движок игры определяет её дизайн. Сам выбор «мотора» — первый шаг в геймдизайне. К началу разработки 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 подкинул своим создателям.

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

Нравится9
Комментарии (19)
  • 13
    Rakszas
    Красиво это только в презентациях. В самой же игре всё выглядит очень однообразно.
  • 13
    VenomTRat
    Пока не начался вой, тут не говорится о том, какая замечательная игра, тут разбор технологии, которая полностью работает.
    Спойлер
  • 4
    lookjaklook
    Для того чтобы создать нечто подобно разнообразности, при этом всё работало как надо, надо трудится над механикой генерации, сделать так, чтобы были планеты. А не кусок текстурки который может в разных углах либо подняться либо опустится -_-
  • 9
    magister1
    VenomTRat
    В технологии да, прогресс был большой, по само генерируемому миру. Но всё испортило жадность, и недоработанность игровова процесса, с этой системой. По-этому у многих рядовых пользователей, будут с ужасом вспоминать эту игру, и этого разработчика. Но, он и сам виноват надо было выпускать альфу, а не ААА проект.
  • 5
    Rakszas написал:
    В самой же игре всё выглядит очень однообразно.

    Были в игре и "райские" планеты. Очень красивые.
  • 4
    VenomTRat
    magister1
    да, хотя они щас ее активно дорабатывают, на данный момент игра уже из симулятора созерцания превращается в нечто большее
  • 4
    В попу все градиентные шумы. Надо либо фрактальные, либо по производным. Правда в последнем может случиться недифференцируемая функция (конус в вершине).
    А если не получается, то лучше и не пробовать, а то получится No Man's Sky.
  • 1
    Бомбардировщик
    Проблема этой технологии фундаментальна.
    В природе, несмотря на кажущийся ХАОС всё на самом деле очень органично и подчинено физическим законам мира и эволюции.
    В игре же эта процедурная генерация представляет из себя самый настоящий ХАОС, без подчинения каким либо законам и поэтому выглядит УРОДЛИВО.
    именно поэтому копия с реального ландшафта или же его повторение всегда будет выглядеть естественнее и красивее этого беспорядка, что мы наблюдаем в но ман скай.
  • 0
    DimakSerpg
    Так и? В чем смысл? Игра-то все равно гавно :D

    Бомбардировщик Вот вот, а судя по нмс, там физика вообще отсутствует. Даже, простейшая. Планетарная.
  • 1
    Как никрути - игра полнейшое рандомизированное математическое фуфло:)
  • 2
    Бомбардировщик
    технически возможно в целом заделать например полярные шапки по которым можно пек-пек-пек ехать и всякие там снежные шапки у гор. если поднатужицо можно ввести для автоматической текстурной покраски понятие температуры и на пример где то на экваторе снег будет лежать на 5000м над уровнем моря а где то на севере на километре итд. с эрозией рек например то это однако проблема и решать ее в реал тайме затруднительно весьма. однако есть такой процедурный генератор - волд машин там заначицо тоже процедурная генерация и сдается мне многие опен волд игры им пользуцуюцо для создания всяких гор и удаленных рельефов.
    единственное в чем проблема - процедурная генерация особенно массивная должна идти на гпу а тут возникают проблемы с обратной связью физикой и собственно генерацией травооонаааа и всяческих скал. ибо на шейдерах ты лев толстой а на физмате петушок и данные о вешиннах процессору недоступны с приемлемым быстродействием. от тут классические шутерные движки пук и приехали. да и движки и современные игры сосут с реальными размерами планет и солнечных систем
    поэтому к процедурной генерации можно следующие проблемы
    малый размер мира в том числе генерируемый за раз и видимый
    малая детализация этого самого мира. чем выше детализация и сложность тем больше это не про физику и реальное время.
    миры лысые и унылые. в них мало травона.
  • 0
    Бомбардировщик
    MunchkiN 616
    проще вручную делать короче
  • 2
    Бомбардировщик
    основы автоматической генерации и текстур ускорят разработку игрорей размером с готику 3 в несколько раз. а потом у школьников начнется денува правда.
    а на то чтоб допустим запилить все планеты что есть в массыффект андромеда понадобитцо очень много китайцов которы будут пилить это лет 5. второя проблема с детерминированным чисто ручным дизайном это что он много весит и в идеале то что он там весит ашди планеты - ему бы пришлось грузить в видеокарту и и озу что много гигубов
  • 0
    taburetckinvasily
    За-то математическое!!!
  • 0
    Мюррей участвовал в создании движка Renderware

    Разработчик даже оставил в них что-то вроде «авторской подписи»: баг, из-за которого у персонажей при определённых условиях отваливались руки.

    И тут поднасрал всем и вся.)
  • 0
    Viruss canre
    lookjaklook
    игру делали двадцать человек
  • 2
    lookjaklook
    Viruss canre
    Сидели в студии двадцать человек, это еще не означает что они работали
  • 1
    Silver Arrow
    VenomTRat
    Да это впечатляет стоит отдать ему должное, но вот как можно было просрать такой проект, который мог бы быть очень успешным, но жадность взяла свое и они быстренько похоронили свой проект и возможно студию под тонной г*вна и кто знает, получится ли когда нибудь оттуда выбраться у них.
  • 1
    VenomTRat
    Silver Arrow
    Обновы клепают, так что пока все хорошо. Основная претензия у всех, это мульт. Как его вернут, игра встанет в один ряд с элиткой и евой
B
i
u
Спойлер