How to optimize the distance function?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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!

Answer 5

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.

Answer 6

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.