在2d游戏中“射击”目标的AI算法

Question

在我的2d游戏中，我想创建一个可以向玩家“射击”的智能机器人。假设我可以传递给我的机器人：

actual xEnemy, yEnemy

also enemy speed and angle direction

考虑到机器人必须将它的枪旋转到正确的方向，我如何计算“在哪里射击”？

这对我来说是个很大的问题，因为..我的数学绝对不好！提前感谢您的宝贵帮助！

Answer 1

表示法:我用大写字母写向量，用小写标量写标量，用∠V表示向量V与x轴的夹角。(在许多语言中，您可以使用函数atan2进行计算。)

最简单的情况是可以立即旋转的固定式射手。

假设目标在A位置，以VA速度移动，射手在B位置静止，并能以s的速度发射子弹。让射手在时间0射击。子弹在时间t命中，使得|A−B+t VA| =t s。这是一个关于t的简单的二次方程，你应该很容易求解(或者确定没有解)。确定了t之后，您现在可以计算出射击角度，即∠(A−B+t VA)。

现在假设射手不是静止的，而是具有恒定速度VB。(我在这里假设牛顿相对论，即子弹速度与射手的速度相加。)

这仍然是一个简单的二次方程来计算命中时间：|A−B+ t(VA−VB)| =t s。在这种情况下，射击角度是∠(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点开火吗？是。你能在半小时内开火吗？不是的。等)

Answer 2

你所要求的不是微不足道的。我将从最简单的解决方案开始，然后对其进行扩展。

首先，假设你和你的敌人都是静止的。你需要计算你和你的敌人之间的角度，旋转你的武器指向敌人，然后开火。使用你最喜欢的搜索引擎来查找如何找到平面上两点之间的角度的描述(你确实说的是2D)。

一旦您编写了可以执行上述操作的代码，请转到：

你的敌人正以恒定的速度朝恒定的方向移动。你仍然是静止的。这是一个令人惊讶的难题。为了简单起见，我们假设你可以瞬间瞄准你的武器。

如果你知道你和敌人在哪里，知道敌人的速度和方向，那么你就可以随时确定敌人的位置(以及敌人离你的距离和方向)。

你知道你的弹丸能有多快。因此，如果你从你目前的位置划一条线来拦截敌人预期行进路线上的任何位置，你就可以确定你的投射物击中敌人需要多长时间。因此，关键是要找到敌人路径上的点，如果你立即发射弹丸，它将在适当的时间与敌人相交。这通常需要逐次逼近。

如果你不能瞬间转动你的武器，那么问题就会变得更加困难，因为转动你的武器指向敌人所需的时间取决于敌人移动的速度和方向。需要更多的近似值。

当你和敌人都在移动时，事情会变得更加复杂，尽管可以构建数学模型，让你“保持不动”。也就是说，对敌人的速度和轨迹进行变换，以反映敌人是如何相对于你移动的。然后，数学就会变得与你静止不动的情况相同。

数学本身至多是初等三角学。您需要知道如何计算两点之间的距离，直线和点之间的距离，两点之间的角度，计算给定起点和方向的直线上的点，以及如何围绕任意点旋转。所有这些都是众所周知的问题，在网上有很多很好的例子。不过，您必须做一些研究才能找到它们。

也许你最好的选择就是找到一个好的计算机图形教程。

Answer 3

对于“简单”的情况，这个问题的解决方案已经被多次询问和回答，其中枪不需要旋转()。我发现最好的答案是this post (Jeffrey Hantin有一个很好的解释)。

正如Jim Mischel所说，旋转案例的答案甚至不是微不足道的。这是因为您必须执行的旋转量是目标的截距位置(发生碰撞的位置)的函数。我不知道是否有一个干净的封闭形式的解决方案(似乎不太可能给出公式)，但我能够通过反向工作和迭代到一个解决方案来解决它。

基本的想法是这样的：

假设你的“实体”将从当前面对的位置旋转到面对拦截的位置，然后立即开火。

在给定目标以恒定的速度移动的情况下，选择impact.

• Calculate的时间，目标的最终位置。，velocity.

• Calculate，impact.

• Calculate，

• 调整向上/向下的影响时间，这样每次的差异都会变小(例如，二进制search).

• When你足够接近，你就完成了。否则，请重新开始计算。

在简单的情况下，您可以从二次型的判别式中知道您是否有0、1或2个解决方案，并选择最佳解决方案。我不认为你可以在这里保证这一点，但你可以限制你愿意搜索的时间范围和你将搜索的迭代次数。这在实践中效果很好。

因为我在网上找不到这个问题的解决方案，所以我打算发布我的解决方案。我专门写了一个函数来处理这个问题。I have a blog entry on the entire calculation here。还有一个nice video showing it here。

代码：

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