Mathematics
November 2015 9

Использование МатАнализа в компьютерных играх

From Sandbox

Введение


Во многих играх, особенно РПГ очень большое значения имеют «статы». Атака, защита, сопротивление, урон, пробивание брони, промахи и прочее влияют на наносимый противнику урон или вами от противника получаемый. Чаще всего игроки предпочитают придерживаться тактики – «чем больше всего и сразу, тем лучше». Такой подход скорее вызван не продуманной стратегией развития персонажа, а отсутствием детального анализа игры, лени, или же недостатком информации о конкретном характере(конкретной расчётной формулы) влияния «статов» на те или иные показатели. Более того, очень часто, по задумке создателей игры, бывает невозможно увеличивать все характеристики одновременно, и поэтому правильно выбрать «что и куда «вкачивать» становится особенно важно.

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

Метод будет описываться на примере вычислении силы заклинаний питомцев от интеллекта, и процент снижения получаемого урона игроком от суммарной величины защиты в игре ArcheAge. Собственно основа метода это «Метод наименьших квадратов», который очень широко известен и очень часто используется в разных областях. Для вычислений будет использоваться Wolfram Mathematica (любая версия). Собственно пошаговое описание того, что нужно делать для получения интересуемого закона и является основной ценностью данной статьи. Те, кто знаком с МНК и Wolfram Mathematica, могут перейти непосредственно к примерам.

Метод наименьших квадратов (МНК)


Метод МНК очень подробно описан в литературе, я лишь в общих словах опишу суть. Пусть мы знаем общий вид зависимости одной величины от другой. Откуда можно узнать общий вид, я объясню позже. На данный момент для примера возьмём зависимость вида y=а*x^2 +b*x +c. Где y это одна величина, а x это другая. При этом a, b, c это некоторые параметры. И что бы полностью опередить зависимость одной величины от другой, нужно определить именно эти параметры, ведь сам вид зависимости предполагается известным.

В самом простом случае можно узнать значение одной величины при каком-то конкретном значении другой величины из наблюдений, экспериментов или каких-то других источников. Таких пар нужно три, чтобы составить полную систему уравнений и решить её относительно трёх неизвестных параметров a,b,c. Более того, в ряде случаев этого бывает достаточно и в играх.

Всё усложняется, когда к функции зависимости добавлен ещё один член – а именно некоторая случайная величина. y=а*x^2 +b*x +c +Случайная_Величина. Она может быть введена разработчиками игры специально, как например разброс при уроне, но может иметь и иную причину. Дело в том, что точное значение некоторой функции может иметь в своей записи количество цифр большее, чем размер поля вывода в меню игры. В таком случае выводится округленное значение, и нельзя сказать точное значение больше или меньше чем то, что мы можем прочитать в поле интерфейса игры. Таким образом, можно сказать что округление нам добавляет некоторую случайную величину (она может быть и отрицательной и положительно, но в среднем она ноль).

Когда к «точной» функции зависимости y=а*x^2 +b*x +c добавляется случайная величина, то реально наблюдаемые, измеренные значения y не будут лежать на кривой а*x^2 +b*x +c какие бы ни были параметры. При ни слишком большой дисперсии (среднем значении разброса) случайно величины, реально наблюдаемые значения, отмеченные на координатной плоскости будут лежать довольно «близко к кривой а*x^2 +b*x, если мы даже знаем параметры a b и с. Часть точек даже может попасть на эту кривую, т.к. вполне возможно что случайная величина в какой-то момент просто приняла значение ноль. Но как в таком случае нам найти параметры нашей функции если даже точки, которые мы знаем, на ней не лежат? МНК заключается в том, чтобы так подобрать параметры, чтобы расстояние от точек до кривой было минимальным! Это главная суть МНК.

Тут стоит уточнить, что под расстоянием от точки до кривой подразумевается не расстояние до ближайшей точки кривой, а разница между значением точки (точка это пара переменная величина — наблюдаемое значение функции) и «точным»значением функции при том же значении переменной что и у точки. Вообще говоря в идеальном случае эта разница равна конкретному значению той самой Случайной_Величины в данной точке. Уточнить стоит так же то, что нужно, чтобы сумма именно всех разностей между наблюдаемыми значениями и «точными» значениями была минимально. К сожалению, часто возникает соблазн выкинуть наиболее «неудобные», сильно отстающие от предполагаемой «точной» кривой точки, чтобы всё остальное смотрелось лучше. Этого делать нельзя, если конечно вы абсолютно не уверены что измерение было проведено ошибочно. И ещё один важный момент – расстояние в данном случае измеряется как строго положительная величина. Не важно, выше наблюдаемая точка, чем нужно или ниже – главное это как далеко.

Общий вид зависимости, как было сказано ранее y=а*x^2 +b*x +c +Случайная_Величина. Причём, из наблюдений мы знаем наблюдаемые значение пар обеих величин x,y. Пар мы можем измерить столько сколько захотим, и желательно чем больше, тем лучше! (почем это так, читайте в литературе). Чтобы найти разницу между наблюдаемым и «точным» значением нужно вычесть измеренные значение величин y_измер и а*x_измер ^2 +b*x_измер+c. То есть мы считаем, что переменная у нас известна точно, и что при точных параметрах a b c а*x_измер ^2 +b*x_измер+c это как бы «точное» значение нашей функции. От полученной разности нужно взять модуль, чтобы получить как уже говорилось абсолютное значение.( Стоит отметить, что на самом же деле «точная» означает такую кривую, которая наиболее близко расположена ко всем точкам. Реально_Точное значение мы не можем вычислить никак. Но за неимением Реально_Точного остаётся довольствоваться тем, что можно посчитать.

К такому повороту событий если вы ещё не привыкли, то стоит привыкнуть. Когда нет идеала – используем лучшее из того что есть.) Но с модулем неудобно работать, и проще вместо модуля возвести полученную разность в квадрат. И просуммировать все квадраты разностей. Полученная сумма будет одной очень длинной функцией со множеством слагаемых, но всего от трёх переменных. Остаётся лишь найти такие значения a b c при которых эта функция будет минимальной. Что равносильно нахождению экстремумов функции от нескольких переменных. Что в свою очередь (на первый) взгляд является тривиальной задачей мат анализа. Это и есть метод наименьших квадратов.

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

Wolfram Mathematica

Если вы никогда не работали с программами типа Mathematica MATLAB и Maple, то самое время начать. Если совсем очень просто, (так чтобы вы не пугались их осваивать) то эти программы нужны для того, чтобы решать системы дифференциальных уравнений символьно, или интегрировать символьно, или нарисовать график, причём всё это делается «вежливой просьбой» в одну строчку. Вы только подумайте, вы пишете уравнение, в символьном виде (НЕ ЧИСЛОВОМ! Всё буквами, переменными, параметрами) и получаете такой же ответ – в общем символьном виде. Нахождение параметров методом АНК они тоже умеют. (…и не только им, но это уже детали). Советую попробовать поиграться с Wolfram Mathematica. Может кому станет интересенее если вы узнаете тот факт, что из Mathematica есть доступ к базам данных соцсетей, например вконтакте. (Понятно что только открытых данных, но всё же) Вы можете сами проводить какие-то исследования, используя данные реальных людей. Их вкусы, профессии, интересы, частоту постов, и всё что захотите касательно социологии и поведения людей. Статей как работать с Mathematica очень много, но что особенно приятно, это колоссальное количество примеров во встроенном хелпе – буквально на все случаи жизни. Это очень упрощает осваивание Mathematica (про MATLAB я так лестно не буду отзываться: у него тоже, конечно, есть плюсы, но всё же мой выбор за Mathematica).

Пара слов о тех функция которые будут применятся ниже. Для нахождения параметров функции известного типа, при наличии набора наблюдаемых (измеренных) данных (к которым добавлена некоторая случайная величина), используется функция FindFit. Для отображения массива точек используется функция ListPlot. Для построения графика используется просто Plot. Массивы обычно заключены в фигурные скобки {}, доступ к элементу массива производится через двойные квадратные скобки [[]]. Так же для создания массива можно использовать различные функции, например Table. Для отображения графика и массива точек на одном рисунке используется функция Show[{}] от массива из двух элементов (или более) каждый из которых может являться любой функцией для графического отображения данных.

Примеры


В большинстве случаев, в играх не используются слишком сложные функции для зависимостей одних параметров от других. Чаще всего используются линейные функции ax+b, либо отношение вида (ax+b)/(cx+d). Нет чёткого правила для поиска функций. Разработчик может при желании сделать очень сложную и запутанную функцию, которую угадать почти невозможно. Однако такие случаи крайне редки. Отношение вида (ax+b)/(cx+d) часто используется там, где вычисляется значение, которое должно быть ограничено сверху, например снижение получаемого урона от значения защиты. Действительно, нет смысла вводить такое понятие как снижение урона больше чем 100%. В подобных случаях, когда есть величины ограниченных сверху, лучше всего начать пробовать именно с функции вида y= (ax+b)/(cx+d).

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

OurDefSource = {{637, 10.73}, {689, 11.5}, {462, 8.02}, {585, 9.94}, {358, 6.33}, {317, 5.64}, {281, 5.03}, {99, 1.83}, {0, 0}, {3668, 40.9}, {1287, 19.54}, {495, 8.54}, {2471, 31.8}, {4596, 46.44}};

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

Def=Sort[OurDef,#1[[1]]<#2[[1]]&];
MaxDef=Last[Transpose[Def][[1]]];
MinDef=First[Transpose[Def][[1]]];

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

Fdef[x_]:=(a*x+b)/(c*x+d);
CoefsFdef={a,b,c,d};

После чего используем FindFit для поиска параметров функции определённого вида, используя полученные экспериментальным путём данные.

CoefsFdefFit=FindFit[Def,Fdef[x],CoefsFdef,x]

После чего показываем вид функции с найденными параметрами ( для этого используется «/.» )

Fdef[x]/.CoefsFdefFit

В результате мы получаем: (-1.1499 + 7.32728 x)/(388.234 + 0.0732995 x)

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

(-0.156933+ x)/( 52.9848_+0.0100036 x)

Как мы помним переменная x означает величину защиты в единицах. Характерные значения для x порядка тысяч. Поэтому числовой константой в числителе можно пренебречь, что означает что общий вид функции на самом деле несколько иной, чем мы предполагали, а именно без константы в числителе. Что касается знаменателя, то множетель перед х очень похож на 0.01. Слагаемое же в знаменателе очень похоже на 53.00. Сделав все эти допущения, а также умножив знаменатель на 100, получаем, что процент снижения получаемого урона равен 100*x/(5300+x), где — х это суммарное количество защиты.

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

OurDiff= Fgood[x_]:=100*x/(5300+x);
OurDiff=Table[Fgood[Def[[i]][[1]]]-Def[[i]][[2]],{i,1,Length[Def]}]
Max[OurDiff]

Макимальное значение разности 0.00493997, что меньше половины последней значимой(отображаемой) цифры в значении процентов. Что вполне удовлетворительно.

Результат можно отобразить на графике.

Show[{ListPlot[Def,PlotStyle->{Blue}],Plot[Fgood[x],{x,MinDef,MaxDef},PlotStyle->{Green}]}]

Полный код для Mathematica:

OurDefSource = {{637, 10.73}, {689, 11.5}, {462, 8.02}, {585, 9.94}, {358, 6.33}, {317, 5.64}, {281, 5.03}, {99, 1.83}, {0, 0}, {3668, 40.9}, {1287, 19.54}, {495, 8.54}, {2471, 31.8}, {4596, 46.44}};
Def = Sort[OurDefSource, #1[[1]] < #2[[1]] &];
MaxDef = Last[Transpose[Def][[1]]];
MinDef = First[Transpose[Def][[1]]];
Fdef[x_] := (a*x + b)/(c*x + d);
CoefsFdef = {a, b, c, d};
CoefsFdefFit = FindFit[Def, Fdef[x], CoefsFdef, x]
Fdef[x] /. CoefsFdefFit
OurDiff = Fgood[x_] := 100*x/(5300 + x);
OurDiff =  Table[Fgood[Def[[i]][[1]]] - Def[[i]][[2]], {i, 1, Length[Def]}]
Max[OurDiff]
Show[{ListPlot[Def, PlotStyle -> {Blue}],  Plot[Fgood[x], {x, MinDef, MaxDef}, PlotStyle -> {Green}]}]

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

a51+b51*(c51*x+y)

где a51 это константа в расчёте конкретного спела; b51 это множитель в формуле спела; c51 это коэффициент пропорциональности силы заклинаний и инты; x это инта а y это бонусный прирост к силе заклинаний со шмота. FindFit способна работать и для функции от нескольких переменных. В результате мы получаем:

Урон заклинания Ядовитое дыхание=1669+4.8*(1.25* Инта+БонусСилаЗакл);

Стоит заметить, что в отличии от персонажа, коэффициент пропорциональности силы заклинаний и инты равен не 0.2 а 1.25, что означает что сила заклинаний от спелов у петов растёт в почти в 6 раз быстрее.

Для сравнения:

«ураган лесовика» 654+1.92*(1.25* x+y);
«стрела лесовика” 980+2.88*(1.25* x+y);

Выводы


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

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

Заключение


Матан помогает даже в играх. Надеюсь описанный пример использования МНК в играх, увеличит ваш интерес к матану.
+16
26.8k 175
Comments 6
Top of the day