2D 游戏：通过预测弹道和单位的相交点，向移动目标开火。

Question

好的，这一切都发生在一个漂亮而简单的二维世界中... :)

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

如何计算A必须射击的角度才能击中B，考虑到B的线性速度和A的弹药速度？

现在瞄准点是物体的当前位置，这意味着当我的项目到达那里时，该单位已经转移到更安全的位置了:)

- Led

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

这段文字涉及到IT技术，需要翻译的内容是标准二次方程式，其中包含变量t。通过求解该方程式的正实根，可以得到（零个、一个或两个）可能的命中位置，这可以使用二次公式来完成：

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

- Jeffrey Hantin

---

@JeffreyHantin 你好，我知道这个问题很旧了，但我想知道您能否解释一下“t”的两种解决方案。我可以看到会有一个解决方案（两条直线相交），但第二个是什么？ - unknownSPY

@unknownSPY，假设t的两个解都是正的且没有障碍物，将它们代回去会得到两个不同的主导角度，你可以朝这两个角度开火，都能够打中目标。当弹道速度比目标慢时，这种效应最为明显：你可以瞄准目标直接击中它，也可以将弹道放在目标离开的路径上。 - Jeffrey Hantin

@JeffreyHantin 感谢您的回复，那么如果弹丸的速度超过了目标，我可以假设只会有一个解吗？ - unknownSPY

@unknownSPY，我相信在这种情况下，t 会有两个解，一个是正数，一个是负数，但只有正数解才有用。 - Jeffrey Hantin

@kriper 选择目标上的任意一点将起作用，或者我相信您可以在圆方程中使用sqr(target_radius + t * projectile_speed)并从那里解决相关问题。 - Jeffrey Hantin

Answer 2

在Jeffrey Hantin的出色答案上+1。我在谷歌上搜索了一些解决方案，但要么太复杂，要么与我感兴趣的情况无关（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)

- broofa

---

为什么t是一个全局变量？ - vpzomtrrfrt

糟糕，已修复。感谢 @vpzomtrrfrt。 - broofa

已经很久了，你还在循环中吗，broofa？如果是这样，我有一个问题要问你，关于这个问题和你的解决方案。 - user431806

@user431806 你好吗？ - broofa

好的。您提供的解决方案可以拦截具有固定速度的目标。我有一个只能行驶一定距离的弹丸，我想知道它是否能够拦截另一个也只能行驶固定距离而不是无限距离的弹丸。假设拦截器和被拦截的弹丸都只能移动200个单位 - 我该如何调整您的代码以考虑最大距离的限制？例如http://codepen.io/AncientSion/pen/wzWNAV，正如您所看到的，拦截轨迹很好，但它假设目标运动具有无限延续性。有什么简单的想法吗？ - user431806

@user431806 很抱歉回复晚了（我最近不怎么上SO）。此代码返回的解决方案是目标和弹丸相遇的X/Y坐标。您只需要计算从发射点到该点的距离并相应地采取行动。 - broofa

Answer 3

首先通过旋转将AB轴垂直（进行一次旋转）。

现在，将B的速度向量分解为x和y分量（称为Bx和By）。您可以使用这些分量来计算需要射击的向量的x和y分量。

B --> Bx
|
|
V

By


Vy
^
|
|
A ---> Vx

你需要 Vx = Bx 和 Sqrt(Vx*Vx + Vy*Vy) = 弹药速度。这应该给你在新系统中所需的向量。回转至旧系统，完成操作（通过向另一个方向旋转）。

- Aryabhatta

---

为了完整起见，Vy = sqrt(aVelocityaVelocity - BxBx)，角度为atan2(Vy, Vx) + 旋转到该位置所使用的角度。 - FryGuy

我完全不理解这个答案。有没有其他措辞或描述方式？ - Clay Fowler

@Clay：基本思路是考虑速度，以初始AB方向的速度和垂直于AB方向（这里也是初始方向）的方向来考虑。在答案中，通过坐标变换使AB沿y轴。在新系统中，速度的x分量必须相等才能发生碰撞。 - Aryabhatta

虽然我欣赏这种与大多数其他地方看到的二次方方法不同的解决问题的方式，但我感觉它的解释并不是特别清楚。改进的方式：1/ 更好的图表（展示实际向量，而不仅是x/y分量），2/ 详细说明坐标变换是如何（未）应用的，3/ 详细说明如何解决Ax和Bx。 - broofa

@moron: 你的图表显示A和B在Y轴上，但这只是其中最重要的部分。它没有表明最重要的部分：Bx和Vx是相同的（事实上，你的Vx/Bx线条长度不同）。我认为，显示向量，并通过终点延伸一条垂直线到x轴，标记为“Bx/Vx”，会更好地表达这一点。关于2和3，当然，这些是常见和众所周知的问题。但你没有给出解决方案-你将其留给读者作为“练习”。表达解决方案每个步骤的代码，或至少公式，将非常有用。 - broofa

Answer 4

Jeffrey Hantin提供了一个不错的解决方案，尽管他的推导过于复杂。下面是一种更简洁的方法，并附有一些结果代码。

我将使用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

- Trey Reynolds

Answer 5

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

如果要用直角坐标系使用该代码，需要先将目标的相对坐标转换为角度/距离，将目标的x/y速度转换为角度/速度。

“speed”输入是弹丸速度。速度和目标速度的单位不相关，因为计算中仅使用速度比率。输出是应该发射弹丸的角度和碰撞点的距离。

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

- Joe

---

嘿，感谢你的回答。我现在想要实现它，但是我不清楚targetDirection是什么意思。 - Coldsteel48

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;
}

- Kentyman

Answer 7

这是一个关于预测目标定位问题，我提出和实施了一个递归算法的例子：http://www.newarteest.com/flash/targeting.html

虽然计算一步到位似乎更为高效，但我会试试其他的解决方案。我的解决方案是首先估计目标位置，并将该结果反馈回算法中以得到一个新的更准确的估计，多次重复此过程。

对于第一个估计，我在目标当前位置“开火”，然后使用三角函数确定射击到达指定位置时目标的位置。然后在下一次迭代中，我就朝着那个新的位置“开火”，并确定目标此时的位置。经过大约四次重复，我可以达到精度误差只有一个像素的效果。

- jhocking

---

这是一个非常糟糕的算法，很抱歉要这么说。 - AgentFire

有什么问题吗？只说“不好”太模糊了。它能满足我的需求，并且我曾经有人指出了一个优点，那就是如果没有解决方案，算法仍然会让射手朝向目标的大致方向瞄准。 - jhocking

假设弹丸的速度小于目标的速度。还假设弹丸的速度是目标速度减去一些 epsilon。在后一种情况下，弹丸将最终到达目标，而在第一种情况下可能甚至无法解决。 - AgentFire

没有解决方案可行：这就是为什么你只递归4次，而不是直到找到解决方案的原因。 - jhocking

即使进行10亿次递归（嗨，堆栈溢出），第一种情况可能仍无法解决。实际上，它将在第二次通过中“失败”其计算。 - AgentFire

Answer 8

我在此提供一个公共领域的Unity C#函数：
http://ringofblades.com/Blades/Code/PredictiveAim.cs
它适用于3D环境，但你可以通过将Vector3替换为Vector2并使用所选的向下轴作为重力（如果有重力）来轻松修改为2D。

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

- Kain Shin

Answer 9

我从这里找到了一个解决方案，但是它们都没有考虑射手的移动。如果你的射手在移动，你可能需要考虑这一点（因为当你开火时，应该将射手的速度加到子弹的速度上）。实际上，你只需要从目标速度中减去射手的速度即可。所以，如果你正在使用broofa上面的代码（我建议这样做），请更改以下行：

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

到

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

你应该一切就绪了。

- Thomas Hyman

Answer 10

我看到很多通过数学方式解决这个问题的方法，但是这是一个与我在高中课程中必须完成的项目相关的组件，并非每个参加编程课的人都有微积分甚至矢量方面的背景知识，因此我创造了一种更具编程风格的解决这个问题的方式。交点将是准确的，尽管可能会比数学计算略晚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++
}

- SpiderShlong