Archived

This topic is now archived and is closed to further replies.

Argus

2d targeting

Recommended Posts

Hi all - I''ve come up with a fairly standard problem that I can''t seem to find a simple answer for. Google returns garbage results, and the search function here is broken, so perhaps someone can help. The problem is that I have all relevant details about a particle (position, velocity), and I need to know what angle to take (from an arbitrary point) in order to intercept it. So I need to pick an angle such that if I travelled in a straight line, me and the particle in question would collide. Or in other words, what angle would I fire a projectile in if I wanted to hit a moving target? I''m sure there''s a way to calculate this without testing various angles to get closer and closer to the correct angle. Does anyone know?

Share this post


Link to post
Share on other sites
struct Point
{
float x, y;
};

float GetAngle(Point Object1, Point Object2)
{
return atan2(Object2.y - Object1.y, Object2.x - Object1.x);
}

This may be the code your looking for? It returns the Angle between 2 objects in 2d.

Share this post


Link to post
Share on other sites
I don''t think that is what he means. The second of the two particles will not instantly move to the first one.

There is going to be some time in which the first particle will cruise along at it''s velocity. By the time the second particle gets to where the first particle was, it will have moved.

I''m not sure about the rest of the problem, but I know that there will not be an angle for every possible position and velocity of the particles. In other words, sometimes there will not be an angle that you can shoot particle two at so that it hits the first one.

Share this post


Link to post
Share on other sites
Sorry Ximmer - that''s not quite what I''m looking for. The difference is that in my problem, one of the points is moving at a constant velocity. Thanks for offering a suggestion though.

Wht - That''s true, although I can pretty much guarantee (for this problem) that I can hit the target at some angle.

Share this post


Link to post
Share on other sites
Don''t think in terms of angle for a bit; that can be calculated later. I must warn you though that there isn''t guaranteed to be an intersection point if we have two fixed speeds, even if we can alter direction of one of those projectiles. However, since we assume that there is an intersection, we have to give ourselves the liberty of altering the speed of the object being fired.

Let''s define a few things for easy reference first. Object A is what we are trying to intercept and Object B is the object we are firing.

What we essentially have here is a problem in 3 dimentions - X, Y, and time. Let''s say we know the speed and direction of A. We can get corresponding X and Y velocities using trigonometry. Since our third axis Z is supposed to represent time, we now have the following vector for our object - (X_Speed,Y_Speed,1) - since all speeds are in distance per unit time. This simply represents the direction of our 3D line. We also know where the point started at time 0, so that point is (X_Initial,Y_initial,0).

Ok, now for B. We have a fixed initial position, but can have any direction or speed we want. If you think about, there is an infinite number of intersections, since if we can alter speed and direction of this object, we can have it intersect the other object virtually... anywhere! However, let''s say we are looking for the first possible speed and direction at which it can reach A. In our 3D grid, where A was represented by a line, B is represented by a hemisphere. What we need to do is find where the line intersects the hemishere at a single point. This is simple the closest point on the line of A to the initial point of B. There were a few topics resently dealing with calculating the closest point on a line to a point, so you can look around. Our point would be (Xb_Initial,Yb_Initial,0), and the line would be at (Xa_Initial,Ya_Initial,0) and with direction (Xa_Velocity,Ya_Velocity,1), however you need to normalize the latter first.

Anyways, one you find the point, you can figure out the orientation AND the speed of B. Take both the intersection point and the location of B and discard the Z component. Use a simple arctangeant to find the angle. As for the speed of the object, it would be the normalized displacement of the latter two points (intersection - B location).

If anything is unclear or you have any questions, I''ll try my best to straigten it out. This is really conceptual stuff; you pretty much have to able to picture it in your head to get what''s going on

Share this post


Link to post
Share on other sites
Zipster - that helps a bit thanks, but my problem is one where the speeds are fixed. It doesn''t matter if there is no intersection, but since the intercepting projectile''s speed is greater than the speed of the object being intercepted, I think it must have an intersection.

Thinking about them in terms of a 3-tuple (correct terminology?) helps, but I''m still not sure one how to get the intercept angle. Any further help would be much appreciated.

Share this post


Link to post
Share on other sites
Estimate current distance between launcher and target.
Estimate time interval necessary for projectile to travel said distance.
Estimate position change of target during said time interval.
Estimate distance from launcher to future position of target, plus "noise".
Estimate time required.
Fire.

It''s not 100% accurate, but there is no mathematical formula that is for fixed speeds (independent variable speeds may be even more complex).

Share this post


Link to post
Share on other sites
I''m glad I helped, because what I''m telling you now is to ignore a lot of what I said, because it was blatently wrong (I wrote the thing at 3am, whadaya expect? )

We can still use the 3D representation, but instead of B being represented by a hemisphere, it''s represented by a cone. Now, the radius of this cone represents the distance of object B from its origin. Since this distance is dependent on time, what we have is a cone that extends into infinity. However, we do know that at any Z value (which is time), the radius of the cone just at that point is equal to the distance at that time. What you have to do is find the intersection between a line and a cone.

Share this post


Link to post
Share on other sites
I did the analysis in 2D and it''s very simple but is it much more complicated in 3D?

What I thought:

The target particle will be travelling in a certain direction that we know. If we fire the intercepting particle along the same plane then the analysis becomes simple 2D trigonometry. We also have to fire it in the same plane for an intercept to be possible. Then we just have a triangle with all sides and angles known except for our one angle we are trying to assertain. If we plug in all the numbers and we get a number greater than 1 or less than -1 for our arccos calculation then we know intercept is not possible (am I right here) else we get an angle out and voila.

-Meto

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The idea is to represent objects positions as a function of time.

Say you have object a with initial position Xa0, Ya0, speed Va and direction (angle) alpha; then its position at any moment of time t is:

Xa = Xa0 + Va * cos(alpha) * t
Ya = Ya0 + Va * sin(alpha) * t

The other object has its own position, speed and angle and its equations will look similar:

Xb = Xb0 + Vb * cos(beta) * t
Yb = Yb0 + Vb * sin(beta) * t

You are trying to find beta (angle) and t (time) that would satisfy the system:
Xa = Xb
Ya = Yb

I tried to solve it for you but I got lost in calculations and got some results which are probably wrong cause they''re too complicated

Share this post


Link to post
Share on other sites
quote:
The target particle will be travelling in a certain direction that we know. If we fire the intercepting particle along the same plane then the analysis becomes simple 2D trigonometry. We also have to fire it in the same plane for an intercept to be possible. Then we just have a triangle with all sides and angles known except for our one angle we are trying to assertain. If we plug in all the numbers and we get a number greater than 1 or less than -1 for our arccos calculation then we know intercept is not possible (am I right here) else we get an angle out and voila.

That''s a good gist of the situation, but the problem is that the actual position of the object is a function of time. As long as the "bullet" is fired towards the "target''s" trajectory on the same plane, then we know that at some point their trajectories will intersect, but that says nothing but whether the objects themselves intersect. Out problem is trying to find a time for both projectiles and a direction for the "bullet" that will give equal positions for the same time value. Eventually, the solution will look like a triangle, but since position is a function of time, we are missing the angle and the length of two sides. We have too many unknowns for a simple 2D analysis.

What we have to do is then say that time is a dimension, and throw that in there as a Z. Now, we have the position of the "target" as a function of Z, which is a 3D line, and the position of the "bullet" as a function of Z. However, since we still don''t know the direction of the "bullet," at any given Z value we can have a circle whos radius represents the absolute distance the "bullet" can be from it''s initial point. So as Z increases, the radius of the circle increases, and we have the surface area of a cone. As long as the "target" isn''t constantly fleeting from the "bullet," there will be a intersection between the surface of this cone and the line that represents the position of the "target." As a matter of fact there can be two possible points of intersection, since a line can intersect a cone at a maximum of two points. The trick then is to find the time value where the line will intersect the cone only once, at the cone''s bottom, circular edge.

My suggestion would be to use a cone-line intersection method. For your cone, selection a super high-time value and find the radius of the cone at that time. Once you actually have a large, discrete cone to work with, you can use the cone-line intersection method to find where the cone intersects the line. The Z point where they intersect will be the time, the X and Y...well, the position (), and you can work backwards from there to find out what direction that point is from the "bullet." Now, since the line can intersect at more than one point, you can chose either one, but my guess is that you''d want to chose the first one with the lesser Z.

Sorry, it''s about time I finally got around to articulating everything

Share this post


Link to post
Share on other sites