2d - 2d 游戏：通过预测弹丸和单位的交点向移动目标开火

Question

好的，这一切都发生在一个美好而简单的 2D 世界中...... :)

假设我在位置 Apos 处有一个静态物体 A，在 Bpos 处有一个具有 bVelocity 的线性运动物体 B，以及一个具有速度 Avelocity 的弹药...

考虑到 B 的线速度和 A 弹药的速度，我如何找出 A 必须射击、击中 B 的角度？

现在目标是物体的当前位置，这意味着当我的弹丸到达那里时，单位已经移动到更安全的位置:)

score 47 · Accepted Answer

不久前，我为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 == 0thent1和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)

score 24 · Accepted Answer

+1 杰弗里·汉廷 (Jeffrey Hantin) 的出色回答。我四处搜索，发现解决方案要么过于复杂，要么与我感兴趣的案例无关（2D 空间中的简单等速射弹）。他正是我需要的，以生成下面的自包含 JavaScript 解决方案。

我要补充的一点是，除了判别式是否为负之外，您还必须注意一些特殊情况：

“a == 0”：如果目标和弹丸以相同的速度行进，则发生。（解是线性的，不是二次的）
“a == 0 and 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 ({x, y}) src position of shooter
 * @param ({x, y, vx, vy}) dst position & velocity of target
 * @param (Number) v   speed of projectile
 *
 * @return ({x, y}) Coordinate at which to fire (and where intercept occurs). Or `null` if target cannot be hit.
 */
function intercept(src, dst, v) {
  const tx = dst.x - src.x;
  const ty = dst.y - src.y;
  const tvx = dst.vx;
  const tvy = dst.vy;

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

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

  // Find smallest positive solution
  let sol = null;
  if (ts) {
    const t0 = ts[0];
    const t1 = ts[1];
    let 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) {
  let 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 {
    let 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;
}

// For example ...
const sol = intercept(
  {x:2, y:4},              // Starting coord
  {x:5, y:7, vx: 2, vy:1}, // Target coord and velocity
  5                        // Projectile velocity
)

console.log('Fire at', sol)

score 10 · Accepted Answer

首先旋转轴，使 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。

这应该为您提供新系统中所需的向量。转换回旧系统，你就完成了（通过在另一个方向旋转）。

score 8 · Accepted Answer

Jeffrey Hantin 对这个问题有一个很好的解决方案，尽管他的推导过于复杂。这是一种更简洁的方法，可以使用底部的一些结果代码来派生它。

我将使用 xy 来表示向量点积，如果一个向量是平方的，这意味着我用它自己来点它。

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，然后求解根。bc

不过，在求解之前，请记住，我们想要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

score 2 · Accepted Answer

以下是 C++ 中基于极坐标的瞄准代码。

要使用直角坐标，您需要首先将目标相对坐标转换为角度/距离，并将目标 x/y 速度转换为角度/速度。

“速度”输入是弹丸的速度。速度和目标速度的单位无关紧要，因为在计算中只使用速度的比率。输出是射弹应该发射的角度以及到碰撞点的距离。

该算法来自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;
}

score 1 · Accepted Answer

我刚刚破解了这个版本以瞄准 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;
}

score 1 · Accepted Answer

这是一个示例，我使用递归算法设计并实现了预测目标问题的解决方案：http: //www.newarteest.com/flash/targeting.html

我将不得不尝试提出的其他一些解决方案，因为一步计算它似乎更有效，但我想出的解决方案是估计目标位置并将结果反馈给算法以制作新的更准确的估计，重复几次。

对于第一个估计，我在目标的当前位置“开火”，然后使用三角函数来确定当射击到达射击位置时目标的位置。然后在下一次迭代中，我在那个新位置“开火”并确定这次目标的位置。大约 4 次重复后，我得到了一个像素的精度。

score 1 · Accepted Answer

我在这里创建了一个公共域 Unity C# 函数：
http ://ringofblades.com/Blades/Code/PredictiveAim.cs

它适用于 3D，但您可以通过将 Vector3s 替换为 Vector2s 并在有重力时使用您选择的重力下轴来轻松修改 2D。

如果您对理论感兴趣，我会在这里介绍数学的推导：
http ://www.gamasutra.com/blogs/KainShin/20090515/83954/Predictive_Aim_Mathematics_for_AI_Targeting.php

score 0 · Accepted Answer

我从这里抓住了一个解决方案，但没有一个考虑到射手的移动。如果您的射手正在移动，您可能需要考虑到这一点（因为射击时应该将射手的速度添加到子弹的速度上）。实际上，您需要做的就是从目标的速度中减去射手的速度。因此，如果您使用上面的 broofa 代码（我会推荐），请更改行

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

至

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

你应该准备好了。

score 0 · Accepted Answer

基本上，这里并不真正需要相交概念，就您使用弹丸运动而言，您只需要以特定角度击中并在射击时实例化，以便您获得目标与源的确切距离，然后一旦你知道了距离，你就可以计算出击中目标的适当速度。

以下链接使概念清晰，被认为有帮助，可能会有所帮助：始终击中移动目标的弹丸运动

score 0 · Accepted Answer

我见过很多用数学方法解决这个问题的方法，但这是与我的班级在高中时需要做的一个项目相关的一个组成部分，并不是这个编程课上的每个人都有微积分，甚至是向量的背景，所以我用更多的编程方法创造了一种方法来解决这个问题。交点将是准确的，尽管它可能会比数学计算晚 1 帧。

考虑：

S = shooterPos, E = enemyPos, T = targetPos, Sr = shooter range, D = enemyDir
V = distance from E to T, P = projectile speed, Es = enemy speed

在这个问题的标准实现中，[S,E,P,Es,D] 都是给定的，你正在解决找到 T 或射击的角度，以便在适当的时间击中 T。

这种解决问题的方法的主要方面是将射手的射程视为一个圆圈，其中包含在任何给定时间可以射击的所有可能点。这个圆的半径等于：

Sr = P*time

其中时间计算为循环的迭代。

因此，为了在给定时间迭代的情况下找到敌人行进的距离，我们创建了向量：

V = D*Es*time

现在，为了实际解决这个问题，我们想要找到一个点，在该点从目标 (T) 到我们的射手 (S) 的距离小于我们的射手 (Sr) 的射程。这是这个等式的一些伪代码实现。

iteration = 0;
while(TargetPoint.hasNotPassedShooter)
{
    TargetPoint = EnemyPos + (EnemyMovementVector)
    if(distanceFrom(TargetPoint,ShooterPos) < (ShooterRange))
        return TargetPoint;
    iteration++
}

2d - 2d 游戏：通过预测弹丸和单位的交点向移动目标开火

11 回答 11

怎么做

推导

Related

Reference