Хабрахабр

[Из песочницы] Немного о физике в почти Agar IO на aicups.ru

image

В соревновании MiniAICup#2 Почти Agar IO надо управлять амёбами, есть еду и других амёб.
Для реализации алгоритма управления амёбой напрашиваются потенциальные поля, но есть одно большое НО.
Физика движения в игре задаются вот такими уравнениями:

speed_x += (nx * max_speed — speed_x) * INERTION_FACTOR / mass;
speed_y += (ny * max_speed — speed_y) * INERTION_FACTOR / mass;

Получается физика с трением и инерцией, которая все портит. Если физику не учитывать, и направлять вектор усилия (nx) прямо на ближайшую цель, то получается вот так:

image

Для оптимального поедания еды и противников нужно эти уравнения учитывать.

Для начала приведу их в удобный векторный вид:

$$display$$ \vec V_n = (\vec\varphi * V_m - \vec V_)*\mu \\ \vec X_n = \vec X_{n-1} + \vec V_n \\ \varphi - \textrm{вектор силы (помним, что его моудуль 1)}\\ V_m - \textrm{максимальная скорость} \\ \mu - \textrm{INERTION_FACTOR}/mass $$display$$

На поле собственная амёба с известными координатами и скоростью. Итак, есть поле с едой. Нужно вычислить в какую сторону приложить вектор силы, чтобы съесть еду максимально быстро.

image

Расчет траекторий движения

Самый очевидный вариант заключается в следующем:
Мы допускаем, что на протяжении следующих T шагов не будем менять вектор силы φ, выбираем K направлений приложения силы и просчитываем траекторию движения по каждому направлению. В каждой точке траектории смотрим, удается ли съесть еду.

image

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

У нас есть:

  • K траекторий
  • P кусков амёбы
  • S еды
  • T шагов траектории

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

Тем не менее такой алгоритм поиска еды с некоторыми оптимизациями легко влезает в топ 52.

Аналитическое решение уравнений движения

Имея начальные значения V0 и X0 можно посчитать любую точку траектории сразу на n-ом шаге.

Уравнения движения путем простейших преобразований превращаются вот в это:

$$display$$ \vec V_n = \vec \varphi*V_m + (\vec V_0 - \vec \varphi*V_m) * (1-\mu)^n \\ \vec X_n = \vec X_0 + \vec \varphi * n * V_m + (\vec V_0 - \vec \varphi*V_m) * (1-\mu) * \frac {1-{(1-\mu)}^n}{\mu} $$display$$

Не пугайтесь. Выглядит страшно, особенно уравнение для координаты, но оно вычисляется просто.

Имея эти уравнения, можно попытаться сразу вывести на каком шаге n, расстояние до наперед заданной еды будет минимальным.

image

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

Поэтому я воспользовался алгоритмом золотого сечения для поиска точки, имеющей минимально расстояние до заданной еды. Но аналитически вывести номер такой точки у меня не вышло.

На длине траектории в 100 тиков, этот подход требует вычисления всего 10 точек для нахождения ближайшей к еде.

Может, из-за использованных лямбд, а может из-за какой-то ошибки. Однако, испытания показали, что первый описанный метод требует меньше времени на вычисления для траекторий длинной <100 тиков.

Области достижимости

Если внимательно посмотреть на уравнение координаты на n-м шаге, то можно заметить:

$$display$$ \vec X_n = \vec X_0 + \vec V_0*хрень(n) + \vec \varphi * другаяхрень(n) $$display$$

Помним, что модуль силы φ равен единице.

Получается, то куда бы ни была направлена сила φ, через время n амеба окажется на окружности (если сила направлен всегда в одну сторону в течение всех шагов n), либо внутри окружности (если направление силы в течении n шагов менялось).

Центр и радиус окружности:

$$display$$\vec O_n = \vec X_0 + \vec V_0*хрень(n) \\ R_n = \vec \varphi * другаяхрень(n)$$display$$

image

За n шагов амеба обязательно будет либо внутри этой области, либо на ее границе! Это и есть область достижимости!

Как нам это использовать?

Наведение на еду

Нам необходимо найти такой шаг n, на котором граница области достижимости коснется еды. Взять вектор из центра области достижимости на еду. Это и будет искомое направление силы, задав которое амеба максимально быстро подойдет к еде.

image

Наведение и уход от врагов

У врагов тоже есть своя область достижимости. Следует найти шаг, на котором своя и вражеские области достижимости соприкоснуться. Если врага нужно догнать, то вектор силы нужно направить по линии, соединяющий центры двух областей достижимости.

Если же надо убежать, то вектор силы надо направить в противоположном направлении.

image

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть