Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
add comment

6 Answers

up vote 21 down vote accepted

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.

share|improve this answer
1  
I believe the last sentence of the question says OP is looking for other alternatives (they know about using the squared distance). –  Byte56 Jan 24 at 0:05
    
@Byte56 yes you are correct, I didn't read that. –  concept3d Jan 24 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 at 0:20
    
@Grimshaw I edited the answer to tackle the original problem. –  concept3d Jan 24 at 0:25
    
@Byte56 thanks for pointing out. I edited the answer. –  concept3d Jan 24 at 0:26
show 5 more comments

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

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.

share|improve this answer
3  
Interesting, haven't seen this before! Does it have a name, or just "average of Chebyshev and Manhattan"? –  congusbongus Jan 24 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 at 6:59
1  
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 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 at 9:01
add comment

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!)

share|improve this answer
6  
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 at 7:10
3  
The accepted answer also covers spatial partitioning, otherwise your answer is really optimal. Thank you. –  Grimshaw Jan 24 at 17:39
    
My time was very well spent reading your answer. Thank you, Joey. –  Patrick M Jan 24 at 19:41
1  
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. –  Jimmy Shelter Jan 25 at 1:06
    
@JimmyShelter what happened when I answered at first, is the question was worded like this "Better alternatives to the distance function?" after that it has been edited. So I kept the history of my answer edits (check the comments and my answer). Next time, if that happens, trust me I am going to delete my answer and post a new one! –  concept3d Jan 25 at 1:23
show 2 more comments

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

distance

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:

distance2

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!

share|improve this answer
1  
You could also use Manhattan distance as an upperbound. –  congusbongus Jan 24 at 3:04
1  
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 at 11:34
add comment

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.

share|improve this answer
add comment

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 fuck?
  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.

share|improve this answer
1  
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 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 at 0:41
    
+1 for fun! (+10 for history). –  luser droog Jan 25 at 9:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.