# How to optimize the distance function?

While developing a reasonably simple RTS-like game, I noticed my distance calculations were causing an impact in performance.

At all times, there are distance checks to know if a unit is in range to its target, if the projectile has reached its target, if the player has run over a pickup, general collision, etc. The list goes on, and checking for distance between two points is used a lot.

My question is exactly about that. I want to know what alternatives game developers have for checking distances, other than the usual sqrt(x*x + y*y) approach, which is fairly time consuming if we are performing it thousands of times per frame.

I'd like to point out I am aware of the manhattan distances and squared distance comparisons (by skipping the sqrt bottleneck). Anything else?

• – MichaelHouse Jan 24 '14 at 0:02
• If you have objects that you don't expect to move, like buildings, for example, it might be worth it to take a 2D taylor series of the distance function, truncate it at the square term, and then store the resultant function as the distance function from that particular building. That would relocate some of the grunt work to initialization and could speed things up a little bit. – Alexander Gruber Aug 3 '14 at 19:29

TL;DR; Your problem is not with performing the distance function. Your problem is performing the distance function so many times. In other words you need an algorithmic optimization rather than a mathematical one.

[EDIT] I am deleting the first section of my answer, because people are hating it. The question title was asking for alternative distance functions before the edit.

You are using a distance function where you are calculating square root everytime. Yet, you can simply replace that without using the square root at all and calculate the distance squared instead. This will save you a lot of precious cycles.

Distance^2 = x*x + y*y;

this is actually a common trick. But you need to adjust your calculations accordingly. It can also be used as initial check before calculating the actual distance. So for example instead of calculating the actual distance between two points/spheres for an intersection test we can calculate the Distance Squared instead and compare with radius squared instead of radius.

Edit, well after @Byte56 pointed out that I didn't read the question, and that you were aware of the squared distance optimization.

Well in your case, unfortunately we are in computer graphics almost exclusively dealing with Euclidean Space, and distance is exactly defined as Sqrt of Vector dot itself in euclidean space.

Distance squared is the best approximation you are going to get (in terms of performance), I can't see anything beating 2 multiplications, one addition, and an assignment.

So you say I can't optimize the distance function what should I do ?

Your problem is not with performing the distance function. Your problem is performing the distance function so many times. In other words you need an algorithmic optimization rather than a mathematical one.

The point is, instead of checking player intersection with each object in the scene, each frame. You can easily use spatial coherency to your advantage, and only check the objects that are near the player (that are most likely to hit/intersect.

This can be easily done by actually storing those spatial info in a spatial partitioning data structure. For a simple game I would suggest a Grid because it's basically easy to implement and fits dynamic scene nicely.

Every cell/box contains a list of object that the bounding box of the grid enclose. And it's easy to track the player position in those cells. And for the distance calculations, you only check the player distance with those objects inside the same or neighbor cells instead of everything in the scene.

A more complicated approach is to use BSP or Octrees.

• I believe the last sentence of the question says OP is looking for other alternatives (they know about using the squared distance). – MichaelHouse Jan 24 '14 at 0:05
• @Byte56 yes you are correct, I didn't read that. – concept3d Jan 24 '14 at 0:07
• Thanks for you answer anyway. Would you add a sentence confirming that even though that method doesn't give us a euclidean distance, it is very accurate in comparisons? I think that would add something to someone coming here from a search engine. – Grimshaw Jan 24 '14 at 0:20
• @Grimshaw I edited the answer to tackle the original problem. – concept3d Jan 24 '14 at 0:25
• @Byte56 thanks for pointing out. I edited the answer. – concept3d Jan 24 '14 at 0:26

If you need something that stays linear over any distance (unlike distance^2) and yet appears vaguely circular (unlike the squarish Chebyshev and diamond-like Manhattan distances), you can average the latter two techniques to get an octagonally-shaped distance approximation:

dx = abs(x1 - x0)
dy = abs(y1 - y0)

dist = 0.5 * (dx + dy + max(dx, dy))

Here is a visualization (contour plot) of the function, thanks to Wolfram Alpha:

And here is a plot of its error function when compared to the euclidean distance (radians, first quadrant only):

As you can see, the error ranges from 0% on the axes to approximately +12% in the lobes. By modifying the coefficients a bit we can get it down to +/-4%:

dist = 0.4 * (dx + dy) + 0.56 * max(dx, dy)

## Update

Using the above coefficients, the maximum error will be within +/-4%, but the average error will still be +1.3%. Optimized for zero average error, you can use:

dist = 0.394 * (dx + dy) + 0.554 * max(dx, dy)

which gives errors between -5% and +3% and an average error of +0.043%

While searching the web for a name for this algorithm, I found this similar octagonal approximation:

dist = 1007/1024 * max(dx, dy) + 441/1024 * min(dx, dy)

Note that this is essentially equivalent (though the exponents are different - these ones give a -1.5% to 7.5% error, but it can be massaged to +/-4%) because max(dx, dy) + min(dx, dy) == dx + dy. Using this form, the min and max calls can be factored out in favor of:

if (dy > dx)
swap(dx, dy)

dist = 1007/1024 * dx + 441/1024 * dy

Is this going to be faster than my version? Who knows... depends on the compiler and how it optimizes each for the target platform. My guess is it'd be pretty difficult to see any difference.

• Interesting, haven't seen this before! Does it have a name, or just "average of Chebyshev and Manhattan"? – congusbongus Jan 24 '14 at 6:54
• @congusbongus It probably has a name, but I don't know what is is. If not, perhaps one day it will be called the Crist Distance (hah... probably not) – bcrist Jan 24 '14 at 6:59
• Note that floating-point multiplications are not very efficient. That's why the other approximation uses 1007/1024 (which will be implemented as integer multiplication followed by bit shift). – MSalters Jan 24 '14 at 8:24
• @MSalters Yes, floating point operations are often slower than integer operations, but that's irrelevant - 0.4 and 0.56 could just as easily be converted to use integer operations. Furthermore, on modern x86 hardware, most floating point operations (other than FDIV, FSQRT, and other transcendental functions) cost essentially the same as their integer versions: 1 or 2 cycles per instruction. – bcrist Jan 24 '14 at 9:01
• This looks very similar to Alpha max + Beta Min: en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm – drake7707 Mar 27 '16 at 20:06

Sometimes this question can arise not because of the cost of performing distance calculations, but because of the number of times the calculation is being made.

In a large game world with many actors, it is unscalable to keep checking the distance between one actor and all the others. As more players, NPCs and projectiles enter the world, the number of comparisons that need to be made will grow quadratically with O(N^2).

One way to reduce that growth is to use a good data structure to quickly discard unwanted actors from the calculations.

We are looking for a way to efficiently iterate all the actors that might be in range, whilst excluding the majority of actors which are definitely out-of-range.

If your actors are fairly evenly spread across the world space, then a grid of buckets should be a suitable structure (as the accepted answer suggests). By keeping references to actors in a coarse grid, you need only check a few of the nearby buckets to cover all the actors which could be in range, ignoring the rest. When an actor moves, you may need to move him from his old bucket to a new one.

For actors which are less evenly spread a quadtree may do better for a two-dimensional world, or an octree would be suitable for a three-dimensional world. These are more general purpose structures that can efficiently partition large areas of empty space, and small areas containing lots of actors. For static actors there is binary space partitioning (BSP), which is very fast to search but far too costly to update in realtime. BSPs separate the space using planes to repeatedly cut it in half, and can be applied to any number of dimensions.

Of course there are overheads to keeping your actors such a structure, especially when they are moving between partitions. But in a large world with many actors but small ranges of interest, the costs should be far lower than those incurred by naive comparison against all objects.

Consideration of how the expense of an algorithm grows as it receives more data is crucial for scalable software design. Sometimes simply choosing the correct data structure is enough. Costs are usually described using Big O notation.

(I realise this is not a direct answer to the question, but it may be useful for some readers. My apologies if I have wasted your time!)

• This is the best answer. There is nothing to optimise in the distance function; one just needs to use it less often. – sam hocevar Jan 24 '14 at 7:10
• The accepted answer also covers spatial partitioning, otherwise your answer is really optimal. Thank you. – Grimshaw Jan 24 '14 at 17:39
• My time was very well spent reading your answer. Thank you, Joey. – Patrick M Jan 24 '14 at 19:41
• This is the best answer and the only one that focusses on the real problem rather than the red-herring of distance function performance. The accepted answer may well cover spatial partitioning too, but it's as an aside; it focusses on the distance calculation. The distance calculation is not the primary problem here; optimizing the distance calculation is a brute-force non-solution that doesn't scale. – Maximus Minimus Jan 25 '14 at 1:06
• Could you please explain why the number of comparisons would be exponential? I though it would be quadratic, comparing each actor with each other during each time frame. – Petr Pudlák Jan 25 '14 at 7:03

How about the Chebyshev distance? For points p, q it is defined as follows:

So for points (2, 4) and (8, 5), the Chebyshev distance is 6, as |2-8| > |4-5|.

Furthermore, let E be the Euclidean distance and C be the Chebyshev distance. Then:

$C <= E <= \sqrt{2C^2}$

The upper bound probably isn't much use since you'd have to calculate the square root, but the lower bound could be helpful - whenever the Chebyshev distance is large enough to be out of range, the Euclidean distance must be too, saving you from having to calculate it.

The trade-off, of course, is that if the Chebyshev distance is within range, you'll have to calculate the Euclidean distance anyway, wasting time. Only one way to find out if it'll be a net win!

• You could also use Manhattan distance as an upperbound. – congusbongus Jan 24 '14 at 3:04
• True enough. I suppose from there it's only a hop, skip and a jump to the "average of Chebyshev and Manhattan" as suggested by bcrist. – Tetrinity Jan 24 '14 at 11:34

A very simple local optimization is to simply to check a single dimension first.

That is :

distance ( x1, y1 , x1, y2) > fabs (x2 - x1)

So just checking fabs (x2 - x1) as a first filter may give an appreciable gain. How much will depend on the size of the world versus the relevant ranges.

Furthermore, you can use this as an alternative to the spatial partitioning data structure.

If all relevant objects are sorted in a list in x coordinate order, then nearby objects must be nearby in the list. Even if the list becomes out of order due to not being fully maintained as objects move, then given known bounds of speed you can still reduce the section of the list to be searched for nearby objects.

Efforts were made in the past to optimize sqrt. Although it no longer applies to today's machines, here is an example from the Quake source code, which uses the magic number 0x5f3759df:

float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;

x2 = number * 0.5F;
y  = number;
i  = * ( long * ) &y;  // evil floating point bit level hacking
i  = 0x5f3759df - ( i >> 1 ); // what the hell?
y  = * ( float * ) &i;
y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
// ...
return y;
}

A detailed explanation of what's going on here can be found on Wikipedia.

In short, it is a few iterations of Newton's method (a numerical algorithm which iteratively improves an estimate), with the magic number used to provide a reasonable initial estimate.

As Travis points out, this kind of optimization is no longer useful on modern architectures. And even if it was, it could only provide a constant rate speedup to your bottleneck, whilst algorithmic redesign might achieve better results.

• This is not a worthwhile optimization anymore. Almost all consumer-grade PC architectures you can purchase nowadays have hardware-optimized sqrt instructions that perform the square root in a clock cycle or less. If you really need the fastest sqrt possible, you use the x86 simd floating point sqrt instruction: en.wikipedia.org/wiki/… For things like shaders on GPU, calling sqrt will automatically result in such an instruction. On CPU, I assume many compilers implement sqrt via SIMD sqrt if available. – TravisG Jan 25 '14 at 0:02
• @TravisG Yes that is worth mentioning, so I have updated the answer. This answer was provided for fun and historical interest only! – joeytwiddle Jan 25 '14 at 0:41