help speeding up some basic math code

[aarku]

Here are a couple of math functions I have. I know square roots are slow, but I think I need one for the FindAngle function. How can I speed them up? (if at all?)

FindDistance: returns the distance between two points
FindAngle: returns the angle (in degrees) "him" is in relationship to "me"

float FindDistance (float meH,float meV, float himH, float himV)
{
return (sqrt(((fabs( ((himH)-(meH))*((himH)-(meH)) )))+((fabs( ((himV)-(meV))*((himV)-(meV)) )))));
}

float FindAngle(float meH,float meV, float himH, float himV)
{
float x,y;
float distance;
float angle;

x = meH - himH;
y = meV - himV;

distance = FindDistance (meH, meV, himH, himV);
angle = (( asin (x/distance) )/(0.01745329252));

// don't understand why I have to do this,
// but if I don't the angle is screwed up.
// anyone know why this is happening?
if ((x>0) && (y>0) )
angle = (fabs((angle)-360));
if ((x>0) && (y<0))
angle = 180+angle;
if ((x<0) && (y<0))
angle = 180-fabs(angle);
if ((x<0) && (y>0))
angle = fabs(angle);

return (angle);
}



Thank you
-Jon

[OneSadCookie]

Are you sure these are really what needs optimization? Have you profiled?

Try these (untested; should work):

#define square(x) ((x) * (x))

float FindDistance (float meH, float meV,
float himH, float himV)
{
return sqrt(square(meH - himH) + square(meV - himV));
}

float FindAngle(float meH, float meV,
float himH, float himV)
{
float inverseMeLength = 1 / sqrt(square(meH) + square(meV));
float inverseHimLength = 1 / sqrt(square(himH) + square(himV));

return acos((meH * himH + meV * himV)
* inverseMeLength * inverseHimLength);
}

[inio]

Originally posted by OneSadCookie
Are you sure these are really what needs optimization? Have you profiled?

Indeed. Unless you're doing several thousand of these calculations per frame, I highly doubt these are your bottleneck.

[aarku]

I have done a fair amount of profiling... trying to squeeze some more fps. I think I can say that most of the code is very optimized, this is just one of the areas I'm not very sure on.

These calcs don't take very much time, but I call them a lot every frame. And I'm going to be calling them even more soon. To summarize... I have a bunch of space ships flying around in 2d space shooting weapons at each other and I am going to have the ships try to dodge weapons and have the option to flee. Unless I can come up with a different solution, this means that each ship will have to:

1. compute the distance and angle to each weapon and ship taking into account enemy/friendly fire
2. compile them in a list
3. have AI sort out what to do.

Once you get 10 ships loaded up in the engine each with a realistic average of 15 weapon sprites on the screen each... that's 150 weapons to be tracked by each of the ten ships. So that's 1500 weapon calculations + 100 ship calculations per frame. Hmm well not it's not sounding that bad :) I'll have to try it... now to figure out how step 3 will work.

-Jon

[inio]

If this does turn out to be a bottleneck, you might think about using vectors intead of angles and distances. You can do almost any type of positional comparison (including taking velocity vectors into account) with just a couple multiplies and adds. You can also work with distance squared if you're only trying to figure out which projectile is the closest - that saves you a square root per calc.

An example:
How close will a projectile at Pl moving at Pv and your ship at Sl moving at Sv will get how close if left unattended?

distance squared at time t: distance^2 = VLengthSqr((Pl+t*pv)-(Sl+t*Sv))=VLengthSqr(Pl-Sl+t*(Pv-Sv))
To make things easier lets define two new vectors, Dl=Pl-Sl and Dv=Pv-Sv so that:
distance squared at time t: distance^2 = VLengthSqr(Dl+t*Dv)
decomposing that into pure arithmatic: distance^2 = (Dl.x+t*Dv.x)^2+(Dl.y+t*Dv.y)^2
taking the derivative: d(distance^2)/dt = 2*(Dl.x+t*Dv.x)+2*(Dl.y+t*Dv.y)
equals zero at: Dl.x+Dl.y+t*(Dv.x+Dv.y)=0 => t(min)=-(Dl.x+Dl.y)/(Dv.x+Dv.y)

so we know that the distance could only reach an absolute minimum at t=-(Dl.x+Dl.y)/(Dv.x+Dv.y). If this t is less than zero, then you can bail out now because they would have collided in the past. You can also bail out of its too far in the future. If however it's soon, you need to calculate the distance at that time:
min(distance^2) = VLengthSqr(Dl+t(min)*Dv)

In C that would look like


typedef struct Vector2 {
float h, v;
} Vector2; // to make the protype less ugly

// meLoc and themLoc are in spatial units.
// meVel and themVel are in spatial units per time unit
// if time is not NULL, it will be the number of time units
// in the future when this nearest approach occurrs.
// returns square of minimum distance at nearest approach.
float HowCloseDoTheyGet(Vector2 meLoc, Vector2 meVel,
Vector2 themLoc, vector 2 themVel, float *time) {
Vector2 dl, dv;
float t;

dl.h = meLoc.h-themLoc.h;
dl.v = meLoc.v-themLoc.v;
dv.h = meVel.h-themVel.h;
dv.v = meVel.v-themVel.v;

t = -(dl.h+dl.v)/(dv.h+dv.v);

if (t<0) { // allready happened.
if (time)
*time = -1;
return 10000000; // or some other ReallyBigNumber&trade;
}
if (time)
*time = t;

// re-use dl to hold delta vector at time t.
dl.h = dl.h + t*dv.h;
dl.v = dl.v + t*dv.v;

// and find the square of the length of this vector.
return dl.h*dl.h+dl.v*dl.v;
}