Constant time way to find intersection of two objects when given speeds and directions of both?

[1337GameDev]

I plan to make a missile track and opponent and collide wi the opponent. I need to know a good intersection point when given my missile and opponent speeds and direction.

This is mainly a physics problem. I know I have to try and set up a few equations based on the equation of distance = rate * time, then solve time and extrapoloate position from t.

I saw this post in another forum:
intersection

I am still a bit confused. Can somebody explain this to me, rather than jumping to a result?

[jared-cone]

I like to split these problems out into two components. Figure out how long it will take your missile to reach your target, then use that time to predict where your target will be.

To figure out the first part, you’ll want to figure out how far your target is from the missle currently and how fast your target is moving away from the missile. This means trimming the target’s velocity so that all that remains is how fast he is moving along the line between where he is and where the missile is. You then use this relative velocity to determine how long it will take for the missile to catch up to the target. Once you have that time, you use it to predict where your target will be in that time, and then aim the missile for that destination.

// The vector that extends from the missile to the target
TargetOffset = TargetLocation - MissileLocation;

// The distance from the missile to the target
TargetDistance = TargetOffset.magnitude;

// Normalize the offset vector into a direction - same as doing TargetOffset.normalized
TargetDirection = TargetOffset / TargetDistance;

// How fast the target and missle are moving relative to one another (if the missile
// hasn't been fired yet, use TargetDirection * FiringSpeed for his velocity)
// Another way to think of this is how fast the missile would be moving relative to
// the target if the target wasn't moving at all
RelativeVelocity = MissileVelocity - TargetVelocity;

// How fast the target is moving away from the missile
RelativeSpeed = Vector3.Dot( RelativeVelocity, TargetDirection );

// If RelativeSpeed is negative, that means the target is traveling faster than the
// missile and the missile cannot catch up to it.
// For this case, you can just fake an estimated intercept time so the missile at
// least makes a decent attempt
if ( RelativeSpeed <= 0.0 )
{
	InterceptTime = 1.0;
}
else
{
	InterceptTime = TargetDistance / RelativeSpeed;
}

// We now have an estimate of how long it will take our missile to catch up to the
// target - plug it in to his physics equation to predict where the target will be.
InterceptLocation = TargetLocation + TargetVelocity * InterceptTime;

// Aim the missile towards this location
AimDirection = ( InterceptLocation - MissileLocation ).normalized;
MissileVelocity = AimDirection * MissileVelocity.magnitude;

Note I didn’t test any of this code, it’s just from the top of my head from having to do this several times. Also, this won’t give you the calculus-perfect interception time and location, but it’s pretty close and can be refined by running another iteration of it on the newly-predicted intercept location.

[recursiveAI]

Maybe I don’t fully understand the problem. But, if the missile is constantly tracking the target, you can simply pass the target’s transform to the missile continuously in Update() and have the missile continuously update the vector it is moving along. (This vector is given in the first line of the example script in the previous comment).

This will make the missile behave more like an heat-seeking missile than a ballistic missile. But I am assuming that is what you want ?

[gruntmaster1]

As this was the first result when googling this problem and there isn’t an answer to the exact question, I hope there is no issue posting in this old question.

I had the same issue, and found the solution by illustrating the problem as a triangle:

• Q = our current position,
• P = target current position,
• V1 = target velocity,
• v2 = our velocity,
• z = time from now that intersection will happen,
• FP(z) = position of intersection.
• By || I mean the magnitude of the vector inside.

As you can see, we have an angle and three sides of which two are dependent on z.
We can then use the formula to create an equation:

a^2 = b^2 + c^2 - 2 * b * c * cos(A)

(|V2| * z)^2 = (|V1| * z)^2 + |PQ|^2 - 2 * |V1| * z * |PQ| * cos(angle(PQ, V1))

Note: it is important for the angle that we use PQ and not QP, for the magnitude it doesn’t matter.

After some re-writing, we get a quadratic function = 0 with the coefficients:

• a = |V2|^2 - |V1|^2
• b = 2 *|V1| * |PQ| * cos(angle(PQ, V1))
• c = -(|PQ|)^2

We then use the normal formula for solving a quadratic function = 0 to find z. If there is a possible intersection, then we will get a positive z. Remember to check if a != 0 and that the determinant >= 0 (return a negative number if we can not find a solution).

If we get a positive number, we can use FP(z) to find the position of the intersection. FP(z) is a simple line equation for lines in 3d:

FP(z) = P + z * V1

If we get a negative z, it is up to yourself how to handle this. You might also want to create an upper bound on z, so if the missile is chasing behind the target with a small velocity difference, it isn’t aiming 10km ahead.

Update: One thing I didn’t take into account when writing this answer was that it is possible for two intersections to exist. In that case we will get two positive z values. Choosing the lowest positive z should be the most optimal option (earliest intersection point), but choosing the other is still valid. Just make sure to be consistent between choosing the closest or furthest intersection or you can end up with constantly switching between the points ending up not really reaching either.