Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Say I have a moving circular target defined as:

Vector2 position;
Vector2 velocity;
float radius;

And a rotating turret (mounted on a moving vehicle of some kind) defined as:

Vector2 position;
Vector2 velocity;
float angle; // radians
float angularVelocity; // radians per second
const float maxAngularVelocity; // radians per second
const float maxAngularAcceleration; // radians per second per second

(Or something along those lines. Note that position and velocity of both are controlled elsewhere - assume velocity is constant and position changes based on velocity.)

I am trying to write two related AI functions to determine, on a given frame:

  • What angular acceleration (and in which direction) to apply to the turret's angle to keep the turret pointing at the target?

  • If the target is currently in sight, can it (any part within its radius) be kept in sight for x seconds, where x is a fraction of a second? (Alternatly: is there another strategy to ensure the target is actually "locked on" and not simply flying across the sights?)

And I could use some help...

share|improve this question
    
You might have different values for rotational acceleration and deceleration - in the real world, one's probably a motor and the other a brake. –  e100 Mar 22 '12 at 15:36

5 Answers 5

up vote 17 down vote accepted

First you need to determine the difference in angle between the turret facing direction and the direction to the target.

Vector2 turretToTarget = target.position - turret.position;
float desiredAngle = atan2(turretToTarget.y, turretToTarget.x);
float angleDiff = desiredAngle - turret.angle;

// Normalize angle to [-PI,PI] range. This ensures that the turret
// turns the shortest way.
while (angleDiff < -PI) angleDiff += 2*PI;
while (angleDiff >= PI) angleDiff -= 2*PI;

Once you have these quantities you can set up a second degree expression for the turret angle. You need to compute this on each update to make sure you always use the latest data of positions and velocities.

// Compute angular acceleration.
const float C0 = // Must be determined.
const float C1 = // Must be determined.
float angularAcc = C0 * angleDiff - C1 * turret.angularVelocity;

Here, the first term (zero degree) in the acceleration expression will cause the turret to begin turning towards the target. However it will not stop in time but rather oscillate back and forth over it. To make it stop we need the dampening second term (first degree) which causes a high turning velocity to be opposed by a high acceleration.

Now the positive constants (not necessarily program constants) need to be determined and balanced to make the system behave well. C0 is the major control for the speed of the system. A high value for C0 will give a fast turning speed and a low value will give a low turning speed. The actual value depends on many factors so you should use trial and error here. C1 controls the damping magnitude. The discriminant of the quadratic equation tells us that if C1*C1 - 4*C0 >= 0 we have a non-oscillating system.

// New definition.
const float C1 = 2*sqrt(C0); // Stabilizes the system.

You probably should choose C1 a little bigger than this for numerical reasons, but not too big because it may get very over-damped and slow to respond instead. Again, you need to tweak.

Also it is important to note that this code only computes the angular acceleration. The angle and angular velocity needs to be updated from this somewhere else, using and integrator of some sort. From the question I assume that this has been covered.

Finally there is something to say about lagging, because the turret will probably always be behind when tracking a fast target. A simple way to tackle this is to add a linear prediction to the target's position, i.e. always aim slightly ahead in the target's forward direction.

// Improvement of the first lines above.
const float predictionTime = 1; // One second prediction, you need to experiment.
Vector2 turretToTarget = target.position + predictionTime * target.velocity - turret.position;
/// ...

As for keeping the turret aimed within the radius of the target for some time, this may be a tough requirement to impose directly on this sort of system. You can be certain that this controller will strive to keep the turret aimed at the target (or rather the predicted position) at all times. If the result turns out not to be satisfactory you have to modify the parameters predictionTime, C0 and C1 (within stable bounds).

share|improve this answer
    
I'm not qualified to say if this is right or not, but it sounds like some clever stuff! I have solved these types of problems in the past by forward predicting the effect of acceleration to work out when to accelerate and when to "apply the breaks". Does that mean I have been doing it wrong? –  Iain Jul 30 '10 at 14:44
    
The atan2 makes this method difficult to adapt to a predictive system since the x and y parameters to atan2 become dependant on t. –  Skizz Jul 30 '10 at 15:34
    
This is exactly the solution I was hinting at in my answer below. Excellent detail and presentation! –  drxzcl Jul 30 '10 at 15:48
    
@Iain: No there is no right and wrong here. While I guess your method would have two discrete states: accelerate/decelerate, this method is inspired by a regulator from control theory, scaling the acceleration to make a fast response while reducing overshoot and oscillations. –  Staffan E Jul 30 '10 at 15:58
    
@Skizz: I'm not exactly sure what you mean. The system should swing in towards the predicted direction, yes, which is dependent on the chosen prediction time. But this would be the same if I used arctan(y/x) instead, which is the pure mathematical operation. atan2 just hides away some handling of special cases. Could you please explain your question a bit further? –  Staffan E Jul 30 '10 at 16:09

What you have here is a basic control problem. The turret is the system, the acceleration is the control and the sensor measures position/velocity. There are many ways of tackling these problems, as it's a very well-studied problem in engineering.

Key is ending up with a stable system, i.e. a system that does not generate oscillations. This is usually done by adding damping. The wikipedia page should get you started.

share|improve this answer

First off, calculate the vector from turret to target. Then compare this with the turret's current vector. Then use the difference between the two to work out the angular acceleration and angular velocity required to get the turret to turn to point in the right direction within a given time.

OK, that seemed simple. However, you should really try to anticipate the target's position since the target is going to move by the time you've turned the turret. To do this:-

Pd' = Pd + t.Vd
Ps' = Ps + t.Vs

where P is position and V is velocity and the subscript is d for destination (target) and s for source (turret), which gives a direction vector:-

Dsd' = Pd' - Ps' = Pd + t.Vd - (Ps + t.Vs) = Pd - Ps + (Vd - Vs).t

where D is a direction vector and Dsd' is the required direction at time t. Now, work out the direction of the turret based on current position and maximum velocity and acceleration for a given time t:-

Ds' = t.Ds.Rs -> this is a vector rotation

Ds and Ds' are the source directions and Rs is the rotational velocity. With all that, you want to find t for when Dsd' == Ds' and thus Rs, the required rotational velocity. Don't forget that all the P's, D's and V's have x and y components.

I haven't taken acceleration into account here - that adds a lot more to the complexity. Once you've got Rs and t you could probably approximate a parabolic Rs (i.e. accelerate and decelerate) to get the same result.

share|improve this answer

What you're probably looking for here is a PID Controller, similar to the answer accepted on this SO question

I had initially answered that question by "rolling my own" but this answer is significantly more complete and elegant.

share|improve this answer

First thing to do is to calculate the angle between the turrent and the tracked object.
Next thing is to check if using the current torrent speed and applying the maximum acceleration backwards(stopping the torrent) will the torrent stop before or after the tracked object.
If the answer is that the torrent will stop before the tracked object, apply maximum acceleration forward(increasing speed).
If the answer is that the torrent will stop after the tracked object, apply maximum acceleration backward(stopping the torrent).
This way the torrent will alwais arrive the fastest and will stop at the right point(or a fraction after).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.