View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# How to find the closest interception point?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

12 replies to this topic

### #1Kryzon  Prime Members

Posted 03 November 2012 - 02:40 PM

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:

• Object A will travel at a defined constant speed and angle. Object B does not have a defined angle, only speed:

• 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:

• Object B will move at a certain angle, calculated with the formula, as such to intercept A with the shortest travel possible:

• 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:

------------
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:

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, 03 November 2012 - 02:47 PM.

### #2JTippetts  Moderators

Posted 03 November 2012 - 03:26 PM

Maybe this thread might be of some use:

### #3Kryzon  Prime Members

Posted 08 November 2012 - 06:13 PM

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.

### #4Bacterius  Members

Posted 08 November 2012 - 07:17 PM

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.

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..

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

### #5max343  Members

Posted 08 November 2012 - 07:28 PM

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.

### #6Álvaro  Members

Posted 08 November 2012 - 07:30 PM

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. Here's one I wrote. If you have trouble following any of it, post a more specific question.

### #7Bacterius  Members

Posted 08 November 2012 - 07:57 PM

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.

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.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

### #8Kryzon  Prime Members

Posted 08 November 2012 - 10:01 PM

Hi,

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.

Agreed! in that case it would be pixels/logic cycle.

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?

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.

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.

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?

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.

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.

### #9max343  Members

Posted 09 November 2012 - 04:07 AM

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.

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.

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?

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.

### #10Álvaro  Members

Posted 09 November 2012 - 08:48 AM

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.

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.

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

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?

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.

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.

### #11max343  Members

Posted 09 November 2012 - 04:27 PM

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, 09 November 2012 - 04:35 PM.

### #12Kryzon  Prime Members

Posted 09 November 2012 - 09:14 PM

I think I understand. You're using triangle similarity:

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, 09 November 2012 - 10:08 PM.

### #13max343  Members

Posted 10 November 2012 - 04:35 AM

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, 10 November 2012 - 04:52 AM.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.