Range checking is a hugely important topic for AI War, since it is relevant for targeting, movement, and calculation of other values such as danger levels, etc. So some of the key optimizations that I talked about in the past had to do with using distance approximation methods instead of more highly accurate distance calculations.
Here’s the accurate distance calculations:
public static int DistanceBetweenPoints( Point P1, Point P2 )
{
int xd = P2.X – P1.X;
int yd = P2.Y – P1.Y;
FInt preSqF = (FInt)( ( (long)xd * (long)xd ) + ( (long)yd * (long)yd ) );
int val = Sqrt( Abs( preSqF ) ).IntValue;
if ( val < 0 )
return -val;
return val;
}
public static FInt DistanceBetweenPointsF( Point P1, Point P2 )
{
int xd = P2.X – P1.X;
int yd = P2.Y – P1.Y;
FInt preSqF = (FInt)( ( (long)xd * (long)xd ) + ( (long)yd * (long)yd ) );
return Mat.Abs( Sqrt( Abs( preSqF ) ) );
}
public static double DistanceBetweenPointsD( Point P1, Point P2 )
{
int xd = P2.X – P1.X;
int yd = P2.Y – P1.Y;
return Math.Abs( Math.Sqrt( Math.Abs(
( ( (long)xd * (long)xd ) + ( (long)yd * (long)yd ) ) ) ) );
}
Three different variations there show you how to get an integer, double, or fixed-integer format result. This uses my FInt struct, which you can get the full source code for over at StackOverflow.
Those are the less-efficient methods of calculating a range check, and I’ve posted them mostly for illustrative purposes. If you need a highly accurate range check, or if you need to just run a few range checks, by all means use those. However, they run vastly more slowly than a distance approximation method primarily because of the use of the Sqrt function (either the FInt version below, or the built-in .NET one for doubles). Sqrt is a surprisingly expensive call in terms of CPU, because it is an iterative function. See below:
public static FInt Sqrt( FInt f, int NumberOfIterations )
{
if ( f.RawValue < 0 ) //NaN in Math.Sqrt
throw new ArithmeticException( “Input Error” );
if ( f.RawValue == 0 )
return (FInt)0;
FInt k = f + FInt.OneF >> 1;
for ( int i = 0; i < NumberOfIterations; i++ )
k = ( k + ( f / k ) ) >> 1;
if ( k.RawValue < 0 )
throw new ArithmeticException( “Overflow” );
else
return k;
}
public static FInt Sqrt( FInt f )
{
byte numberOfIterations = 8;
if ( f.RawValue > 0x64000 )
numberOfIterations = 12;
if ( f.RawValue > 0x3e8000 )
numberOfIterations = 16;
return Sqrt( f, numberOfIterations );
}
All of this goes to show the need for a distance approximation method when you don’t need quite as high a degree of accuracy, or when you only need to tell relatively how far apart two points are compared to one another. In AI War’s case, this is good enough for 99% of all distance checks. The only times I need to use the more CPU-intensive, precise methods above is as a final check when ships are moving the last little bit of space in towards a destination, and other similar situations. Everywhere else, the following distance approximation method is instead used:
EDIT: Thanks to a reader comment, I finally have the original source for this again: Rafael Baptista The approximate distance function is all his, and his article does a great job of explaining the way the accuracy works. Please his article for the approximation method used.
Maybe from here?
http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml
You might not need the Abs() calls; it seems that the arguments are always positive (except maybe you have overflow).
If there’s a fixed range I want to check against, e.g., code like “Distance(a,b) <= 30”, then you can gain some speed by replacing that with “DistanceSquared(a,b) <= 30*30”. Essentially instead of testing sqrt(xyz) <= pqr, you square both sides and test xyz <= pqr*pqr. Much cheaper 🙂
Square root may be iterative, but it should be sent directly to your floating point processor, where it is a hardware operation.
Actually, the whole distance function should be optimized into something that never gets off the FPU. Otherwise your compiler is broken.
If this is really a speed issue, you should submit it to Microsoft as a bug in .NET.
That’s the one! Thanks, Anonymous, I’ve updated the article to just link to his original code.
The other reason for not using the FPU is for synchronous operations in different CPU/FPU operations. Basically, different FPU and CPU architectures can have very slightly different results, given the inherent way that floating-point is calculated. When you are writing a synchronized simulation that has to run exactly the same on multiple machines at once, then even slight variances can add up over time and cause a desync. So there is a speed component to this, as well as a need for something that will run the same on any CPU architecture.
Plus, these techniques work on smaller devices such as the Nintendo DS, which doesn’t have an FPU. So there fixed-point math is really common in environments like that.
As Amit said, why bother using sqrt at all? Just compare the distances squared. If all you need to know is which of a bunch of things are closest, or similar, doing the comparison with the squared values is perfectly valid, and much faster.
This is true, for relative distance comparisons, you can just use that method and it will be faster than the Sqrt method. However, often I am also needing to find a reasonably accurate actual distance to a location (to know if I am at all in range, etc), and that’s where the least squares method that I linked to is really invaluable. It is super fast in general, so just using that all the time does plenty well enough for most of my purposes. The only time I use the Sqrt-based distance checks is when I need to very precisely know the distance between two points for some reason (which is almost never).
What about a tradeoff memory-space against cpu-time?
Just make a table and lookup the value using a select-statement…
The pre-calculation of the table is done in a second, i recommend to /8 the precision.
The lookup can also be done with a select-statement.
Well, I had also thought to do something like that (as I do that sort of thing in a variety of other areas, such as precalculating deceleration rates based on distance to target, or Sine table, etc), but the problem is one of scale here. In a game with a maximum fixed size map, I could see that working very well, but here the possible range is -2 billion to +2 billion ion both the Z and Y directions. Generally plays stick to the -80 thousand to +80 thousand on the range of ship positions, but even that is way to huge to precalculate and store in memory.
Unless I’m missing something about what you’re suggesting, that would be 160,000×160,000 = 25.6 billion points just in that smaller area, and then it would need to calculate 25.6 billion x 25.6 billion (which is some astronomical number that I don’t think has a name) in order to get all of the possible distances between points.
Now, some of that might be able to be simplified out, certainly, by figuring out the x and y differences and then using some formula to determine the distance between the points. That could work, especially if I noted to consider anything greater than (say) 100,000 units distant to be equally “very far away.” That would be only 100,000 precalculations and an array lookup into a 100,000-long array. And even that would only use something like 390kb of space in RAM, so it’s absolutely negligible.
I don’t know a good formula for getting the distance between points based on and x and y differential, though. Anyone have any ideas on that?
Very fast, accurate enough at longer distances:
min = x < y ? x : y;
max = x < y ? y : x;
distance = min + (max – min);
This gets you the 45-degree diagonal distance (min) plus the remaining vertical or horizontal distance (max – min). Plus, it’s two compares, three assignments, an addition and a subtraction.
Maybe I’m missing something pretty basic (did just get back to work for the year), but how is:
“distance = min + (max – min);”
not equivalent to
“distance = max;”?
and thus:
“distance = x < y ? y : x”
also, I’m assuming x means “abs(point1.x – point2.x)” and y means “abs(point1.y – point2.y)” but I’m not sure you intended that.
@Keith (and Anonymous right above): I think it should be min*sqrt(2) + (max – min); min*sqrt(2) is diagonal distance, max-min is the cardinal distance. maybe that’s the solution?