AI алгоритм "стрелять" по цели в 2d игре

Question

в моей 2d игре я хотел бы создать интеллектуального бота, который сможет «стрелять» в игрока. Предположим, я могу перейти к своему боту:

actual xEnemy, yEnemy

also enemy speed and angle direction

Как я могу вычислить «куда стрелять», учитывая, что бот должен повернуть свое оружие в правильном направлении?

Это действительно большая проблема для меня, потому что .. я абсолютно не хорош в математике! Заранее благодарим за вашу драгоценную помощь!

Answer 1

То, что вы спрашиваете, нетривиально.Я начну с самого простого решения и остановлюсь на этом.

Сначала предположим, что и вы, и ваш враг неподвижны.Вам нужно вычислить угол между вами и вашим врагом, повернуть оружие, чтобы указать на врага, а затем стрелять.Используйте вашу любимую поисковую систему, чтобы найти описание того, как найти угол между двумя точками на плоскости (вы сказали, 2D).

После того, как вы напишите код, который может выполнить вышеизложенное, перейдите к:

Ваш враг движется в постоянном направлении с постоянной скоростью.Вы все еще неподвижны.Это удивительно сложная проблема.Для упрощения предположим, что вы можете нацелить свое оружие мгновенно.

Если вы знаете, где вы и противник, а также скорость и направление противника, то вы можете определить позицию противника (и,следовательно, его расстояние и направление от вас) в любое время.

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

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

Вещи становятся еще более запутанными, когда вы и враг движетесь, хотя можно построить математику так, чтобы вы "держали себя неподвижно".То есть выполните преобразование скорости и траектории противника, чтобы отразить, как противник движется относительно вас.Математика становится идентичной случаю, когда вы неподвижны.

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

Вероятно, вам лучше всего найти хороший учебник по компьютерной графике.

Answer 2

Обозначения: я пишу векторы заглавными буквами, скаляры в нижнем регистре и ∠V для угла, который вектор V образует с осью x. (Который вы можете вычислить с помощью функции atan2 на многих языках.)

Самый простой случай - это стационарный стрелок, который может вращаться мгновенно.

Пусть цель находится в позиции A и движется со скоростью VA, а стрелок неподвижен в позиции B и может стрелять пулями со скоростью s . Пусть стрелок стреляет в момент 0. Пуля попадает в момент времени t так, что | A - B + t VA | = т с . Это простое квадратное уравнение в t , которое вы легко сможете решить (или определить, что решения не существует). Определив t , теперь вы можете определить угол стрельбы, который составляет всего ∠ (A - B + t VA).

Теперь предположим, что стрелок не стоит на месте, но имеет постоянную скорость VB. (Я предполагаю, что ньютоновская теория относительности здесь, то есть скорость пули прибавляется к скорости стрелка.)

Это все еще простое квадратное уравнение для определения времени попадания: | A - B + t (VA - VB) | = т с . В этом случае угол стрельбы составляет ∠ (A - B + t (VA - VB)).

Что, если стрелок ждет, пока время u , прежде чем выстрелить? Затем пуля попадает в цель, когда | A - B + t (VA - VB) | = ( t - u ) s . Угол стрельбы по-прежнему составляет ∠ (A - B + t (VA - VB)).

Теперь к вашей проблеме. Предположим, что стрелок может совершить половину оборота за время r . Тогда он, безусловно, может выстрелить в момент времени r . (В основном: определите необходимый угол стрельбы, если таковой имеется, для выстрела во время r , как описано выше, поверните на этот угол, остановитесь, подождите до времени r , затем выстрелите .)

Но вы, вероятно, хотите знать самое раннее время, когда стрелок может стрелять. Вот где вы, вероятно, хотите использовать последовательное приближение, чтобы найти его. (Схема алгоритма: Можете ли вы стрелять во время 0? Нет. Можете ли вы стрелять во время r ? Да. Можете ли вы стрелять во время ½ r ? Нет. И т. Д.)

Answer 3

Решение этой проблемы для «простого» случая, когда пистолет нуждается в НЕ необходимости поворота, запрашивалось и отвечало несколько раз.Я нашел лучший ответ в этом посте (Джеффри Хантин имеет хорошее объяснение).

Как сказал Джим Мишель, ответ на вращающийся случай не является даже немного тривиальным.Это потому, что количество вращения, которое вы должны сделать, является функцией позиции перехвата цели (где происходит столкновение).Я не знаю, есть ли для этого чистое решение в закрытой форме (кажется маловероятным, учитывая формулы), но я смог решить его, работая в обратном направлении и перебирая решение.

Основная идея работает следующим образом:

Предположим, что ваша "сущность" будет вращаться из своей текущей позиции лицом к позиции перехвата, а затем немедленно выстрелит.

• Укажите время удара.
• Вычислите конечную позицию цели в это время, если она движется с постоянной скоростью.
• Вычислите, сколько времени понадобилось бы снаряду, чтобы добраться до этой позиции.
• Вычислите, сколько времени она будетповерните ваше лицо, чтобы повернуть лицом к точке пересечения.
• Рассчитайте разницу времени удара и времени вращения / перемещения.
• Отрегулируйте время удара вверх / вниз, чтобы разница каждый раз уменьшалась (например, двоичный поиск).
• Когда вы достаточно приблизитесь, все готово.В противном случае, запустите вычисления снова.

В простом случае вы могли бы узнать по дискриминанту квадратичного, если у вас было 0, 1 или 2 решения и выбрать лучшее.Я не думаю, что вы можете гарантировать это здесь, но вы можете ограничить временной интервал, который вы хотите искать, и сколько итераций вы будете искать.Это очень хорошо работает на практике.

Так как я не мог найти решение этой проблемы в Интернете, я собираюсь опубликовать мое.Я написал функцию для решения этой проблемы конкретно. У меня есть запись в блоге обо всех вычислениях здесь .Здесь также есть хорошее видео, показывающее его .

Код:

/* Calculate the future position of a moving target so that 
 * a turret can turn to face the position and fire a projectile.
 *
 * This algorithm works by "guessing" an intial time of impact
 * for the projectile 0.5*(tMin + tMax).  It then calculates
 * the position of the target at that time and computes what the 
 * time for the turret to rotate to that position (tRot0) and
 * the flight time of the projectile (tFlight).  The algorithms
 * drives the difference between tImpact and (tFlight + tRot) to 
 * zero using a binary search. 
 *
 * The "solution" returned by the algorithm is the impact 
 * location.  The shooter should rotate towards this 
 * position and fire immediately.
 *
 * The algorithm will fail (and return false) under the 
 * following conditions:
 * 1. The target is out of range.  It is possible that the 
 *    target is out of range only for a short time but in
 *    range the rest of the time, but this seems like an 
 *    unnecessary edge case.  The turret is assumed to 
 *    "react" by checking range first, then plot to shoot.
 * 2. The target is heading away from the shooter too fast
 *    for the projectile to reach it before tMax.
 * 3. The solution cannot be reached in the number of steps
 *    allocated to the algorithm.  This seems very unlikely
 *    since the default value is 40 steps.
 *
 *  This algorithm uses a call to sqrt and atan2, so it 
 *  should NOT be run continuously.
 *
 *  On the other hand, nominal runs show convergence usually
 *  in about 7 steps, so this may be a good 'do a step per
 *  frame' calculation target.
 *
 */
bool CalculateInterceptShotPosition(const Vec2& pShooter,
                                    const Vec2& vShooter,
                                    const Vec2& pSFacing0,
                                    const Vec2& pTarget0,
                                    const Vec2& vTarget,
                                    float64 sProjectile,
                                    float64 wShooter,
                                    float64 maxDist,
                                    Vec2& solution,
                                    float64 tMax = 4.0,
                                    float64 tMin = 0.0
                                    )
{
   cout << "----------------------------------------------" << endl;
   cout << " Starting Calculation [" << tMin << "," << tMax << "]" << endl;
   cout << "----------------------------------------------" << endl;

   float64 tImpact = (tMin + tMax)/2;
   float64 tImpactLast = tImpact;
   // Tolerance in seconds
   float64 SOLUTION_TOLERANCE_SECONDS = 0.01;
   const int MAX_STEPS = 40;
   for(int idx = 0; idx < MAX_STEPS; idx++)
   {
      // Calculate the position of the target at time tImpact.
      Vec2 pTarget = pTarget0 + tImpact*vTarget;
      // Calulate the angle between the shooter and the target
      // when the impact occurs.
      Vec2 toTarget = pTarget - pShooter;
      float64 dist = toTarget.Length();
      Vec2 pSFacing = (pTarget - pShooter);
      float64 pShootRots = pSFacing.AngleRads();
      float64 tRot = fabs(pShootRots)/wShooter;
      float64 tFlight = dist/sProjectile;
      float64 tShot = tImpact - (tRot + tFlight);
      cout << "Iteration: " << idx
      << " tMin: " << tMin
      << " tMax: " << tMax
      << " tShot: " << tShot
      << " tImpact: " << tImpact
      << " tRot: " << tRot
      << " tFlight: " << tFlight
      << " Impact: " << pTarget.ToString()
      << endl;
      if(dist >= maxDist)
      {
         cout << "FAIL:  TARGET OUT OF RANGE (" << dist << "m >= " << maxDist << "m)" << endl;
         return false;
      }
      tImpactLast = tImpact;
      if(tShot > 0.0)
      {
         tMax = tImpact;
         tImpact = (tMin + tMax)/2;
      }
      else
      {
         tMin = tImpact;
         tImpact = (tMin + tMax)/2;
      }
      if(fabs(tImpact - tImpactLast) < SOLUTION_TOLERANCE_SECONDS)
      {  // WE HAVE A WINNER!!!
         solution = pTarget;
         return true;
      }
   }
   return false;
}