Best Heading/Orientation for Fastest Interception of a Moving Target

[nilum]

I am trying to write an addon for a videogame which will give the best orientation/heading to intercept a target. The best would mean the fastest route to a moving target.

There is no acceleration in the game.

I can get the speed/velocity of the target and player, as well as their coordinates and orientation/heading in three dimensions.

For the most part I will only need to use the XY plane, but there are some instances where being able to figure in pitch would be handy.

--

The problem is I am not very adept with math or physics.

I've tried to find a formula, but haven't had much luck.

Can anyone help me out?

 

[0xDEADBEEF]

If you assume that the target is moving in a straight line without acceleration, and your speed is also fixed, then you are looking for the direction in which the decrease of the square of the distance to the target is the greatest. Smells like twelfth grade math. Maybe I scribble something and come back...

 

[0xDEADBEEF]

I found another way: If you plot the time on the z axis, you will see that you need to find the intersection of a line with a cone.

 

[diazona]

Well, if you have the coordinates of the target as three functions of time
$$\begin{align}x_t(t) &= x_{t0} + v_{tx}t \\ y_t(t) &= y_{t0} + v_{ty}t \\ z_t(t) &= z_{t0} + v_{tz}t\end{align}$$
and you have the current position [itex](x_{p0}, y_{p0}, z_{p0})[/tex] and speed $v_{p}$ of the player, then the intersection point will be

$$(x_{t0} + v_{tx}t)^2 + (y_{t0} + v_{ty}t)^2 + (z_{t0} + v_{tz}t)^2 - x_{p0}^2 - y_{p0}^2 - z_{p0}^2 = (v_{p}t)^2$$

or

$$\left(x_{t0}^2 - x_{p0}^2 + y_{t0}^2 - y_{p0}^2 + z_{t0}^2 - z_{p0}^2\right) + \left(2x_{t0}v_{tx} + 2y_{t0}v_{ty} + 2z_{t0}v_{tz}\right)t + \left(v_{tx}^2 + v_{ty}^2 + v_{tz}^2 - v_p^2\right)t^2 = 0$$

which is a quadratic equation you can solve to get the time it will take to intercept the target. It's messy but it shouldn't be hard to program the computer to do it. Once you figure out the time, you can get the position by plugging in the time to the target coordinate formulas above. Then just figure out what heading the player needs to aim for that position.

If you happen to have access to a vector math library, the equation (and the programming) becomes a lot simpler:
$$(\vec{x}_{t0}^2 - \vec{x}_{p0}^2) + 2\vec{x}_{t0} \cdot \vec{v}_{t}t + (\vec{v}_{t}^2 - \vec{v}_{p}^2)t^2 = 0$$

 

[nilum]

Thanks a lot guys. This helps a lot.

 

[nilum]

hey diazona

Thanks for the formula, but one thing I noticed was that it doesn't take into consideration the angle my target is heading. I think with this formula it just gives me the time it will take if the player and target are heading straight for each other.

I think some trig needs to be involved in the formula as well.

 

[A.T.]

For the most part I will only need to use the XY plane, but there are some instances where being able to figure in pitch would be handy.

You can always reduce this problem to 2D by doing the caluclation in a local coordinate system where the XY plane contains the target & player postions and the direction vector of the target.

As for the trigonometry, I would apply the http://en.wikipedia.org/wiki/Law_of_sines" to the triangle formed by the target, player and the planed interception:
You know the angle between player-target and target-interception (or target direction). And you know the ratio of the distances player-interception and target-interception: it is the player / target velocity ratio. So you can compute the angle between player-target and player-interception. Your program might have to handle some special cases and there is not always a solution (if the target is faster than the player).

 

[nilum]

This is what I have so far:
P = (Xp,Yp) = Player Coordinate
T = (Xt, Yt) = Target Coordinate

What we need to do is create a triangle with the line PT, Target vector (Tv), and Player vectory (Pv).

The Angle of TvPT (that is the angle formed by the Target Vector and line PT) = the Angle of PvPT (that is the angle formed by the Player Vector and line PT)

The Inerception point is then where Tv intersects with Pv.

The final part is the velocity ratio. If Ps (Player Velcoity/Speed) is twice as much as Ts (Target Velocity/Speed) then the ratio is 2:1. So the angle PvPT is half (i.e. if it was 45 degrees it would be 22.5 degrees). If Ps (Player Velocity/Speed) is half as much as Ts (Target Velocity/Speed) then the ratio is 1:2. So the angle PvPT is twice as much (i.e if it was 35 degrees it would be 70 degrees).

The Interception point will still be where Tv intersects with Pv.

There will be some cases where Interception is not possible. It could be because the Target moves faster than the Player or Tv is 90 degrees or greater.

Knowing all this I am still having trouble coming up with a formula or a function. Any help?

 

[A.T.]

This is what I have so far:
P = (Xp,Yp) = Player Coordinate
T = (Xt, Yt) = Target Coordinate

What we need to do is create a triangle with the line PT, Target vector (Tv), and Player vectory (Pv).

The Angle of TvPT (that is the angle formed by the Target Vector and line PT) = the Angle of PvPT (that is the angle formed by the Player Vector and line PT)

The Inerception point is then where Tv intersects with Pv.

Yes but first you compute the absolute value of angle PvPT:

|PvPT| = asin( sin(TvPT) * (target_velocity / player_velocity) )

Now to get the direction of Pv you rotate PT around P by a signed PvPT(multiply it with a http://en.wikipedia.org/wiki/Rotation_matrix" ). PvPT is negative (clockwise rotation) if (Xpt * Ytv) - (Ypt * Xtv) is negative (or the other way round, try it out).

There might be a simpler way using vector algebra only. Ask in some math / game programming forum.