As if all the mucking about with coordinates before wasn’t bad enough, next I had to deal with unit vectors, polar/Cartesian coordinate conversion, sign adjustment vs. trigonometric functions… you get the idea.
In this case, my problem wasn’t caused by needing to update the algorithms Mike used at all, but rather by my need to replace the old MacToolbox FixRatio() and AngleFromSlope() functions with modern trigonometrics. Now, I’d already done all this, or else the impulse and warp drives would never have worked for this long, but in poking about in the implementation for mobile enemies, I realized I’d have to generalize the code, or else end up repeating it in about a dozen places, a well-known recipe for disaster.
In literal code, warp speed goes like this:
double diffx = warpCoordX - playerCoordX, diffy = warpCoordY - playerCoordY,
theta_raw = atan2(-diffy, diffx), theta = round(fma(theta_raw, RAD_TO_DEG_FACTOR, 360 * signbit(theta_raw))),
// make use of theta in degrees here to calculate a turn factor
maxSpeed = warpSpeed,
newDeltaX = cos(theta * DEG_TO_RAD_FACTOR), newDeltaY = -sin(theta * DEG_TO_RAD_FACTOR),
finalDeltaX = playerDeltaX + newDeltaX, finalDeltaY = playerDeltaY + newDeltaY;
if (fabs(addedDeltaX) >= fabs(maxSpeed) * newDeltaX) finalDeltaX = maxSpeed + newDeltaX;
if (fabs(addedDeltaY) >= fabs(maxSpeed) * newDeltaY) finalDeltaY = maxSpeed + newDeltaY;
Conceptually, this reads:
- Calculate the difference between the player’s current position and the destination in Cartesian coordinates.
- Take the arctangent of the Cartesian coordinates, adjusted for inverted Y, converted to degrees and adjusted to the range [0,360] (atan2() returns [-π,π]).
- Convert the polar coordinates (using the implied mangitude of 1) back to Cartesian coordinates.
- Calculate the movement delta with a speed limit.
Why, one wonders, do I do a Cartesian->polar conversion, only to immediately convert back to Cartesian again? Answers: 1) I need the angle to calculate which way to turn the ship towards its destination. 2) The distance between current position and destination is a vector of (usually) rather high magnitude; I need to normalize that vector to get a delta. And the formula for normalizing a Cartesian vector is x/sqrt(x*x+y*y), y/sqrt(x*x+y*y). Two multiplies, an add, a square root, and two divides, all floating point. Without benchmarking I still intuitively think that’s slower (and I’m SURE it’s conceptually more confusing) than cos(atan2(-y, x)), -sin(atan2(-y, x)), two negations, an arctangent, a sine, and a cosine. Maybe I’m crazy.
Of course, typing all this out made me realize that I can, in fact, eliminate the degree/radian conversion entirely, as well as the range adjustment, by changing the conditional in the turn calculation. Once again I fell for the trap of not thinking my way through the code I was porting. At least you weren’t as bad at geometry as me, Mike :-).
Then I had to go and get really curious and benchmark it:
#include <stdio.h>
#include <math.h>
#include <sys/time.h>
int main(int argc, char **argv)
{
struct timeval cS, cE, pS, pE;
// Volatile prevents compiler from reading the loops as invariant and only running them once.
volatile double x1 = 1.0, x2 = 2.5, y1 = 0.4, y2 = 3.2, dx = 0.0, dy = 0.0, inter = 0.0;
gettimeofday(&cS, NULL);
for (int i = 0; i < 100000000; ++i)
{
dx = x2 - x1;
dy = y2 - y1;
inter = sqrt(dx*dx+dy*dy);
dx /= inter;
dy /= inter;
}
gettimeofday(&cE, NULL);
gettimeofday(&pS, NULL);
for (int i = 0; i < 100000000; ++i)
{
inter = atan2(y2 - y1, x2 - x1);
dx = cos(inter);
dy = sin(inter);
}
gettimeofday(&pE, NULL);
struct timeval cD, pD;
timersub(&cE, &cS, &cD);
timersub(&pE, &pS, &pD);
printf("Cartesian diff = %lu.%06u\n", cD.tv_sec, cD.tv_usec);
printf(" Polar diff = %lu.%06u\n", pD.tv_sec, pD.tv_usec);
return 0;
}
Foot in mouth. cos|sin(atan2()) is consistently 3x slower than x|y/sqrt(x^2+y^2) at all optimization levels. Somehow I just can’t see this as being an artifact of the brutal abuse of volatile for the benchmark.
Mike got around the whole issue, in the end. Knowing that he only ever had to calculate cos()/sin() for the angles in the period [0,35]*10, he just precalculated them in a lookup table. And cutting the cosine and sine calls out of the benchmark reduces the difference between the methods to about 1.6x, making his way a win over a four-way compare/branch for the turn calculation.
Live and learn.
Oh, and changes to Missions: Again, nothing you can see in play yet. But at least now I have the right building blocks to make the enemies from.
