# How to find the closest interception point?

## Recommended Posts

Kryzon    4629
Hi.
I've been having some trouble coming up with a generic formula for figuring out the closest interception point between two travelling objects, and I'd appreciate any help on this.
Here's the context:

[list]
[*]Object A will travel at a defined constant speed and angle. Object B does not have a defined angle, only speed:
[/list]
[img]http://i45.tinypic.com/fz28vb.png[/img]

[list]
[*]Object B is perpendicularly distant to object A's path by a certain amount. The intersection of B's perpendicular distance to A's path gives point P:
[/list]
[img]http://i49.tinypic.com/1zytg2.png[/img]

[list]
[*]Object B will move at a certain angle, calculated with the formula, as such to intercept A with the shortest travel possible:
[/list]
[img]http://i49.tinypic.com/260v1hz.png[/img]

[list]
[*]When both objects start to move (A with its predefined speed and angle, B with its predefined speed and calculated angle), they will meet at a specific point, taking as little time as possible for this:
[/list]

------------
Note there are a couple of cases where B will not intercept A:
- When B is positioned "ahead" of A in A's path (like in these diagrams), if B takes more time than A to reach point P then B can never intercept A (since B can't even reach A by the shortest distance possible, which would be the perpendicular distance).
- When B is positioned behind A in A's path, if B's speed is equal to or less than A's then B can never reach A (they'll either move by the same amount and never get closer, or A will only gain on B).

I have an early-out test for these, so proceeding to calculate the angle\point of interception is the difficulty!

So far I had something that used the time B took to reach P, and how far A travelled along this time. A's travel subtracted from the distance from A-to-P gives a sort of B's "advantage" distance over A. We know that the point of closest interception we want to calculate lies between this segment, until point P.

I also tried (fruitlessly) to model the tangent transformation of segment BP so as to figure out which angle segment BP needs to be transformed by to become a segment that intersects A's path, and that B takes the same amount of time to travel this segment as does A to get to the point of intersection:

[img]http://i46.tinypic.com/xc2l34.png[/img]

In the above example, B should cover distance BI as fast as A covers distance AI. By "as fast" I mean, "in as many logic cycles as"; there's no unit of time. Both objects move by their speeds and angles at every logic cycle. Edited by Kryzon

##### Share on other sites
JTippetts    12950
Maybe this thread might be of some use:

##### Share on other sites
Kryzon    4629
Hi JTippets, thank you for the link.
I still haven't managed to come up with a solution, so I'd really appreciate if anyone could take a look.

##### Share on other sites
Bacterius    13165
[quote name='Kryzon' timestamp='1351975207' post='4996969']
In the above example, B should cover distance BI as fast as A covers distance AI. By "as fast" I mean, "in as many logic cycles as"; there's no unit of time. Both objects move by their speeds and angles at every logic cycle.
[/quote]
Well, no. Your velocities are then expressed in units of meters/logic cycles (or whatever your distance unit is, perhaps pixels). There is always a unit of time.

If I understand the problem correctly, you need to find the point on A's trajectory where A and B will intersect taking the shortest time, taking into account their two velocities, and be able to detect if no such point exists? Do you need the solution in angles? It would make it about, a billion times easier if you worked with vectors here - then it's a matter of finding which range of points on A's path are eligible for intersection, getting an expression in terms of the intersection position for the time to intersection, differentiating it to minimize it, obtaining an expression for the shortest time to intersection (and deducing B's direction from the calculated intersection point). I will try and write it down properly shortly..

##### Share on other sites
max343    346
By interception you mean collision?
If so, then if the speed of B is given by Vb, then there's no closest, there's exactly one.
Their relative velocity must point against their initial relative distance, so all you need to find is its size and you're set.

Now you can apply the law of sines to get: Vba=Va*sin(a+b)/sin(b)
Where 'a' is the angle between the velocities Va and Vba. Applying the law of sines once more will yield: sin(b)=Va*sin(a)/Vb
Now computing the velocity Vb from velocities Va and Vba is just a matter of adding vectors.

##### Share on other sites
alvaro    21247
The general structure of the solution (explained already in many other threads), is to find the time t when the interception would occur, compute where the target will be at time t and then move in that direction.

Several of us have written detailed descriptions of the solution to this problem in the past. [url="http://www.gamedev.net/topic/401165-target-prediction-system--target-leading/page__p__3663387#entry3663387"]Here[/url]'s one I wrote. If you have trouble following any of it, post a more specific question.

##### Share on other sites
Bacterius    13165
[quote name='max343' timestamp='1352424512' post='4999093']
By interception you mean collision?
If so, then if the speed of B is given by Vb, then there's no closest, there's exactly one.
[/quote]
I think the speed of B (the magnitude of its velocity vector) is set, but the direction of the vector has to be determined, so there is a range of possible intersections, which depend on the relative positions and A and B, and the speed of A. At least that's how I interpreted it.

##### Share on other sites
Kryzon    4629
Hi,
[quote name='Bacterius' timestamp='1352423874' post='4999091']
Well, no. Your velocities are then expressed in units of meters/logic cycles (or whatever your distance unit is, perhaps pixels). There is always a unit of time.
[/quote]
Agreed! in that case it would be pixels/logic cycle.

[quote]
If I understand the problem correctly, you need to find the point on A's trajectory where A and B will intersect taking the shortest time, taking into account their two velocities, and be able to detect if no such point exists?
Do you need the solution in angles?
[/quote]
The format of the result can be in whatever's easiest to calculate. In the end, I was going to convert whatever solution I came up with (such as component vectors, an angle or even a sloped-line equation for point 't' on A's line of path) to the game engine equivalent.

[quote name='max343' timestamp='1352424512' post='4999093']
By interception you mean collision?
If so, then if the speed of B is given by Vb, then there's no closest, there's exactly one.
Their relative velocity must point against their initial relative distance, so all you need to find is its size and you're set.

Now you can apply the law of sines to get: Vba=Va*sin(a+b)/sin(b)
Where 'a' is the angle between the velocities Va and Vba. Applying the law of sines once more will yield: sin(b)=Va*sin(a)/Vb
Now computing the velocity Vb from velocities Va and Vba is just a matter of adding vectors.
[/quote]
I'm having some trouble visualizing how this works, though I'm very interested in this method. Could you elaborate on how their relative velocity of Vba is used in this? also, what does angle 'b' stand for?

[quote name='Bacterius' timestamp='1352426262' post='4999103']
I think the speed of B (the magnitude of its velocity vector) is set, but the direction of the vector has to be determined, so there is a range of possible intersections, which depend on the relative positions and A and B, and the speed of A. At least that's how I interpreted it.
[/quote]
That's absolutely correct; the speed of B is predefined as 'pixels/logic cycles', same as A.
Depending on the way the scene is setup (relative positions, speeds and A's direction), there may or may not be that single most efficient way of B intercepting A. As far as I can imagine, there are just those two cases where B can never get to A.
What I meant with 'interception' is that both objects would meet\be positioned at the same point in space, such point belonging to both their paths.

Thank you for the replies.

##### Share on other sites
max343    346
[quote name='Bacterius' timestamp='1352426262' post='4999103']
I think the speed of B (the magnitude of its velocity vector) is set, but the direction of the vector has to be determined, so there is a range of possible intersections, which depend on the relative positions and A and B, and the speed of A. At least that's how I interpreted it.
[/quote]
I also meant the magnitude of the velocity of B. What I meant is that if the only unknown is the direction of the velocity of B, then it's computable as it depends only on the given data.

[quote name='Kryzon' timestamp='1352433676' post='4999133']
I'm having some trouble visualizing how this works, though I'm very interested in this method. Could you elaborate on how their relative velocity of Vba is used in this? also, what does angle 'b' stand for?
[/quote]
I had a small error in some sign I think, it should be:
Vba=Va*sin(a-b)/sin(b)
The angle b is the angle between the velocities Vb and Vba.

It works real simple, the velocities Va, Vb, Vba define a triangle. In this triangle you know the magnitudes of Vb and Va, as well as the angle between Va and Vba. Now you can compute everything else.

##### Share on other sites
alvaro    21247
[quote name='max343' timestamp='1352455669' post='4999209']
[quote name='Bacterius' timestamp='1352426262' post='4999103']
I think the speed of B (the magnitude of its velocity vector) is set, but the direction of the vector has to be determined, so there is a range of possible intersections, which depend on the relative positions and A and B, and the speed of A. At least that's how I interpreted it.
[/quote]
I also meant the magnitude of the velocity of B. What I meant is that if the only unknown is the direction of the velocity of B, then it's computable as it depends only on the given data.[/quote]

You also said there is only one solution, and in general this is not true: There may be two.

[quote]
[quote name='Kryzon' timestamp='1352433676' post='4999133']
I'm having some trouble visualizing how this works, though I'm very interested in this method. Could you elaborate on how their relative velocity of Vba is used in this? also, what does angle 'b' stand for?
[/quote]
I had a small error in some sign I think, it should be:
Vba=Va*sin(a-b)/sin(b)
The angle b is the angle between the velocities Vb and Vba.

It works real simple, the velocities Va, Vb, Vba define a triangle. In this triangle you know the magnitudes of Vb and Va, as well as the angle between Va and Vba. Now you can compute everything else.
[/quote]

That is interesting. Indeed, one could compute the angle between Va and (B-A) (call it beta), and then the angle between (A-B) and Vb (call it alpha) will satisfy
sin(alpha) = (|Va|/|Vb|) * sin(beta)

So alpha = asin((|Va|/|Vb|) * sin(beta)), but that asin is a multivalued function, so there might be more than one solution (say, 83 degrees and 97 degrees have the same sine).

The "standard" method using the dot product to describe an equation in time t, solving for t, computing where the target will be at time t and shooting there is probably easier to program (fewer special cases) and faster to execute (no trigonometric functions), but still max343's is an interesting solution.

##### Share on other sites
max343    346
Thanks for the correction. Yes, it seems I omitted (so conveniently) that asin is multivalued, so there can be up to two solutions.

However, using the law of cosines (instead of sines) fixes this inconvenience and also eliminates the need to use trigonometric functions.
Also, it'll be the solution with the relative velocity that has the larger magnitude (trivial).
Let's say <Va,Vba>/|Va|/|Vba|=cos(a)
So: Vba = sqrt(Va^2(cos(a)^2-1) + Vb^2) - Va*cos(a)

So still, no need to find the actual time of collision. Edited by max343

##### Share on other sites
Kryzon    4629
I think I understand. You're using triangle similarity:

[img]http://i45.tinypic.com/xbya38.png[/img]

First you find the magnitude of 'd' by using either the Law of Sines or Cosines. Then you can calculate the ratio of 'D / d', which you can then use to modulate Va or Vb to find the distance each object has to travel in order to reach the interception point.
This is a very smart solution. Thanks a lot!

EDIT: I see now you're finding the angle between Vba and Vb with the Law of Sines, which is just as well. The angle object B needs to be turned by will be 'alpha + beta' (as it's external to the triangle, and relative to A's path). Edited by Kryzon

##### Share on other sites
max343    346
Yep, you got it exactly right!

I just thought that all you were really interested is the velocity of B, so I stopped there. But if you need the intersection point itself then this is the way to obtain it. Edited by max343