Генерация миссий с использованием классического машинного обучения и рекуррентных нейронных сетей в состоянии зомби

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

Всем привет! Меня зовут Лев Кобелев, я гейм-дизайнер в MY.GAMES. В этой статье я хотел бы поделиться своим опытом использования классического машинного обучения и простых нейронных сетей, объяснить, как и почему мы остановились на процедурной генерации миссий, а также подробно углубиться в реализацию этого процесса в Zombie. Состояние.

Основы миссии «Ящик»: волны, спавны и прочее

☝🏻 Прежде всего, немного терминологии: « арены », « уровни » и « локации » являются синонимами в данном контексте, как и « площадь », « зона » и « зона появления ».

Теперь давайте определим « миссию ». Миссия — это заранее определенный порядок, в котором враги появляются на локации по определенным правилам . Как уже упоминалось, локации в Zombie State генерируются, поэтому мы не создаем «постановочный» опыт. То есть мы не размещаем врагов в заранее заданных точках — на самом деле таких точек нет. В нашем случае враг появляется где-то возле игрока или конкретной стены. Далее, все арены в игре прямоугольные, поэтому любую миссию можно пройти на любой из них.

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

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

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

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

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

1. Чтобы поддерживать постоянное ощущение действия, обязательно часто порождайте обычных зомби рядом с игроком в видимых точках.
2. Чтобы подчеркнуть выход или подтолкнуть игрока с определенной стороны, старайтесь в первую очередь порождать врагов дальнего боя возле стен.
3. Иногда перед игроком появляются особые враги, но в невидимых точках.
4. Никогда не порождайте врагов ближе, чем на X метров от игрока.
5. Никогда не порождайте более X врагов одновременно.

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

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

Декомпозиция миссии

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

✍🏻 Некоторые термины, которые вы встретите в тексте:

• Кластеризация — это задача разделения данной коллекции на непересекающиеся подмножества (кластеры) так, чтобы похожие объекты принадлежали одному кластеру, а объекты из разных кластеров существенно отличались.

• Категориальные признаки — это данные, которые принимают значение из конечного набора и не имеют числового представления. Например, тег стены возрождения: Север, Юг и т. д.

• Кодирование категориальных признаков — это процедура преобразования категориальных признаков в числовое представление по некоторым заранее заданным правилам. Например, Север → 0, Юг → 1 и т. д.

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

  
  

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

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

• Категориальные переменные были закодированы
• Все данные нормализованы

Так, например, вектором [0.5, 0.25, 0.2] стал спавн, который описывался как «породить 10 зомби-стрелков у северной стены на участке с отступом 2 метра, шириной 10 и длиной 5». , 0,8, …, 0,5] ( ←эти числа абстрактны).

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

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

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

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

Теперь небольшое отступление для тех, кто ничего не знает об этом алгоритме (строгих математических рассуждений не будет, поскольку эта статья посвящена разработке игр, а не основам ML). K-Means итеративно делит данные на K кластеры, минимизируя сумму квадратов расстояний от каждого объекта до среднего значения назначенного ему кластера. Среднее значение выражается внутрикластерной суммой квадратов расстояний.

Об этом методе важно понимать следующее:

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

Давайте рассмотрим второй пункт немного подробнее.

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

Метод локтя часто используется для выбора оптимального количества кластеров. Идея очень проста: мы запускаем алгоритм и пробуем все K от 1 до N, где N — некоторое разумное число. В нашем случае их было 10 — больше кластеров найти было невозможно. Теперь давайте найдем сумму квадратов расстояний внутри каждого кластера (показатель, известный как WSS или SS). Отобразим все это на графике и выберем точку, после которой значение по оси Y перестанет существенно меняться.

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

Если локоть не видно, то можно воспользоваться методом «Силуэт», но он выходит за рамки статьи.

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

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

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

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

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

Таблица кластера 1

Вот два полезных трюка:

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

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

Несколько интересных вещей о кластеризации

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

• Pokmean — Кластеризация KMean в Pokedex
• Кластеризация игр League of Legends
• Кластеризация полевых игроков FIFA20

Время для миссии

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

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

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

Введем следующие термины:

• HP - общее здоровье врагов в миссии.
• DPS — ожидаемый урон игрока в секунду.
• Время действия — это количество секунд, которое игрок тратит на уничтожение врагов в миссии.
• Свободное время — это дополнительное время, в течение которого игрок может, например, сменить цель.
• Ожидаемое время миссии — это сумма действий и свободного времени.

Итак, ХП = ДПС * время действия + свободное время. При создании главы руководства мы записывали ожидаемое время каждой миссии; теперь нам нужно найти время для действия.

Если вы знаете ожидаемое время миссии , вы можете рассчитать время действия и вычесть его из ожидаемого времени , чтобы получить свободное время : свободное время = время миссии - время действия = время миссии - HP * DPS. Затем это число можно разделить на среднее количество врагов в миссии, и вы получите свободное время на каждого врага. Поэтому остается просто построить линейную регрессию от ожидаемого времени миссии к свободному времени на одного врага.

Дополнительно построим регрессию доли времени действия от времени миссии.

Давайте рассмотрим пример расчетов и разберемся, почему используются эти регрессии:

1. Введите два числа: время миссии и DPS: 30 и 70.
2. Посмотрите регрессию доли времени действия от времени миссии и получите ответ: 0,8.
3. Рассчитайте время действия как 30*0,8=6 секунд.
4. Рассчитайте HP как 6*70=420.
5. Посмотрите регрессию свободного времени на одного врага от времени миссии и получите ответ, который составит 0,25 секунды.

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

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

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

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

• Учебное пособие по линейной регрессии
• Базовый проект машинного обучения — линейная регрессия
• Линейная регрессия для начинающих

Создание новых миссий

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

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

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

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

Верхняя часть диаграммы — это кластер, к которому она ведет, вершина, а вес ребра — это вероятность того, что кластер окажется следующим.

Проходя по такому графу, мы могли бы сгенерировать последовательность. Однако этот подход имеет ряд недостатков. К ним относятся, например, недостаток памяти (он знает только текущее состояние) и вероятность «застрять» в одном состоянии, если он имеет высокую статистическую вероятность превратиться в самого себя.

✍🏻 Если рассматривать этот граф как процесс, то получаем простую цепь Маркова.

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

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

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

• Набор из N последовательностей длины L
• Ответом на каждую из N последовательностей является горячий вектор, то есть вектор длины 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]. Разобьем последовательность на вход L символов и ответ (цель) - (L+1)-й символ*.* Например, [1, 2, 3, 4] → [1, 2, 3] и [ 4]. Мы кодируем ответы в горячие векторы, [4] → [0, 0, 0, 0, 1].

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

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

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

Вот еще материалы по RNN для интересующихся:

• Руководство для начинающих по генерации текста с использованием LSTM
• Борьба с токсичностью с помощью Keras
• Знакомство с продвинутыми играми Gameboy

Процесс генерации

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

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

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

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

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

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

Давайте посмотрим на процесс генерации:

1. Модель получает на вход последовательность и выдает ответ — вектор вероятностей того, что i-й кластер будет следующим. Алгоритм бросает кубик, если число больше шанса ошибки , то берем наиболее вероятное, в противном случае случайное. Этот трюк добавляет немного креатива и разнообразия.
2. Процесс продолжается до заданного количества итераций. Это больше, чем количество спавнов в любой из миссий, созданных вручную.
3. Последовательность продолжается; то есть каждое число обращается к сохраненным данным кластера и получает от них случайные значения.
4. Здоровье внутри данных суммируется, а все, что больше ожидаемого здоровья, выбрасывается из последовательности (о его расчете говорилось выше)
5. Спавны делятся на волны в зависимости от заданного распределения здоровья, а затем делятся на группы (чтобы появлялось сразу несколько врагов), а время их появления задается как сумма действия и свободного времени предыдущей группы спавнов.
6. Миссия готова!

Выводы

Итак, это хороший инструмент, который помог нам ускорить создание миссий в несколько раз. Кроме того, некоторым дизайнерам это помогло преодолеть страх перед «писательским кризисом», так сказать, поскольку теперь получить готовое решение можно за несколько секунд.

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

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

Иллюстрации шаббириста