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.

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.

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.

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.

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?
[/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.

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.

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.

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

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.

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