CODEWITHSUNDEEP
performancealgorithmdistance
user1012037
user1012037

Reputation: 501

Distance approximation?

I am doing pathfinding on a 2D grid.

I need to calculate distance as one of my heuristics.

Furthermore I need to return the closest spot if the full path is not found.

Calculating the exact distance to a double precision seems like unnecessary overhead. Is there any fast approximation I can use, which will still be accurate enough to meet my needs? (within rounding accuracy of 1)

By the way, path lengths are typically only around 5-30 nodes, so using a more accurate function at the end wouldn't be worth it.

Upvotes: 8

Views: 2054

Answers (3)

aioobe
aioobe

Reputation: 421220

I need to return the closest spot if the full path is not found.

In this case you could skip the square root operation in the distance calculation, i.e. compare squared distances using just dy * dy + dx * dx.

This works since a2 < b2 if and only if a < b for two arbitrary distances a and b.

In a 2D grid this would be implemented purely with integers.

If you need non-integer values, I'd probably go with doubles until that proves to be a bottleneck.

Upvotes: 10

pjheink
pjheink

Reputation: 306

Slightly better than Manhattan distance and nearly as fast would be:

unsigned int fastDist(unsigned int dx, unsigned int dy) {
    if ( dy < dx ) return (dx + (dy >> 1));
    else return (dy + (dx >> 1));
}

It's exact when either dx or dy are zero. The error on the diagonal is about 6% and the maximum error is about 12%.

And this can be improved by adding another term:

unsigned int fastDist(unsigned int dx, unsigned int dy) {
    unsigned int w;
    if ( dy < dx ) {
        w = dy >> 2;
        return (dx + w + (w >> 1));
    }
    else {
        w = dx >> 2;
        return (dy + w + (w >> 1));
    }
}

This has a maximum error of less than 7% and the error along the diagonal is less than 3%.

Upvotes: 3

Jeff Foster
Jeff Foster

Reputation: 44736

If it is a 2D grid you could consider using the Manhattan distance. This would allow you to work in grid units all the time and avoid the square root. As aioobe suggests, this is probably micro-optimizing.

Upvotes: 2

Related Questions