collision detection - 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?

Answer

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.