Distance calculation without square roots

Math and Physics Programming

Started by Narf the Mouse December 16, 2010 02:50 PM

10 comments, last by DekuTree64 13 years, 4 months ago

322

Author

December 16, 2010 02:50 PM

Calculating the distance between two points is easy to write out: ((DisX2 - DisX1)^2 + (DisY2 - DisY1)^2)^0.5

However, it's not so fast to calculate, because of that square root. However, if we treat the movement as a diagonal movement of length equal to Min(Abs(DisX2 - DisX1), Abs(DisY2 - DisY1)), we can do the following (Psuedocode):

        Distance(x1, y1, x2, y2)        {            r = 0.0;            axD = Abs(x2 - x1);            ayD = Abs(y2 - y1);            dD = Min(axD, ayD);            r += dD * 1.4142135623730950488016887242097;            r += (axD - dD) + (ayD - dD);            return r;        }

It relies on the simple fact that, for any 2D vector, you can subtract a (0, infinity] length, 45 degree diagonal vector from it and end up with either a vertical, horizontal or zeroed vector.
This might already be known, but I've never seen it anywhere, so I'm posting it here.

Edit: ...I think my math is bad. It works well enough for A*, though.

Now open: MouseProduced Games

luca-deltodesco

638

December 16, 2010 03:10 PM

It's not correct, you're right about that.

It's also no faster than a normal distance function anyways in my own tests :P

popsoftheyear

2,195

December 16, 2010 03:12 PM

Can't you just compare the squared distance and avoid all the hassle? Do you actually need the sqrt (whether real or approximate) of it?

Palidine

1,315

December 16, 2010 03:16 PM

For calculations where you're only interested in relative distance, like A*, distance squared usually works just fine. For places where you need the actual distance, a sqrt is typically not anywhere close to being your performance bottleneck when compared to encapsulating algorithms.

I hope that you were at least interested in trying to remove the square root because a profiler told you that sqrt was your biggest performance problem. Typically the biggest limiting factor in A* performance is accessing the open list; I would think that sqrt wouldn't be anywhere near the top of the profile.

-me

grhodes_at_work

1,385

December 16, 2010 03:19 PM

I don't believe the success of your method has anything to do with 45 degree angles or subtracted vectors. Why don't you just let r = axD + ayD? Try that and see what happens. Its simpler than your code and will probably work just as well. This simple addition of components is called the L1-norm of the vector. The Euclidian length that requires a square root is the L2-norm (aka Euclidian norm). Both norms are representations of the distance between the two points. The L2-norm just happens to be the shortest distance in a Euclidian space. Both norms increase as the points get farther away from each other and both decrease when the points get closer, which is a key important thing in computing the A* costs.

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

alvaro

21,604

December 16, 2010 03:57 PM

I have seen very similar code before, but I don't have a link (EDIT: Actually, it's described here). What you are doing is using a linear approximation to the distance that works OK for a 45-degree region from the origin, and then applying it in all 8 regions.

This can be seen by plotting a ball as defined by your distance function:

#include <cstdio>#include <algorithm>double Distance(double x1, double y1, double x2, double y2) {  double r = 0.0;  double axD = std::abs(x2 - x1);  double ayD = std::abs(y2 - y1);  double dD = std::min(axD, ayD);  r += dD * 1.4142135623730950488016887242097;  r += (axD - dD) + (ayD - dD);  return r;}int main() {  for (int i=0; i<50; ++i) {    for (int j=0; j<100; ++j)      std::printf("%c","# "[Distance(i,j*.5,25,25)>20]);    std::puts("");  }}

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      #                                                                                               #########                                                                                      ###################                                                                            #############################                                                                  #######################################                                                        #################################################                                               #########################################################                                          ###########################################################                                        #############################################################                                       #############################################################                                      ###############################################################                                    #################################################################                                  ###################################################################                                #####################################################################                              #######################################################################                             #######################################################################                            #########################################################################                          ###########################################################################                        #############################################################################                      ###############################################################################                    #################################################################################                    ###############################################################################                      #############################################################################                        ###########################################################################                          #########################################################################                            #######################################################################                             #######################################################################                              #####################################################################                                ###################################################################                                  #################################################################                                    ###############################################################                                      #############################################################                                       #############################################################                                        ###########################################################                                          #########################################################                                               #################################################                                                        #######################################                                                                  #############################                                                                            ###################                                                                                      #########                                                                                               #

Fenrisulvur

186

December 16, 2010 05:27 PM

Quote:Original post by Palidine
I hope that you were at least interested in trying to remove the square root because a profiler told you that sqrt was your biggest performance problem. Typically the biggest limiting factor in A* performance is accessing the open list; I would think that sqrt wouldn't be anywhere near the top of the profile.

O(log(n)) per poll at best, so, yeah, this.

On this note, it should be pretty clear that a heap-based queue (PriorityQueue in ADT terms) would be your best bet for an open list. Normally something like a graph or a grid directly corresponding to the search space is your best shot for a closed list, and accesses should be O(1). If either of these is deficient, that's your bottleneck.

rubicondev

296

December 16, 2010 05:34 PM

I'm trying to remember the first time I used that formula. Has to be at least 25 years ago, probably more. In the days of assembler I'd just use *1.5 instead of root2 as that could be done with a shift instruction

I'm sure it used to be called the manhattan distance before the math community appropriated the term for something else.

EDIT: My bad, said it was a long time ago. This is of course the Euclidean distance!

------------------------------Great Little War Game

alvaro

21,604

December 16, 2010 05:42 PM

Quote:Original post by Rubicon
I'm sure it used to be called the manhattan distance before the math community appropriated the term for something else.

That's very strange. The streets in most of Manhattan (North of Houston St or so) are in a regular grid, which means that to go from 48th and 6th to 53rd and 5th you need to walk 6 blocks (See the Wikipedia article on the Manhattan distance). It's hard to imagine that something else would be called Manhattan distance. Mathematicians usually call it the L_1 norm anyway.

rubicondev

296

December 16, 2010 05:44 PM

Heh, see above. Glad I edited it before you made your comment :)

Edit: The shift-friendly version was basically:

max(absxdiff,absydiff)+(min(absxdiff,absydiff)>>1) ie maxdiff + half mindiff

------------------------------Great Little War Game

Distance calculation without square roots

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Distance calculation without square roots

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines