Changing angle to seek a moving target position

[vonWolfehaus]

[SOLVED]
When I get in these situations I break everything down into their simplest forms and build back up. Works every time. Here's the new angle modifier code:

dx = targetPos.x - (x + halfWidth);
dy = targetPos.y - (y + halfHeight);
var targetAngle:Number = (Math.atan2(dy, dx) * 57.295) - angle;
if (targetAngle < -180) targetAngle += 360; // shortest route
if (targetAngle > 180) targetAngle -= 360;
var delta:Number = maxAngular * _elap; // elap is always < 0.33 so it tempers the speed, keeps it consistent across differing framerates
if (targetAngle > delta) targetAngle = delta; // limit angle change to a max speed
else if (targetAngle < -delta) targetAngle = -delta;
angularVelocity = targetAngle;

This seeks the target smoothly (combined with the thrust code below), but now my problem is finding a way to avoid the target. Simply reversing the targetAngle makes it jumpy and eventually "locks" it in a circular motion (which is the problem I was having before). So I'll just comb through the above code and reverse it more completely. I'll eventually figure it out I guess. Nice forum btw :)

UPDATE: I get rid of the jumpiness and locking by simply adding 180deg to target angle before the shortest route stuff. But this causes it to sometimes take the longest route, if the target position moves too fast. I think this is fine--adds character to the game objects ;) Ok I'm done here. Prost!

[OLD POST]
Quick intro: Hi my name is Corey, my favorite color is game development. I'm terrible at math but I REALLY want to learn because it makes my graphics move all over the screen in neat ways ;) I frequent other forums but this time no one had the answer. So without further adieu...

Homework Statement

I can't figure out a computationally "cheap" algorithm that results in simple seeking/avoiding behavior for my game objects.
My design is such that each object has a target position (a point object containing X,Y coordinates in pixels) that it always "seeks" (or avoids, if necessary).
I know the position of the object and target. Also known are the object's properties such as speed, velocity, acceleration/drag, as well as the angular equivalent of those.

The resulting movement must be fluid (ie turn according to max angular delta/change, stay within max velocity). I found something that only kind of works (see below). The problem is that the resulting movement is something like a drunken object, in that it does not precisely move towards the target position, but somewhere near it or in many cases, somewhere else entirely different. Eventually the equation with make the angle "lock" and increase non-stop one way, resulting in circular motion, no matter where the target position is. This happens at the line that says "angle += angularVelocity * _elap;". So the problem is angularVelocity is getting stuck as a static number, regardless of what I feed it.

Homework Equations

I've tried a lot. Flocking/boids, steering behaviors, altering velocity directly, and so on. But here's my current algorithm that has what I want (close enough anyway, I'm getting desperate!). Problem is (as described above) it eventually gets locked into going in circles and it doesn't directly seek the target. Here's the code:

dx = targetPos.x - this.x;
dy = targetPos.y - this.y;
var da:Number = Math.atan2(dy, dx) * 57.295; // convert to degrees since angle is in degrees
var targetAngle:Number = da - angle;
if (targetAngle < -180) targetAngle += 360; // without these two lines, angle will spin endlessly no matter what at the start
if (targetAngle > 180) targetAngle -= 360;
			
if (avoiding) angularAcceleration = (targetAngle > 0) ? angularDrag : -angularDrag;
else angularAcceleration = (targetAngle > 0) ? -angularDrag : angularDrag;

angularVelocity = FlxU.computeVelocity(angularVelocity, angularAcceleration, angularDrag, maxAngular);
angle += angularVelocity * _elap;
var thrustComponents:FlxPoint;
if (thrust != 0) {
	thrustComponents = FlxU.rotatePoint(-thrust,0,0,0,angle);
	var maxComponents:FlxPoint = FlxU.rotatePoint(-maxThrust,0,0,0,angle);
	var max:Number = (maxComponents.x > 0) ? maxComponents.x : -maxComponents.x;
	var may:Number = (maxComponents.y > 0) ? maxComponents.y : -maxComponents.y;
	if (max > may) maxComponents.y = max;
	else max = may;
	maxVelocity.x = maxVelocity.y = (max > 0) ? max : -max;
} else thrustComponents = _pZero;

velocity.x = FlxU.computeVelocity(velocity.x, acceleration.x + thrustComponents.x, drag.x, maxVelocity.x);
velocity.y = FlxU.computeVelocity(velocity.y, acceleration.y + thrustComponents.y, drag.y, maxVelocity.y);
x += velocity.x * _elap;
y += velocity.y * _elap;

NOTE all Math operations take radians, but to make it easier for me, angle is in degrees, so I have to convert between the two all the time.
The "(angle > 0) ? something : somethingElse" is just shorthand for "if angle is greater than 0, then something, else something else". I'm writing this in ActionScript 3, the language for Flash.
avoiding = boolean that tells me whether or not to seek or avoid the targetPos
_elap = timestep, ie how much time passed since the last time this function was run.
FlxPoint = a simple point object containing x,y coordinates, nothing else.

Here's FlxU.rotatePoint:

static public function rotatePoint(PivotX:Number, PivotY:Number, X:Number, Y:Number, Angle:Number):FlxPoint {
Angle *= 0.01745;
var sin:Number = Math.sin(Angle);
var cos:Number = Math.cos(Angle);
var dx:Number = X - PivotX;
var dy:Number = Y - PivotY;
flxp.x = dx * cos + dy * sin;
flxp.y = dy * cos - dx * sin;
flxp.x += PivotX;
flxp.y += PivotY;
return flxp;
}

Here's FlxU.computeVelocity:

static public function computeVelocity(Velocity:Number, Acceleration:Number=0, Drag:Number=0, Max:Number=10000):Number {
if (Acceleration != 0) Velocity += Acceleration*_elap;
else if (Drag != 0) {
	var d:Number = Drag*_elap;
	if (Velocity - d > 0) Velocity = Velocity - d;
	else if (Velocity + d < 0) Velocity += d;
	else Velocity = 0;
}
if ((Velocity != 0) && (Max != 10000)) {
	if (Velocity > Max) Velocity = Max;
	else if (Velocity < -Max) Velocity = -Max;
}
return Velocity;
}

The Attempt at a Solution

The above IS my attempt :( I tried making sure that angularAcceleration is 0 if the targetAngle is 0, but that didn't work (no noticeable change actually). I tried a lot of other things quickly and I just never found what was wrong. Help?

 

[N-Gin]

Here's my attempt, in case you maybe interested. I didn't analyze your code since I'm not a programmer, but maybe I can help.

The mathematical background is pretty simple. I divided the motion of the object in small rectilinear steps, so that it always follows the current target position. I doesn't intercept the target directly - it is assumed that object doesn't know target's path.

Let (x_{10},y_{10}) be the coordinates of the object at t=0 and v be its velocity (which is constant through time). Target is initially located at (x_{20},y_{20}) and has two components of its speed, v_{x},v_{y}.

Object's motion can be described as a series of linear equations in parametric form (time is the parameter). At the beginning (the first step):

x_{1}=x_{10}+\frac{x_{20}-x_{10}}{ \sqrt{(x_{10}-x_{20})^{2}+(y_{10}-y_{20})^{2}} }v\Delta t

y_{1}=y_{10}+\frac{y_{20}-y_{10}}{ \sqrt{(x_{10}-x_{20})^{2}+(y_{10}-y_{20})^{2}} }v\Delta t

Fractions are easily recognizable as sine and cosine of the angle between the object and the target. \Delta t is the time step.

Motion of target can be anything we want, but (just for simplicity) I assumed that it has constant speed and moves rectilinearly. Therefore

x_{2}=x_{20}+v_{x}n\Delta t
y_{2}=y_{20}+v_{y}n\Delta t

n is the number of times steps.

Generally, coordinates of the object are given recursively

x_{1}((n+1)\Delta t)=x_{1}(n\Delta t)+\frac{x_{2}(n\Delta t)-x_{1}(n\Delta t)}{ \sqrt{(x_{1}(n\Delta t)-x_{2}(n\Delta t))^{2}+(y_{1}(n\Delta t)-y_{2}(n\Delta t))^{2}} }v\Delta t

y_{1}((n+1)\Delta t)=y_{1}(n\Delta t)+\frac{y_{2}(n\Delta t)-y_{1}(n\Delta t)}{ \sqrt{(x_{1}(n\Delta t)-x_{2}(n\Delta t))^{2}+(y_{1}(n\Delta t)-y_{2}(n\Delta t))^{2}} }v\Delta t

and are easily implemented in C code.

I tried to write it myself and I attached it. Maybe the code looks a bit "clumsy" but, as I said, I'm not a programmer. You need to input initial conditions, time step and the number of steps. The program then returns coordinates of the object's path in given time. I haven't fully tested it, but it seemed to work fine.