Is there some way to calculate a distance between two points VERY quickly (2D points, not 3D)? I don''t need it to be super accurate, i''d be happy with a 10% error. I''m using just the standard d = sqrt((x1 - x2)*(x1-x2) + (y1 - y2)*(y2-y2)) formula to calculate my accurate distances. Is there a faster way than that? Two multipies and a square root doesn''t look too fast, especially since I''m doing this 1000s of times per frame.

Is a sqrt lookup table an idea ?

You aren't going to be able to get around the multiplies. But the sqrt can be optimized. If you are using the distance to check against some constant distance (for example you are seeing if your character is a certain distance away from something) then you can calculate the constant as a squared and then remove the sqrt from your equation. That way you only check the two squared distances and get away with not using the sqrt. Example:


#define MAX_DIST 100
#define MAX_DIST_SQR (MAX_DIST * MAX_DIST)

.... somwhere in your code
float dist = ((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1));

if(dist > MAX_DIST_SQR)
{
...do something
}


Also, you could use Manhattan (i think thats how you spell it) distances. I'm not sure how to calculate them and they aren't exactly accurate, but a quick search on google should help you find out about them. I don't think they use any multiplies. Hope this help.

[edited by - regularkid on June 15, 2002 2:26:30 PM]

[edited by - regularkid on June 15, 2002 2:26:58 PM]

I''m pretty sure there is a fast way of getting approximate distances. The vector library I use has a Vector::sloppyMag() function built in, which doesn''t use square roots.
I think the method is described in one of the game programming gems books.


"Math is hard" -Barbie

There was a thread about this exact question a couple of days ago. Anyways, here's the distance function. If you want the explanation behind it check out the other thread.

int Fast_Distance_2D(int x, int y){  // this function computes the distance from 0,0 to x,y with 3.5 error  // first compute the absolute value of x,y  x = abs(x);  y = abs(y);  // compute the minimum of x,y  int mn = MIN(x,y);  // return the distance  return(x+y-(mn>>1)-(mn>>2)+(mn>>4));} // end Fast_Distance_2D 

Give a man a fish and you feed him for a day; teach him to use the Net and he won't bother you for weeks.


[edited by - thooot on June 15, 2002 12:08:57 AM]

There''s something on this in the book Tricks of the Game Programming Guru (or something like that) by Andre Lamothe.


"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com