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?

  • 1
    \$\begingroup\$ Related: Are there any disadvantages of using Distance Squared checks rather than Distance? \$\endgroup\$
    – House
    Commented Jan 24, 2014 at 0:02
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 3, 2014 at 19:29

6 Answers 6


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.

  • 2
    \$\begingroup\$ I believe the last sentence of the question says OP is looking for other alternatives (they know about using the squared distance). \$\endgroup\$
    – House
    Commented Jan 24, 2014 at 0:05
  • \$\begingroup\$ @Byte56 yes you are correct, I didn't read that. \$\endgroup\$
    – concept3d
    Commented Jan 24, 2014 at 0:07
  • \$\begingroup\$ 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. \$\endgroup\$
    – Grimshaw
    Commented Jan 24, 2014 at 0:20
  • \$\begingroup\$ @Grimshaw I edited the answer to tackle the original problem. \$\endgroup\$
    – concept3d
    Commented Jan 24, 2014 at 0:25
  • \$\begingroup\$ @Byte56 thanks for pointing out. I edited the answer. \$\endgroup\$
    – concept3d
    Commented Jan 24, 2014 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:

Contour Plot

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

Error Plot

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)

enter image description here


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.

  • 3
    \$\begingroup\$ Interesting, haven't seen this before! Does it have a name, or just "average of Chebyshev and Manhattan"? \$\endgroup\$ Commented Jan 24, 2014 at 6:54
  • \$\begingroup\$ @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) \$\endgroup\$
    – bcrist
    Commented Jan 24, 2014 at 6:59
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – MSalters
    Commented Jan 24, 2014 at 8:24
  • \$\begingroup\$ @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. \$\endgroup\$
    – bcrist
    Commented Jan 24, 2014 at 9:01
  • 1
    \$\begingroup\$ This looks very similar to Alpha max + Beta Min: en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm \$\endgroup\$
    – Drakarah
    Commented Mar 27, 2016 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 not scalable 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 consideration.

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 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 unsuitable to update in realtime. BSPs partition 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 in such a structure, especially when they are moving between partitions. But in a large world with many actors but small ranges of interest, the savings should be far greater than the costs.

Consideration of how the expense of an algorithm grows as it receives more data is called computational complexity 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!)

  • 7
    \$\begingroup\$ This is the best answer. There is nothing to optimise in the distance function; one just needs to use it less often. \$\endgroup\$ Commented Jan 24, 2014 at 7:10
  • 3
    \$\begingroup\$ The accepted answer also covers spatial partitioning, otherwise your answer is really optimal. Thank you. \$\endgroup\$
    – Grimshaw
    Commented Jan 24, 2014 at 17:39
  • \$\begingroup\$ My time was very well spent reading your answer. Thank you, Joey. \$\endgroup\$
    – Patrick M
    Commented Jan 24, 2014 at 19:41
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 25, 2014 at 1:06
  • \$\begingroup\$ 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. \$\endgroup\$
    – Petr
    Commented Jan 25, 2014 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:


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!

  • 1
    \$\begingroup\$ You could also use Manhattan distance as an upperbound. \$\endgroup\$ Commented Jan 24, 2014 at 3:04
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Tetrinity
    Commented Jan 24, 2014 at 11:34

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.

  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – TravisG
    Commented Jan 25, 2014 at 0:02
  • \$\begingroup\$ @TravisG Yes that is worth mentioning, so I have updated the answer. This answer was provided for fun and historical interest only! \$\endgroup\$ Commented Jan 25, 2014 at 0:41

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .