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

Question

Хорошо, все это происходит в красивом и простом 2D мире ...:)

Предположим, у меня есть статический объект A в позиции Apos, и линейно движущийся объект B в Bpos с bVelocity, и патрон с патроном со скоростью Avelocity ...

Как бы я узнал, какой угол должен стрелять А, чтобы попасть в В, учитывая линейную скорость В и скорость боеприпасов А?

Прямо сейчас цель находится в текущей позиции объекта, что означает, что к тому времени, когда мой снаряд попадет туда, юнит переместится в более безопасные позиции:)

Answer 1

Я написал подпрограмму прицеливания для 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)

Answer 2

+ 1 о превосходном ответе Джеффри Хантина здесь. Я гуглил и нашел решения, которые были либо слишком сложными, либо не совсем в конкретном случае, который меня интересовал (простой снаряд с постоянной скоростью в 2D-пространстве.) Это было именно то, что мне было нужно для получения автономного решения 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;
}

Answer 3

Сначала поверните оси так, чтобы AB был вертикальным (выполняя вращение)

Теперь разделите вектор скорости B на компоненты x и y (скажем, Bx и By). Вы можете использовать это, чтобы вычислить компоненты x и y вектора, в который нужно стрелять.

B --> Bx
|
|
V

By


Vy
^
|
|
A ---> Vx

Вам нужно Vx = Bx и Sqrt(Vx*Vx + Vy*Vy) = Velocity of Ammo.

Это должно дать вам вектор, который вам нужен в новой системе. Преобразование обратно в старую систему, и все готово (вращением в другом направлении).

Answer 4

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

Я буду использовать x.y для представления векторного точечного произведения, и если векторное число возведено в квадрат, это означает, что я делю его на себя.

origpos = initial position of shooter
origvel = initial velocity of shooter

targpos = initial position of target
targvel = initial velocity of target

projvel = velocity of the projectile relative to the origin (cause ur shooting from there)
speed   = the magnitude of projvel
t       = time

Мы знаем, что положение снаряда и цели относительно t времени можно описать некоторыми уравнениями.

curprojpos(t) = origpos + t*origvel + t*projvel
curtargpos(t) = targpos + t*targvel

Мы хотим, чтобы они были равны друг другу в некоторой точке (точке пересечения), поэтому давайте установим их равными друг другу и решим для свободной переменной projvel.

origpos + t*origvel + t*projvel = targpos + t*targvel
    turns into ->
projvel = (targpos - origpos)/t + targvel - origvel

Давайте забудем о понятии происхождения и целевой позиции / скорости. Вместо этого давайте работать в относительном выражении, поскольку движение одной вещи относительно другой. В этом случае у нас теперь есть relpos = targetpos - originpos и relvel = targetvel - originvel

projvel = relpos/t + relvel

Мы не знаем, что такое projvel, но мы знаем, что хотим, чтобы projvel.projvel было равно speed^2, поэтому мы возведем в квадрат обе стороны и получим

projvel^2 = (relpos/t + relvel)^2
    expands into ->
speed^2 = relvel.relvel + 2*relpos.relvel/t + relpos.relpos/t^2

Теперь мы можем видеть, что единственной свободной переменной является время t, а затем мы будем использовать t для решения projvel. Мы решим для t с квадратной формулой. Сначала разделите его на a, b и c, затем найдите корни.

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

a  = relvel.relvel - speed^2
b  = 2*relpos.relvel
c  = relpos.relpos

h  = -b/(2*a)
k2  = h*h - c/a

if k2 < 0, then there are no roots and there is no solution
if k2 = 0, then there is one root at h
    if 0 < h then t = h
    else, no solution
if k2 > 0, then there are two roots at h - k and h + k, we also know r0 is less than r1.
    k  = sqrt(k2)
    r0 = h - k
    r1 = h + k
    we have the roots, we must now solve for the smallest positive one
    if 0<r0 then t = r0
    elseif 0<r1 then t = r1
    else, no solution

Теперь, если у нас есть значение t, мы можем вставить t обратно в исходное уравнение и решить для projvel

 projvel = relpos/t + relvel

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

globalpos = origpos
globalvel = origvel + projvel

И все готово!

Моя реализация моего решения в Lua, где vec * vec представляет векторное произведение точек:

local function lineartrajectory(origpos,origvel,speed,targpos,targvel)
    local relpos=targpos-origpos
    local relvel=targvel-origvel
    local a=relvel*relvel-speed*speed
    local b=2*relpos*relvel
    local c=relpos*relpos
    if a*a<1e-32 then--code translation for a==0
        if b*b<1e-32 then
            return false,"no solution"
        else
            local h=-c/b
            if 0<h then
                return origpos,relpos/h+targvel,h
            else
                return false,"no solution"
            end
        end
    else
        local h=-b/(2*a)
        local k2=h*h-c/a
        if k2<-1e-16 then
            return false,"no solution"
        elseif k2<1e-16 then--code translation for k2==0
            if 0<h then
                return origpos,relpos/h+targvel,h
            else
                return false,"no solution"
            end
        else
            local k=k2^0.5
            if k<h then
                return origpos,relpos/(h-k)+targvel,h-k
            elseif -k<h then
                return origpos,relpos/(h+k)+targvel,h+k
            else
                return false,"no solution"
            end
        end
    end
end

Answer 5

Ниже приведен код прицеливания на основе полярных координат в 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;
}

Answer 6

Я только что взломал эту версию для прицеливания в 2d пространстве, я еще не очень тщательно ее тестировал, но, похоже, она работает. Идея заключается в следующем:

Создание вектора, перпендикулярного вектору, направленному от морды к цели. Для того чтобы произошло столкновение, скорости цели и снаряда вдоль этого вектора (оси) должны быть одинаковыми! Используя довольно простой косинус, я пришел к следующему коду:

private Vector3 CalculateProjectileDirection(Vector3 a_MuzzlePosition, float a_ProjectileSpeed, Vector3 a_TargetPosition, Vector3 a_TargetVelocity)
{
    // make sure it's all in the horizontal plane:
    a_TargetPosition.y = 0.0f;
    a_MuzzlePosition.y = 0.0f;
    a_TargetVelocity.y = 0.0f;

    // create a normalized vector that is perpendicular to the vector pointing from the muzzle to the target's current position (a localized x-axis):
    Vector3 perpendicularVector = Vector3.Cross(a_TargetPosition - a_MuzzlePosition, -Vector3.up).normalized;

    // project the target's velocity vector onto that localized x-axis:
    Vector3 projectedTargetVelocity = Vector3.Project(a_TargetVelocity, perpendicularVector);

    // calculate the angle that the projectile velocity should make with the localized x-axis using the consine:
    float angle = Mathf.Acos(projectedTargetVelocity.magnitude / a_ProjectileSpeed) / Mathf.PI * 180;

    if (Vector3.Angle(perpendicularVector, a_TargetVelocity) > 90.0f)
    {
        angle = 180.0f - angle;
    }

    // rotate the x-axis so that is points in the desired velocity direction of the projectile:
    Vector3 returnValue = Quaternion.AngleAxis(angle, -Vector3.up) * perpendicularVector;

    // give the projectile the correct speed:
    returnValue *= a_ProjectileSpeed;

    return returnValue;
}

Answer 7

Вот пример, в котором я разработал и реализовал решение проблемы прогнозирующего таргетинга с использованием рекурсивного алгоритма: http://www.newarteest.com/flash/targeting.html

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

Для первой оценки я «стреляю» по текущей позиции цели, а затем использую тригонометрию, чтобы определить, где будет цель, когда выстрел достигнет позиции, по которой был произведен выстрел. Затем в следующей итерации я «стреляю» в эту новую позицию и определяю, где будет цель в этот раз. Приблизительно после 4 повторений я получаю пиксель с точностью до пикселя.

Answer 8

Я взял отсюда одно из решений, но ни одно из них не учитывает движение стрелка.Если ваш стрелок движется, вы можете принять это во внимание (поскольку скорость стрелка должна добавляться к скорости пули при стрельбе).На самом деле все, что вам нужно сделать, это вычесть скорость вашего стрелка из скорости цели.Поэтому, если вы используете приведенный выше код brooa (который я бы порекомендовал), измените строки

  tvx = dst.vx;
  tvy = dst.vy;

на

  tvx = dst.vx - shooter.vx;
  tvy = dst.vy - shooter.vy;

, и все должно быть в порядке.

Answer 9

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

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

Answer 10

Я сделал общедоступную функцию Unity C # здесь:
http://ringofblades.com/Blades/Code/PredictiveAim.cs

Это для 3D, но вы можете легко изменить это для 2D, заменив Vector3s на Vector2s и используя свою ось вниз для гравитации, если есть гравитация.

Если теория вас заинтересует, я прохожу здесь вывод математики:
http://www.gamasutra.com/blogs/KainShin/20090515/83954/Predictive_Aim_Mathematics_for_AI_Targeting.php