Determining fire angle to hit a specific point...

[ImprisonedPride]

Hey all. Got a tricky question. Say I have two points and one point was say... a cannon in a game. The cannon has limited power, and can only shoot so high and so far. I'm trying to think of a way that I could manage to check and see if a shot can reach a specific point, and also how I calculate the formula the make a bullet how the path to the target? I mean if the point is too far or too high from the cannon, obviously the cannon wouldn't be able to hit it, and I'd rather disallow the cannon from firing at all than to fire and miss. Any ideas? Is this using Bezier Curves?

[renderhjs]

wouldn´t that be simple quadratics?
e.g

y = a*x² + b*x + c;

where a and be determine the curve itself and c displaces the curve itself on the y- axis.
http://en.wikipedia.org/wiki/Quadratic_equation
at least with that formula you could calculate the y- coordinate based on the x- coordinate.

I wouldn´t do splines if it´s not needed. There are some Catmull-Rom Spline code snippets even for flash on the net where you define some rough points and it will interpolate smooth between them. That way you can even calculate the excact point on a given spline at a certain spline distance or percantage.
I wrote some of that stuff myself some time ago for a 3d tool that used motion splines in 3d space. I can digg it up for you if you need it
otherwise some other links:
http://www.algorithmist.net/cranimation.html
http://algorithmist.wordpress.com/20...ll-rom-spline/
http://www.mvps.org/directx/articles/catmull/

[VENGEANCE MX]

Had to do this as part of my work experience.

http://en.wikipedia.org/wiki/Trajectory_of_a_projectile

Choose 'Angle θ required to hit coordinate (x,y)' or 'Angle of reach'. I'd go with the former (or to be more specific, I went with the former), because it supports firing from a point raised above the ground.

Also note that there's a stage in this equation (finding delta), that you can determine whether or not you're getting an imaginary number (ie, if the value you're square rooting is negative). This will happen if your shot, given the allocated power, is incapable of reaching its target. What I do in this situation is tell the AI to walk closer before firing.

Also, at the ± point, you can follow either + or - for one of two different projectile arcs. I did this to mix it up a little, so some shots would arc high, and others low.

By the way, there's no way to make it choose both power _and_ angle for you, because there's an infinite number of possibilities. If you had to make it look like the enemy was choosing the power, I'd just make it pick a random power and see what angle it has to use to compensate.

[rje]

Looks like I was beaten to it by the previous post :-)

I implemented this in AS3 and it was very fast (http://home.planet.nl/~borst595/Sepe...ineOfSight.swf)

I added some predictave targeting in as well, also worked. I'll post the function here where I get back home.

[ImprisonedPride]

Good responses people. I really appreciate it.

V, the cannon is at a constant point above ground level and will always fire a constant max velocity.

The whole point of this is so that i don't have to check each projectile to see what they hit, I will know before hand what the target will be and I can apply damage when the project reaches it's target. That way I can just use priority and range to determine what object the cannon will fire at. (Basically you place the cannon and then the cannon takes over from there.) i.e. if an enemy cannon is within range, fire at the cannon, else fire at any other random enemy object within range.

[ImprisonedPride]

EDIT: Pissed...

So I'm trying to convert



to flash's math context. I thought I had it correct (working out ok on paper), but when I do it in Flash I always get NaN for my value.

Here's what I got two different ways in flash (first step by step, and then all at once):

// step by step
    x = _xmouse;
    y = _ymouse;
    v = 30;
    g = .96;
    b = Math.pow(v, 2);
    c = Math.pow(v, 4);
    d = g * Math.pow(x, 2);
    e = Math.pow(v, 2);
    f = 2 * y * e;
    h = g * (d + f);
    i = c - h;
    j = Math.sqrt(i);
    y = b + j;
    x = g * x;

    angle = Math.atan2(y, x);

// and now all at once

angle = Math.atan2((v * v) + Math.sqrt((v * v * v * v) - g * ((g * x * x) + 2 * (y * v * v)))); 

If anyone's got a quick second (someone who's used this before), could you double check to see where I might be going wrong?

[tonypa]

both work for me

x = _xmouse;
y = _ymouse;
v = 30;
g = .96;
angle2 = Math.atan2 (v * v + Math.sqrt (v * v * v * v - g * (g * x * x + 2 * y * v * v)), g * x);
b = Math.pow (v, 2);
c = Math.pow (v, 4);
d = g * Math.pow (x, 2);
e = Math.pow (v, 2);
f = 2 * y * e;
h = g * (d + f);
i = c - h;
j = Math.sqrt (i);
y = b + j;
x = g * x;
angle = Math.atan2 (y, x);

[rje]

This was my code. Replace the Vector2D class with any vector or point class.

public static function calcTrajectory( startPos:Vector2D , targetPos:Vector2D , projVelocity:Number , gravity:Number ):Number {

	var targetX:Number = targetPos.x - startPos.x;
	var targetY:Number = -(targetPos.y - startPos.y);
	var r1:Number = Math.sqrt(  (projVelocity*projVelocity*projVelocity*projVelocity) - gravity*(gravity*(targetX*targetX) + ( (2*targetY)*(projVelocity*projVelocity) ) ) );
	if (!isNaN(r1)) {
		var a1:Number = ( (projVelocity*projVelocity) + r1 )/(gravity*targetX);
		var a2:Number = ( (projVelocity*projVelocity) - r1 )/(gravity*targetX);
		a1 = Math.atan(a1);
		a2 = Math.atan(a2);
		a1 = -a1 * 180 / Math.PI;
		a2 = -a2 * 180 / Math.PI;
		if (targetX<0) {
			a1 -= 180;
			a2 -= 180;
	             }
		return a1; //or a2
	}
	return null;
}

[VENGEANCE MX]

Your x and y are wrong. The article says x is the range you want to travel, and y is the altitude. So you use relative coordinates. That's not the only problem. I reckon your y value needs to be negative, because of Flash's inverted y axis. As in rje's code, this is (probably) what you need to use:

x = _xmouse - cannon._x;
y = -(_ymouse - cannon._y);

Also, NaNs can come from not having enough power. As I said, the NaN comes when the value under the square root is negative (so if your variable i comes out negative, you've got a problem). Check your values of c and h, and all their dependencies. Might help shed some light on things.

[rje]

btw I also found I had to tweek the gravity variable a little to produce good results.

[ImprisonedPride]

Yeah I figured in the possibility of not having enough power, but the cannon wouldn't turn to the right angle if I got a number at all (which was always between 1 and 2), and even clicking only a few pixels away from the cannon still gave NaN with 30 power.

So I got it to work via rje's method. My beef is this. Now you have the angle, how do you fire the projectile based on the velocity of the cannon? In this case it's 30, but how would I convert that to the sin/cos method of moving the projectile along the curve?

[VENGEANCE MX]

IP, the reason you were always getting a value between 1 and 2 is that you were working in radians the whole time. D'oh!

As for firing the projectile, there are two ways to do this. One frame at a time, like this:

x += xs;
y += ys += g;

Finding xspeed and yspeed is relatively straightforward... used a projectile script in this little sandbox:

http://www.birchlabs.co.uk/Cannon.zip

You're in luck, because I think that's the only fla I've EVER commented. Can't remember why. Here's the snippet you'll be interested in:

// When the mouse is clicked:
onMouseDown = function () {
    // Declare Trigonometric variables for the ratio of yspeed to xspeed in the cannonball we make.
    sine = Math.sin(cannon._rotation*degToRad);
    cosine = Math.cos(cannon._rotation*degToRad);
    // Attach a new cannonball into the cannonballs movie clip.
    cannonballs.attachMovie("cannonball", "cannonball"+cannonballs.getNextHighestDepth(), cannonballs.getNextHighestDepth(), {_x:cannon._x+sine*cannonLength, _y:cannon._y-cosine*cannonLength, xs:sine*cannonPower, ys:cosine*-cannonPower, g:-.5});
};
// This part from the main loop:
// Move the ball horizontally.
c._x -= -c.xs;
// Move the ball vertically, apply gravity to its yspeed.
c._y += c.ys -= c.g;
// Set ball's rotation
c._rotation = Math.atan2(c.ys, c.xs)*radToDeg+90; 

The other way is to just increment a time variable each frame, and set the x and y position accordingly:




Which is more flexible, for obvious reasons.

[ImprisonedPride]

I may truly consider using the time restraint so that I know when the projectile hit's the target. Thanks a million V, and yes, I realized it was in radians after reviewing the wiki page again.

[VENGEANCE MX]

Glad I could help. Glad I've had a chance to save someone else the hours I spent trying to get that working myself.

[webgeek]

Not sure if this is still useful or not but Jobe posted this recently:
http://jobemakar.blogspot.com/2008/0...-shooting.html

Basically, perfect accuracy on a constantly moving target.

[JerryScript]

Not sure if this is still useful or not but Jobe posted this recently:
http://jobemakar.blogspot.com/2008/0...-shooting.html

Basically, perfect accuracy on a constantly moving target.

Don't you mean perfect accuracy on a consistantly moving target?

I don't think Jobe's algorithm (or anyone's for that matter) can hit a constantly moving target unless it's motion is consistant (either linear or curvi-linear).

[webgeek]

Yup, as soon as I typed it I knew it was poorly phrased. I figured someone would come out of the woodwork to correct me. What I was thinking when I typed it was "perfect accuracy on a target with constant motion - ie, unchanging".

[rachil0]

Actually I think you could develop similar tracking algorithms that work with higher order accuracy. It's trivial to solve the problem when the target has constant position, and not too much worse to solve the problem when the target has constant velocity. Though I haven't done it, I would think the constant acceleration case is doable. It might even have a nice closed form solution but IDK. Once you know the position and its time derivatives, the motion of the target is deterministic (clockwork) physics. The firing solution is the intersection of a smooth space curve and a cone (at least, in 2D position).

You can extract higher order derivatives of the position from the target using multiple position observations and finite differencing them. Finite difference two recent position observations to get a velocity estimation, finite difference three position observations to get an acceleration estimation, and so on. Of course, if velocity is a state variable of the target anyway, just finite difference two velocity observations to get the acceleration estimation.

I think it would be a really fun problem to work on more but no time ATM.

[JerryScript]

Actually I think you could develop similar tracking algorithms that work with higher order accuracy. It's trivial to solve the problem when the target has constant position, and not too much worse to solve the problem when the target has constant velocity. Though I haven't done it, I would think the constant acceleration case is doable. It might even have a nice closed form solution but IDK. Once you know the position and its time derivatives, the motion of the target is deterministic (clockwork) physics. The firing solution is the intersection of a smooth space curve and a cone (at least, in 2D position).

You can extract higher order derivatives of the position from the target using multiple position observations and finite differencing them. Finite difference two recent position observations to get a velocity estimation, finite difference three position observations to get an acceleration estimation, and so on. Of course, if velocity is a state variable of the target anyway, just finite difference two velocity observations to get the acceleration estimation.

I think it would be a really fun problem to work on more but no time ATM.

I can see how this would work using brute-force, but I'm not sure how you would work out the max/min deviation for a non-brute-force approach? Is it possible to work it out dynamically, or would it have to be based on known physics of the object (ie how fast can the object change velocity in any single axis)?

I think radar tracking still uses a table lookup, but I couldn't tell you the paper I read that in if my life depended on it!

[rachil0]

All right looked at this some more and I think no brute force is needed, the constant acceleration case does have a closed form solution. You need to solve a quartic polynomial in t, so it just barely makes the cut.

Assume the firer is at the origin (x=0, y=0) and needs to decide which direction to fire. The fire time is the origin of the time axis, t=0.

Assume some oracle tells you the position, velocity and acceleration of the target all at time t=0. In reality this oracle is either peeking into state variables of the target, or finite differenced observations like mentioned earlier. Denote these quantities px&py, vx&vy and ax&ay. (For position, velocity and acceleration respectively). Any higher order variations in position (like jerk) are ignored and assumed zero.

Given these observations, the position of the target changes in time as:

x(t) = px+t*vx+1/2*ax*t^2
y(t) = py+t*vy+1/2*ay*t^2

Assume the velocity of our bullet is V. So as time marches on, the position of the bullet will be along some ray cast out from the tower, where the (radial) distance from the tower to the bullet is:

r = V*t

[Now, the cone intersection part]. We'd like to figure out a time such that the bullet and the target are at the same radial distance from the tower. The targets radial position is:

r(t) = sqrt( x(t) ^ 2 + y(t) ^ 2 )

So, we're looking for a time such that:

sqrt( x(t) ^ 2 + y(t) ^ 2 ) = V*t

Square both sides

x(t) ^ 2 + y(t) ^ 2 = (V*t)^2

Move everything to left side

x(t) ^ 2 + y(t) ^ 2 - (V*t)^2 = 0

Now, expand out out x(t)^2 and y(t)^2 and group like powers of t:

(1/4*ax^2+1/4*ay^2)*t^4+(vy*ay+vx*ax)*t^3+(py*ay+vy^2+px*ax+vx^2-V^2)*t^2+(2*py*vy+2*px*vx)*t+px^2+py^2 = 0

This is a quartic equation in t. It can be solved in closed form like this. This is a drawn out procedure in and of itself, and it involves solving a cubic equation along the way. But it's a 400 year old, documented procedure so someone can surely find source somewhere that does it already.

There are four possible solutions. Some of them will probably be negative, indicating that a hit would be possible if we were to run the simulation in reverse. Those aren't solutions we're interested in. The root of interest is the smallest t that is still positive. Call this t_collide. At this time, the bullet and the target could be in the same place, if we fired right now, in the right direction. What direction is right?

Figure out where the target is going to be, at time t = t_collide:

x_collide = x(t_collide) = px+t_collide*vx+1/2*ax*t_collide^2
y_collide = y(t_collide) = py+t_collide*vy+1/2*ay*t_collide^2

So fire the bullet, right now, in that direction.

fire_angle = Math.atan2(y_collide, x_collide)

If we do that, the bullet and target will have the same coordinates (in polar form, relative to the tower) at time t_collide. Any holes in the logic? Would love to see this get implemented.

Should be possible to have the tower accelerating and moving as well. Changes very little, except the velocity and acceleration variables need to be measured relative to the tower. (IE ax = ax_target - ax_tower; ETC).