Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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.

  • You cannot reply to this topic
12 replies to this topic

#1 Kryzon   Prime Members   -  Reputation: 3243

Like
0Likes
Like

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

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

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

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



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

Posted Image

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.


Sponsor:

#2 JTippetts   Moderators   -  Reputation: 8593

Like
1Likes
Like

Posted 03 November 2012 - 03:26 PM

Maybe this thread might be of some use:

http://www.gamedev.net/topic/614147-enemies-leading-their-shots/

It talks about leading shots on enemies, and one poster presents a solution to the shot-leading problem by solving a quadratic equation.

#3 Kryzon   Prime Members   -  Reputation: 3243

Like
0Likes
Like

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.

#4 Bacterius   Crossbones+   -  Reputation: 9081

Like
1Likes
Like

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

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#5 max343   Members   -  Reputation: 340

Like
1Likes
Like

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   Crossbones+   -  Reputation: 13670

Like
1Likes
Like

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.

#7 Bacterius   Crossbones+   -  Reputation: 9081

Like
0Likes
Like

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.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#8 Kryzon   Prime Members   -  Reputation: 3243

Like
0Likes
Like

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.

#9 max343   Members   -  Reputation: 340

Like
0Likes
Like

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   Crossbones+   -  Reputation: 13670

Like
1Likes
Like

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.

#11 max343   Members   -  Reputation: 340

Like
1Likes
Like

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.


#12 Kryzon   Prime Members   -  Reputation: 3243

Like
1Likes
Like

Posted 09 November 2012 - 09:14 PM

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

Posted Image

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.


#13 max343   Members   -  Reputation: 340

Like
0Likes
Like

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.



PARTNERS