Компьютерные игры про танки являются одними из самых популярных в game-индустрии. История подобных игр насчитывает десятки лет, но популярность их не угасает. Тема танков и танковых сражений получает развитие не только в компьютерных играх, но и является предметом соревновательного процесса в программировании. Например, в 2012 году проходили соревнования по программированию Russian AI Cup — CodeTanks. Участникам предлагалось разработать искусственный интеллект управления танком. Спустя несколько лет подобное соревнование повторилось. Организатором выступила компания National Instruments, которая ежегодно проводит олимпиады по программированию в среде LabVIEW среди студентов и молодых ученых. Участникам олимпиады 2015 года предлагалось разработать алгоритм для автономного управления танком средствами LabVIEW (представление об этой среде программирования можете получить по ссылке: «LabVIEW — первое знакомство»). Данная статья посвящена описанию алгоритма танка-победителя от команды LabVIEWPortal.
Команда представителей сообщества единомышленников LabVIEWPotral традиционно принимает участие в состязании программистов. В 2011 году выступление было удачным — команда заняла 1 место. В олимпиаде 2015 года команде удалось повторить свой успех. От портала была сформирована команда из трех человек. Некоторую сложность представляла территориальная удаленность, т. к. члены команды живут в разных городах и часовых поясах. Но надо искать не проблемы, а пути их решения, с чем команда удачно справилась.
Игрокам по очереди передаются следующие параметры:
1. Параметры поля боя (размеры, описание препятствий: координаты крайних точек преград и их оставшаяся прочность);
2. Параметры танка (габариты, скорости поворота корпуса и башни, перемещения, скорость снарядов и пр.);
3. Описание выпущенных на данный момент снарядов (координаты текущего положения снаряда, вектор скорости и номер игрока, выпустившего снаряд);
4. Описание препятствий (массив координат крайних точек преград и их оставшаяся прочность);
5. Текущее состояние танков (координаты центра корпуса, углы поворота корпуса и башни, оставшаяся прочность и оставшееся время перезарядки);
За определенный квант времени игрок должен принять решение и указать действие для корпуса танка (движение или поворот), относительный угол поворота башни танка, а также указать, требуется ли произвести выстрел. Если за отведённое время решение не принято, работа функции игрока прерывается и ход переходит к другому игроку. Победителем считается либо тот, кто успел уничтожить танк противника, либо тот, у кого запас прочности больше чем у противника по истечении отведенного на раунд времени. Урон наносится исключительно снарядами (при столкновениях танков друг с другом или со стенами урон не причиняется). Режим боя: один на один, карты для сражений заранее неизвестны.
Одним из первых вариантов тактики боя был непрерывный огонь и перемещение по кротчайшему пути до противника в обход стен. Но, проведя анализ быстродействия среди некоторых популярных алгоритмов поиска пути (волновой алгоритм, метод выпуклых полигонов, алгоритм поиска А*), пришли к выводу, что наш танк может не успеть рассчитать траекторию движения с последующим анализом ситуации. От этой тактики пришлось отказаться в пользу более простого варианта: «ждать, стрелять и маневрировать».
Ждать, стрелять: из начального положения стреляем в центр противника, невзирая на стены, т. к. они постепенно разрушаются снарядами. Каждый ход корректируется положение башни так, чтобы она смотрела точно в центр противника.
Маневры: корпус танка располагаем перпендикулярно линии огня. Из этого положения уклониться от вражеских снарядов проще всего. В связи с этим каждый ход, при отсутствии опасности, мы корректируем угол поворота корпуса. Соответственно, манёвр уклонения заключается в откате танка назад или вперед.. Выбор направления зависит от места предполагаемого попадания: передняя или задняя части танка.
Однако в ходе предварительных состязаний, были обнаружены два существенных недостатка стратегии:
Эти недостатки были устранены путём добавления нескольких проверок и условий:
Независимо от режима корректируем угол корпуса так, чтобы он был перпендикулярен линии огня (линии соединяющей центры танков).
Общий вид программного кода:
На предварительном этапе анализа исходных данных (до выполнения основного цикла) происходит отсев разрушенных стен и своих снарядов. Далее следует выбор стратегии. Если находимся в опасной зоне, то
Если противник скрылся за стеной, то в безопасный режим не возвращаемся, поскольку поворот башни к ближайшей стене и обратно занимает время, а лишняя трата времени в условиях боя недопустима.
Если зона безопасная, то выполняем две проверки:
1. Количество стен между танком и противником;
2. Количество стен между танком и каждым из снарядов.
Одна стена выбирается из соображений безопасности: если «щитов» осталось мало, то необходимо заранее повернуть башню на противника для экономии времени. Проверка стен между танком и противником приведена ниже и использует ту же функцию что и проверка стен между танком и снарядом (только разные концы отрезков).
Функция поиска количества «щитов» описана ниже.
Снаряды перебираются в цикле, но проверка опасности снаряда ведётся по точке попадания, а не по центру корпуса. Причина: «хитрый» враг, стреляющий из-за угла.
Для упрощения расчетов танк рассматривается как окружность, описанная вокруг корпуса. Точкой попадания принимается точка пересечения линии траектории снаряда и перпендикуляра из центра танка на эту линию. Кроме того, начало координат переносится в центр танка.
Для прямой Ax + By + C = 0 точка перпендикуляра из начала координат вычисляется по формулам:
x0 = — AC / (A^2+B^2)
y0 = — BC / (A^2+B^2)
Т.к. начало координат в центре танка, то для проверки попадания необходимо вычислить длину отрезка [(0,0) (x0,y0)]. Если длина меньше «радиуса» танка, то снаряд опасен.
Затем вычисляется расстояние, на которое потребуется откатиться при маневре от снаряда (это понадобится в дальнейшем).
Далее определяется область попадания: передняя/задняя часть танка. Для этого вычисляется угол, под которым расположена прямая ((0,0) (x0,y0)) относительно оси 0x. Для упрощения расчётов (подобные углы потребуется и в дальнейшем) используются
Если угол между этой прямой и направлением движения танка меньше pi/2, то попадание в переднюю часть, иначе — в заднюю.
Последняя проверка, которую необходимо выполнить: летит ли снаряд в наш танк. Первая версия танка не учитывала направление полёта, и танк пытался убежать и от безопасных снарядов.
Проверка выполняется следующим образом: поскольку снаряд задан началом и длиной вектора (покомпонентно), то это позволяет вычислить расстояние от начала вектора до центра танка и от конца вектора до центра танка. Если конец вектора ближе к танку, значит снаряд летит в нашу сторону.
Далее проверяется, сколько существует стен-щитов. Проверка ведётся по всем снарядам, включая безопасные снаряды.
Каждая стена — отрезок. Между центром корпуса или точкой попадания и центром противника или снарядом строится ещё один отрезок. Далее проверяется, пересекаются ли эти отрезки. Алгоритм проверки взят из статьи по следующей ссылке: grafika.me/node/237. Его суть заключается в анализе векторных произведений векторов, соединяющих различные концы отрезков.
Проверка всех стен выполняется в цикле, точкой останова считается первый опасный снаряд: поскольку положение уже опасное, то проверять дальше смысла нет. Таким образом, если до противника осталось меньше двух стен, или в танк летит снаряд (не перекрываемый стенами), то необходимо переходить в атаку, иначе продолжается уничтожение ближайших стен для будущего маневрирования.
Вначале корректируется угол поворота корпуса. Затем определяется угол прямой «танк-противник» с осью х, используя уже описанные функции нахождения вектора и его угла с осью Ox.
Определение угла доворота корпуса выполняется следующим образом:
Из двух углов выбирается меньший по модулю, т. к. «право-лево» тут не важно.
Стоит отметить что, как и в случае со стрельбой, системе (программе-арбитру) указывается желаемое действие: поворот сразу на весь угол, сделать выстрел. Затем система выполняет допустимую часть желаемого: допустимый поворот, выстрел (если орудие перезарядилось).
Параллельно вычисляется расстояние от центра танка до всех стен и выбирается наименьшее значение.
После выбора стены определяется её центр, куда и будет производиться стрельба. Следует отметить, что минимумов может быть несколько, но система выдаст первый по порядку. После разрушения одной стены (зелёное направление), выбирается следующая ближайшая. По идее, она может быть синей (предположим, что расстояния равны), но следующей по порядку может оказаться дальняя стена (красная линия), и башня будет долго поворачиваться до нее, при этом, несколько выстрелов пойдёт в другие стены. При желании можно доработать выбор так, чтобы из ближайших стен выбиралась ближайшая к пушке.
Расстояние до стены — это расстояние от точки (центр танка) до отрезка. При этом необходимо учитывать, что иногда ближайшая точка будет точкой пересечения данного отрезка перпендикуляром, а иногда — один из концов отрезка.
Воспользуемся скалярным произведением векторов, знак которого даёт информацию о сонаправленности векторов (весь алгоритм написан в комментарии к коду).
Далее определяется угол между осью Ox и соединительным отрезком (только отрезки другие), а затем вычисляется угол доворота башни:
Далее проверяется, куда ближе выполнить разворот: по часовой или против часовой стрелки.
Углы поворота корпуса и башни вычисляются ранее приведенными способами. Далее, находится первый опасный снаряд и выполняется маневр в «лучшую» сторону с учётом точки попадания снаряда. Однако, необходимо проверить отсутствие препятствий на пути отступления. Если опасных снарядов нет, выполняем поворот корпуса.
Расстояние, которое необходимо проехать, вычислялось при проверке опасности снаряда. Обозначим текущее положение танка чёрным цветом, а конечное положение – серым. Таким образом, получается прямоугольник, боковые грани которого — это боковые грани корпуса танка, а фронтальные грани — текущее и желаемое положение передней части корпуса (синяя рамка). Необходимо определить, пересекает ли этот прямоугольник какой-нибудь из отрезков, которыми заданы стены.
Для определения пересечения используется алгоритм Коэна-Сазерленда, с описанием которого можете ознакомиться в данной ссылке: ru.wikipedia.org/Алгоритм_Коэна_—_Сазерленда). Для упрощения задачи выполним следующие действия:
Таким образом, прямоугольник, проверку которого необходимо выполнить будет:
Далее необходимо повернуть и сместить все отрезки-стены при проверке. Каждая стена проверяется отдельно.
Теперь положение «правее», «левее», «выше», «ниже» точек относительно прямоугольника определяется сравнением отдельно компонент x и y с границами прямоугольника.
Если было найдено пересечение, то проверка завершается и в эту сторону двигаться нельзя, и для точно выбранного знака скорости даем «полный газ».
Предложенный программный код не претендует на оптимальность ввиду того, что процесс разработки, тестирования и отладки занял непродолжительное время. Так же следует заметить, что часть алгоритмов бралась из головы, часть из интернета и команда ни в коем случае не покушается на авторство используемых алгоритмов. В процессе баталий танк иногда вёл себя не совсем по алгоритму — «прилипал» к стене. Несмотря на это, интеллектуальная система управления танком от команды LabVIEWPortal проявила себя наилучшим образом и заняла первое место в олимпиаде. Плейлист с видеозаписью основных боев турнира можно посмотреть по ссылке: www.youtube.com/playlist?list=PLKDkvzW_BvvH36vPdeiGKRvmhcZrjMseD
Спасибо за проявленный интерес, будем рады услышать ваши отзывы.
О команде
Команда представителей сообщества единомышленников LabVIEWPotral традиционно принимает участие в состязании программистов. В 2011 году выступление было удачным — команда заняла 1 место. В олимпиаде 2015 года команде удалось повторить свой успех. От портала была сформирована команда из трех человек. Некоторую сложность представляла территориальная удаленность, т. к. члены команды живут в разных городах и часовых поясах. Но надо искать не проблемы, а пути их решения, с чем команда удачно справилась.
Входные данные
Игрокам по очереди передаются следующие параметры:
1. Параметры поля боя (размеры, описание препятствий: координаты крайних точек преград и их оставшаяся прочность);
2. Параметры танка (габариты, скорости поворота корпуса и башни, перемещения, скорость снарядов и пр.);
3. Описание выпущенных на данный момент снарядов (координаты текущего положения снаряда, вектор скорости и номер игрока, выпустившего снаряд);
4. Описание препятствий (массив координат крайних точек преград и их оставшаяся прочность);
5. Текущее состояние танков (координаты центра корпуса, углы поворота корпуса и башни, оставшаяся прочность и оставшееся время перезарядки);
За определенный квант времени игрок должен принять решение и указать действие для корпуса танка (движение или поворот), относительный угол поворота башни танка, а также указать, требуется ли произвести выстрел. Если за отведённое время решение не принято, работа функции игрока прерывается и ход переходит к другому игроку. Победителем считается либо тот, кто успел уничтожить танк противника, либо тот, у кого запас прочности больше чем у противника по истечении отведенного на раунд времени. Урон наносится исключительно снарядами (при столкновениях танков друг с другом или со стенами урон не причиняется). Режим боя: один на один, карты для сражений заранее неизвестны.
Выработка стратегии
Одним из первых вариантов тактики боя был непрерывный огонь и перемещение по кротчайшему пути до противника в обход стен. Но, проведя анализ быстродействия среди некоторых популярных алгоритмов поиска пути (волновой алгоритм, метод выпуклых полигонов, алгоритм поиска А*), пришли к выводу, что наш танк может не успеть рассчитать траекторию движения с последующим анализом ситуации. От этой тактики пришлось отказаться в пользу более простого варианта: «ждать, стрелять и маневрировать».
Ждать, стрелять: из начального положения стреляем в центр противника, невзирая на стены, т. к. они постепенно разрушаются снарядами. Каждый ход корректируется положение башни так, чтобы она смотрела точно в центр противника.
Маневры: корпус танка располагаем перпендикулярно линии огня. Из этого положения уклониться от вражеских снарядов проще всего. В связи с этим каждый ход, при отсутствии опасности, мы корректируем угол поворота корпуса. Соответственно, манёвр уклонения заключается в откате танка назад или вперед.. Выбор направления зависит от места предполагаемого попадания: передняя или задняя части танка.
Однако в ходе предварительных состязаний, были обнаружены два существенных недостатка стратегии:
- В некоторых случаях манёвр от снаряда приводил к «езде в стену».
- Некоторые стены мешали в целом для совершения маневра.
Эти недостатки были устранены путём добавления нескольких проверок и условий:
- Безопасный режим. Если между танком и противником больше одной стены, то расстреливаем ближайшую стену, не обязательно лежащую на пути. Это важный момент, поскольку неизвестно, как будет повёрнут корпус при выходе противника на открытую линию огня.
- Опасный режим. Если между танком и противником менее 2х стен, поворачиваем башню в центр противника и непрерывно стреляем.
- Уклонение. Если в танк летит вражеский снаряд, то рассчитываем точку попадания: «передняя/задняя» часть. Далее выбираем направление движения и оцениваем, на какое расстояние необходимо сместиться. Если по ходу движения происходит столкновение со стеной, то движемся в противоположном направлении. Отступаем до тех пор, пока есть опасность попадания снаряда. При проверке снарядов учитываются стены. Таким образом, снаряд, который гарантированно попадает в стену — игнорируется.
Независимо от режима корректируем угол корпуса так, чтобы он был перпендикулярен линии огня (линии соединяющей центры танков).
Программный код и детальное описание алгоритма действий
Общий вид программного кода:
На предварительном этапе анализа исходных данных (до выполнения основного цикла) происходит отсев разрушенных стен и своих снарядов. Далее следует выбор стратегии. Если находимся в опасной зоне, то
уже никаких проверок не производится
Если противник скрылся за стеной, то в безопасный режим не возвращаемся, поскольку поворот башни к ближайшей стене и обратно занимает время, а лишняя трата времени в условиях боя недопустима.
Если зона безопасная, то выполняем две проверки:
1. Количество стен между танком и противником;
2. Количество стен между танком и каждым из снарядов.
Проверку снарядов необходимо выполнять, поскольку противник может прятаться за стеной и расстреливать углы танка. Ожидать выхода противника из-за стены в этом случае становится бессмысленным.
Одна стена выбирается из соображений безопасности: если «щитов» осталось мало, то необходимо заранее повернуть башню на противника для экономии времени. Проверка стен между танком и противником приведена ниже и использует ту же функцию что и проверка стен между танком и снарядом (только разные концы отрезков).
Функция поиска количества «щитов» описана ниже.
Снаряды перебираются в цикле, но проверка опасности снаряда ведётся по точке попадания, а не по центру корпуса. Причина: «хитрый» враг, стреляющий из-за угла.
Для упрощения расчетов танк рассматривается как окружность, описанная вокруг корпуса. Точкой попадания принимается точка пересечения линии траектории снаряда и перпендикуляра из центра танка на эту линию. Кроме того, начало координат переносится в центр танка.
Для прямой Ax + By + C = 0 точка перпендикуляра из начала координат вычисляется по формулам:
x0 = — AC / (A^2+B^2)
y0 = — BC / (A^2+B^2)
Т.к. начало координат в центре танка, то для проверки попадания необходимо вычислить длину отрезка [(0,0) (x0,y0)]. Если длина меньше «радиуса» танка, то снаряд опасен.
Затем вычисляется расстояние, на которое потребуется откатиться при маневре от снаряда (это понадобится в дальнейшем).
Далее определяется область попадания: передняя/задняя часть танка. Для этого вычисляется угол, под которым расположена прямая ((0,0) (x0,y0)) относительно оси 0x. Для упрощения расчётов (подобные углы потребуется и в дальнейшем) используются
отрезки dx, dy.
Если угол между этой прямой и направлением движения танка меньше pi/2, то попадание в переднюю часть, иначе — в заднюю.
Последняя проверка, которую необходимо выполнить: летит ли снаряд в наш танк. Первая версия танка не учитывала направление полёта, и танк пытался убежать и от безопасных снарядов.
Проверка выполняется следующим образом: поскольку снаряд задан началом и длиной вектора (покомпонентно), то это позволяет вычислить расстояние от начала вектора до центра танка и от конца вектора до центра танка. Если конец вектора ближе к танку, значит снаряд летит в нашу сторону.
Компоненты вектора вычисляются как разность координат двух точек. Длина вектора вычисляется по теореме Пифагора.
Далее проверяется, сколько существует стен-щитов. Проверка ведётся по всем снарядам, включая безопасные снаряды.
Каждая стена — отрезок. Между центром корпуса или точкой попадания и центром противника или снарядом строится ещё один отрезок. Далее проверяется, пересекаются ли эти отрезки. Алгоритм проверки взят из статьи по следующей ссылке: grafika.me/node/237. Его суть заключается в анализе векторных произведений векторов, соединяющих различные концы отрезков.
Векторное произведение в компонентах
Проверка всех стен выполняется в цикле, точкой останова считается первый опасный снаряд: поскольку положение уже опасное, то проверять дальше смысла нет. Таким образом, если до противника осталось меньше двух стен, или в танк летит снаряд (не перекрываемый стенами), то необходимо переходить в атаку, иначе продолжается уничтожение ближайших стен для будущего маневрирования.
Атака стен (безопасный режим)
Вначале корректируется угол поворота корпуса. Затем определяется угол прямой «танк-противник» с осью х, используя уже описанные функции нахождения вектора и его угла с осью Ox.
Определение угла доворота корпуса выполняется следующим образом:
Из двух углов выбирается меньший по модулю, т. к. «право-лево» тут не важно.
Стоит отметить что, как и в случае со стрельбой, системе (программе-арбитру) указывается желаемое действие: поворот сразу на весь угол, сделать выстрел. Затем система выполняет допустимую часть желаемого: допустимый поворот, выстрел (если орудие перезарядилось).
Параллельно вычисляется расстояние от центра танка до всех стен и выбирается наименьшее значение.
После выбора стены определяется её центр, куда и будет производиться стрельба. Следует отметить, что минимумов может быть несколько, но система выдаст первый по порядку. После разрушения одной стены (зелёное направление), выбирается следующая ближайшая. По идее, она может быть синей (предположим, что расстояния равны), но следующей по порядку может оказаться дальняя стена (красная линия), и башня будет долго поворачиваться до нее, при этом, несколько выстрелов пойдёт в другие стены. При желании можно доработать выбор так, чтобы из ближайших стен выбиралась ближайшая к пушке.
ближайшая к пушке
Расстояние до стены — это расстояние от точки (центр танка) до отрезка. При этом необходимо учитывать, что иногда ближайшая точка будет точкой пересечения данного отрезка перпендикуляром, а иногда — один из концов отрезка.
Воспользуемся скалярным произведением векторов, знак которого даёт информацию о сонаправленности векторов (весь алгоритм написан в комментарии к коду).
Скалярное произведение векторов
Далее определяется угол между осью Ox и соединительным отрезком (только отрезки другие), а затем вычисляется угол доворота башни:
Далее проверяется, куда ближе выполнить разворот: по часовой или против часовой стрелки.
Алгоритм атаки вражеского танка
Углы поворота корпуса и башни вычисляются ранее приведенными способами. Далее, находится первый опасный снаряд и выполняется маневр в «лучшую» сторону с учётом точки попадания снаряда. Однако, необходимо проверить отсутствие препятствий на пути отступления. Если опасных снарядов нет, выполняем поворот корпуса.
Проверка пути отступления на наличие/отсутствие препятствий
Расстояние, которое необходимо проехать, вычислялось при проверке опасности снаряда. Обозначим текущее положение танка чёрным цветом, а конечное положение – серым. Таким образом, получается прямоугольник, боковые грани которого — это боковые грани корпуса танка, а фронтальные грани — текущее и желаемое положение передней части корпуса (синяя рамка). Необходимо определить, пересекает ли этот прямоугольник какой-нибудь из отрезков, которыми заданы стены.
Для определения пересечения используется алгоритм Коэна-Сазерленда, с описанием которого можете ознакомиться в данной ссылке: ru.wikipedia.org/Алгоритм_Коэна_—_Сазерленда). Для упрощения задачи выполним следующие действия:
- поворот оси координат таким образом, чтобы движение вперёд было вдоль оси x
- перенос начала координат в переднюю часть танка.
Таким образом, прямоугольник, проверку которого необходимо выполнить будет:
- горизонтальные отрезки y=+- s/2 (половина ширины танка);
- вертикальные: x=0, x=godist (расстояние, которое необходимо пройти).
Далее необходимо повернуть и сместить все отрезки-стены при проверке. Каждая стена проверяется отдельно.
Теперь положение «правее», «левее», «выше», «ниже» точек относительно прямоугольника определяется сравнением отдельно компонент x и y с границами прямоугольника.
Если было найдено пересечение, то проверка завершается и в эту сторону двигаться нельзя, и для точно выбранного знака скорости даем «полный газ».
Заключение
Предложенный программный код не претендует на оптимальность ввиду того, что процесс разработки, тестирования и отладки занял непродолжительное время. Так же следует заметить, что часть алгоритмов бралась из головы, часть из интернета и команда ни в коем случае не покушается на авторство используемых алгоритмов. В процессе баталий танк иногда вёл себя не совсем по алгоритму — «прилипал» к стене. Несмотря на это, интеллектуальная система управления танком от команды LabVIEWPortal проявила себя наилучшим образом и заняла первое место в олимпиаде. Плейлист с видеозаписью основных боев турнира можно посмотреть по ссылке: www.youtube.com/playlist?list=PLKDkvzW_BvvH36vPdeiGKRvmhcZrjMseD
Спасибо за проявленный интерес, будем рады услышать ваши отзывы.
