Немного о физике в почти 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 V_{n-1} + (\vec\varphi * V_m - \vec V_{n-1})*\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-ом шаге.

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

$ \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} $


Не пугайтесь. Выглядит страшно, особенно уравнение для координаты, но оно вычисляется просто. Здесь Vn и Xn зависят только от начальных условий X0 и V0 времени.

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

image

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

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

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

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

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


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

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


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

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

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

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


image

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

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

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


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

image

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


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

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

image

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 4

    0
    Про область достижимости, вроде как похоже и очень ловко, но глядя на формулы у меня возникает чувство, что мне завтра экзамен сдавать, а я ещё даже книжки не открывал. Так что верю и про модуль силы и про фи, а больше… тут наши полномочия всё.

    P.S. По крайней мере, хотя бы один комментарий статья заслуживает.
      0
      Мне кажется, или выкладывать такие статьи до окончания турнира несколько преждевременно?
      Или автор не соревнуется а участвует чисто по фану?
        0
        Мне тоже это интересно. Надеюсь, автор прояснит :)
          +1
          Ну сейчас все топы пойдут запиливать новые фичи для стратегий и наловят кучу багов, тут-то я и в призовые места вырвусь.

      Only users with full accounts can post comments. Log in, please.