Parabolic Aiming Calculation Help Needed.

#1 I have no clue what parabolic shooting is, and neither did Google. Shoot me if I'm talking about something way different than from what you asked :)

Quote:
With a parabolic shot I'd have to like...raycast maybe up at the angle of shot for so long, then over, then down?

Grab your forward vector, and the target vector. Diff, normalize, do dotProduct? You'll get the angle in radians, compare it to your FOV.

Quote:
The second problem is knowing what angle to shoot at for a given drag, gravity and muzzle velocity.

You shouldn't know what the drag or gravity is to lead a target. You need to know:

* Projectile velocity of your weapon.
* Target velocity. No gravity, no drag. Velocity is a result of those anyway.
* Your position and target position.

Then do:

F32 a = bullet_speed * bullet_speed - mDot (target_velocity, target_velocity);
F32 b = -2 * mDot (target_velocity, target - shooter);
F32 c = -mDot (target - shooter, target - shooter);

return target + (b + mSqrt (b * b - 4 * a * c)) / (2 * a) * target_velocity;

#2 A parabola is an arc. If you enable drag (ballistics) on a projectile and fire it into the air you'll see what I mean. Targeting enemies with a weapon of this nature requires a different method of shooting then with guns and beam weapons. Think catapaults, arrows and other old age projectiles hehe. I didn't know what else to call it, heh.

The drag will affect the shape of the projectile's arc, and therfore where the projectile lands. So the AI has to calculate what angle into the air it needs to fire to hit its target. The "hang time" of projectiles like these is what requires more advanced target leading. The AI will have to approximate how long the projectile will be in the air, then do a quick calculation to target the spot it thinks the enemy will be at. I guess all I really need is to know the time the hang time of the projectile and then I can calculate the estimated placement of the enemy. The problem is if the enemy is running away from you, the new location could be farther away, require a new aiming angle, and therfore have a larger hangtime. So some recursion would have to take place to correct for this error.

I hope that explains it in some more detail. I figure code has been written to solve this problem a hundred times over by now, and would like to avoid reinventing the wheel if possible :P Adding drag to some of the projectiles in my game will give it a much more realistic appearance, which is what I am aiming for.

The line of sight check is to determine if something can be hit. Bullets travel in straight lines, so their line of sight check is a raycast. Drag enabled projectiles arc however, meaning they can go over obstacles to hit their targer. Ideally the AI would know when it could lob something over a building to hit an enemy.

Thanks again for tips you can give me regarding this!

#3 Ouch, that's way out of my league.

Good luck to you.

#4 Here is a page I have used to help me with some various projectile formulas. The equations and built in calculators have helped me solve several problems and I think they will be helpful to you. Your knowns will be the launch velocity, the initial vertical displacement, and the final impact vertical displacement. Horizontal movement/velocity can be zeroed out, assume the ai is aiming toward the target. That just leaves angle of origin to solve.

In particular There is a solver almost at the end which will help you with the angle of launch needed :)

Trajectories

The formula you're looking for looks like this:

(Sin^-1(gR/vo^2)) /2



Starting in the middle in english:
a = (gravity * range) / (original velocity squared)
b = inverse sine of (a)
c = b / 2

c is your final angle.

There are 2 solutions for the equation also as the diagram on the page suggests

#5

Quote:The first problem with parabolic aiming, is detecting if the target is in my parabola line of sight. With traditional shooting I just do a raycast. With a parabolic shot I'd have to like...raycast maybe up at the angle of shot for so long, then over, then down? Can anyone think of an easier method?

If you want to check whether an enemy can be seen, then simply use a raycast like normal. After all, your soldiers will have to look in a straight line. If you're thinking about telling the AI whether their shot will hit things like the ceiling or a low roof over the enemy, you can just do some basic checks.
1. Is the firer inside? Chances are there'll be a roof, then, so probably no shooting. Unless you're standing by an arrow slit or similar, or looking out a window.
2. Is the target inside? Chances are there'll be a roof, and unless you're an amazing archer who can fire the wrong way through arrow slits, it's probably not worth trying
3. Do a very, very basic check to see if there are any buildings between you and the target. If so, maybe check their heignt - if it's too high, then don't risk a shot.
Based on the results of these checks, you may want to have some soldiers fire and some not. Or your commander guy could give an order to fire or not to fire.

Quote:The second problem is knowing what angle to shoot at for a given drag, gravity and muzzle velocity. I guess I could maybe come up with some formulas experimentally. In real life I could do the trig and come up with something - but I don't know if in game physics is modeled accurately enough for gravity and drag. Has anyone worked with this before?

The solution I would think of first is simply set up some demo scripts - create a projectile in mid-air, record its position, velocity, etc., then when it collides, echo its position, velocity. Graph these, get an equation with theta (angle of firing) in terms of distance to hit location, gravity, drag, wind, etc. Then simply plug those factors in when you need an angle.
The other option is to look inside the engine and figure out what factors are being taken into account, maybe derive equations of motion directly from the code. That may be a bit more complicated...

#6 The Stock TGE projectile doesn't include air drag, as far as I can see. It would be straight forward to add it for physics. You could add a wind field of whatever complexity as well, once you add drag. I'm not sure how it would affect the client/server model though. (I'm so far more used to the vehicles that use an updateforces.)

In the vehicles, a drag force linear with velocity is used in Stock Torque. A more realistic-to-the-real-world would be drag force that is proportional to speed squared. (Quadratic drag)

Once you add realistic quadratic air drag you make the problem non-linear and not amenable to analytic solution (you can't write down an equation for the path, or solve directly for the angle to aim at.) I don't know off hand if you can solve the trajectory analytically with linear drag, but I suspect you might be able to. (That isn't something that is studied much ;) , but is an interesting question.)

Even if you could solve it, you might just as well fire several test shots iterating toward the target. "Newton's Method" works well for this type of thing. It would likely be more robust and certainly easier to derive, requiring only 3 to 5 trajectories. In two dimensions (windage and elevation) for moving targets or with wind, use "Newton-Raphson". If you stick to problems that CAN be solved by analytic means (that is, linear drag I believe), the problem must be linear, hence Newton-Raphson should converge very quickly. (Essentially, one over and one under and the next one should hit.)

As long as you understand the big picture that there exist two solutions in general, a high and a low lofting shot, then you can iterate to find both of them if needed. My experience is with rifle bullet trajectories (fast and flat). In these cases, I have quickly iterated to hit targets. (I used to run hundreds of trajectories (integrating at the equivelent of TGE integration=16 or stepping 500 times per second) to build up a ballistics chart quickly enough to show it on the UI. It is nearly instantaneous with a 5 year old computer. Of course rifle trajectories are only about 2 seconds in length even though they fly fast.)

Your AI's won't need to be running this type of calculation continually, just when they decide to fire, or perhaps a few times per second and you can schedule it so not all of your catapults are thinking on the same tick. Nor do they have to complete the thinking on the tick they started it either, assuming that the target moves relatively slowly. After a couple seconds at even only one trajectory per tick they should have a pretty good solution. You would likely have to project your targets motion ahead in time as you said if the projectile is fairly slow so this gives the target the chance to dodge too since you would be aiming where they are supposed to be in the future when you fire.

For the catapults, it might be useful (and realistic) to prepare some kind of firing table before hand (target points that are pre-"zeroed" that the catapults know how to aim for. Use the closest zeroed point as the initial guess to start the Newton solver.) In real life they probably fired only when someone blundered into those zones anyway ;)

I have done this kind of thing professionally both in aerospace and in video games (4 real-world ballistics shooting games) so if you have questions, ask away. I can also provide a Newton-Raphson class you can start from if you decide to iterate. It uses my own vector and matrix classes and the STL however, so you would need to modify it to work in stock Torque but you should see the structure of the Newton-Raphson iteration in 2 or 3 dimensions there clearly enough.

#7 If you keep to drag linear in velocity, the trajectory with gravity can be integrated analytically.

With linear drag, the constant coefficient ordinary differential equations of motion are:
x'' = - x' a
y'' = - g - y' a
where g is the gravity and a is the acceleration coefficient due to drag (that is, drag force divided by mass per velocity).
y'' is the vertical accleration, y' is the vertical velocity, etc.

The drag is linear in velocity which is unrealistic to the real world but gives a "visible drag-like effect" while still allowing analytic solution.
See picture: [IMG]http://img169.imageshack.us/img169/5057/2dtrajdx5.th.jpg[/IMG]

Note that this example is set up for a lot of drag: kind of a wiffle catapult ;) It shoots the projectile off a 10m high wall at 15 m/s at a 45 degree upward elevation.


The simple equations should make the AI aiming solution very quick even if iterating. (You can likely use analytic derivatives for even more accuracy and convergence.)

Here is a "GnuPlot" script to plot one test trajectory as in the picture. The equations for x(t), y(t) which are functions of time, with x downrange and y vertical are near the bottom, just above the plot command.

Theoretically, you could invert these 2 equations to solve for elevation angle and time of flight, but the analytic solution would be very complex and also hard to use with multiple branches (see other forum threads you can find searching for things like "catapult").

The way I would suggest using these trajectory equations is to solve via Newton-Raphson, iterating to drive the x(t),y(t) to a moving in-the-future target point at time t, solving for the elevation angle and time-of-flight to hit the target point. This is a 2x2 problem and you can pre-calculate equations for the derivative of x with time-of-flight and so on, and analytically invert the 2x2 matrix to make the iteration even more accurate and fast.

I plan to sumbit a resource in the next week or so for a Newton-Raphson solver implementation for 2D and 3D problems using this as an example.

set title "---------- p_2dProj.gp -------------"
set grid
#set clip two
set terminal windows
set autoscale
set xtics
set ytics

set parametric
set dummy t

set xrange [0:15/0.7]
set yrange [0:15]
set xtics 0,5,100
set ytics 0,5,100

g = 10.0
a = 1.0

theta = 45.0   * (3.141592654 / 180.0)
v0 = 15.0

x0 = 0.0
xd0 = v0 * cos(theta)
y0 = 10.0
yd0 = v0 * sin(theta)

cx1 = xd0 # x'[0]
cx2 = x0 + cx1/a  # x[0] + cx1/a
cy1 = yd0 + g/a   # y'[0] + g/a
cy2 = y0 + cy1/a   # y[0] + cy1/a
x(t)= -(cx1/a) * exp(-a *t) + cx2
y(t)= -(g/a) *t - (cy1/a) * exp(-a* t) + cy2

plot [t=0:4] x(t), y(t)

#8 A Newton-Raphson resource is available to solve this kind of problem via iteration.
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=14749

As an example of what you can do with this (beyond the simpler "2D" example in the resource):

Set up a problem where the trajectory is integrated analytically similar to the equations above but in 3 dimensions, X,Y,Z.
Set up a moving target by assuming that the target keeps its current velocity.

Guess how far ahead you should aim (for example, 2 seconds: whatever you thnk the time of flight to the targets expected range will be). Guess what elevation angle and windage (lateral) aiming angles you should use. In most cases you could just aim up 45 degrees, and just aim at the target laterally. You shouldn't have to guess it too close to the final solution, but it should probably be at least far enough so the shell is well on the way down toward the target.

This results in an iteration problem with three "control variables" (variables the iterator changes trying to get closer to the target): elevation angle, windage angle, and time-of-flight. You set these to your initial guesses.

And three constraints (X,Y,Z error: where the catapult shell has flown to by the time-of-flight minus where the target is at that same time)

This is a 3 by 3 problem that the Newton-Raphson iteration should be able to solve.

The resource handles 2x2 and 3x3 problems. Larger problems take more complex matrix inversion techniques than are implemented in this resource.

#9 Well, I never got back to say thank you for the above comments and suggestions.

I took a look at your Newton-Raphson resource and it seems a bit much for what I had in mind. I have decided to just cut wind from the game right now. I may keep it as a special defensive spell effect, but the AI won't be compensating for it.

After relearning a lot of trig, I wrote some code that lets the AI arc shots accurately to hit stationary targets. All that is left to do is first calculate time of flight, and then calculate the predicted enemy position at that time - not too hard to do.

After seeing what I have in action I have to wonder if maybe it won't result in fun gameplay. While realistic physics are nice, sometimes it doesn't make for a good game. If the player builds a bunch of defenses and the enemy just runs around it - what good is it :/

So I took a step back and thought about my options. One option is to incorporate a to-hit roll and then the projectile flight is just eye candy. Another option is to make the projectile fly 2/3rds of the distance using traditional physics, then enable a "homing" option for the rest of the path.

I'm not saying it will look accurate - I know we've all winced at games where you shoot an enemy and the bullet curves around to make an impact. But its nice to know your built defenses are actually going to hit once and a while even if the enemies are wiley.

I've seen some resources for homing projectiles, but I'm not sure what would make sense for an eye candy projectile that conformed to a path that was intended to always visually hit the target. Does anyone have any ideas for that? Thanks again!

#10 Jason,

About a year ago I was in a thread called "Mortar Ballistics" where we worked out some code that you might use to add drag and target movements. It solved the base problem of hitting a target knowning its height (relative to mortar height), a desired muzzle speed and distance to target. Here's the code we used:

function p1( %v, %b, %r )
{ 
	return mSqrt(%v*%v*%v*%v - 2.0*%v*%v*%b*$g - $g*$g*%r*%r);
}

function p2(%v, %b, %r)
{
	return -2.0*%v*%v + 2*%b*$g + 2*p1(%v,%b,%r);
}

function p3(%v, %b, %r)
{
	return -2.0*%v*%v + 2.0*%b*$g - 2.0*p1(%v,%b,%r);
}

function a1(%v, %b, %r)
{
	return mAtan( ($g-0.5*%b*$f3)/(%v*mSqrt(-$f3)), 0.5*mSqrt(-$f3)*%r/%v );
}

function a3(%v, %b, %r)
{
	return mAtan( ($g-0.5*%b*$f2)/(%v*mSqrt(-$f2)), 0.5*mSqrt(-$f2)*%r/%v );
}


$PI = 3.14159265359;
$g=9.81;   

test(%v, %b,  %r)
{
//	%b=5;   
//	%r=2200;    
//	%v=200;   
	%k = %b*%b+%r*%r;   
	$f2 = p2(%v,%b,%r)/%k;   
	$f3 = p3(%v,%b,%r)/%k;   
	%b1 = a1(%v,%b,%r) * 180.0/$PI;   
	%b3 = a3(%v,%b,%r) * 180.0/$PI;   
	if( %b1 > %b3 )
		echo("Out of range!");
	else
		echo("b1,b3 =" SPC %b1 SPC %b3);
}

#11 Heh, I'd actually found that resource while searching and did make some use of it. Thanks for the link though!

My current problem is that...well.. I guess projectiles are very CPU intensive. With 5 towers shooting 20 arrows each every 500ms the game bugged out. Projectiles would not fire, would get fired from the wrong position, and the game would start stuttering.

I am doing it all in script, so maybe there are speed gains to be had by moving it to code. But thats a big pain in the ass :sigh: Would you consider the calculations above to be the sort of thing you can't do a lot of?

function Volley::onEndCasting(%this, %spell)
{
	%projectile = ArrowProjectile;
	%classname = %spell.caster.GetClassName();
	
				
	%botpos = %spell.target.getTransform();	  					// get the target position
	%mypos = %spell.caster.getTransform();						// get the caster position
	%distance = mAbs(VectorLen(VectorSub(%botpos,%mypos)));		// find the distance between them
	%aimangle = findangle(20, -1,  %distance);					// get the aim angle to hit the target
	%newheight = mTan(%aimangle*$PI/180) * %distance;			// calculate the height you should shoot above the target to hit
		
		
	for(%i=0;%i<20;%i++)
	{	
		
		if (%classname $= "AITower")
		{	// a tower is firing the volley, so we want it to arc
			%position = %spell.caster.GetPosition();	// get the caster's position
				
			%eye = %spell.caster.getEyeVector(); 		// get the caster's eye vector
			%target = %spell.target.GetPosition(); 		// get the target's position

			%x = GetWord(%position, 0);
			%y = GetWord(%position, 1);
			%z = GetWord(%position, 2) + 5;				// the tower is 5 units tall

			%position = %x SPC %y SPC %z;
			

			%x = GetWord(%target, 0);
			%y = GetWord(%target, 1);
			%z = GetWord(%target, 2) + %newheight + .3;	// add in the arc height and .3 so we aim at its chest.

			%target = %x SPC %y SPC %z;

//  echo("End Casting");
//echo("The caster's type is " @ %spell.casterType);
//echo("The caster's AIM is " @ %spell.caster.getMuzzlePoint(0));

			%eye = VectorSub(%target, %position);
			%eye = VectorNormalize(%eye);

//echo("Muzzle Velocity is " @ %projectile.muzzleVelocity);
//echo("Eyeball is " @ %eye);
//echo("Muzzle Vector Is " @ %muzzleVector);
//  echo("Veloc = " @ %muzzleVector);		

			%randomAngle = getRandom(1, 180)-90;	// get a random angle to modify the arrow by
			%randomDistance = getRandom(.75, 1.5);		// create a random distance
			%randomMuzzleVel = (getRandom(85, 115) * %projectile.muzzleVelocity)/100;
			
			%muzzleVector = VectorScale(%eye, %randomMuzzleVel);		
			
			%vec = VectorSub(%position, %target);			  // get a line from the tower to the target
			%vec = VectorNormalize(%vec);					  // Normalize the vector to a scale of 1
			%vec = VectorScale(%vec, %randomDistance);		  // 1 was a bit too much so we scale it down to .6
			
			%xAngle = %randomAngle * 3.1415926 / 225;
			%yAngle = 0;
			%zAngle = %randomAngle * 3.1415926 / 225;
			%matrix = MatrixCreateFromEuler( %xAngle SPC %yAngle SPC %zAngle);
			%Avec = MatrixMulVector( %matrix, %vec );		// find a point 90 degrees to the side of the main point
			%position = VectorAdd(%position, %Avec);			// now we have our point
		}
		else
		{
		// otherwise its the player casting it so just shoot in a straight line
			%eye = %spell.caster.getEyeVector();
			%muzzleVector = VectorScale(%eye, %projectile.muzzleVelocity);
			%position = %spell.caster.getMuzzlePoint(0);	
		}
//echo("Muzzle velocity is " @ %muzzleVector);
		
	  // Create the projectile object
	  %p = new Projectile() {
	     dataBlock        = %projectile;
	     initialVelocity  = %muzzleVector;
	     initialPosition  = %position;//%spell.caster.getMuzzlePoint(0);
	     sourceObject     = %spell.caster;
	     sourceSlot       = 0;
	     client           = %spell.caster.client;
	  };
	  
	  serverPlay3D(VolleyFireSound,%position);
	  
	  MissionCleanup.add(%p);
	} // for loop
}

Any recommendations? I'm using a simple spellcasting resource to manage all the attacks as "spells". I hope it makes sense. Please let me know if you need any clarification.

#12 I would be surprised if the execution of onEndCasting() twice per second is itself accounting for significant lag.

i too would be more suspicious of the number of projectiles in play at a given moment.

one test would be to gut all the calculations and just use a constant %muzzleVector and set %position to just be some very simple linear function of %i. (eg "0 0" SPC %i).

or try reducing the number of projectiles per pass to one or so.

.. wait, so if i read the code right, you expect to get the same %muzzleVector and %position for each of the 20 projectiles ? if so, you could certainly optimize by doing the calculations once and creating the projectile from the results 20 times. do the projectiles have random spread or something ?

#13 Hmm, you are correct that I could calculate the muzzle velocity and position only once, then apply the random components 20 times. Still, I was hoping to get 1000+ projectiles, not just a few 100 :P

EndCasting() is actually called twice per second by all 5 towers. If I have 100 towers placed then it would fire 200 times per second. I've been trying to think of "tricks" I could play to get the same effect without so much overhead, but am drawing a blank.

I'll setup some more test cases tonight if I have the time and revisit it. For my game I'd like to have something like your typical RTS (Supreme Commander or Total Annihilation) where each unit/building can fire off projectiles using collision and gravity. Perhaps the default projectile class is too heavy for such a use - but on the surface it wouldn't appear to be. That or perhaps my goals are unrealistic!

#14 Firing 200 projectiles per second is quite a lot.
i would expect the system to handle a few hundred projectiles without too much trouble,
but when you start getting above 500 or so i think you're going to start saturating the networking.
what's the average lifetime of each projectile ?

#15 Hmm, the arrows can fly for about 5-6 seconds each? I've sped them up a bit to help out.

How do real time strategy games handles thousands of projectiles and bots pathfinding simultaneously? Games like Supreme Commander?

Does anyone have ideas for fake projectiles that don't use as much resources? Say I wanted to just shoot an enemy using a raycast and a to-hit roll, then make a projectile that is eye candy. It wouldn't need the same kind of overhead a normal projectile would need (ie, collision, network synching). Has anyone done this before?

#16 So you're looking at maybe 1000 or 1200 or so projectiles in flight at any given time,
which is an awful lot to do physics & networking on.

i'm not sure how other games deal with a situation like that.

as you suggest, one way might be to eliminate the real collision detection,
and do a custom ghosting routine which instead of constantly broadcasting the position of the object simply broadcasts the starting point, velocity, and time of the object, as well as the end time, and only checks for collision at the end time. that would reduce networking & physics quite a lot, but also wouldn't allow for more complex interactions such as hitting some unexpected intervening object.

#17 Dang, you know just having 5 towers shooting 5 arrows each every 2 seconds is too much. This is ~25 projectiles fired every 2 seconds.

I am beginning to think maybe it is not processing related. Wouldn't my framerate be dropping really badly if that were the case?

I am seeing the first tower shoots fine, the second tower shoots a bit later with the projectiles appearing farther out, and by the last tower the projectiles are appearing quite a bit farther out from the tower and the sound is delayed by about a second.

I'm going to go sort out some of the engine changes I added to fix the bug where bots would herky-jerky skip about. Maybe some "tweak" I made is creating issues with the network code :( That or there is something else I am missing here.

#18 Sounds like you're on the trail.

one thing i do when i suspect i've screwed up the engine is go back to a clean copy of the stock engine and test stuff out there.

i agree, it sounds like networking versus processing.

~25 arrows every two seconds w/ a lifespan of six seconds means about 75 objects in flight at a given time, and 25 being created every two seconds. i've found that there's a networking hit when an object comes in to network scope (eg when it's created), so it might not be the 75 in flight, but the 25 new ones. i've toyed with the idea of keeping a pool of objects instantiated on the client and calling them up as needed rather than instantiating new ones, but that sounds like a bit of work.

#19 I'm not sure if this sounds like a usable idea, but what I'd do is I'd precalculate an array of values depending on range and height offset. I'd calculate the matrix for these for each weapon type before the game begins, and use these calculations for every single shot. Ie. for an arrow you would have a 2d array of values such as (pseudo code):

angle = arrowShotMatrix[range][hOffset]

Generating the angle matrix is not so hard this way, the only thing you have to decide on is how refined / rounded the stored range / height offset values are. For example, you could step both range and height offset by 0.5 and see how that works out.

You also could rule out extremes - say a distance of less than 5 units is close range and the bow cant be used, or when abs(hOffset) is larger than the actual range you are calculating for, you can just skip the calculation, and mark the shot as impossible (for which there is no value in your matrix).

I'd go further, and generate these matrices only when your weapons' properties change - much like a lightmap. This could be loaded externally as a generated script, or even better - you could make a quick wrapper around it and handle the whole thing in code.

I have a feeling that'd be REALLY fast. :) You might still have network issues, to which Orion's solution sounds really good (not having to recreate projectiles), but at least you could definitely rule out the calculations - they would not weight so much.

#20 Interesting approach - I'll try it.

My projectile issue goes even deeper, and I've eliminated any engine changes as the root cause. All I had done was increase the ClientPacket rate and size anyways. The herky jerk walk fix was adding a check for ghosted IDs.

So.... its confusing :P I find that even if I have NOTHING going on in game, if my player casts a "spell", there is a 1 unit or so variability in where the projectile actually appears. If there is a lot going on in the game this obviously increases. I do not think that creating a new projectile should be such a resource consuming operation.

Can objects only be created on certain tick boundaries? Has anyone else seen this before where projectiles don't start where they should? So confusing... My towers are all firing every 2 seconds based off schedules created when they are created. Yet the projectiles all try to appear at once, as if the schedule isn't the controlling factor or something.

Oh, and does anyone have a tried and true method for measuring passed time in Torquescript? I want to put some timestamps in to see if adjustments I am making are resulting in the performance gains I am looking for.

Thanks again for all the help everyone :P