===Premise===
The issue: Okay, so your making any kind of a game with a pretty damn fast pace, and while any human player knows how to lead a moving target, how the hell are you going to make your rather stupid-looking CPU's hit the player back?

There are two ways I've found that klikers mask this problem (without solving it):
1) Make all bullets instant hit (gets really old after a while)
2) Make the directions the enemies shoot in random enough that they get lucky sometimes and hit you anyway (looks ridiculously bad)

Why does nobody ever address the damn problem anymore? :/

So, i decided i will include three examples to try to convince people to add this simple little feature (with varying quality in the results and modification):

1st method: (balance the equation)
Degree of modification: You would only need to change the actions that give the bullet a direction
Relative ease: Ridiculously simple

2nd method: (iterative)
Degree of modification: You wouldn't modify the shooting equation, but you would need to add a fastloop and modify the bullet's heading
Relative ease: Definitely worth your time

3rd method: (quadratic equation)
Degree of modification: You would need to add multiple events and modify much of a formula (your definitely gonna be solving a quadratic equation in TGF2...)
Relative ease: None at all, definitely not worth it. Unless, of course, this happens to be a very important issue to you.

Feel free to pick the solution you want and scroll down to the appropriate part


===Balance the equation===
This is a little trick I figured out myself while trying to solve the 'moving target' issue

For this to work, your bullets need to be moved by actually adding the vectors' components rather than a heading and speed:

Like this:
<pseudocode>
//Create our bullet
+On loop('shoot')
->Create object ('bullet') at 0,0 from turret
->set xAdd of bullet to 'sin(angle('turret'))*bulletSpeed'
->set yAdd of bullet to 'cos(angle('turret'))*bulletSpeed'

//Move our bullet
+Always
->set X coordinate of bullet to 'X('bullet')+xAdd'
->set Y coordinate of bullet to 'Y('bullet')+yAdd'
</pseudocode>

NOT like this:
<pseudocode>
//Create our bullet
+On loop('shoot')
->Create object ('bullet') at 0,0 from turret
->set heading of bullet to 'angle('turret')'
->set speed of bullet to 'bulletSpeed)'

//Move our bullet
+Always
->set X coordinate of bullet to 'X('bullet')+sin(heading('bullet'))*bulletSpeed'
->set Y coordinate of bullet to 'Y('bullet')+cos(heading('bullet'))*bulletSpeed'
</pseudocode>

Personal opinion: You should use the former anyway, it's better to only compute the sin() and cos() once than in every frame that the bullet is in flight.

Anyway, what you do is simple: you add the vector components of the target to the vector components of the bullet! (in our example above, this is 'xAdd' and 'yAdd') The bullets will hit the target like its sitting still (and I really mean this in the most literal way)

Why this works:
If you think of it like an equation, the goal is to have the target's position equal the bullet's position at some future point in time:

X('bullet') = X('target')
Y('bullet') = Y('target')

But, the target is moving! The equation, as they say, is unbalanced; and we are going to need to compensate for this. Remember middle school algebra, where to negate something on one side of the equation you simply added it to the other? Well, we can simply add the target's move vector to the bullet's move vector and instantly the equation becomes balanced.


Example:
<pseudocode>
+On loop('shoot')
->Create object ('bullet') at 0,0 from turret
->set xAdd of bullet to 'sin(angle('turret'))*bulletSpeed+sin(angle('target'))*moveSpeed('target')'
->set yAdd of bullet to 'cos(angle('turret'))*bulletSpeed+cos(angle('target'))*moveSpeed('target')'

+Always
->set X coordinate of bullet to 'X('bullet')+xAdd'
->set Y coordinate of bullet to 'Y('bullet')+yAdd'
</pseudocode>

(I bolded the key part!)

Upside:
-You only have to make a small modification to events that would have been there anyway

Downside:
-you have to mask the effect by having high bullet speeds. (If the target is moving fast, and its moving towards you, the bullets might appear to 'float' out and hit the enemy!) Similarly, if the targets moving away, you'll notice a significant improvement in how fast the bullets fly (lol).

Extra explaining: What I mean when I say 'the bullet hits the target like its standing still' is that the bullet always hits the target with the same relative speed! So, relative to the target, the bullet will always hit with the same speed whether the target's sitting still, or flying towards you or away from you. But, relative to the player, the bullet doesn't seem to be flying at a constant speed. Short answer: its not

But, this does solve the problem without even having to touch on possible cases like 'what if the bullet isn't fast enough to catch the target?'

No headache, no mess! I think you owe it to yourself to at least try to implement this

For an example, use frame 9 of my general example:
http://www.mediafire.com/?wnjmmiznmne


Right on, next we can use the
===Iterative method===
This is the most intuitive method I've found, and this happened to be the only one I knew would work (until I discovered the next one of course).

Now, when most people try to find a solution to the moving target issue, their first idea is to find the distance between you and the target, find how long it would take the bullet to close this distance, then aim that far ahead of your target. It makes sense, and people never can figure out why it cant work. Well, the reason? This method doesn't take into account the fact that, because the target never stops moving, the distance between the shooter and the target is changing. The flaw in this method is that assumes that the distance remains constant. (The only way this method would obtain a hit would be if the distance did remain constant, eg. if the target was flying perfect circles around the shooter)

But, the method will get the bullet closer to the target! So how can we can we actually score a hit doing this? Easy, simply continue to iterate this method.
(Every time we do this, it gets the bullet just a little bit closer to the target)

Just some talk about theory (using vector math for simplicity):
To aim perfectly, we would need to know how long it would take the bullet to hit the target, then aim exactly that far ahead of it:

targetPosition + timeToTarget*targetHeading*targetMagnitude

This is how you would guarantee a perfect hit. We already know the target's position, heading, and magnitude, but what we dont know is how long the bullet will take to reach the target.

Heres how we have been calculating timeToTarget:
(where 'bulletSpeed' is a scalar)

timeToTarget = dist(shooterPosition, targetPosition)/bulletSpeed

The issue is, it doesn't take into account that the distance to the target will not remain a constant while the bullet is in flight, meaning that our time estimate is wrong. So how would we make it possible to reiterate this event for better accuracy? Simple:

timeToTarget = dist(shooterPosition, targetPosition+targetHeading*targetMagnitude*timeToTarget)/bulletSpeed

So in essence, you:
1) Find the distance to the target
2) See how long it will take the bullet to close this distance
3) Find how much the target would have moved in this time
4) Then find the distance to the target's new position and repeat from (2)...

For those who visualize things better, here's what actually is going on every time we iterate it:
Image

Given a moving target at a 'reasonable' range (within 1000) pixels, reiterating this 5 times is enough to reliably hit the target. The biggest deciding factor in the reliability, surprisingly, isn't speed, but range. This method has no problem hitting a target at ridiculous speeds; but as the range increases, so does the number of iterations necessary to produce an 'acceptable' result. (Simple solution: give units that lead targets with this method a 'maximum attack range')

Another improvement:
Say a fixed iteration amount isn't good enough for you, and you wanted to guarantee that the target will be hit to within, say, 5 pixels of perfect, you could feed the results into a recursive event that will compare how far the target moves every time, and if its over 5, reiterate. This does have the added advantage that it will only iterate as much as necessary; it won't continue if it only took 2 iterations to reach the 'error tolerance'

Using an error tolerance can be risky though:
1)The farther out the target is from the shooter, the more iterations it takes to get within the error tolerance (This means at normal distances, it could take as few as 3 iterations, but at distances > 8,000 pixels Ive actually gotten frame rates LOWER than 1fps)
2)You can NEVER set the error tolerance to zero! If you do, the game is guaranteed to crash, as 0 would be perfect, and this can never reach perfect, only approach it (but the game will iterate endlessly trying to reach it anyway).
3)The bullet must be faster than the target, or else the game will freeze. (If every time it iterates the distance to the target gets greater?! It will never reach the error level.)

The upside to this:
-No dodgy changing the bullet speed, then masking it with higher speed The bullet can be as fast or as slow as you want.
-The results are very convincing, the player wont be able to tell the difference.

Downside:
-Moderate rearranging of the code
-The quality of the results can be very dependent on the situation
-Certain error tolerances at certain distances can completely eat up your CPU

For an example, check out frame 11 of my general example:
http://www.mediafire.com/?wnjmmiznmne


===Quadratic equation===
WARNING: To give you an idea of just how bad this is, you have to break the equation up into parts to avoid getting an 'expression too complicated' error in the expression editor. Proceed at own risk.

Okay, so remember from earlier how you could guarantee a perfect hit on the target if you could just figure out how long it would take the bullet to hit the target? Well this is the only perfect method, it figures out the time by formula. To implement this, you will need to reserve a temporary variable (it doesn't have to be local, it can be a global value or something) and a local variable inside whatever object's doing the shooting for saving the time it will take the bullet to reach the target (in this section, referred to as 'timeToImpact').

Upside:
-The only perfect method to ensure a hit on the target.
-Requires the same amount of events no matter where the target is or how fast its moving, the results aren't dependent on the situation.

Downside:
-Complicated as mess.
-If you make so much as a single mistake, due to the above point, your screwed.
-I am no mathematician, I do understand the reasoning behind it, but barely enough to explain it.

Ill do my best to explain why its a quadratic.
Because the equation factors in both the target position/move vector and bullet speed, the nature of the solutions means that:

If the bullet is faster than the target, you have two solutions,
1) You can shoot at the target while it's heading towards you (the positive root to equation)
-and-
2) You can also shoot at the target while its heading away from you (the negative root to equation)

If the bullet is slower than the target and its heading towards you, you have one solution,
1) Shoot where the target will run into it (the only root to equation)

And if the bullet is slower than the target and the target is heading away from you, you have no solutions.

Either way, I will go ahead and post credits now:
(I found this on the usenet forums)
http://www.usenet.com/newsgroups/comp.games.development.programming.algorithms/msg00957.html

If any of you guys are good with your vector algebra, then the above article can explain the 'whys' of it much better than I can and I would strongly recommend you take a look.

For those of you who are not the best with their vector maths, there is a very fast way you can implement this (using copy/paste and notepad!).

Now, remembering from the second method that the only thing we need to produce a perfect hit on a target is the time it would take a bullet to reach it, this author has posted two equations that will solve this problem for us:

The first:
timeToImpact = [ - dot(V,R0) (+/-) sqrt( dot(V,R0)^2 - (v^2-s^2)d0^2)]/(v^2-s^2)

And the second:
timeToImpact = d0 [ - dot(V,R0)/d0 (+/-) sqrt( (dot(V,R0)/d0)^2 - (v^2-s^2))] / (v^2-s^2)

(Don't worry about what all the variables mean, they represent different vectors)
Now, to apply a vector equation like this to a scalar program like TGF2/MMF2, we need to convert the vector terms into scalar terms and supply all the necessary variables. I won't bore you with how I manipulated the equation though, I'm sure you just want to get to the good stuff


Notice: To make this work, first copy to notepad so we can use our handy replace feature (with case sensitivity on):
-Replace all single quotes (') with double quotes(''), as this webpage removes double quotes (or I would have already done this for you)
-'targetHeading' with the name of your variable for your target's move direction
-'targetSpeed' with the name of your variable for your target's move speed
-'bulletSpeed' with the name of your variable for your bullet speed
-'Target' with the name of your target
-'Turret' with the name of whatever's shooting the bullet



Notice all the 'dot(V,R0)' in the second time equation from above? Those are dot products of the two vectors 'V' and 'R0', and more importantly what I chose to single out to make TGF2 stop complaining about complexity.

So, set your first temporary variable to:
temp1 = dot(V,R0) = (Sin(targetHeading('Target'))*targetSpeed('Target'))*(X('Target')-X('Turret'))+(Cos(targetHeading('Target'))*targetSpeed('Target'))*(Y('Target')-Y('Turret'))

Then, using our temporary variable from before, set your variable for time to:
timeToImpact('Turret') = DistPoints('Clickteam Movement Controller, X('Turret'), Y('Turret'), X('Target'), Y('Target'))*(-1.0*temp1/DistPoints('Clickteam Movement Controller, X('Turret'), Y('Turret'), X('Target'), Y('Target'))-Sqr((temp1/DistPoints('Clickteam Movement Controller, X('Turret'), Y('Turret'), X('Target'), Y('Target'))*(temp1/DistPoints('Clickteam Movement Controller, X('Turret'), Y('Turret'), X('Target'), Y('Target'))))-((targetSpeed('Target')*targetSpeed('Target'))-(bulletSpeed*bulletSpeed))))/((targetSpeed('Target')*targetSpeed('Target'))-(bulletSpeed*bulletSpeed))


=O Crazy! But its true, that really will produce the exact time that a bullet of the given speed will hit your target. You should know what to do now, all you have to do is take the time and plug it back in to the pseudo-equation from the last method!

-Many kudos to Ron Levine for being such a damn good mathematician and coming up with that equation in the first place.


===Conclusion===
Hopefully this helped somebody. My apologies about the last method being such a mess, but its the only 'real' way to do it, and I felt that this article would be incomplete without it (as atrocious as the method is to look at).

Anyway, I believe that I have just made it so easy to lead a target that if you read this and continue to have your CPU's aim behind their moving targets, your just lazy

-Cameron
EDIT: 5/1/09 Added in picture, major edits for clarity and fluidity