2d игра: стреляйте по движущейся цели, предсказывая пересечение снаряда и юнита

Ниже приводится код прицеливания на основе полярных координат на C ++.

Для использования с прямоугольными координатами вам необходимо сначала преобразовать относительную координату цели в угол / расстояние, а скорость цели по x / y в угол / скорость.

«Скорость» - это скорость снаряда. Единицы скорости и targetSpeed ​​не имеют значения, так как в расчетах используется только соотношение скоростей. Выходные данные - это угол, под которым должен быть выпущен снаряд, и расстояние до точки столкновения.

Алгоритм взят из исходного кода, доступного на http://www.turtlewar.org/ .

// C++
static const double pi = 3.14159265358979323846;
inline double Sin(double a) { return sin(a*(pi/180)); }
inline double Asin(double y) { return asin(y)*(180/pi); }

bool/*ok*/ Rendezvous(double speed,double targetAngle,double targetRange,
   double targetDirection,double targetSpeed,double* courseAngle,
   double* courseRange)
{
   // Use trig to calculate coordinate of future collision with target.
   //             c
   //
   //       B        A
   //
   // a        C        b
   //
   // Known:
   //    C = distance to target
   //    b = direction of target travel, relative to it's coordinate
   //    A/B = ratio of speed and target speed
   //
   // Use rule of sines to find unknowns.
   //  sin(a)/A = sin(b)/B = sin(c)/C
   //
   //  a = asin((A/B)*sin(b))
   //  c = 180-a-b
   //  B = C*(sin(b)/sin(c))

   bool ok = 0;
   double b = 180-(targetDirection-targetAngle);
   double A_div_B = targetSpeed/speed;
   double C = targetRange;
   double sin_b = Sin(b);
   double sin_a = A_div_B*sin_b;
   // If sin of a is greater than one it means a triangle cannot be
   // constructed with the given angles that have sides with the given
   // ratio.
   if(fabs(sin_a) <= 1)
   {
      double a = Asin(sin_a);
      double c = 180-a-b;
      double sin_c = Sin(c);
      double B;
      if(fabs(sin_c) > .0001)
      {
         B = C*(sin_b/sin_c);
      }
      else
      {
         // Sin of small angles approach zero causing overflow in
         // calculation. For nearly flat triangles just treat as
         // flat.
         B = C/(A_div_B+1);
      }
      // double A = C*(sin_a/sin_c);
      ok = 1;
      *courseAngle = targetAngle+a;
      *courseRange = B;
   }
   return ok;
}

Некоторое время назад я написал подпрограмму прицеливания для xtank. Я попытаюсь изложить, как я это сделал.

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

Как это делается

Это сводится к решению квадратного уравнения вида:

a * sqr(x) + b * x + c == 0

Обратите внимание, что под sqr я подразумеваю квадрат, а не квадратный корень. Используйте следующие значения:

a := sqr(target.velocityX) + sqr(target.velocityY) - sqr(projectile_speed)
b := 2 * (target.velocityX * (target.startX - cannon.X)
          + target.velocityY * (target.startY - cannon.Y))
c := sqr(target.startX - cannon.X) + sqr(target.startY - cannon.Y)

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

disc := sqr(b) - 4 * a * c

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

t1 := (-b + sqrt(disc)) / (2 * a)
t2 := (-b - sqrt(disc)) / (2 * a)

Заметим, что если disc == 0, то t1 и t2 равны.

Если нет других соображений, например, препятствий, просто выберите меньшее положительное значение. (Для использования отрицательных значений t придется стрелять назад по времени!)

Подставьте выбранное значение t обратно в уравнения положения цели, чтобы получить координаты ведущей точки, в которую следует целиться:

aim.X := t * target.velocityX + target.startX
aim.Y := t * target.velocityY + target.startY

Вывод

В момент времени T снаряд должен находиться на расстоянии (евклидовом) от пушки, равном прошедшему времени, умноженному на скорость снаряда. Это дает уравнение для окружности, параметрическое по прошедшему времени.

sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
  == sqr(t * projectile_speed)

Аналогично, в момент времени T цель движется вдоль своего вектора по времени, умноженному на ее скорость:

target.X == t * target.velocityX + target.startX
target.Y == t * target.velocityY + target.startY

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

sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
  == sqr(target.X - cannon.X) + sqr(target.Y - cannon.Y)

Замечательно! Подстановка выражений для target.X и target.Y дает

sqr(projectile.X - cannon.X) + sqr(projectile.Y - cannon.Y)
  == sqr((t * target.velocityX + target.startX) - cannon.X)
   + sqr((t * target.velocityY + target.startY) - cannon.Y)

Подстановка другой стороны уравнения дает следующее:

sqr(t * projectile_speed)
  == sqr((t * target.velocityX + target.startX) - cannon.X)
   + sqr((t * target.velocityY + target.startY) - cannon.Y)

... вычитаем sqr(t * projectile_speed) из обеих сторон и переворачиваем:

sqr((t * target.velocityX) + (target.startX - cannon.X))
  + sqr((t * target.velocityY) + (target.startY - cannon.Y))
  - sqr(t * projectile_speed)
  == 0

... теперь решаем результаты возведения подвыражений в квадрат...

sqr(target.velocityX) * sqr(t)
    + 2 * t * target.velocityX * (target.startX - cannon.X)
    + sqr(target.startX - cannon.X)
+ sqr(target.velocityY) * sqr(t)
    + 2 * t * target.velocityY * (target.startY - cannon.Y)
    + sqr(target.startY - cannon.Y)
- sqr(projectile_speed) * sqr(t)
  == 0

... и сгруппируйте похожие выражения ...

sqr(target.velocityX) * sqr(t)
    + sqr(target.velocityY) * sqr(t)
    - sqr(projectile_speed) * sqr(t)
+ 2 * t * target.velocityX * (target.startX - cannon.X)
    + 2 * t * target.velocityY * (target.startY - cannon.Y)
+ sqr(target.startX - cannon.X)
    + sqr(target.startY - cannon.Y)
  == 0

... затем объедините их...

(sqr(target.velocityX) + sqr(target.velocityY) - sqr(projectile_speed)) * sqr(t)
  + 2 * (target.velocityX * (target.startX - cannon.X)
       + target.velocityY * (target.startY - cannon.Y)) * t
  + sqr(target.startX - cannon.X) + sqr(target.startY - cannon.Y)
  == 0

... давая стандартное квадратное уравнение в t. Нахождение положительных вещественных нулей этого уравнения дает (ноль, один или два) возможных мест попадания, что можно сделать с помощью квадратичной формулы:

a * sqr(x) + b * x + c == 0
x == (-b ± sqrt(sqr(b) - 4 * a * c)) / (2 * a)

+1 к отличному ответу Джеффри Хантина здесь. Я гуглил и находил решения, которые были либо слишком сложными, либо не относились конкретно к интересующему меня случаю (простой снаряд с постоянной скоростью в двумерном пространстве). Его ответ был именно тем, что мне было нужно для создания самодостаточного решения на JavaScript, приведенного ниже.

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

• "a == 0": возникает, если цель и снаряд движутся с одинаковой скоростью. (решение линейное, а не квадратичное)
• "a == 0 и b == 0": если цель и снаряд неподвижны. (решения нет, если c == 0, т.е. src и dst - одна точка)

Код:

/**
 * Return the firing solution for a projectile starting at 'src' with
 * velocity 'v', to hit a target, 'dst'.
 *
 * @param Object src position of shooter
 * @param Object dst position & velocity of target
 * @param Number v   speed of projectile
 * @return Object Coordinate at which to fire (and where intercept occurs)
 *
 * E.g.
 * >>> intercept({x:2, y:4}, {x:5, y:7, vx: 2, vy:1}, 5)
 * = {x: 8, y: 8.5}
 */
function intercept(src, dst, v) {
  var tx = dst.x - src.x,
      ty = dst.y - src.y,
      tvx = dst.vx,
      tvy = dst.vy;

  // Get quadratic equation components
  var a = tvx*tvx + tvy*tvy - v*v;
  var b = 2 * (tvx * tx + tvy * ty);
  var c = tx*tx + ty*ty;    

  // Solve quadratic
  var ts = quad(a, b, c); // See quad(), below

  // Find smallest positive solution
  var sol = null;
  if (ts) {
    var t0 = ts[0], t1 = ts[1];
    var t = Math.min(t0, t1);
    if (t < 0) t = Math.max(t0, t1);    
    if (t > 0) {
      sol = {
        x: dst.x + dst.vx*t,
        y: dst.y + dst.vy*t
      };
    }
  }

  return sol;
}


/**
 * Return solutions for quadratic
 */
function quad(a,b,c) {
  var sol = null;
  if (Math.abs(a) < 1e-6) {
    if (Math.abs(b) < 1e-6) {
      sol = Math.abs(c) < 1e-6 ? [0,0] : null;
    } else {
      sol = [-c/b, -c/b];
    }
  } else {
    var disc = b*b - 4*a*c;
    if (disc >= 0) {
      disc = Math.sqrt(disc);
      a = 2*a;
      sol = [(-b-disc)/a, (-b+disc)/a];
    }
  }
  return sol;
}