Я обожаю RPG, меня привлекают их богатый сюжет, стратегическая глубина и захватывающие миры. Также меня восхищают data-driven подходы к разработке. Они не только улучшают логическую структуру игровых механик, но и гарантируют, что каждый элемент игры сбалансирован и вносит значимый вклад в опыт игрока. Баланс - один из самых сложных аспектов разработки игр, поскольку он требует тщательного внимания к взаимодействию игровых механик. Сегодня я расскажу о том, как использовать линейную алгебру для баланса стоимости предметов в игре.
В чём проблема?
Допустим, мы добавили в нашу игры базовые предметы, которые добавляют скорость атаки, урон, ману и т.д. На основе таких предметов довольно легко создать новые: например, в игре существует меч, дающий + 3 урона, стоит он 30 монет. Не составит труда оценить меч, дающий +9 урона: единица урона стоит 10 монет, следовательно, второй меч будет стоить примерно 90 монет. О том, почему примерно, мы поговорим дальше.
Но что если вы набросали несколько предметов, дающих разное количество характеристик, протестировали их, но их стоимость нельзя явно выразить через эти характеристики? Рассмотрим упрощенный пример:
Топор берсерка: дает 9 единиц урона и 2 единицы скорости атаки, стоит 40 монет,
Кинжал трикстера: 4 урона и 8 скорости атаки, стоит 35 монет,
Меч тамплиера: 5 урона и 5 скорости атаки, стоит 38 монет.
Это оружие можно представить в виде линейного уравнения:
Эта система не имеет решения, значит ли это что мы что-то сделали не так и теперь мы не можем балансить игру? Не совсем.
![Система не имеет решения Система не имеет решения](https://habrastorage.org/getpro/habr/upload_files/34b/c45/3fe/34bc453fef3536dc2ba9e1ac869a2176.png)
Применим линейную алгебру
Давайте попробуем решить эту систему уравнений иначе. Для этого запишем её в матричной форме:
где ?- матрица коэффициентов, ? - вектор переменных, и ? - постоянный вектор.
Обычно такие системы решаются с помощью обратных матриц:
Дело в том, что все нижеописанные операции можно автоматизировать в каком-нибудь wolfram или математических библиотеках для python, поэтому, если вам неинтересно как именно мы пытаемся найти решение системы уравнений, прочитайте спойлер и листайте до следующего заголовка).
Hidden text
В результате всех этих упражнений, система уравнений всё ещё не имеет решения
Чтобы определить, имеет ли данная система решение, мы исследуем ранг матрицы A и ранг расширенной матрицы Если ранг A меньше ранга расширенной матрицы, то система противоречива и не имеет решения. Запишем расширенную матрицу:
Чтобы найти ранг, мы можем выполнить операции над строками матрицы , чтобы свести ее к ступенчатому виду:
Вычтем 4/9 раз первый столбец из второго, получим:
Вычтем 5/9 раз первый столбец из третьего, получим:
Эта ступенчатая форма строк показывает, что матрица имеет полный ранг (ранг 2), что означает, что исходные уравнения линейно независимы.
Теперь рассчитаем ранг расширенной матрицы Для этого также вычтем
раз первый столбец из второго и
раз из третьего:
Упростим матрицу ещё сильнее: вычтем из третьего ряда второй, умноженный на :
Ранг дополненной матрицы равен 3, что больше, чем ранг
, который равен 2.
Собственно, мы ещё раз доказали, что система уравнений противоречива и не имеет решения.
Так что же делать или Мура-Пенроуза
Мы исследовали эту систему уравнений со всех сторон, убедились в том, что она не имеет решений, неужели мы не сможем теперь высчитывать стоимость новых предметов в игре исходя только из их характеристик? Конечно, сможем. Именно на тот случай, когда не существует явного решения, человечество придумало псевдо-решения.
Давайте сначала разберёмся, что именно значит "система не имеет решения". Матричная запись предполагает поиск обратной матрицы
, но когда система не имеет решения, этой матрицы просто не существует. Однако, в начале-середине прошлого века два математика Элиаким Мур и Роджер Пенроуз сформулировали концепцию псевдообратной матрицы.
Псевдообращение можно понимать как решение задачи поиска наиболее близкого приближения к правильному решению (простите за тавтологию) системы линейных уравнений по методу наименьших квадратов.
Если говорить по-человечески: хоть мы и не можем найти решение системы уравнений (то есть стоимость каждой характеристики оружия), просто потому что его нет, но мы можем найти наиболее правдоподобное, которое будет наиболее близким к каждому из решений для всех уравнений.
То есть теперь мы имеем следующую формулу:
Дальше мы найдём псевдообратную матрицу. Если вам неинтересен и этот процесс, то снова прочитайте спойлер и листайте к результату.
Hidden text
Начнём с формулы расчёта псевдообратной матрицы
Посчитаем :
Теперь перейдём к (
где - определитель
, а
- сопряжённая матрица
Ну и отсюда следует, что:
Теперь вычислим саму псевдообратную матрицу:
Результат
значения, которые мы получаем из представляют собой оптимальную стоимость каждой единицы урона и скорости атаки, рассчитанную по методу наименьших квадратов. Эти значения могут не полностью совпадать с первоначальной стоимостью предметов, но они предлагают последовательную стратегию ценообразования, которая наилучшим образом уравновешивает различные атрибуты всех предметов.
Приближенное решение с использованием псевдоинверсии Мура-Пенроуза дает нам следующую стоимость характеристик:
Стоимость единицы урона (
): примерно 4.01 монеты
-
Стоимость единицы скорости атаки (
): примерно 2.68 монеты
Эти значения говорят о том, что для баланса затрат по всем предметам каждое очко урона должно стоить 4.01 монеты, а каждое очко скорости атаки 2.68 монеты.
Вывод
Используя псевдоинверсию Мура-Пенроуза, мы можем устранить несоответствие в исходной стоимости предметов и найти приближенное решение, которое уравновешивает стоимость каждого атрибута для всех предметов.
Однако, помните, что результаты, полученные в результате вычислений не обязательно должны быть истиной в последней инстанции. Экспериментируйте, накладывайте на вычисленные стоимости предметов шум, тестируйте это всё в игре, ведь в конце концов главное - не справедливость распределения стоимости атрибутов и максимальная выверенность всех метрик, а фан от игры.
Если вам интересны такого рода посты, можете подписаться на моq telegram, там я пишу посты поменьше
Комментарии (24)
ildarz
19.08.2024 10:54+5Все это очень интересно, только насколько это вообще применимо на практике? Совершенно непонятно, почему стоимость предметов в RPG вообще должна напрямую зависеть именно от их характеристик. Если игрок покупает предметы за некие денежные единицы - очевидно, в игре есть некая экономика, в рамках которой игрок денежные единицы добывает и тратит. Сравнительная ценность предмета экипировки и денег становится ясна только и исключительно в рамках этой экономики, и определяется балансом доходов/расходов игрока и (отчасти) объективной необходимостью в этой экипировке. Отчасти - потому что при избытке денег игроки, как правило, склонны покупать даже объективно не нужные предметы, если на них больше плюсов, или если они просто куколку одевают.
Простейший вырожденный пример - если у игрока миллион монет, в игре есть два меча (с 9 и 3 единицами урона), то в границах от 1 монеты до этого самого миллиона вы можете выставить на оба меча абсолютно любую цену - игрок все равно купит меч с 9 и не купит с 3. Т.е. реальная цена меча с 3 единицами равна нулю. Понятно, почему? Высчитывать на этом фоне цену через системы уравнений просто не имеет никакого смысла.
youngmysteriouslight
19.08.2024 10:54+3Если в игре есть экономика, то она устанавливает стоимость предмета. Но для этого она должна быть, включая 1) механику купли-продажи, 2) наличие спроса и предложение (достаточное число игроков). Если игроки разводятся по инстансам и вообще это одиночная РПГ, то экономики не будет.
Полезность метода вот в чём. Допустим, игроделы выпустили прототип игры, собрали данные от тестеров, понерфили-побалансировали характеристики, включая цену, выпустили в народ. А затем начали клепать контент, включая предметы в большом количестве. Какие характеристики установить, чтобы не надо было дополнительно балансировать их?
Предлагается все, кроме цены, взять с потолка, а цену рассчитать по формуле.
Я так вижу практическую значимость статьи. Другое дело, линейное приближение мне кажется плохим. Вон выше уже написали об этом, а кроме того в дуэлях единица урона может отделять победу, так что в тех случаях цена может быть очень нелинейной.
Tiriet
19.08.2024 10:54+2Кмк, в описанной задаче вообще нет возможности найти хорошее приближение. у нас банально отсутствует возможность сравнивать итоговую "ценность" оружия и определять, что считается "хорошее" а что- "плохое" приближение.
Автор привел три характеристики оружия, взятых с потолка- урон, скорость, цена. И почему-то решил, что между этими характеристиками есть какая-то связь, и что эта связь близка к линейной. А дальше с этой гипотезой начал строить математику уровня первого курса технаря.
Меч с +3 урона стоит 10 монет. а меч с +9 урона стоит 90 монет. А какой вообще базовый урон? если он 100, то тогда меч, который лучше на 6%, стоит дороже в 9 раз. что выглядит неоправданным. Правда, если все бегают с хелсом на 108, первый меч валит в двух ударов, а второй меч- с одного, и потому второй просто невозможно победить, а значит и преплата за уберфичу скромна и незаметна.
А если базовый урон 3, то меч, дающий урона в 2 раза больше стоит примерно в 2^3 раз дороже- кубическая зависимость уже наверное норм. Опять же, если стоимость добычи монеты не запредельно высока и не пренебрежимо мала. Правда, если все бегают в броне на +5, то меч с уроном 3+3 получается в 11 раз хуже меча с уроном 3+9.
Была такая игра, Князь называлась. РПГ отечественная. И был там, как помню, такой момент, что для прохождения нужно было взять меч с уроном +100 (нормальный урон оружия был в районе 10-15, емнип). А чтобы взять меч с уроном +100, надо было сначала надеть "трусы" с "сила+100". А без этих трусов нельзя взять меч, а без этого меча нельзя было завалить главгада. Вопрос- сколько стоил меч, если обычное оружие на +Х стоило 5X монет, а обычные трусы на "сила+Y" стоили 2Y монет? И с учетом того, что без этого меча главгад не валится никак, просто потому что к нему двери не открываются?
Получается, что применять линейные аппроксимации к сильно нелинейным задачам с со скрытыми параметрами- бесперспективная затея. Баланс в старкрафте патчили много-много лет- потому что даже в его сравнительно простой боевой системе огромное количество нелинейных связей между параметрами юнитов и их групп.
CBET_TbMbI
19.08.2024 10:54+2только насколько это вообще применимо на практике?
Вообще не применимо. Вернее, применить можно. Но смысла в этом нет.
Это не приближает ни геймдизайнера к ответу "каким надо сделать меч, чтобы он не ломал баланс", ни игрока к ответу "этот меч стоит того, чтобы его купить или нет".
Вопрос автору на миллион.
Стоимость единицы урона (
): примерно 4.01 монеты
-
Стоимость единицы скорости атаки (
): примерно 2.68 монеты
Эти значения говорят о том, что для баланса затрат по всем предметам каждое очко урона должно стоить 4.01 монеты, а каждое очко скорости атаки 2.68 монеты.
А что если какая-то из этих характеристик бесполезна? Например, динамика обмена ударами насколько медленная, что скорость атаки вообще не влияет на ход боя?
Ты определил её стоимость исходя из цен, которые сам и назначил. Но это ни капли не говорит о том, сколько она на самом деле стоит. Если она бесполезна, то её цена будут ноль! И хоть за миллион продавай меч с этой скоростью, полезней он от этого не станет. Может быть и обратная ситуация, когда реальная стоимость некого параметра может уходить в бесконечность (но это значит, что с механикой и балансом не лады).
И это я ещё молчу, что полезность характеристик может быть не линейной.
saboteur_kiev
19.08.2024 10:54+4Как человек, который балансил mmorpg, скажу что весь баланс делается в формуле урона, и лимиты должны быть или прямо в этой формуле, или в формуле по которой создаются/апгрейдятся вещи. Но лучше в формуле урона, чтобы не было возможности "нарисовать слишком крутой предмет". Там в эту формулу еще и безопасность от "админишков" надо встраивать сразу..
Ну и да, кучи моментов с формулами могут быть завязаны на скорость.Например ты наносишь урон 300.
Монстра с 500 здоровья ты сносишь за 2 удара
При уроне в 500 ты сносишь за 1 удар. И получается что 300 и 499 ничем не отличаются, а 499 и 500 в два раза для конкретного монстра. Дотошные игроки могут выискивать на чем могут качаться почти в два раза быстрее, и это не баг а фича, ибо этот момент вообще невозможно сбалансировать.A_Anonimov
19.08.2024 10:54Но разве это не должно гаситься разнообразием мобов? Если помимо монстра с 500 здоровья будет монстр с 400 здоровья, меч на 300 урона все так же будет убивать его за 2 удара, а с 499 - ваншотнет.
То есть, чем больше вариантов мобов, тем ближе фактическая игра к модельным условиям
EpiSH
19.08.2024 10:54насколько это вообще применимо на практике?
Мне кажется, что это применимо только в Диаблоидах и прочих играх с рандомными характеристиками предметов. Например, у нас может сгенерироваться "меч от 2 до 10 урона и от 0 до 5 скорости атаки". Мы полноценно (то есть с учетом игровой экономики и формулы dps) определяем цены худшей (+2/+0) и лучшей (+10/+5) генерации и с помощью линейной зависимости можем вычислять все остальные промежуточные варианты прямо в процессе дропа. При чем для другого типа оружия и с мечами для более поздней игры стоимости единицы характеристики будет другой.
ildarz
19.08.2024 10:54+1Могу ошибаться, но вроде бы там применяется другой подход - у каждой вещи есть "бюджет" характеристик, который может быть разбит между разными типами усилений. Т.е., абстрактно говоря, есть 10 очков, единица урона стоит 1 очко, единица крита - 2, единица скорости - 2, и т.п. Вещи с одинаковым бюджетом считаются условно равнозначными, балансировка делается путем изменения стоимости статов в этих "бюджетных" очках, а вендорская стоимость предметов в игровой валюте уже является некой производной от одной игромеханической цифры - этого самого бюджета вещи. Дальше мы говорим "в этой локации падают вещи с бюджетом 100" и, имея таблицу стоимости статов в бюджетных очках, спокойно на лету генерим характеристики.
EpiSH
19.08.2024 10:54единица урона стоит 1 очко, единица крита - 2, единица скорости - 2
Так надо же сначала как-то определить сколько стоит единица урона, крита, скорости. И если зависимость линейная, то метод из статьи как раз подходит, вне зависимости определяем цену в магазине или определяем условную ценность для генератора дропа.
ildarz
19.08.2024 10:54В том-то и дело, что цена в магазине тут вообще ни при чем - экономика при таком подходе балансируется фактически отдельно от игромеханики. У меня ведь вопрос был не к балансировке параметров предметов как таковых, а именно в прямой привязке этого процесса к экономике.
Andy_U
19.08.2024 10:54+2А эта "псевдообратная" матрица, это не та же самая, что в обычном методе наименьших квадратов?
randomsimplenumber
19.08.2024 10:54+6Вы не описали, что такое баланс, и сразу принялись его оптимизировать математической магией..
GospodinKolhoznik
19.08.2024 10:54+5Описан стандартный подход решения задачи, содержащей в исходных данных погрешности - минимизация суммы квадратов ошибок.
Другое дело, что как в реальной жизни, так и в рпг интереснее, когда стоимость любого товара зависит от его качества не линейно, а по экспоненте - и если для дешёвого орудия (любой вещи) небольшая прибавка в стоимости даёт существенную прибавку к качеству, то для дорогих орудий увеличение качества на пару процентов приводит к возрастанию цены в разы, если не в сотни раз.
А в вашей линейной модели скрипка Страдивари будет стоить в 2-3 раза дороже скрипки с АлиЭкспресс.
EvgeniyDobro
19.08.2024 10:54+2Я не понял при чем тут баланс в игре.
Получается мы взяли уже готовую игру и начали рассчитывать стоимость уже заданных характеристик ? а зачем?
не интереснее ли самим придумать и рассчитать свою систему оценки характеристик ? и тогда не будет нерешенных уравнений.
Acid_Bl4ck
19.08.2024 10:54Там уже выше накидали критики резонной, добавлю только следующее
Эта система не имеет решения, значит ли это что мы что-то сделали не так и теперь мы не можем балансить игру?
Таки да, значит. Если у изначальной системы нет простого алгебраического решения, значит предметы из примера не сбалансированы. Вопрос: а чего хочет добиться автор? Взять не сбалансированный набор снаряжения и сделать еще больше подобного? А почему изначальный набор не сбалансирован? Потому что характеристики проставлялись от балды, а теперь мы между ними ищем зависимость?
Короче, Вот так, с помощью нехитрых приспособлений буханку белого (или чёрного) хлеба можно превратить в троллейбус.
playermet
19.08.2024 10:54А почему изначальный набор не сбалансирован?
Потому что в любой RPG есть прогрессия характеристик, в том числе у предметов. Игра начинается с "[мусор] ржавый железный ножик", и заканчивается с "[мифический] зачарованный адамантиевый убийца-богов". А если прям идеально сбалансировать все предметы до одинаковой полезности то у них просто будет одинаковая цена.
Acid_Bl4ck
19.08.2024 10:54Спасибо, кэп. Только то, что конкретно в этом наборе есть какая-то прогрессия - ничем не подкрепленный домысел. В этом тексте нет вообще никакого контекста об игре или о наборе снаряжения. Единственное, что автор предполагает (неявно), что этот набор сбалансирован, т.к. он пытается из этого набора вывести какие-то зависимости.
Первый закон логики говорит, что из истины можно получить истину, из лжи можно получить что угодно. Так что если мы пытаемся выводить какие-то зависимости и делать какие-то выводы, следовало бы озаботиться тем, чтобы изначальный датасет был истинным.
Только дисбаланс там очевиден, потому что снаряжение с большим количеством статов (независимо от конкретных формул урона) стоит меньше денег. И не сбалансированы они не между собой а по соотношению польза/цена.
И это я еще не затрагиваю тему того, что почти наверное считать суммарную пользу этого снаряжения как сумму скорости атаки и урона не корректно, т.к. это не ортогональные характеристики - они обе являются составной частью DPS. Там чаще всего будет произведение. Хотя в некоторых приближениях можно и так, но это надо на конкретные случаи смотреть.
avshkol
19.08.2024 10:54Здесь уже много критики накидали, но я бы зашел вот с какой стороны:
Предположим, что каждый игрок - индивидуальный вычислитель и постоянно взвешивает для себя, насколько его ситуация улучшится:
Вариант 1 - если мы получим вещь Х, но лишимся денег Дх, и у нас останется запас (Д - Дх)
Вариант 2 - если мы сохраним деньги, но не получим вещь Х, и она будет доступна в следующих ходах (а там у нас будет другая ситуация с потребностью в вещи Х и с деньгами)
Вариант 3 - если мы сохраним деньги, но вещь Х будет недоступна И ее купит другой игрок, изменив свой баланс деньги/вещи (в плюс или в минус для нас - это может быть как соперник, так и союзник)
Вариант 4 - если мы сохраним деньги, но потом вещь Х будет недоступна, и уйдет с рынка (такие механики тоже бывают).
В этой ситуации ценность любой вещи может меняться от 0 до "многаденех", и оцениваться субъективно, поскольку каждый игрок субъективно оценивает риски...
А считать лучше с обратной стороны: при разработке игры принять единицу силы столько-то денег и не допускать сильно резких отклонений в цене, балансируя с общим ожидаемым запасом денег у игрока.
Ababaj
19.08.2024 10:54Смешно читать интерпретацию сути линейной алгебры АТишниками! Ранее надо было изучать основы ЛА! Ближайшее расстояние (ортогональное) по автору, только в конечномерном Евклидовом пространстве.
playermet
19.08.2024 10:54Экономика и стоимость оружия (и тем более других предметов) полностью зависят от геймплея и его видения разработчиком. В игре где можно подобрать оружие каждого убитого соперника, и в игре где оружие вообще не выпадает из противников экономика будет разной. В игре на 5 часов геймлея и на 50 экономика будет разной. В игре про иммерсивное выживание и казуальную мультяшку экономика будет разной. В игре где оружие сломается со временем и нет она будет разной. В игре где есть крафт оружия (или из оружия) и нет. В игре где подразумевается возможность заработка на торговле оружием и нет. В синглплеере и мультиплеере. В игре с гриндом и без. В игре с массовым производством и без. И еще множество других примеров, которые можно придумать.
Свести несколько линейных параметров в цену не слишком сложно. Сложней свести геймлейные показатели к линейным параметрам. Вот в статье делается предположение что линейное увеличение атаки линейно увеличивает его стоимость. Но если в RPG есть механика защиты (почти наверняка), которая например отнимается от прочности, фактический урон может отличаться в разы, причем по разному против разных противников, в зависимости скила персонажа, бафов, и т.д. и т.п. А ведь атака это простейший параметр, а предметы это не только оружие. Предметы могут давать сложные эффекты, вроде невидимостей, телепортаций, ситуационных бафов. Польза от предмета может сильно зависеть от билда игрока. Броня может иметь бонусы от сбора сетов. Предметы могут иметь улучшения с разным потенциалом (больше слотов, наприемр). Предмет может быть ресурсом, расходником, элементом крафта или декорацией. Предмет может быть редким или повсеместным. Может быть отдельная цена на покупку и продажу, или даже разные наборы цен в разных городах. Игрок может иметь возможность качать навык торговли или повышать отношение с торговцем, и иногда это следует учитывать.
Ну и само собой, стоимость предметов зависит от того, с какой скоростью игрок может зарабатывать деньги на соответствующем этапе игры. В статье несколько изначальных цен просто выбраны с потолка, а они выступают важнейшими стартовыми точками ценообразования в игре.
EpiSH
19.08.2024 10:54Всё так. Я не гейм дизайнер, но я бы для начала составил таблицу на каком уровне сколько денег в среднем должно скопиться у игрока (на основе формулы дропа, наград за квесты, трат на расходники и т.д.). И дальше, например всё шмотье 10го уровня оценивал по потенциальному кошельку среднестатистического игрока 10го уровня.
saboteur_kiev
19.08.2024 10:54но я бы для начала составил таблицу на каком уровне сколько денег в среднем должно скопиться у игрока
Так это ж зависит от игрока.
Один сидит, золото зарабатывает, другой бегает ресурвы выбивает, третий просто в рейдах просиживает.
Многие из подобных игр - ролевые, и отиграть за гнома или некроманта - разные вещи, плюс ну хочет человек сидеть в Гиране и торговать золотом с утра до вечера - флаг ему в руки.
saboteur_kiev
Интересное чисто математическое решение.
Но примеры не очень понятные. У вас же явно есть коэффициент на тип оружия, поскольку "Топор берсерка: дает 9 единиц урона и 2 единицы скорости атаки, стоит 40 монет, Кинжал трикстера: 4 урона и 8 скорости атаки, стоит 35 монет,"
В топоре 11 единиц за 40 монет, в кинжале 12 единиц за 35 монет.
Или единица атаки и урона стоят по разному, или коэффициент на тип/размер оружия разный. И тут формулы могут очень сильно упроститься, если знать эти коэффициенты.
В играх есть и другие аспекты, например персонаж может взять только один меч, а меч можно улучшить только на силу, тогда как лук улучшить только на ловкость - считается очень легко.
Но при этом если меч может дать сразу два параметра, то второстепенный может идти с коэффициентом. Или просто добавлять коэффициент, если предмет в принципе дает более одного параметра, плюс типы эффектов, например скажем damage - коэффициент 2, dextrity - 2, а cold_effect - 2.5 на каждую единицу значения. Плюс глобальный коэффициент на тип оружия, вроде двуручный топор должен давать больше чем маленький кинжал.
В результате все оружие просчитывается с элементарными формулами.