Gamedev Владимир Семыкин
9 555

Случайный мир: разбор генераторов игровых уровней

Практические особенности разных алгоритмов.

В закладки
Аудио

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

Майк Кук, геймдизайнер и исследователь ИИ, на своём сайте опубликовал текст, в котором рассказал про разные алгоритмы для создания генераторов уровней. Особое внимание он уделил соотношению понятий «генеративное пространство» и «пространство возможностей». Мы выбрали главное из материала.

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

Мировой генератор Minecraft содержит в общей сложности 2⁶⁴ случайных номера, что является по-настоящему огромным числом: это 18 446 744 073 709 551 616 миров, которые он может сгенерировать. При каждом нажатии на кнопку «Новый мир», выпадает один из номеров. Число 2⁶⁴ является размером генеративного пространства Minecraft — набора всех вещей, которые он может сгенерировать.

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

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

Диаграмма выше даёт представление о том, как это выглядит. Всё в генеративном пространстве Minecraft также находится пространстве возможностей. Но не всё в пространстве возможностей находится в генеративном пространстве. Например, это касается плоского травяного мира. Но диаграмма не отражает реальный масштаб. Фактически, пространство возможностей Minecraft намного больше, чем его генеративное пространство.

Чтобы увидеть, насколько оно велико, нужно посчитать размер отдельного мира Minecraft. Объём — это ширина, умноженная на высоту, умноженная на глубину. Миры Minecraft по умолчанию имеют 256 тайлов в высоту и около 30 000 000 тайлов в любом направлении от начала.

256 x 60 000 000 x 60 000 000 = 921 600 000 000 000 000 блоков

Каждый из этих блоков может отличаться по типу: камень, трава, воздух, вода. Всего в Minecraft насчитывается 64 стандартных типов блоков. Формула для вычисления количества возможных миров — это число вариантов каждого блока, возведённое в степень количества блоков:

64⁹²¹⁶ºººººººººººººº возможных миров в Minecraft

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

Алгоритм 1: хаотичность

Генератор первого уровня очень прост — он абсолютно случайный. Каждая карта имеет стартовый тайл с левой стороны и тайл выхода с правой стороны. Любой другой тайл на карте имеет 33% шанс быть пустым, 33% шанс быть твёрдым и 33% шанс стать блоком усиления.

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

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

Самые забавные и интересные уровни находятся в этом генеративном пространстве. Здесь даже есть карта с надписью «SUPER MARIO IS AWESOME», составленная из блоков усиления. К сожалению, генеративное пространство настолько велико, что найти такой крутой уровень очень и очень маловероятно. Большинство возможных уровней просто мусор.

Алгоритм 2: рисунок произвольной формы

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

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

Ниже представлен тот же алгоритм, который генерирует не 20 фигур, а 10. Он позволяет быстрее сформировать подходящий уровень.

Генератор с 20 фигурами имеет большее генеративное пространство. Фактически он содержит в себе всё генеративное пространство алгоритма с 10 фигурами. Тем не менее любой уровень с 20 фигурами никогда не может быть отрисован генератором с 10 фигурами.

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

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

Алгоритм 3: фрагменты уровня

Этот алгоритм основан на генераторе уровней, используемом в Spelunky. Генератор уровней случайным образом выбирает кусок уровня, разработанного человеком, и вставляет его в уровень. Затем он случайным образом выбирает другой кусок уровня и вставляет его рядом. И так далее, пока уровень не будет завершён.

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

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

Алгоритм 4: дизайн от человека

Ниже представлен уровень, полностью сделанный человеком. Этот подход — окончательный компромисс контроля и качества.

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

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

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

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

Найти способ уравновесить сильные и слабые стороны этих двух крайностей — это искусство генеративного проектирования.

#геймдизайн #long
{ "author_name": "Владимир Семыкин", "author_type": "editor", "tags": ["long","\u0433\u0435\u0439\u043c\u0434\u0438\u0437\u0430\u0439\u043d"], "comments": 27, "likes": 88, "favorites": 161, "is_advertisement": false, "subsite_label": "gamedev", "id": 38681, "is_wide": false, "is_ugc": false, "date": "Wed, 06 Feb 2019 14:21:43 +0300" }
{ "id": 38681, "author_id": 94357, "diff_limit": 1000, "urls": {"diff":"\/comments\/38681\/get","add":"\/comments\/38681\/add","edit":"\/comments\/edit","remove":"\/admin\/comments\/remove","pin":"\/admin\/comments\/pin","get4edit":"\/comments\/get4edit","complain":"\/comments\/complain","load_more":"\/comments\/loading\/38681"}, "attach_limit": 2, "max_comment_text_length": 5000, "subsite_id": 64954, "possessions": [] }

27 комментариев 27 комм.

Популярные

По порядку

Написать комментарий...
41

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

Ответить
3

Да ладно вам, все равно прикольно же. :)

Ответить
9

вот вроде ни о чем статья, но на фоне обмусоливания одних и тех же новостей нравится, спасибо

Ответить
8

Ща-ща, я всё исправлю, чтобы сохранить привычную атмосферу сайта:
-- Epic Games красавчики/дьяволы.
-- Галёнкин красавчик/дьявол.
-- Метро: Исход ушёл к красавчикам/дьяволам.
-- Apex... вышел.
-- Редакция DTF облизывает Ubisoft.
-- Кто-то в индустрии жалуется на переработки.
-- Кто-то в индустрии кого-то оскорбил.
-- В игре *** опять кто-то гей.
-- Разоблачения/опровержения прошлых шокирующих новостей.

Лучше?,)

Ответить
2

Где пункт "Кодзима - гений", еретик?

Ответить
0

Не упоминаю имя господа в суе.
Да и это само собой разумеющееся.

Ответить
0

-- Epic Games красавчики/дьяволы.

-- Галёнкин красавчик/дьявол.

А слеши тут к чему, это не взаимоисключающие понятия.

Ответить
0

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

Ответить
0

-- Редакция DTF облизывает Ubisoft.

Как будто это плохо? Есть за что

Ответить

1

Вашу мать! Вы только что учли в своей унылой статье мой уникальный, ещё не созданный, самый охренительный уровень, который только можно создать в Майнкрафте!

Это плогеат! Зосужу!

Ответить
8

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

Ответить
2

Прикольный реверсивный левел-дизайн. Ага. Может быть, MeatBoy, HollowKnight и иже с ними так и создавали )

Ответить
1

Алгоритм 3: фрагменты уровня

Оно об этом

Ответить
0

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

Ответить
1

Чанки никуда не исчезнут, вопрос лишь в их размере. На примере Minecraft - чанк может быть кубом, а может быть комнатой из кубов.
Условие "персонаж должен пройти" превращается в набор правил, когда герой может пройти кусочек. С оптимизацией (не будем же мы перебирать зазря нерабочие варианты?) это становится правилами "как можно группировать чанки". Т.е "генератор на грамматике" из этого пункта.

Так что это на самом деле одни и те же вещи, вопрос лишь в масштабе

Ответить
0

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

Или я не прав?

Ключевое "Генератор уровней случайным образом выбирает кусок уровня, разработанного человеком"

Ответить
1

Кусок уровня, сделанный человеком, может быть любого размера ведь.
Просто если у тебя куски здоровые, вроде комнат, то в "грамматике" будет описано, как эти комнаты можно стыковать. Плюс будет задана "грамматика" минимального пути, чтоб не вышло, что ты сгенерировал огромный лабиринт с выходом на в комнате входа.
Если у тебя куски минимального размера, как кускив Minecraft, то при генерации "снизу вверх" придется описывать "грамматику" как можно стыковать эти блоки, при желании описывать ему концепции "платформ", "стен", "этажей". "Сверху-вниз" - это если сначала мы генерируем области "деревня", "лес", "река", а потом уже заполняем их. Подобное, вроде делали разработчики Frozen Synapse.

Правила будут разные, но суть останется прежней.

Ответить
0

Спутал чанки и тайлы

Ответить
0

Вроде в каких-то рогаликах генератор уровней отталкивается от точек интереса. Я могу путать, но, вроде, в статье, где о подобном алгоритме говорилось, приводили в пример Enter the Gungeon

Ответить
0

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

Ответить
5

А звучит то как:
-- Генеративное искусство!,)

Или, всё же, не хватает слога вначале..?

Ответить
3

Рассчитывал прочитать длинную статью про различные алгоритмы, а узнал сколько возможных миров в Minecraft :/

Ответить
2

И опять оборвали статью на полуслове.

Ответить

0

Теперь нужно представить абсолютно пустой мир Minecraft. В нём нет ничего, кроме слоя травы. Помимо того, что он довольно скучный, этот мир не является чем-то, что можно сгенерировать в Minecraft

А как же superflat режим?https://minecraft.gamepedia.com/Superflat

Ответить
0

Блин, думал что-нибудь новое узнаю, по генерации. Оказалось нет. Но написано недурно)

Ответить
0

Прямой эфир

[ { "id": 1, "label": "100%×150_Branding_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox_method": "createAdaptive", "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfl" } } }, { "id": 2, "label": "1200х400", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfn" } } }, { "id": 3, "label": "240х200 _ТГБ_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fizc" } } }, { "id": 4, "label": "240х200_mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "flbq" } } }, { "id": 5, "label": "300x500_desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "ezfk" } } }, { "id": 6, "label": "1180х250_Interpool_баннер над комментариями_Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "clmf", "p2": "ffyh" } } }, { "id": 7, "label": "Article Footer 100%_desktop_mobile", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjxb" } } }, { "id": 8, "label": "Fullscreen Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjoh" } } }, { "id": 9, "label": "Fullscreen Mobile", "provider": "adfox", "adaptive": [ "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fjog" } } }, { "id": 10, "label": "Native Partner Desktop", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyb" } } }, { "id": 11, "label": "Native Partner Mobile", "provider": "adfox", "adaptive": [ "phone" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fmyc" } } }, { "id": 12, "label": "Кнопка в шапке", "provider": "adfox", "adaptive": [ "desktop", "tablet" ], "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fdhx" } } }, { "id": 13, "label": "DM InPage Video PartnerCode", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox_method": "createAdaptive", "adfox": { "ownerId": 228129, "params": { "pp": "h", "ps": "clmf", "p2": "flvn" } } }, { "id": 14, "label": "Yandex context video banner", "provider": "yandex", "yandex": { "block_id": "VI-250597-0", "render_to": "inpage_VI-250597-0-1134314964", "adfox_url": "//ads.adfox.ru/228129/getCode?pp=h&ps=clmf&p2=fpjw&puid1=&puid2=&puid3=&puid4=&puid8=&puid9=&puid10=&puid21=&puid22=&puid31=&puid32=&puid33=&fmt=1&dl={REFERER}&pr=" } }, { "id": 15, "label": "Плашка на главной", "provider": "adfox", "adaptive": [ "desktop", "tablet", "phone" ], "adfox": { "ownerId": 228129, "params": { "p1": "byudo", "p2": "ftjf" } } }, { "id": 17, "label": "Stratum Desktop", "provider": "adfox", "adaptive": [ "desktop" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fzvb" } } }, { "id": 18, "label": "Stratum Mobile", "provider": "adfox", "adaptive": [ "tablet", "phone" ], "auto_reload": true, "adfox": { "ownerId": 228129, "params": { "pp": "g", "ps": "clmf", "p2": "fzvc" } } } ]
Узнавайте новости о мостах
Санкт-Петербурга первыми
Подписаться на push-уведомления