Компьютерные игры про танки являются одними из самых популярных в game-индустрии. История подобных игр насчитывает десятки лет, но популярность их не угасает. Тема танков и танковых сражений получает развитие не только в компьютерных играх, но и является предметом соревновательного процесса в программировании. Например, в 2012 году проходили соревнования по программированию Russian AI Cup — CodeTanks. Участникам предлагалось разработать искусственный интеллект управления танком. Спустя несколько лет подобное соревнование повторилось. Организатором выступила компания National Instruments, которая ежегодно проводит олимпиады по программированию в среде LabVIEW среди студентов и молодых ученых. Участникам олимпиады 2015 года предлагалось разработать алгоритм для автономного управления танком средствами LabVIEW (представление об этой среде программирования можете получить по ссылке: «LabVIEW — первое знакомство»). Данная статья посвящена описанию алгоритма танка-победителя от команды LabVIEWPortal.

О команде

Команда представителей сообщества единомышленников 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

Спасибо за проявленный интерес, будем рады услышать ваши отзывы.

Комментарии (19)


  1. mayorovp
    15.06.2015 17:21
    -1

    Интересно, насколько нехватка времени была обусловлена сложностью задачи — а насколько уродством языка программирования?

    Вот эта картинка:

    image


    в идеальном мире должна была бы выглядеть примерно вот так:


    1. NationalInstruments Автор
      15.06.2015 19:48

      Интересно, насколько нехватка времени была обусловлена сложностью задачи — а насколько уродством языка программирования?

      ваше непонимание чего-либо не является основанием называть это уродством.
      Сложность задачи не в вычислении расстояния между двух точек, а в поиске алгоритма поведения системы в заданных условиях.


      1. mayorovp
        15.06.2015 19:51

        Найденный алгоритм надо потом еще и закодировать (или нарисовать). Упрощает эту задачу такая IDE как LabView или усложняет?


        1. NationalInstruments Автор
          15.06.2015 20:47

          Лично мне упрощает. Кому-то может усложнять. Это опять же не повод говорить, что раз они иные, то все тупые уроды.


          1. mayorovp
            15.06.2015 20:49

            А вот тем, кто писал олимпиаду — усложнила. Видно по скриншотам.


            1. NationalInstruments Автор
              15.06.2015 20:53

              Вы не поверите, я и есть тот, кто писал этот код.


              1. mayorovp
                15.06.2015 21:07

                Странно. Тогда мне, наверное, следует пояснить, как я вижу ситуацию. На примере той самой картинки.

                Хотел написать простыню текста с негодованием, но тут пришел AndreyDmitriev и успокоил меня.


    1. AndreyDmitriev
      15.06.2015 21:00
      +1

      Не, в идеальном мире этот код будет выглядеть как-то вот так:

      На самом деле вы в какой-то мере правы — в некоторых случаях использование текстовых вставок, особенно в таких вот тривиальных вычислениях будет действительно проще, и LabVIEW это в общем-то не запрещает — это называется «Formula Node». Я б тоже не стал так делать, особенно использовать вложенные case структуры — они прячут часть кода, что в данном случае не есть хорошо. Наличие комментария из тектового кода рядом с графическим тоже наводит на мысль о необходимости небольшого рефакторинга.
      А что касается вставок «традиционного кода», ну вот, к примеру из проекта, над которым я сейчас работаю и это у меня на экране:

      Ну или пара примеров из учебника:

      Результатом этого кода будет вот такой график:

      Можно и более зубодробительный пример найти, вот, скажем быстрая сортировка сотни чисел:

      Но дело в том, что LabVIEW программист и не будет с этим заморачиваться, он просто сделает вот так:

      Вообще «чувство» где использовать тестовые вставки, а где — графические элементы — оно приходит с опытом. Моё мнение таково, что к LabVIEW нельзя подходить, не освоив как минимум один-два текстовых языка (скажем, Паскаль и Си — хорошие кандидаты для этого). Также владение как минимум одним объектно-ориентированным языком будет совсем не лишним (для понимая классов и полиморфизма). Но уродским я б этот язык не стал называть — там всё довольно неплохо продумано. Ну и сравнивать тестовые и графические языки тоже не всегда корректно, такое сравнение порой сродни сравнению апельсинов с помидорами.


      1. mayorovp
        15.06.2015 21:03

        О, спасибо.
        Вычеркнул LabView из списка тех языков, от которых надо бежать сломя голову, и добавил в список языков, которые надо попробовать


    1. alexxz
      15.06.2015 22:01

      У меня есть опыт работы с LabView на производстве (лет 5 назад). Программирование и отладка на нём почти не отличается от текстовых языков. Некоторые вещи трудновато делать (например делать хитрые циклы или рекурсии). Однако есть и свои преимущества (в основном интерфейсная SCADA часть). Вобщем — дело привычки и накопленных знаний.


      1. mayorovp
        15.06.2015 22:20

        Спасибо, но Андрей Дмитриев меня уже успокоил :)


  1. mezastel
    15.06.2015 18:24
    -1

    Вообще вся эта тема с визуальным программированием очень болезненна. На обычном текстовом коде это все пишется намного быстрее. Визуальные темы — это хорошо когда например идет ETL (типа MapForce), и то, даже там порой это излищне… чтобы написать A+B нужно сделать блок (+) и подтащить к нему стрелочки… как-то стремно.


    1. NationalInstruments Автор
      15.06.2015 19:45

      На обычном текстовом коде это все пишется намного быстрее.

      доказательства такого утверждения можно увидеть?
      И часто ли вы пишете программы, делающие только a+b?
      Реальные системы, это не только простейшая арифметика над двумя слагаемыми, здесь нужен и интерфейс, и работа с железом, и много всего другого. LabVIEW не претендует на звание универсального суперязыка. на котором нужно писать всем. У этого языка своя ниша. где он занимает лидирующие позиции именно потому, что на нём в разы быстрее и проще создаются конкретные приложения.


      1. mezastel
        15.06.2015 19:48
        +1

        Так а можно пример этих конкретных приложений? Потому что в статье как бы контр-пример.


        1. NationalInstruments Автор
          15.06.2015 20:45

          По-моему, это я просил привести доказательства утверждения, почему этот вопрос был переадресован обратно?
          В очередной раз предлагаю привести доказательства
          БАК достаточно конкретен?
          И просьба


        1. NationalInstruments Автор
          15.06.2015 20:52

          По-моему, это я просил привести доказательства утверждения, почему этот вопрос был переадресован обратно?
          В очередной раз предлагаю привести доказательства утверждения, на этот раз второго, например, указанием времени, которое будет потрачено на написание такого же приложения на «обычном» языке.

          БАК достаточно конкретен? Он создан с использованием PXI (железо) и LabVIEW (софт).

          Ещё раз повторяю, статья про решение конкретной задачи, частью которой было использование конкретно этого языка. Выбор задания лежит на авторах олимпиады, а не решавших её.


        1. AndreyDmitriev
          15.06.2015 21:15
          +4

          Ну, из того, что навскидку приходит в голову — в своё время в одной из дискуссий на хабре пользователь ttools поставил вот такую задачку:

          Я приведу тот коммент целиком:
          Я бы хотел посмотреть, как бы вы красиво выполнили код такой несложной задачи, вполне практической: Имеется 30 датчиков одинакового типа, каждый датчик в реальном времени выдает 4 параметра, допустим float ток и напряжение и два boolean параметра: датчик исправен и датчик включен. Надо отобразить показания всех датчиков на одном экране, допустим 3 ряда по 10 слева направо, сверху вниз, в виде 2 танков (ток, напряжение) и 2х подписей (включен/отключен, исправен/ неисправен) на каждый датчик. Данные от датчиков можно эмулировать любыми функциями от времени и индекса датчика.

          На Delphi, например, эту задачу я могу выполнить за полчаса, красивым кодом, с короткими методами. Сколько времени уйдет, чтобы сделать это на LabView и насколько это получится красиво и без лапши?"


          Ну вот решение на LabVIEW с нуля за пять минут более-менее красиво и без лапши (при этом я старался не использовать Quick Drop, а проограммировать лишь одной мышкой, чтоб было понятнее что к чему):


  1. mezastel
    17.06.2015 22:07

    Глянул на LabView и платформу PXI. Ну, скажем так, все эти модули — весьма недешево. Но нравится модульность. И конечно пример БАКа впечатляет.


  1. AndreyDmitriev
    18.06.2015 14:11

    Да, продукты эти действительно недешёвые. Мы как-то сравнивали стоимость сравнимых систем на компонентах Сименс против NI и пришли к выводу, что на Сименс — заметно дешевле (по крайней мере в нашем сегменте промышленной автоматизации). Ну и с сервисом проще. А LabVIEW используем как СКАДА, ну и для обработки изображений.

    По коллайдеру вот тут есть немного информации:
    CERN Uses NI LabVIEW Software and PXI Hardware to Control World’s Largest Particle Accelerator
    Ну и видео: