Range Checks - Approximation vs Accurate

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.