Я обожаю RPG, меня привлекают их богатый сюжет, стратегическая глубина и захватывающие миры. Также меня восхищают data-driven подходы к разработке. Они не только улучшают логическую структуру игровых механик, но и гарантируют, что каждый элемент игры сбалансирован и вносит значимый вклад в опыт игрока. Баланс - один из самых сложных аспектов разработки игр, поскольку он требует тщательного внимания к взаимодействию игровых механик. Сегодня я расскажу о том, как использовать линейную алгебру для баланса стоимости предметов в игре.
В чём проблема?
Допустим, мы добавили в нашу игры базовые предметы, которые добавляют скорость атаки, урон, ману и т.д. На основе таких предметов довольно легко создать новые: например, в игре существует меч, дающий + 3 урона, стоит он 30 монет. Не составит труда оценить меч, дающий +9 урона: единица урона стоит 10 монет, следовательно, второй меч будет стоить примерно 90 монет. О том, почему примерно, мы поговорим дальше.
Но что если вы набросали несколько предметов, дающих разное количество характеристик, протестировали их, но их стоимость нельзя явно выразить через эти характеристики? Рассмотрим упрощенный пример:
Топор берсерка: дает 9 единиц урона и 2 единицы скорости атаки, стоит 40 монет,
Кинжал трикстера: 4 урона и 8 скорости атаки, стоит 35 монет,
Меч тамплиера: 5 урона и 5 скорости атаки, стоит 38 монет.
Это оружие можно представить в виде линейного уравнения:
Эта система не имеет решения, значит ли это что мы что-то сделали не так и теперь мы не можем балансить игру? Не совсем.
Применим линейную алгебру
Давайте попробуем решить эту систему уравнений иначе. Для этого запишем её в матричной форме:
где 𝐴- матрица коэффициентов, 𝑥 - вектор переменных, и 𝑏 - постоянный вектор.
Обычно такие системы решаются с помощью обратных матриц:
Дело в том, что все нижеописанные операции можно автоматизировать в каком-нибудь 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, там я пишу посты поменьше
