Генерация миссий с использованием классического ML и рекуррентных нейронных сетей в rogue-lite FPS. 

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

Мой друг и очень талантливый гейм-дизайнер Лев Кобелев делает в составе My.Games экспериментальный роглайк-шутер, в котором игрок управляет выжившим после апокалипсиса и должен убивать орды зомби.

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

От автора (то есть от Sadari)

Данная статья — это почти дословный перевод, так как тема очень конкретная и сделать абстрактное саммари передающихся идей не выйдет при таком подходе.

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

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

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

Но перейдем к самой статье.

Миссии

Арены, уровни, локации — в данном контексте синонимы. Область, зона и площадь спавна также являются синонимами.

Начнем с того, что из себя представляет миссия. Миссия — это заранее заданный порядок появления врагов на локации по определенным правилам.

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

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

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

Область определяется по параметрам спавна, рассмотрим два примера ниже: у игрока и стены:

• Первый способ — у игрока. Появление около игрока задается через сектор, который описывается двумя радиусами: внешним и внутренним (R и r), шириной сектора (β), углом поворота (α) относительно игрока и желаемой видимостью (или невидимость) появления врага. Внутри такого сектора находится нужное количество точек под врагов, и они вылезают! Мы часто спавним простых обычных зомби недалеко от игрока в видимых точках, чтобы поддерживать постоянное ощущение экшена

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

Спавны объединяются в волны.

Волна — это порядок появления спавнов, а именно задержки между ними, мы не же хотим наваливать на игрока всех врагов сразу. Волны объединяются в миссии и запускаются друг за друга по определенным логическим условия, например, вторая волна может запуститься, когда с первой прошло 20 секунд или было убито более 90% зомби внутри нее. Так всю миссию можно рассматривать как большую коробку, внутри которой лежат коробки среднего размера (волны), а внутри них маленькие коробки (спавны).

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

Генерация миссий

Декомпозиция готовых миссий

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

Действительно, никто бы не стал делать безумные и непроходимые миссии.

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

Кластеризация работает в некотором N-мерном пространстве да и ML работает именно с числами, следовательно все спавны должны были стать векторами: категориальные переменные были закодированы, все данные нормализованы.

Так, например, спавн, который описывался “заспавни 10 зомби стрелков у северной стены в зоне с отступом 2 метра, шириной 10 и длиной 5” стал вектором [0.5, 0.25, 0.2, 0.8, …, 0.5] (← цифры абстрактные).

Дополнительно была сокращена мощность множества врагов за счет маппинга конкретных врагов к условным типам.

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

Алгоритм кластеризации

Существует много алгоритмов кластеризации: K-Means, DBSCAN, спектральный, иерархический и так далее. Они базируются на разных идеях, но преследует одну цель — найти кластеры в данных. Ниже проиллюстрировано как по-разному могут быть найдены кластеры для одинаковых данных в зависимости от выбранного алгоритма.

В случае спавнов лучше всего себя показал алгоритм K-Means.

Метод K-Means итерационно делит данные на K кластеров путем минимизации суммы квадратов расстояний от каждого объекта до среднего значения назначенного ему кластера. Среднее выражается внутрикластерной суммой квадратов расстояний.

Важно понимать, что данный метод:

• Не обеспечивает одинаковый размер кластеров — и для нас это не проблема, так как распределение кластеров внутри миссии может быть неравномерным;
• Не определяет число кластеров внутри данных, а требует на вход некоторое число K — желаемое количество кластеров. Иногда это число обусловлено заранее, а иногда нет. Более того, не существует общепринятого метода поиска “наилучшего” числа кластеров.

Разберемся со вторым пунктом чуть подробнее.

Количество кластеров

Для выбора оптимального числа кластеров часто прибегают к методу локтя (elbow method). Его идея очень простая: запустим алгоритм и попробуем все K от 1 до N, где N — некоторое разумное число.

В нашем случае можно было взять 10 — больше кластеров точно нельзя было найти. Теперь найдем сумму квадратов расстояний внутри каждого кластера (оценка известная как WSS или SS). Изобразим всё это на графике и выберем точку, после которой значение по оси y перестает сильно меняться.

Для иллюстрации воспользуемся известным датасетом — Ирисы Фишера. Запустим на нем алгоритм с k от 1 до 10 и посмотрим изменение выше описанной оценки в зависимости от k. Примерно при k=3 оценка перестает сильно меняться — именно столько классов и было в оригинальном датасете.

Если локтя не видно, то можно воспользоваться методом силуэтов (Silhouette method) — но о нем как-нибудь в другой раз.

Да, все вычисления выше и далее делаются на языке Python с использованием стандартных библиотек для машинного обучения и анализа данных: pandas , numpy , seaborn и sklearn.

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

Анализ каждого кластера

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

• Веса врагов для расчета вероятности. Например, обычный зомби = 5, зомби в шлеме = 1, следовательно, вероятность обычного — 5/6, а в шлеме — 1/6. Весами удобнее оперировать
• Границы значений, например, минимальный и максимальный угол поворота зоны или её ширина. Каждый параметр описывается своим отрезком, любое значение из которого равновероятно
• Категориальные значения, например, тэг стены или видимость точек описываются как настройки врагов — через веса

Рассмотрим настройки кластера, который вербально можно описать как “спавн простых врагов где-то около игрока на небольшом расстоянии и, скорее всего, в видимых точках”.

Кстати, 2 трюка:

• Задается не фиксированное количество врага, а отрезок, из которого его число будет выбрано. Это помогает в разных кластерах оперировать одним врагом, но в разных количествах.
• Задается не внешний радиус (R), а дельта (R-delta) относительно внутреннего радиуса (r), чтобы соблюдалось правило R > r. Таким образом, к случайному r прибавляется R-delta, r+R-delta > r ∀ R-delta > 0— значит, всё хорошо.

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

Время на миссию

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

В процессе создания ручных миссий стояла задача выстроить срежиссированный темп главы — последовательности миссий: короткая, длинная, короткая, снова короткая и так далее. Как же получить суммарное здоровье врагов внутримиссии, если известно ожидаемое DPS игрока и её время?

Линейная регрессия — метод восстановления зависимости одной переменной от другой или нескольких других переменных с линейной функцией зависимости. В примерах ниже будет рассматриваться исключительно линейная регрессия от одной переменной: f(x) = wx + b.

Введем следующие обозначения:

• HP — суммарное здоровье врагов в миссии,
• DPS — ожидаемый урон игрока в секунду, чистое время (action time) — количество секунд, которое игрок тратит, чтобы просто уничтожить врагов в миссии, свободное время (free time) — дополнительное время, в рамках которого игрок может, например, менять цель, ожидаемое время миссии (mission time) — сумма чистого и свободного времени.

Таким образом, HP = DPS * action time + free time.

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

Если известно ожидаемое время миссии, то можно посчитать чистое и вычесть его из ожидаемого, чтобы получить свободное: free time = mission time - action time = mission time - HP * DPS. Далее это число можно разделить на среднее количество врагов в миссии и получить свободное время на одного врага.

Следовательно, остается просто построить линейную регрессию от ожидаемого времени миссии к свободному времени на одного врага.

Дополнительно построим регрессию доли чистого времени от mission time.

Рассмотрим на примере, как всё считается и зачем эти регрессии:

• Вводим два числа mission time и DPS — 30 и 70
• Обращаемся к регрессии доли чистого времени от mission time и получаем ответ — 0.8
• Считаем чистое время — 30*0.8=6 секунд
• Вычисляем HP — 6*70=420
• Обращаемся к регрессии свободного времени на одного врага от mission time и получаем ответ — 0.25 секунд

Вопрос: зачем знать свободное время на врага?

Как говорилось ранее, спавны расставляются по времени, следовательно, время i-ого спавна можно рассчитать как сумму чистого времени (i-1)-ого и свободного времени внутри него.

Из всех рассуждений вытекает вопрос: почему доля чистого времени и свободное время не константы?

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

Генерация новых миссий

Если мыслить абстрактно, то любую миссию можно представить как последовательность чисел, где каждое число отражает конкретный кластер спавна. Например, миссия: 1, 2, 1, 1, 2, 3, 3, 2, 1, 3. Значит задача генерации новых миссий сводится к генерации новых числовых последовательностей. После генерации надо просто “развернуть” каждое число по отдельности в соотвествии с настройками кластера.

Базовый подход

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

• Вершина графа — кластер.
• Вес ребра — вероятность кластера, к которому оно ведет, оказаться следующим.

Гуляя по таком графу, можно было бы генерировать последовательность. Однако у такого подхода есть ряд минусов, например, отсутствие памяти (знает только текущее состояние) и возможность “загуляться” в одном состоянии, если оно имеет большую статистическую вероятность перехода самого в себя.

Рекурретные нейронные сети

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

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

• набор из N последовательностей длины L
• ответ на каждую из N последовательностей — one-hot вектор, то есть вектор длины C из C-1 нулей и одной единицы, обозначающей ответ
• C — мощность множества ответов

Простой пример с N=2, L=3, C=5. Берем последовательность 1, 2, 3, 4, 1 и ищем внутри нее подпоследовательности длины L+1: [1, 2, 3, 4], [2, 3, 4, 1].

Последовательность разбиваем на вход (input) из L символов и ответ (target) — (L+1)-ый символ. Например, [1, 2, 3, 4] → [1, 2, 3] и [4]. Ответы кодируем в one-hot вектора, [4] → [0, 0, 0, 0, 1].

Далее, можно на Python, используя tensorflow или pytorch набросать простую нейронную сеть. Как это сделать — можно посмотреть по ссылкам ниже.

Модели генерации на основе машинного обучения имеют несколько определенных метрик, напрмиер, точность генерации, которая показывает пропорцию корректно сгенерированных результатов. Если смотреть на метрику точности (accuracy), то неплохо, если модель работает лучше, чем наугад, то есть accuracy > 1/C. Отлично, если близко к 1.

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

Несколько материалов по LSTM для заинтересовавшихся:

Beginners Guide to Text Generation using LSTMs

Tackling Toxic Using Keras

Exploring Gameboy Advanced Games

Настройка генератора

Обученная модель легко сериализуется, так что можно использовать её как ассет в движке. В нашем случае — Unity.

Соответсвенно, генератор обращается по API к модели и итеративно создает последовательность. Результат разворачивается и сохраняет результат в отдельный csv файл.

Для взаимодействия с моделью было создано кастомное окно в Unity, в котором геймдизайнеры могут выставлять все необходимые параметры миссии:

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

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

Этапы генерации

Разберемся чуть подробнее в процессе генерации:

• Модель получает на вход последовательность и выдает ответ — вектор вероятностей, что i-ый кластер будет следующим. Алгоритм бросает кубик, если выпало число больше, чем error chance, то берем самый вероятный, иначе случайный. Такой трюк помогает добавить немного креатива и разнообразия
• Процесс продолжается до заданного числа итераций. Оно больше, чем количество спавнов в любой из ручных миссий
• Последовательность разворачивается, то есть каждое число обращается к сохраненным данным кластера и получает из них случайные значения
• Здоровье внутри данных суммируется, и из последовательности выкидывается все, что больше ожидаемого здоровья (про его расчет было выше)
• Спавны разбиваются на волны в зависимости от заданного распределения здоровья, а далее разбиваются на группы (чтобы несколько врагов появлялось сразу), и им задается время появления, как сумма чистого и свободного времени предыдущей группы спавнов
• Миссия готова!

Выводы

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

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

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