next »

[Indievelopper]

Hey guys!

My question is pretty simple actually, and i'd be very pleased if you could redirect me to a site or anything about that.

I have a turret on the ground and a plane going in a linear trajectory.
I know the velocity of bullets and plane, and i'd like to know what angle i must use for the turret, so the bullet can hit the plane.

Thanks!

[J. Kyle Pittman]

Ah yes, the leading target problem.  I remember solving this one for a programmer test a few years back.  Turned out to be a little harder than I expected.

You can model this as an intersection test between a line (the plane's location at time t) and a sphere of increasing size (the range of a bullet at time t).  There will be two points where, for some time t, the line intersects the sphere: one as the plane is approaching, and one as it's departing.  Since there are two intersection points, it's a good bet the solution will be a quadratic.  (There also may be no intersection points, if the plane is traveling faster than the bullet.)

Skipping all the math in between, here's some pseudocode for the final product.  I make no guarantees as to its correctness.  In fact, I'm pretty sure it fails in certain cases, but it's been years since I wrote it, so I can't remember when or why it fails.  Use at your own risk.

Code:

// Given:
// vec3 B: The bullet's initial location (turret location)
// float Sb: The bullet's speed
// vec3 P: The plane's initial location
// vec3 Vp: The plane's velocity
// Returns:
// vec3: the bullet velocity required to hit the plane
vec3 GetVb(vec3 B, float Sb, vec3 P, vec3 Vp)
{
	vec3	BP	=	P - B;
	float	a	=	Dot(Vp, Vp) - (Sb*Sb);
	float	b	=	Dot(2*Vp, BP);
	float	c	=	Dot(BP, BP);

	float	a2	=	(2.0f*a);
	float	root	=	sqrt((b*b) - (4.0f*a*c));
	
	float	t1	=	(-b + root) / a2;
	float	t2	=	(-b - root) / a2;

	float	t;

	if (t1 > 0.0f && t2 > 0.0f)
	{
		if (t1 <= t2)
		{
			t = t1;
		}
		else
		{
			t = t2;
		}
	}
	else
	{
		if (t1 > 0.0f)
		{
			t = t1;
		}
		else if (t2 > 0.0f)
		{
			t = t2;
		}
		else
		{
			// If this happens, it means there's no possible way to intercept the plane.
			// (Probably it's moving away from the turret faster than the bullet can travel.)
			t = 0.0f;
		}
	}

	vec3 Pt = P + Vp * t;
	vec3 Db = Normalize(Pt - B);
	vec3 Vb = Sb * Db;

	return Vb;
}

[Indievelopper]

Oh, yeah, look harder than what i'd expected too >_< .

I'll try to understand that(i just can't something i don't understand).

Thanks a lot!

edit : just took at look at your twipics.... for fuck sake, what is this perlin noise

[Tycho Brahe]

What lesson was this in?
 Because that feels like there should be a much simpler solution...

[J. Kyle Pittman]

What do each of the points and edges of the triangle represent in this example?  I assume the target is moving along one of the lines, and the weapon is located at one of the points, but I can't figure out which.

(Btw, there's another thread on this problem in the Tutorials section: http://forums.tigsource.com/index.php?topic=12590.0)

[Tycho Brahe]

How can A, in triangle ABC be a plane? its one of the vertices isn't it? could you provide a labelled diagram, cos I'm having trouble understanding what you're talking about...

[Pineapple]

Very exceedingly simple.

Angle_of_Ballistic_Travel = Atan2 ( Target_Y - Origin_Y , Target_X - Origin_X )

This trigonometric function can be a lifesaver, believe me.

EDIT: Err, just read a bit more thoroughly. It shouldn't be difficult to account for the bullet's and the target's speed, just make the target where the plane will be when the two lines intersect.

[slembcke]

Lol man, you'll never believe this.

I stood up in class, just like that, and wrote my problem to the board(i've translated that into a pure geometrical problem, where you have a triangle, and you only know the length of one side, an angle(the plane is going linear) and a ratio between the two other length).
He laughted, and took half an hour(yeah, in class) to resolve it, and finally came up with that :

Code:

in a triangle ABC where you know AB, the angle BAC, and that BC = a*AC :

AC = AB/(cos(alpha)+a*sqrt(1-(sin(alpha)*sin(alpha))/(a*a)))

And that works perfectly! look if a is smaller than one, there is good chance that the division by a² will fail(the bullet would be slower than the plane, it can still work but the plane need to be far).

Just in case you other people were looking for that, here is the answer, but i'll be posting the code with all functions later if someone wants it(currently coding it).

Thanks anyway for your help!

I'm not sure I follow. In your equation AC is the vector AB divided by a scalar. That would make AC and AB be collinear. Also, you didn't really explain what alpha was. Is it supposed to be the angle of BAC?

Assuming it works, and I'm just misunderstanding. I don't think this is really computationally simpler than the equation from the other thread that only used a single sqrt(). Yours uses a sqrt(), two trig functions and presumably another two sqrt() calls and an inverse trig function to get alpha. Also, which root does it find? Most of the time there will be two roots.

edit: I see, AB and AC are the triangle leg lengths. In that case you still need even more computation in order to triangulate the coordinate of C given the known A and B points and the lengths.

[Tycho Brahe]

I just did some stuff, and assumming that we have it in 2 dimensions, a turret on the ground and a plane passing over it at a constant velocity then we can simply use

arccos(a/b)

where:

a = velocity of plane
b = velocity of bullet

this is for a side on perspective, and now reading back it seems like the op wants it from top down

[BorisTheBrave]

14113: I get the same, doesn't seem to tough.

Here's my reasoning:
A = Plane start
B = Gun
C = collision (unknown)
a = plane speed
b = bullet speed
t = time till collision (unknown)

We want ∠ABC, the forward tracking. Call this β.
Can calculate ∠BAC, as we know A,B and the heading of AC. Call this α.

So, note AC = ta  and BC = tb. Use sin rule.
So
sin β / ta = sin α / tb
beta = arcsin ( ta / tb * sin α)
     = arcsin (  a /  b * sin α)

(which is the same as 14113 baring I've picked a more complex circumstance, and am measuring the opposite angle)

Because we can always find the plane that A,B, and the heading AC are in, we can solve for 3 dimensions straightforwardly.

Actually, I like the Pittman's method better, slembcke's link explains enough to make it clear how to derive it.

[Pineapple]

Here's a topic from a separate forum turned up by Google - Link

One of the posters relates finding the necessary angle for intersection to occur to finding where a line intersects a cone.

Rather than being in simply 2 dimensions, the poster explains, time must be considered as an additional third dimension. Thus, we aren't calculating the interception of an object in 2D X,Y space, but rather in 3D X,Y,Time space.

The airplane target's path is fixed, thus it is represented by a straight line (or more properly a ray) travelling through 3D space. Its start point is marked at (Initial X, Initial Y, 0 Time) and it continues along time at a constant rate and along X,Y as determined by its trajectory. The projectile's trajectory is determined by a cone. The vertex where the top converges is located at (Initial X, Initial Y, 0 Time). The surface of the cone is all possible coordinates this projectile can reach at any angle at any time at a constant speed. The height of the cone is the time, and the radius is related to its velocity.

Something to note is that if the target airplane is travelling more quickly than the projectile and is travelling in the same direction the bullet would need to be fired, the bullet will never reach the plane and there will be no points of intersection. However, if the bullet can possibly intercept the target, then there is a nearly absolute possibility that the interception of the solid and the line will occur at two points; the only exception would occur if the line is tangent to the cone. You would want to fire the bullet along the path that has the lesser Z axis - time - coordinate.

Here's some resources for how to determine where a line and cone intersect:
The formula w/ hefty explanation
Application as code

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.

[Tycho Brahe]

Ive just realised that we had almost this exact same problem in my mechanics mock paper a couple of weeks ago, the only difference was you were trying to work out the time when a boat was x km away from a lighthouse