Distance approximation?

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 1

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 a² < b² 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.

Answer 2

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.