I wonder if there is a way to quickly calculate the euclidean distance between two points. i.e.

sqrt((x2-x1)^2 + (y2-y1)^2)

The calculation doesn't need to be exact. The important thing is that its fast. Currently I'm doing:

ABS(x2-x1) + ABS(y2-y1)

But this is not good enough so I need something better. Any ideas?

the common thing done to optimize that is:

a=x2-x1
b=y2-y1

dist=sqr(a*a + b*b)

but still uses an sqr, and has two multiplications...but, as always you can cheat and calculate x dist and if it is in "colision range" then you calc y dist. It all depends on what are you doing.

You could forget sqr and just use dist=a*a + b*b, and treat distance as distance^2 (instead of doing if dist<10, do if dist<100)

You could also use something like:

if abs(x2-x1) < min_dist then 
   if abs(y2-y1) < min_dist then ...

or removing "abs" (dont know if that's faster or slower)

if (x1<x2+min_dist) then
   if (x1+min_dist>x2) then
      if (y1<y2+min_dist) then 
         if (y1+min_dist>y2) then 

Obviously, that doesnt give you a result, just if something is "in range". If you really need a result, then I think your formula is the fastest.

@dvik

I think that everything depends on what you need to do with that distance

If you need only to do comparisons with thresholds

sqrt((x2-x1)^2 + (y2-y1)^2)

can be for sure replaced by

(x2-x1)^2 + (y2-y1)^2 == dx*dx+dy*dy

that needs 2 multiplications, a sum and two differences

if accurate multiplications are too expensive
you could replace dx*dx by approximate multiplications

e.g.

a = abs(x1-x2)

if (a is in range [1 3] ) then
m = 2*a
elseif (a is in range [4 5] ) then
m = 4*a
elseif (a is in range [6 13] ) then
m = 8*a
elseif (a is in range [14 25] ) then
m = 16*a
etc etc

the switch above can be implemented easily with a single comparison and
a single left rotation for each range of approximation...

But again everything depends on your needs and on the use of the final result

Thanks for the feedback. What I want to do is to compare three vectors originating at point A and pick the one that will get closest to point B.
I did some thinking and I think the fastest is to use a table based v = arctan( dx/dy ) and then compare with the vectors. The vectors are already on the form r*v so the comparison is quite quick. The arctan table takes quite a lot of space though but speed is more important in this case.

to dvik: Can you explain more in depth the reason of your question? maybe (if for a demo, for example) it's possible to use precalculated values...

Its for a game, but I don't want to reveal too many details. Basically its a routine to pick the best of three directions.

When you say "What I want to do is to compare three vectors originating at point A and pick the one that will get closest to point B. "

you mean to you have 3 points in the screen and you need to
compare the distances between each of them and point B ?

yes sortof. The thing I'm really interested in is starting at point A, which of three directions should I take to get as close as possible to point B.

do the vectors steaming out of A have the same size ("amplitude"?

in this case you can compare only the difference in angles from the vector A-B
i.e. you need to find the vector with smaller angle wrt A-B

yes at least in the current version the vectors have the same size. What I did was essentially to compare the angles. For that I needed to calculate arctan to get the angle of the vector AB and then I could compare with my three vectors and use the one with the smallest difference.

think also to the scalar products:

the one with max scalar product with A-B has the smallest difference in angle among the 3

this costs 2 multiplications and a sum per vector

Can't you just use lookup tables for the SQRs?

The scalar product would work fine if my vectors weren't on the form r*angle. Problem with this form is that to calculate scalar product I need to do a sin calculation first. So its the same amount of work as calculating v = arctan ((Bx-Ax)/(By-Ay)) and then comparing v with the angle of the three vectors.

A lookup table for SQRs works too but the table becomes rather big (same as the arctan or sin tables) so it won't be any savings.

sorry, when you say that your vectors are in the form r*angle you mean that
you have modulus and angle of each vector, do you ?

In this case all you need is to compute the angle differences !!

B-A is r0,a0
P1-A is r1,a1
P2-A is r2,a2
P3-A is r3,a3

all you need is to compute |a0-a1|, |a0-a2|, |a0-a3| and choose the minimum

Thats basically what I'm doing. r0 is unknown though and thats why I need the arctan table. First I was thinking of calculating the distance between B and Pn and choose the minimum but then I need the sqrt method. But even with an sqrt table it won't be as fast because I need to do three lookups. With the lookup of r0 I only need one table lookup.