В процессе работы над match-3 проектом рано или поздно обязательно встает вопрос — как оценивать сложность созданных уровней и общий баланс игры?

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

Ниже рассказ о том, как мы это сделали в нашей инди-матч3-игре, над которой сейчас заканчиваем работать. (Осторожно — портянка!)

Постановка задачи

Для автоматизации тестирования уровней мы решили запрограммировать “бота”, который бы отвечал следующим требованиям:

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

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

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

Достоверность — ходы бота должны быть более-менее приближены к ходам среднего игрока.

Первые три пункта говорят сами за себя, а вот как заставить бота играть “по-человечески”?

Стратегия бота. Первое приближение

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

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

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

Например, пусть дан уровень в котором присутствуют “размножающиеся” фишки (если не собрать группу фишек рядом с ними, то перед следующим ходом игрока они захватывают одну из соседних с ними клеток). Цель уровня — спустить определенные фишки в нижний ряд доски. Наша игра посвящена морским приключениям (ага, опять!) поэтому требуется спустить на дно водолазов, а в роли размножающихся фишек выступают кораллы:



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

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

• собирать как можно больше фишек (набор очков)
• собирать фишки определенного типа
• уничтожать “мешающие” фишки\клетки
• создавать бонус-фишки
• атаковать “босса”
• спускать определенные фишки вниз
• и тому подобное…

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





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

1. Уничтожение кораллов (АНТИ-КОРАЛЛ)
2. Создание бонусов (СОБРАТЬ БОНУС)
3. Спуск водолазов (ВОДОЛАЗЫ)
4. Выбор максимально ценных ходов (МАКСИМУМ ОЧКОВ)

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

Алгоритм бота

Бот работает по следующему простому алгоритму:

1. Загрузить список приоритетов для уровня из XML файла
2. Сохранить все возможные в данный момент ходы в массив
3. Взять следующий приоритет из списка
4. Проверить есть ли в массиве ходы соответствующие текущему приоритету
5. Если есть, то выбрать наилучший ход
6. Если нет, GOTO 3.
7. После того как ход сделан, GOTO 2

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

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

СТАТИСТИКА ПО УРОВНЮ:
====================================
ЛИМИТ ХОДОВ: 30
КОЛИЧЕСТВО ПРОГОНОВ: 1000
ПРОЦЕНТ ПРОИГРЫШЕЙ: 63 % (630 ПРОГОНОВ)
СРЕДНЯЯ ЗАВЕРШЕННОСТЬ ПРОИГРАННОГО УРОВНЯ: 61 %
СРЕДНЕЕ КОЛИЧЕСТВО ХОДОВ ПРИ ВЫИГРЫШЕ: 24
------------------------------------
ОЧКИ:
-------------------
МИНИМАЛЬНЫЙ СЧЕТ: 2380
МАКСИМАЛЬНЫЙ СЧЕТ: 7480
-------------------
------------------------------------
СТАТИСТИКА ПРОГОНОВ:
-------------------
0. ПРОИГРЫШ (87.0 % ЗАВЕРШЕНО)
1. ПРОИГРЫШ (12.0 % ЗАВЕРШЕНО)
2. ПРОИГРЫШ (87.0 % ЗАВЕРШЕНО)
3. ПРОИГРЫШ (87.0 % ЗАВЕРШЕНО)
4. ПРОИГРЫШ (87.0 % ЗАВЕРШЕНО)
5. ПОБЕДА (УРОВЕНЬ ЗАВЕРШЕН ЗА 26 ХОДОВ. 2 ЗВЕЗД СОБРАНО.)
6. ПРОИГРЫШ (75.0 % ЗАВЕРШЕНО)
7. ПОБЕДА (УРОВЕНЬ ЗАВЕРШЕН ЗА 26 ХОДОВ. 3 ЗВЕЗД СОБРАНО.)
 
    … 

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

А кто сказал, что игрок будет действовать именно так?

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

Но здесь есть сразу два допущения:

• Реальный игрок вряд ли анализирует все имеющиеся на доске ходы — скорее он выбирает первый найденный более-менее разумный ход. А даже если он и пытается рассмотреть все ходы на доске, то он все равно может попросту не заметить хороший ход.
  
• Игрок далеко не всегда может определить и правильно расставить приоритеты — для этого нужно хорошее знание конкретной игры и ее механик, а значит от него нельзя ожидать оптимальных действий на каждом конкретном ходу. (Хотя это меньшая проблема, потому что игрок будет учиться на своих ошибках и в конце концов разберется, что важно для прохождения уровня, а что может подождать).

Получается, бот построенный на основе этих предположений будет играть не как средний, а как “оптимальный” игрок, отлично знакомый со всеми тонкостями игры. И ориентироваться на статистику собранную этим ботом нельзя. Что же делать?

Стратегия бота. Второе приближение

Очевидно что нужно ввести какой-то поправочный коэффициент, который бы делал действия бота менее “идеальными”. Мы решили остановиться на простом варианте — сделать часть ходов бота просто случайными.

Коэффициент определяющий количество случайных ходов задает опять таки левел-дизайнер исходя из своих целей. Мы назвали этот коэффициент “отклонением от стратегии” — зададим его для этого уровня равным 0.2:



Отклонение в 0.2 означает, что с вероятностью 0.2 (или другими словами в 20% случаев) бот просто выберет случайный ход среди имеющихся на доске. Посмотрим как изменилась статистика по уровню при таком отклонении (предыдущая статистика вычислялась при отклонении равном нулю — т.е. бот абсолютно точно следовал заданным приоритетам):

СТАТИСТИКА ПО УРОВНЮ:
====================================
ЛИМИТ ХОДОВ: 30
КОЛИЧЕСТВО ПРОГОНОВ: 1000
ПРОЦЕНТ ПРОИГРЫШЕЙ: 78 % (780 ПРОГОНОВ)
СРЕДНЯЯ ЗАВЕРШЕННОСТЬ ПРОИГРАННОГО УРОВНЯ: 56 %
СРЕДНЕЕ КОЛИЧЕСТВО ХОДОВ ПРИ ВЫИГРЫШЕ: 24
------------------------------------
ОЧКИ:
-------------------
МИНИМАЛЬНЫЙ СЧЕТ: 2130
МАКСИМАЛЬНЫЙ СЧЕТ: 7390
-------------------
…  
 

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

Статистика показывает, что данный уровень относится к достаточно сложным: 24 из 30 ходов должны быть хорошо обдуманы (30 * 0.2 = 6 ходов могут быть сделаны “впустую”), и даже в этом случае в 78% случаев игрок проиграет.

Остался вопрос — откуда взялся коэффициент 0.2 для этого уровня? Какие взять коэффициенты для других уровней? Мы решили оставить это на усмотрение левел-дизайнера.

Смысл этого коэффициента очень прост: “количество необдуманных ходов, которое может сделать игрок на этом уровне”. Если нужен простой уровень для начального этапа игры, который должен быть с легкостью пройден любым игроком, то можно балансировать уровень при этом коэффициенте равном 0.9 или даже 1. Если же нужен сложный или очень сложный уровень, для прохождения которого игрок должен приложить максимум усилий и умений, то балансировку можно проводить при небольшом или даже нулевом отклонении от оптимальной стратегии.

Производительность

Ну и напоследок пару слов о скорости работы.

Бот мы сделали частью игрового “движка” — в зависимости от выставленного флага, программа либо ждет хода от игрока, либо ходы делаются ботом.

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

Поскольку вся игровая логика завязана на цикл отрисовки, а он ограничен 60ю кадрами в секунду, то для ускорения работы тестировщика было решено отключить вертикальную синхронизацию и “отпустить” FPS. Мы используем LibGDX фреймворк, в котором это делается так (может кому-то пригодится):

cfg.vSyncEnabled = false;
cfg.foregroundFPS = 0; 
cfg.backgroundFPS = 0; 
new LwjglApplication(new YourApp(), cfg);

После этого бот шустро забегал на скорости почти 1000 кадров в секунду! Для большинства уровней этого хватает для того, чтобы сделать 1000 “прогонов” уровня меньше чем за 5 минут. Честно говоря, хотелось бы еще быстрее, но и с этим уже можно работать.

Тут можно посмотреть видео работы бота (к сожалению, при записи видео FPS падает примерно до 120):

Итоги

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

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

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