«Бог всегда на стороне больших батальонов» — Жак д'Стамп де ла Ферте, французский маршал 
Рис.
1 Во многих компьютерных играх необходимо моделировать сражения, не отображая их ход на экране.
Например, это может быть пошаговая игра в стиле Rogue-like, в которой компьютеру остается только просчитывать исход сражения (кто победил) и потери сторон.
Даже в интерактивных играх сражения, происходящие вне поля зрения игрока, можно моделировать упрощенно.
Я разработал интересную математическую модель такого моделирования и представляю ее читателям.
В статье рассмотрен «непрерывный» подход – то есть силы сторон представляют собой непрерывные величины, а их взаимодействие происходит в непрерывном времени.
Это позволяет использовать методы mat. анализ и получить решение в явном виде.
Для армий, состоящих из большого числа боевых единиц, такое упрощение не вносит большой ошибки.
В то же время явное решение позволяет нам многое понять о проблеме.
Исходные данные Исходными данными для моделирования боя обычно являются силы сторон — количество солдат или других боевых единиц.
Известны случаи разнородных армий, состоящих из нескольких типов боевых единиц.
Но мы пока оставим эти трудности и рассмотрим простейший случай: встречу двух армий, состоящих из одинаковых солдат, в равных боевых условиях и различающихся лишь количественно.
Поэтому в качестве исходных данных мы будем иметь две цифры — количество солдат в каждой армии на начало боя.
Модель взаимодействия В реальных боях солдаты стреляют друг в друга или атакуют друг друга в ближнем бою.
Каждый акт атаки дискретен, атака может привести к поражению противника или пройти мимо.
После совершения атаки солдат должен перезарядить или перенацелить ружье, или снова взмахнуть мечом, т.е.
так или иначе, он не может сразу совершить еще одну атаку.
Эффективность атак зависит от мощности оружия солдата, прочности брони противника, ловкости того и другого и других факторов.
Но все эти трудности можно заменить одним коэффициентом без особого ущерба для точности моделирования.
Пусть k — коэффициент, определяющий, сколько врагов в среднем убивает каждый солдат за единицу времени.
В этом коэффициенте можно учесть практически всё: улучшение оружия или точности увеличивает k; броня и уклончивость противника – уменьшаются; Также можно учитывать влияние местности на поле боя, времени суток и т. д. Редко случается, чтобы армии состояли из совершенно одинаковых солдат и встречались в абсолютно равных условиях.
«Защита сильнее нападения» (Р.
Клаузевиц).
Поэтому коэффициент k для каждой армии будет разным.
Но не будем пока усложнять и считать, что коэффициент k одинаков для обеих армий, а позже обобщим результаты на случай разных коэффициентов.
Основные уравнения и их решение Пусть x(t) — количество солдат в первой армии, которое уменьшается по мере их убийства противником.
Пусть y(t) — количество солдат второй армии.
Тогда описанную выше модель взаимодействия можно почти дословно перевести на математический язык: 
То есть: скорость потерь солдат в первой армии пропорциональна количеству солдат во второй армии, и наоборот.
В результате получается система дифференциальных уравнений.
Ее легко решить, в частности, с помощью Wolfram Alpha. Общее решение: 
Где C1 и C2 — константы интегрирования, которые необходимо найти исходя из начальных условий.
Если количество солдат в первой армии на начало боя t=0 равно x0, а количество солдат во второй армии соответственно равно y0, то делаем замену и получаем C1=x0, C2=y0 .
После упрощения конкретное решение, которое нам нужно, в конечном итоге выглядит так: 
Итак, мы нашли функции, устанавливающие зависимость количества оставшихся солдат каждой стороны от времени, проведенного в бою.
Пример графика таких функций показан на рис.
1. Анализ результатов Какого поведения можно ожидать от полученных функций? Подставим, например, x0=y0, т.е.
смоделируем битву между равными армиями и посмотрим, что произойдет. Член с exp(2*k*t) уничтожается, остается x(t) = y(t) = x0*exp(-k*t).
Обе армии уничтожают друг друга в геометрической прогрессии, их численность очень быстро уменьшается, но никогда не достигает нуля.
Битва будет длиться вечно, и бесконечно малое количество оставшихся солдат будет компенсировано бесконечно малой скоростью их потерь.
Если теперь подставить разные значения, например, x0=90 и y0=100 (как на рис.
1), то член с exp(2*k*t) будет действовать по-разному для каждой армии.
Армия, изначально имевшая больше солдат, получит «прибавку» от exp(2*k*t) в положительную сторону, то есть скорость ее упадка замедлится.
Другая армия, меньшая по численности, получит такую же «добавку» к минусу, так что она будет редеть быстрее.
В результате за конечное время t1 численность более слабой армии достигнет нуля.
Битва закончится поражением этой армии.
Давайте еще раз посмотрим на рис.
1. Видно, что в начале графика обе функции убывают примерно одинаково, так как разница в численности армий невелика.
Но постепенно разница в темпах снижения увеличивается, и это самоподдерживающийся эффект. Небольшое начальное численное преимущество (всего 10%) не только обеспечивает победу в бою, но и выживает почти половина солдат армии-победительницы.
Результат тем более впечатляющий, что график на рис.
1 был построен на основе значения k=0,01. Представим, что время измеряется в минутах.
Это означает, что каждую минуту солдат одной армии убивает в среднем 0,01 солдата противника.
То есть, допустим, он стреляет раз в минуту, и попадает с вероятностью 1%.
Это очень низкая скорострельность и вероятность попадания.
Однако битва заканчивается примерно через 150 минут полным уничтожением более слабой армии.
Это все из-за того, что в наших решениях есть экспоненты.
Вычисление x(t) и y(t) после того, как одна из этих функций достигла нуля (т.е.
после того, как одна из сторон выиграла), не имеет смысла.
Так, в частности, при t> t1 x(t) станет меньше нуля, а y(t) начнет увеличиваться.
Чтобы знать, до какого значения t проводить расчеты, следует найти t1. Вывод формул для времени победы t1 и потерь армии-победительницы Найдем момент разрушения t1 для случая x0 Теперь мы можем предоставить код Matlab, который использует формулы (3) и (4) для построения графика хода битвы.
Программа рисования графиков на рис.
1
Также представляет интерес найти потери победившей стороны.x0 = 90; % Number of soldiers in army-1 y0 = 100; % Number of soldiers in army-2 k = 0.01; % Damage to armor factor %---------------------------------- if x0~=y0 t_end = log((x0+y0)./abs(x0-y0)).
/2./k; else t_end = 1000; end t = [0:floor(t_end) t_end]; x = 0.5*exp(-k*t).
*((x0-y0)*exp(2*k*t)+x0+y0); y = 0.5*exp(-k*t).
*((y0-x0)*exp(2*k*t)+x0+y0); figure(1); plot(t,x); hold on plot(t,y,'r'); hold off grid on ylim([0 max(x0,y0)]); xlabel('Time') ylabel('Forces remaining') legend({'Player 1','Player 2'}) title('Battle progress')
Подставив найденное t1 из формулы (4) в формулу (3), после преобразований получим: 
В принципе, формула (5) является основным результатом данной статьи, так как уже было ясно, что побеждает большая армия, и если нас интересует не ход сражения, а только его результат, то это только необходимо найти потери победившей стороны.
Любопытно, что потери победителя не зависят от k, а зависят только от первоначального соотношения сил.
От k зависит только продолжительность боя.
Попробуем выразить время боя и потери победителя не через абсолютные значения х0 и у0, а через их соотношение.
Пусть r=x0/y0 (0
Потери победителя найдем как отношение количества воинов после боя к числу воинов до боя: 
На рис.
2 представлен график функции Ry(r): 
Рис.
2 Видно, что армия-победительница несет в основном небольшие потери, что подтверждает вынесенный в эпиграф тезис о крупных батальонах.
Даже при соотношении сторон 10:9 выживает почти половина армии-победительницы, и только при r> 0,95 победитель несет значительные потери, которые можно назвать «пирровой победой».
Обобщение в случае неравных условий боя
Неравные условия боя (различия в подготовке воинов, вооружении, броне, защите от нападения, факторах местности) можно учесть, если ввести в систему уравнений (1) разные коэффициенты k1 и k2 вместо одного k. То есть средний показатель уничтожения противника среди солдат каждой армии будет различаться: 
Нужное нам частное решение такой системы, аналогичное формуле (3), выглядит так: 
Выражения оказались более громоздкими, но если ввести замену: p=sqrt(k1*k2), r=sqrt(k1/k2)*x0/y0, то все становится существенно проще: 
В принципе, если сделать аналогичную замену системы (3), то системы (3) и (10) будут выглядеть одинаково, а разница между ними будет только в выражении для r: для случая разных k1 и k2, в выражении для r появляется множитель вида sqrt(k1/k2).
Критерием победы теперь является сравнение r с 1. Если r> 1, то побеждает первая армия (x), если r<1, then the second (y).
When r=1, both armies are mutually destroyed in infinite time.
Время победы совпадает с формулой (6) с той лишь разницей, что вместо k теперь фигурирует p: 
И, наконец, оставшиеся солдаты победителя: формула (7) применяется без изменений в случае применения новой замены r.
Заключение
Моделирование боев в непрерывных функциях позволяет получить приемлемые результаты при минимуме вычислительных затрат. Даже в более сложном случае неравных условий боя результат боя можно вычислить с помощью всего лишь трех вызовов квадратного корня и нескольких сложений, умножений и делений.
Вычислительная сложность равна O(1).
Преимущество «больших батальонов» очень четко следует из приведенных формул и графиков.
Что особенно впечатляет, так это то, что даже небольшое численное преимущество в модели приводит к полному разгрому противника с гораздо меньшими потерями, чем можно было интуитивно ожидать.
Почему исход реальных сражений настолько непредсказуем, в отличие от модели? Разумеется, из-за влияния случайных факторов, неизвестных на момент расчетов.
В моей модели влияние случайности может быть отражено где-то в коэффициентах k1 и k2. Эти коэффициенты оказывают решающее влияние на исход боя и могут склонить чашу весов в ту или иную сторону.
Предложенный мною подход может быть развит в направлении применения к нему теории и мат. статистика.
Также было бы интересно разработать модель разнородных армий, состоящих из нескольких родов войск.
Но это тема для отдельного исследования и новой статьи.
Спасибо за внимание.
Теги: #Разработка игр #рогалик #симулятор боя #Разработка игр #математика
-
Как Создать Резервную Копию В Windows 7?
19 Oct, 24 -
Играем В Отличную Игру World Of Tanks
19 Oct, 24 -
Генерация Кода На Языке Go
19 Oct, 24 -
Phd Vi: Как Украли Наш Дрон
19 Oct, 24
