Solve Intercept Point calculations c#, 2D top-down shooter (target leading)

Let me start by saying I’m looking for serious and specific help on this. I’ve Googled extensively and spent all week going over Answers, the Forum, and soloing the fundamental maths, quadratic equations, etc, and I can’t come up with a usable answer, though I’ve felt close a bunch of times, I’m throwing in the towel. I know variations of this question have been asked multiple times before, but the best I can find are incomplete Java answers that I either can’t complete or can’t convert to c# correctly.

You can probably guess the problem. I want enemies (and allies) to lead their targets by an amount that considers their trajectory, speed, distance, and bullet speed. My workaround has been to just shoot at a spot 6 units in front of their targets, but this results in odd behaviour up close or far away.

  • I know the position of the shooter (a moving ship, if that matters. Frame to frame we can consider it stationary at its position, can’t we?) .
  • I can give a value for bullet speed (it’s actually the shooter’s velocity + an Added force once on Enable, so it varies, but for simplicity I can say its velocity.magnitude averages 21).
  • I know the position, vector, and velocity of my target.
  • I can make the shooter look at any point I like, but I need to work out the appropriate point of intercept to feed this into my LookAtTarget() function.

I can’t solve the maths for the Intercept Point, though. I figure you can solve any problem if there’s just one unknown, but as far as I can see, I’ve two. I don’t know the point my shooter is facing (because I don’t know what the intercept point is) and I don’t know the Time (t) until the shot and the target reach said point.

The equation of a circle and equation of a line are the routes I’ve been pursuing to find the intercept point, but I keep running into the problem of having 2 unknowns. Games everywhere have this feature though, so I know it must be solvable easily enough. Need specifics though, as you can hopefully see I do grasp most of the basic concepts and have spent a week working on it without success.

Thanks
Kevin

Well, I’ve been searching for solution too and found this method. Also I think it is possible to solve this problem with a few steps:

  1. Find time a bullet will travel the distance between shooter and target.
  2. Find distance the target will travel in this time.
  3. Compare that distance with allowable error. If it is less than error - ok, you’ve found your intercept point else go to step 1, but this time calculate the time bullet will travel distance between shooter and previously found intercept point.

The idea of approach is that if you will define allowable error less than half of target’s size, your bullet will hit it, just not right in the center. The number of steps depends on speeds of target and bullet. And it’s not hard to take into account shooters speed, you just need to add it to the bullets speed during calculations described above.

Although I did not given you any code, I hope it will help you and give some new ideas.

There are two kinds of “intercept” problems in 2-D (at least normally).
(1) You want to fire a projectile at a position so that a target moving with constant velocity will intercept it. This is the basic “leading the target” problem.

(2) Same as (1), except your body has to rotate to the position you wish to fire at.

There are several sources for (1) on the web, just type “2d projectile intercept” into google and you will find several. One of my favorites is by Jeffrey Hantin and is located on Stack Overflow.

For (2) the problem is MUCH more difficult. If this is the problem you are trying to solve, then I share your pain in searching for an answer. I could not find one on the web, so I wrote one and posted it. The code/solution for it is written in C++, but I suspect that will not limit you using it in Unity (I develop for iPad/iPhone). The basic idea is the same as the solution for (1), but you need to take into account the additional rotation time as part of the equations, using the dot product of the facing vectors.

The basic idea works like this:

Assume your “entity” will rotate from its current facing position to face the intercept position and then fire immediately.

The Algorithm:

  • Pick a time of impact.
  • Calculate the final position of the target at that time given it is moving at constant velocity.
  • Calculate how long it would have taken the projectile to travel to that position.
  • Calculate how long it would take your entity to rotate to face the intercept position.
  • Calculate the difference of the impact time and the rotation/travel times.
  • Adjust the time of impact up/down so that the difference gets smaller each time (e.g. binary search).
  • When you get close enough, you are done. Otherwise, start the calculations again.

In the simple case, you could know from the discriminant of the quadratic if you had 0, 1, or 2 solutions and pick the best one. I don’t think you can guarantee that here, but you can bound the time range you are willing to search over and how many iterations you will search. This works very well in practice.

The Code:

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

There is a lot more detail located here. There is also a demonstration program on github, located here.

There is also a video showing it in action here. You can skip about 45 seconds into the video to see it in action.