Question: 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.

Answer: 
> 
> ***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 `double`s until that proves to be a bottleneck.
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%.