Сложилась традиция, что после соревнований по спортивному программированию победитель или просто игрок выкладывает на Хабре статью, чтобы рассказать как здорово было участвовать в соревновании и как вариант победить в нем. Из его статьи конечно же многое можно почерпнуть для будущих соревнований.
Но вот про участие в текущем соревновании на стадии бета тестирования думаю статей мало, понятно, что нельзя публиковать код решения, не известно еще как хорошо это решение и вообще много еще не известно ведь сейчас по сути только начало турнира, но в этом и прелесть. Автор дает читателю шанс заскочить на отправляющийся поезд и насладиться новогодней поездкой в мир игровых стратегий.
Во первых спасибо, что открыли статью, сразу хочу поделиться секретом: это будет цикл статей, в котором надеюсь затронем и генетические алгоритмы и нейронные сети. А пока как уже написал выше добро пожаловать в путешествие по Russian AI Cup CodeBall.
Ссылка на страницу быстрого старта чемпионата
По вышеуказанной ссылке читатель сможет найти правила чемпионата, правила самой игры и основную часть математического аппарата необходимого для создания бота. Так же на странице быстрого старта есть примеры уже написанных ботов для различных языков программирования, что сильно облегчает начальный старт.
Начнем с простого, с названия чемпионата CodeBall.
Приятное сочетание слов code и ball, почти football. Правила и логика игры тоже похожи на футбол, но с каждым раундом усложняются/ поэтому за основу возьмем начальные условия проведения игр.
Суть игры как говорилось в недавней песне: игроки должны забивать, а вратарь отбивать мячи.
Схематично игровое поле
Обращаю внимание, что боты двигаются в плоскости пола арены XZ, ось Y отвечает за высоту игрового объекта.
Также схематично объекты игры (мяч и боты(организаторы их называют роботы))
Теперь немного текста в поддержку картинок. Игровое поле это трехмерное замкнутое пространство, ни мяч ни боты не могут выйти за его пределы. В этом пространстве существуют две области "ворота" при попадании в которые мяч считается забитым одним из игроков. Для того чтобы гол засчитали, нужно чтобы мяч полностью оказался за линий ворот (на рисунке указана пунктиром).
Для упрощения расчетов столкновений(коллизий) игровых объектов (арена, мяч, боты) боты и мяч считают идеальными сферами(шарами), которые описываются следующими величинами: радиус сферы, координата центра сферы, масса, скорость. Арена также описывается идеальными математическими примитивами, так что расчет столкновений обходится без участия полигонов, что сильно упрощает задачу. Если пролистать правила чемпионата до конца, то там читатель обнаружит программу на псевдокоде, которая как и раз и отвечает за вышеуказанные расчеты. Данный псевдокод после небольших физических усилий переводится на выбранный вами язык программирования и является вполне работоспособным. Но об этом немного позже.
Еще пару слов о физике игрового мира. Для придания достоверности происходящего на арене, введена гравитация, то есть на ботов и мяч постоянно действует сила гравитации направленная вниз относительно пола арены. Остальными формами физического взаимодействия такими как трение или угловые скорости(вращение) объектов организаторы пренебрегли в пользу простоты описания физического мира. При ударе о стенки арены мяч теряет часть энергии, но это не сильно усложняет мир и вполне понятно со стороны, нет возможности создать вечный двигатель в виде мяча.
Чтобы мир казался еще более правдоподобным применена схема расчетов с Тиками и Микротиками. В первой своей статье автор подробно останавливался на понятии Тика игрового времени. В данном соревновании мы можем посмотреть на физический движок в исходных кодах, как уже говорил он нам пригодится в будущем, и обнаружить что для игроков существуют Тики, а внутри движка все происходит в Микротиках, по умолчанию 100 микротиков в одном тике, что дает возможность точнее описывать коллизии объектов и избегать таких неприятных вещей как провал объектов за пределы арены или провал объектов друг в друга приводящие к ошибкам во взаимодействии между ними.
С миром(ареной) и игровым временем вроде разобрались, посмотрим на игровые объекты: боты и мяч. Если быть кратким, то бот это мяч меньшего радиуса и массы которому можно отдавать команды: указать желаемую скорость(это трехмерный вектор содержащий как направление, так и длину или величину скорости) и силу прыжка, если прыжок в данный момент целесообразен с точки зрения логики игры. На данном этапе соревнований введено упрощение, что если бот находится в полете(не касается стенок арены), то у него нет возможности исполнять команды по изменению скорости.
Перейдем к самому трудному или наоборот простому, все зависит от опыта читателя в работе с трехмерными векторами. Описанию местоположения игровых объектов. Картинка в поддержку
Приступим к ботостроению.
На каждом игровом тике, ваша стратегия будет получать следующие объекты:
Мяч:
class Ball:
x: Float // Текущие координаты центра мяча
y: Float
z: Float
velocity_x: Float // Текущая скорость мяча
velocity_y: Float
velocity_z: Float
radius: Float // Радиус мячаи список ботов, с данными по каждому боту:
class Robot:
id: Int
player_id: Int
is_teammate: Bool // true, если это робот вашего игрока
x: Float // Текущие координаты центра робота
y: Float
z: Float
velocity_x: Float // Текущая скорость робота
velocity_y: Float
velocity_z: Float
radius: Float // Текущий радиус робота
nitro_amount: Float // Текущий запас нитро робота
touch: bool // true, если робот сейчас касается арены
touch_normal_x: Float // Вектор нормали к точке соприкосновения с ареной
touch_normal_y: Float (или null, если нет касания)
touch_normal_z: Floatсразу видно что с этими данными неудобно работать, желательно ввести класс(объект) 3D вектор и класс 2D вектор. Здесь многое будет зависеть от языка программирования выбранного вами. Обычно эти классы уже написаны и легко находятся в интернете для нужного языка программирования. Автор сейчас пишет бота на c++, но постарается ограничиться псевдокодом. Если ввести полноценные классы векторов, по операции по сложению, вычитанию, умножению, нормализации и другие векторные операции останутся внутри класса, что сильно упростит работу над стратегией.
Еще есть класс игрока, который указывает какие боты из списка ваши, какие противника:
class Player:
id: Int
me: Bool // true, если это объект вашего игрока
strategy_crashed: Bool
score: Int // Текущий счет игрокаПосле передачи данных об игровом мире на вход вашей стратегии, игровой движок отдает вам управление и запускает таймер времени для расчетов, время на расчеты ограничено, в среднем около 20 микросекунд на все действия внутри тика. Есть подозрение, что в это время входит и время на десериализацию поступивших данных и сериализацию отправляемых вашей стратегией данных на сервер. Но так как количество ботов 4 (2 ваших и 2 противника, далее в финальном раунде общее количество ботов увеличится до 6) временем на эти операции можно пренебречь.
Пришло время команд.
Например, мы хотим дать боту команду двигаться в сторону мяча. Для нахождения нужного вектора направления скорости надо из позиции мяча вычесть позицию бота, получаем вектор направления на мяч, далее его можно нормализовать и умножить на максимальную скорость движения бота из констант мира. На картинке подробнее
Наверное читатель заметил на слайде что расчеты можно проводить как для 3D векторов, так и для 2D векторов. Если учесть тот факт, что бот большее время проводит на плоскости пола арены, то упрощение расчетов до двух координат не скажется сильно на точность расчетов по перехвату мяча. Конечно про высоту мяча не надо забывать, но с учетом гравитации он рано или поздно опустится к боту.
Прыжок бота, это добавление скорости по вертикали(вертикальной скорости), направление прыжка бота будет совпадать с направлением текущей скорости бота с добавлением составляющей по оси Y.
Если к вышеуказанным словам добавить более сложную логику движения, то можно получить следующее поведение ботов:
Сейчас на сайте действует песочница, где можно посмотреть игры, но ничего не сравнится по ощущениям, если вы напишите свою стратегию и будете следить за ее играми. Экспериментально установлено, что даже самый простая стратегия вполне может неплохо играть.
Из простых форм стратегий приходящих на ум, стратегия по выделению одного бота для защиты ворот, второго бота сделать нападающим. Основная задача нападающего это преследование мяча и при удачном положении удар в сторону ворот противника. Бот играющий за вратаря, обычно ограничен в своих перемещениях по полю, и в основном действует в зоне ворот. Все эти вещи легко описываются с помощью if-else конструкций выбранного вами языка. В любом случае придумывать и создавать стратегию на данном этапе придется тебе мой читатель. По условиям конкурса нельзя публиковать исходные коды стратегии. Но обсудить подходы к проектированию стратегии думаю не запрещается.
Как мне кажется организаторы конкурса выбрали интересную тему для турнира, единственное сайт немного тормозит, но надеюсь скоро это исправят.
Жду откликов в комментариях касательно статьи, на чем остановиться более подробно.
В следующей статье попробую описать методы по прогнозированию поведения мяча во времени для более осмысленной игры ботов в вашей стратегии.
А пока поздравляю с наступающим Новым 2019 Годом!
Продолжение следует.
Автор: Geo Evclid
Копипаста