Should I store distances between 2d points in a not grid based A* algorithm

Question

I'm implementing the A* algorithm. Any node can be connected to any other, provided there is nothing obstructing the path, which should rarely be the case. This way found paths will usually contain a small number of nodes (maybe even just 2), but options for moving from node to node are insanely numerous. In grid-based A* algorithm videos I've heard that it's a good idea to store these distances rather than calculating them over and over again, but is this the case here? A node's position isn't bound to a grid and it seems to me that the dictionary of calculated distances would grow too large to use (searching through for the key). There shouldn't be too many nodes (30 to 500), so will 499 reference comparisons in the dictionary's search for the corresponding value take longer than just calculating the distance every time? If not - from what amount of nodes will this dictionary search time matter? Below's the skeleton code of the class I use.

class Node
{
    private Vector2 position;
    public Vector2 Position 
    {
        get 
        {
            return position;
        }
        set 
        {
            position = value; 
            calculatedDistances.Clear();
        }
    }
    private Dictionary<Node, float> calculatedDistances;

    public float DistanceTo(Node to)
    {
        float dist;
        if (calculatedDistances.TryGetValue(to, out dist))
        {
            return dist;
        }
        else
        {
            dist = Vector2.Distance(this.Position, to.Position);
            calculatedDistances.Add(to, dist);
            return dist;
        }
    }
}

Answer 1

The performance characteristics always very very much depend on your actual data sets. You should almost never rely on what you think is going to be faster: profile profile profile. The C# Stopwatch class is great for this purpose.

That being said, here are a few thoughts on your case:

• A Dictionary likely won't do 499 reference comparisons. Depending on the exact implementation of the C# Dictionary (according to MSDN, it uses a hash table), you can get close to O(1) lookups, not O(n) (for a linear scan) or O(log(n)) (for a binary search).
• With A*, you don't need to use the real distance between nodes. Anything which serves as a "metric" will do. In order to be a metric, it just needs to always be positive (unless you compare the same two points, in which case it must be 0) and the distance from A -> B -> C has to be greater than or equal to A -> C. Concretely, you can use the distance squared, rather than the distance. When you're concerned about performance, this saves you an expensive square root computation.