В этой части мы решим задачи об оптимальном размещении оружия на танке, пространственном расположении телепортов в MMORPG и сбалансируем бои четырёх классов персонажей RPG.

Задачи о размещении объектов

Электронные таблицы для этой части можно скачать здесь: (SuperTank) (телепорты, часть 1) (телепорты, часть 2)

SuperTank: задача решена!

В первой статье серии мы рассказали о примере задачи для игры под названием SuperTank. Во второй её части, мы познакомились с основными концепциями моделирования решений и я рассказал о решении простого примера с помощью инструмента «Поиск решений» в Excel.

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


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


На супертанк может поместиться 50 тонн оружия, а игрок может потратить 100 кредитов. Также у супертанка есть 3 «критических слота», в которые помещаются такие специальные пушки, как MegaRocket и UltraLaser.

Электронную таблицу для этого примера можно скачать здесь.

Цель заключается в том, чтобы подобрать вооружение, максимизирующее наносимый супертанком урон, не выходя при этом за ограничения в 50 тонн, 100 кредитов и 3 критических слота. Также мы предполагаем, что в этой таблице находится вся необходимая информация, и что такие факторы, как дальность, частота и точность стрельбы к делу не относятся или уже учтены в параметре Damage соответствующего оружия.

Чтобы оптимизировать эту схему, мы сначала внесём эти данные в электронную таблицу. Сразу под ней мы добавим ещё одну таблицу, в которых будет набор из 5 «количественных» ячеек для указания количества каждого из 5 типов оружия.

Пока мы введём в эти ячейки значение 1, просто чтобы протестировать их работу, но это будут наши ячейки решений — мы попросим инструмент «Поиск решений» (Solver) найти правильные значения этих ячеек. Понять, что это ячейки решений, можно по жёлтой окраске, потому что мы продолжаем следовать правилам форматирования, изложенным во второй части. Справа от «количественных» ячеек мы добавим ячейки вычислений, которые будут умножать значения количества в ячейках решений на значения Damage, Weight, Cost и Critical Slots из таблицы выше. Таким образом, каждая строка этой таблицы будет верно отображать урон, вес, цену и критические слоты, требующиеся для всех использованных пушек во всех категориях вооружений.


Также мы создадим ниже раздел, в котором будут суммироваться все значения количества, веса, стоимости и критических слотов из таблицы выше, и сравниваться с максимальными значениями веса, стоимости и критических слотов, указанных в условиях задачи (соответственно 50, 100 и 3).


В соответствии с правилами форматирования из второй части статьи, синие ячейки наверху являются критериями из условий задачи. Серые ячейки — это ячейки вычислений, представляющие общие значения веса, стоимости и критических слотов на основании суммирования из таблицы количества (т.е. общих значений столбцов Weight x Quantity, Cost x Quantity, и Critical Slots x Quantity). Наконец, оранжевая ячейка представляет общий урон нашего супертанка, полученный на основании общего урона столбца Damage x Quantity из таблицы выше.

Прежде чем мы приступим к решению, давайте сделаем нашу электронную таблицу более дружелюбной к пользователю. Мы воспользуемся возможностью Excel присваивать каждой ячейке название и дадим понятные названия семи ячейкам в последней таблице вычислений. Это необязательно, но в дальней перспективе это позволит электронной таблице выглядеть гораздо понятнее (например, если вместо $F$21 ячейка будет называться MaxCriticalSlots). Для этого мы просто выбираем ячейку и переходим в поле ввода названия слева от поля формул, и вводим новое название.


Теперь наконец-то давайте перейдём в Excel Solver и найдём решение (перейдите в правую часть вкладки Data («Данные») и выберите Solver («Поиск решений»). Если вы её не видите, то зайдите в Options («Параметры») Excel, выберите категорию Add-Ins («Надстройки»), убедитесь, что в раскрывающемся списке Manage («Управление») выбрано Excel Add-Ins («Надстройки Excel»), нажмите Go («Перейти...») и убедитесь, что поставлен флажок Solver Add-in («Поиск решения»).

В поле Set Objective («Оптимизировать целевую функцию») мы выберем оранжевую ячейку цели, а ниже нажмём на радиокнопку Max («Максимум»). В поле By Changing Variable Cells («Изменяя ячейки переменных») выберем ячейки решений (жёлтые ячейки в столбце Quantity второй таблицы). Ниже нажмём на кнопку Add («Добавить»), чтобы добавить следующие ограничения:

• Значения ячеек решений должны находиться в интервале от 0 до какого-то разумного максимума (мы выбрали 50, даже несмотря на то, что это вероятно намного большее предельное значение, чем нужно). Также необходимо задать каждой ячейке решения ограничение "= integer" («цел»), потому что у нас не может быть дробной части вооружения, а Excel Solver считает по умолчанию каждую переменную вещественным числом, если не указать обратное.

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

Теперь мы нажмём на кнопку Solve («Найти решение») и после краткого ожидания Solver заполнит значения Quantity, что даст нам следующее:

• 1 Machine Gun
• 3 Rockets
• 2 MegaRockets
• 1 Laser
• 1 UltraLaser

Всё это даёт нам общий урон в 83 единиц и занимает ровно 50 тонн, 100 кредитов и 3 критических слота. Можно увидеть, что наилучшее решение не меняется от времени выполнения Solver. Если сбросить эти значения и выполнить повторную оптимизацию, или перейти в Options и изменить seed, то мы всё равно получим те же значения. Мы не можем быть уверенными на 100%, что это решение оптимально, но с учётом того, что у Solver не получилось усовершенствовать его после нескольких проходов оптимизации, то с большой вероятностью он и является реальным оптимумом, а не просто локальным максимумом.

Задача решена!

Дополнительные способы использования

Здорово здесь то, что мы не только решили задачу гораздо быстрее, чем справились бы вручную, но и настроили её таким образом, что она позволит протестировать, какое оружие в игре SuperTank будет наиболее полезно с разными параметрами (вес, стоимость, критические слоты). Это значит, что мы сможем относительно просто изменить влияние различных изменений этих параметров на игру SuperTank, и если мы захотим добавить новую альтернативную модель супертанка, который будет легче, тяжелее или иметь другое количество критических слотов, то это можно будет сделать очень просто.

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

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

Чтобы понять, что я имею в виду, перейдите к синей ячейке «Max Cost» и измените её значение с 100 на 99. Теперь запустите Solver заново, и вы получите совершенно другую схему размещения оружия:

• 0 Machine Guns
• 2 Rockets
• 3 MegaRockets
• 3 Lasers
• 0 UltraLasers

Такая схема даёт чуть меньший показатель урона (82 вместо 83), но она радикально отличается от предыдущей.

Если присвоить Max Cost значение 101 или 102, и выполнить расчёт заново, то есть вероятность, что мы получим конфигурацию, похожую первой или совпадающую с ней; как бы то ни было, урон останется равным 83 (схемы могут меняться, потому что в таких случаях есть несколько оптимальных схем). Однако если присвоить Max Cost значение 103, то вы должны получить следующее:

• 1 Machine Gun
• 4 Rockets
• 2 MegaRockets
• 0 Lasers
• 1 UltraLaser

Что увеличивает общий урон до 84.

Это интересно: такая схема размещения оружия очень отличается от первых двух.


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

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

Телепорты-«червоточины»

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

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

Допустим, вы работаете над космической MMORPG. Однажды ваш ведущий дизайнер подходит к вам с видимой тревогой на лице. «Мы завершаем редизайн сектора Омега», — говорит он. «И у нас возникла проблема. Мы планируем добавить несколько телепортов-»червоточин" в этом сегменте мира, но не можем договориться, где их размещать".

«Сколько телепортов?», — спрашиваете вы.

«Мы пока не знаем. Вероятно, три, но их может быть от двух до четырёх. Мы ещё не уверены». Потом он показывает вам карту, которая выглядит вот так:


«Что это?», — спрашиваете вы.

«Это карта сектора Омега. Или, по крайней мере, звёздные системы, которые игрок может посетить в этом квадранте. Нам нужно определить, в каких клетках должны быть „червоточины“».

«Ну ладно, а по каким правилам они размещаются? Можно ли размещать „червоточину“ в одном квадранте со звёздной системой?»

«Мы хотим, чтобы ты разместил „червоточины“ таким образом, чтобы минимизировать расстояние от любой звёздной системы до ближайшей „червоточины“. И да, можно помещать их в тот же квадрант, что и звёздная система; это просто небольшие телепорты, висящие в космосе, поэтому их можно помещать где угодно. И помни, что мы ещё не решили, сколько их должно быть, так что дай мне решения для 2, 3 и 4 „червоточин“».

Как сформулировать эту задачу, и как её решить?

Оптимизируем телепорты!

Давайте начнём с подготовки ячеек решений. Обозначим четыре телепорта как A, B, C и D. Мы знаем, что каждый телепорт по сути является не чем иным, как координатами (x,y) на звёздной карте сектора Омега. Также мы знаем, что нам понадобится какой-то способ указания количества активных телепортов, поэтому мы добавим ячейку, позволяющую задать количество телепортов. Телепорт D мы используем только в случае, когда используются 4 «червоточины», а C — только когда у нас есть 3 или больше.


Ниже мы подготовим таблицу для вычисления расстояния от каждой звёздной системы до ближайшего телепорта. Эта таблица выглядит так:


Слева синим показаны координаты каждой звёздной системы на карте. Каждая строка — это одна звёздная система. Мы просто перенесли их из карты сектора Омега, которую нам дал ведущий дизайнер.

Справа мы вычисляем расстояние до каждого из четырёх телепортов. Это просто теорема Пифагора. Расстояние вычисляется как квадратный корень из горизонтального и вертикального расстояния между звёздной системой и телепортом:

=SQRT(($B14-Ax)^2+($C14-Ay)^2)

(Не волнуйтесь — я обещаю, что это самая сложная математика, которая нам встретится в серии!)

Мы берём координаты X и Y каждой звёздной системы из синих ячеек таблицы выше, а координаты X и Y каждого телепорта (ячейки с названиями Ax и Ay для телепорта A в показанной выше функции SQRT()) — из жёлтых ячеек решений сверху.

Наконец, мы берём минимум из этих четырёх значений в столбце Dist to Closest, то есть просто используем функцию MIN() для определения минимума четырёх значений слева. Затем мы внизу суммируем весь столбец; сумма и является ячейкой цели.

Вы могли заметить, что на скриншоте выше все ячейки имеют значение Dist to D. Причина в том, что мы используем ячейку «Number of Teleporters?» в верхнем разделе модели решений, позволяющую настроить количество учитываемых телепортов. Если количество телепортов равно 2, то мы используем значение 99 и в Dist to C, и в Dist to D, а если оно равно 3, то значение 99 используется только в столбце Dist to D. Благодаря этому каждая звёздная система будет игнорировать все лишние телепорты при вычислении расстояния до ближайшего телепорта в случае 2 или 3 телепортов.

Теперь мы запустим Solver:


Ячейка цели — это сумма внизу столбца Dist to Closest. Заметьте, что в отличие от других примеров, здесь мы хотим использовать радиокнопку «To: Min» («До: Минимум»), потому что нам нужно минимальное расстояние между всеми звёздными системами и телепортами, а не максимум.

Ниже мы укажем в качестве ячеек решений («By Changing Variable Cells») восемь жёлтых ячеек решений координат X и Y «червоточин» A, B, C и D. В разделе ограничений мы ограничим каждую из координат как целочисленное значение в интервале от 0 до 12. Заметьте, что мы используем для этих ячеек решений целочисленное ограничение, потому что подразумеваем, что ведущий дизайнер просто хочет знать, в какой ячейке будет каждый телепорт, но мы можем запросто пропустить это ограничение, если бы дизайнеру понадобились вещественные координаты.

Если мы зададим для «Number of Teleporters?» значения 2, 3 и 4, и последовательно будем запускать Solver при каждом значении, то получим следующие конфигурации:


Имея эту информацию, мы можем подойти к ведущему дизайнеру и показать ему оптимальные места для расположения любого количества телепортов в интервале от 2 до 4. Вот как оптимальные расположения «червоточин» для 2, 3 и 4 телепортов выглядят на карте (показаны зелёным).


Электронную таблицу для этого примера можно скачать отсюда.

Я говорил о ниндзя?

«Потрясающе», — говорит ведущий дизайнер, но на лице его вы видите страдание. «Эээ, но я забыл сказать тебе, что некоторые из этих систем населены космическими ниндзя. И мы хотим, чтобы системы с ниндзя были дальше от „червоточин“, чтобы игроки не ощущали чрезмерной угрозы».

«Ого. Это полностью меняет дело».

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


Он продолжает: «Каждое отрицательное число — это колония космических ниндзя. Система с числом 2 содержит две человеческие колонии, а с числом -2 — две колонии ниндзя. Можешь сказать, где разместить телепорты в этом случае?»

«Скажи, ну вы хотя бы решили уже, сколько будет телепортов: 2, 3 или 4?», — спрашиваете вы язвительно.

«Боюсь, что пока нет».

Решаем с учётом ниндзя

Чтобы решить эту задачу, нам нужно добавить в таблицу новый столбец, обозначающий веса таблицы. Мы назовём его «множителем» (multiplier). Мы просто будем умножать это значение на значение в столбце «Dist to Closest».

Когда мы это делаем, Dist to Closest слегка изменяет свой смысл. Теперь это не расстояние до ближайшей звёздной системы, потому что для звёздных систем ниндзя значение меняется в -1 раз. Оно больше напоминает обобщённые «очки» (score), поэтому давайте так их и назовём.


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

Теперь мы получаем следующие результаты:


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


Электронную таблицу для этой расширенной версии примера с телепортами можно скачать отсюда.

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

Эта задача относится к классу задач, называемых «задачами о размещении объектов», которые очень хорошо изучены в области оперативного управления. Но как видите, потенциально их можно применять и в гейм-дизайне, а также в дизайне уровней, а решение просто (если не тривиально) находится в Excel.

Балансировка классов для боёв Player-vs-Player

Электронную таблицу для этой части можно скачать отсюда: ссылка

Электронные таблицы и симуляции

В предыдущих трёх частях этой серии статей мы познакомились с концепцией моделирования и оптимизации решений, а также с инструментом «Поиск решений» (Solver) пакета Excel. Мы показали, как их можно использовать для вычисления оптимальных налоговых ставок города в 4X-стратегии, для определения оптимального размещения телепортов в космической игре и для выбора оптимальной схемы расположения оружия для задачи с супертанком, описанной в первой части.

Возникает естественный вопрос: а как насчёт балансировки игры? Можно ли применять подобные техники к всевозможным видам задач сложной балансировки, которые встречаются во множестве разных типов игр, в частности, в стратегиях, RPG и MMORPG?

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

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

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

Поэтому лучшее, на что нам стоит надеяться — это демонстрация простого примера, иллюстрирующего общий подход к задачам такого типа: на простом примере в Excel мы узнаем, как подходить к формулировке такого типа задач балансировки и оптимизировать их. Мы покажем, что по крайней мере для примера простого боя Solver может хорошо выполнять балансировку нескольких RPG-классов относительно друг друга. Потом вы сможете использовать эту базовую структуру как основу для решения подобных задач оптимизации с более сложной схемой и глубже интегрированных в симуляцию игры.

Мы надеемся, что вместе с нами вы изучите все хитрости и увидите, что нам может дать этот простой пример.

Балансировка не определена

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

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

Некоторые игроки склонны считать, что балансировка в бою означает равный урон. Это особенно относится к MMORPG, в которых игроки часто жалуются, что величина урона в секунду (damage per second, DPS) одного класса слишком мала или слишком велика относительно других.

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

Крошечная MMO

Представьте, что мы создаём новый проект, очень упрощённую многопользовательскую массовую онлайновую ролевую игру под названием «Tiny MMO». В рамках разработки дизайна мы стремимся сбалансировать четыре класса для боёв «игрок против игрока» (PVP) таким образом, чтобы все четыре класса были относительно равными в бою друг против друга, и чтобы не было явного «лучшего» или «худшего» класса, которым можно сражаться против других классов.

Хоть «Tiny MMO» и является игрой реального времени, действие каждого игрока длится ровно 3 секунды, поэтому мы можем дискретизировать её, представив в виде пошаговой игры, в которой каждый ход является трёхсекундной долей геймплея.

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

• Warrior (Воин) наносит наибольший урон
• Mage (Маг) кастует заклинания на расстоянии и имеет набольшую дальность атаки из всех четырёх классов
• Healer (Хилер) автоматически лечится, восстанавливая за каждый ход определённую часть своего здоровья
• Barbarian (Варвар) имеет больше всего здоровья

Это всё, что мы знаем об этих четырёх классах, и нам нужно задать изначальные параметры здоровья (HP), урона, лечения и дальности атак для всех четырёх классов. Нам нужно сбалансировать их таким образом, чтобы каждый класс был уникальным и его характеристики значительно отличались от всех других классов, но чтобы в результате каждый класс оказался как можно более «сбалансированным» относительно трёх остальных.

Другими словами, мы стремимся оптимизировать следующую таблицу:


Пока мы используем временные значения и предполагаем, что каждый класс начинает с 50 HP, наносит при атаке 10 единиц урона за ход, излечивает 0 HP за ход и имеет дальность атаки 40 метров. Каждый персонаж движется со скоростью 10 метров за ход. Так как в дизайне указано, что все четыре класса персонажей могут двигаться с одной скоростью, то мы будем считать это значение постоянным, и не станем вносить скорость движения в таблицу переменных решений.

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

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

Таблица побед

Нам нужно сбалансировать четыре класса с каждым другим в бою один на один. Так как у нас только 4 класса (Warrior, Mage, Healer и Barbarian), то всего есть 6 возможных комбинаций разных классов:

• Warrior — Mage
• Warrior — Healer
• Warrior — Barbarian
• Mage — Healer
• Mage — Barbarian
• Healer — Barbarian

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


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

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


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

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

«Симулятор боя»

Расположим каждую пару классов на расстоянии 100 метров друг от друга. Каждый персонаж имеет 3 секунды на атаку, поэтому мы можем представить это как пошаговую симуляцию, в которой каждый «ход» обозначает 3 секунды. На каждом «ходу» каждый персонаж или атакует другого, если он находится в пределах дальности атаки, или продолжает двигаться, чтобы сократить расстояние.

Симуляция выглядит так:


Наверху показана пара персонажей, вступивших в бой: в данном случае это Mage (класс 1) и Healer (класс 2). В левом столбце показано текущее расстояние между двумя симулируемыми персонажами.

Для каждого персонажа столбцы будут такими:

• Max Range: это максимальное расстояние, на котором персонаж может атаковать. Оно берётся непосредственно из жёлтых переменных решений в таблице переменных решений.
• Healing: это величина лечения персонажа за ход, получаемая непосредственно из таблицы переменных решений.
• HP: это здоровье персонажа в каждом ходе. Изначально оно равно соответствующему значению HP из таблицы переменных решений, но со временем при атаках другого персонажа уменьшается. Также оно увеличивается в каждом ходе на величину лечения, которую персонаж может применить к себе в каждом ходе.
• Damage: величина урона, наносимого персонажем врагу, когда тот находится в пределах дальности атаки. Когда персонаж умирает, это значение снижается до 0.
• Attacks?: этот столбец проверяет, находится ли персонаж в пределах дальности атаки. Если да, то это будет означать, что в текущем ходе персонаж атакует; если нет, то персонаж перемещается ближе, чтобы дойти до другого персонажа.

Таким образом, оба персонажа начинают двигаться друг к другу, а затем атакуют, пока один из них или оба не умрут. Каждый персонаж перемещается за каждые 3 секунды на 5 метров (5 метров за «ход»). Когда оба персонажа движутся друг к другу, то Range будет изменяться в каждом ходу на 10 единиц, и на 5 единиц, если движется только один из них. Сама игра структурирована так, что оба персонажа могут начать двигаться одновременно, после чего ход разрешается одновременно, поэтому вполне возможно, что оба персонажа могут умереть одновременно.

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

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

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

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

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


И. наконец, Score комбинирует длительность и общую сумму хитпоинтов в виде ( Duration / ( 1 + Total HP ) ). Заметьте, что мы прибавили к делителю 1, потому что Total HP может быть равно 0, и в таком случае мы бы получили ошибку деления на ноль. Таким образом мы можем гарантировать, что вознаграждаем оптимизатор за нахождение максимальной длительности боя и минимального значения суммы хитпоинтов.

(Заметьте, что поскольку в каждой «симуляции» боя класса против класса у нас есть 17 строк. Это значит, что мы по сути приняли дизайнерское решение о том, что бой должен длиться примерно 17 раундов. Если мы хотим, чтобы бой был короче или дольше, то можно изменить количество строк, соответствующим образом отредактировать формулы подсчёта оценки и выполнить повторную оптимизацию.)

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

Можно просто суммировать эти шесть значений оценок и использовать результат как финальное значение Score. Однако, если мы это сделаем, то Solver с большой вероятностью не сможет найти хорошего баланса между наибольшей и наименьшей оценкой для отдельных боёв, а также получит очень высокие оценки для некоторых пар классов и низкие оценки для других. Мы хотим не этого: нам нужно чтобы все оценки были высокими и мы стремимся повышать их все. Чтобы исправить это, мы умножим сумму оценок на наименьшую оценку в группе (с помощью функции Excel MIN()), чтобы заставить Solver сосредоточиться на оценках с наименьшим значением.

Добавляем ограничения

Мы пока не закончили. Если оптимизировать модель решений с текущими параметрами, то, скорее всего, классы будут настроены неправильно — на самом деле, высока вероятность, что модель запишет в таблицу переменных решений одинаковые значения HP, Damage, Healing и Range.

А мы, разумеется, хотим, чтобы у каждого класса была собственная индивидуальность. Нам нужно, чтобы Warrior наносил наибольший урон, Mage имел самый большой Range, Healer имел максимальное значение Healing, а Barbarian обладал наибольшим HP. Также мы хотим, чтобы эти различия не были слишком маленькими — нам нужно чтобы, эти классы сильно отличались друг от друга.

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


В таблице Min difference справа указана минимальная разность каждого атрибута класса относительно всех других классов. Другими словами, Warrior должен иметь по крайней мере на 4 HP больше урона, чем все другие классы, Mage должен иметь дальность атаки по крайней мере на 10 больше, и так далее.

Теперь, когда мы добавили эти особые ограничения, настало время оптимизировать!

Поиск решений

Теперь мы можем запустить встроенный в Excel инструмент Solver («Поиск решений»), чтобы попытаться оптимизировать исходные параметры. В качестве ячейки цели мы выберем ячейку Score, которая комбинирует результаты всех шести турниров. Мы задаём переменные решений так, чтобы включить в них все 16 ячеек в жёлтой таблице Decision variables, которую мы создали в начале.

Также мы задаём ограничения (в поле Subject to the Constraints) следующим образом:

• Все ячейки решений должны быть целочисленными с минимальным значением 0.
• Все ячейки в столбце HP должны иметь максимальное значение 200 и минимальное 30.
• Все ячейки в столбце Damage имеют максимальное значение 20.
• Все ячейки в столбце Healing имеют максимальное значение 15.
• Все ячейки в столбце Range имеют максимальное значение 100.
• Кроме того, все четыре ячейки в особом разделе Constraints должны иметь значение 1, чтобы удовлетворялись их особые условия.

Наконец, выберем в качестве Solving Method значение Evolutionary и запустим Solver. Учтите, так как это эволюционный алгоритм, существует вероятность улучшения найденного решения при втором или третьем прогоне Solver, или после настройки параметров (кнопка Options) для эволюционной оптимизации.

В результате у нас должно получиться нечто подобное:


… и как по волшебству Solver дал нам хорошую исходную конфигурацию баланса.

Как видите, Warrior теперь наносит наибольший урон, Mage имеет наибольшую дальность, Healer лучше всех лечит, а у Barbarian больше всех HP. Кроме того, можно опуститься к результатам отдельных турниров «класс против класса» и увидеть, как классы проявили себя в бою друг с другом; как видно, большинство из них сбалансировано очень равномерно — к концу боя оба класса умирают, или один из них едва выживает. К тому же все турниры длятся достаточно долго, ни один из классов не может «ваншотнуть» другой.

Неплохо для нескольких часов работы, правда?

Заключение

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

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