我应该在不基于网格的 A* 算法中存储 2d 点之间的距离吗

Question

我正在实现 A* 算法。任何节点都可以连接到任何其他节点，前提是没有任何东西阻碍路径，这种情况很少见。通过这种方式找到的路径通常包含少量节点（甚至可能只有 2 个），但是从一个节点移动到另一个节点的选项非常多。在基于网格的 A* 算法视频中，我听说存储这些距离而不是一遍又一遍地计算它们是个好主意，但这里是这种情况吗？节点的位置未绑定到网格，在我看来，计算距离的字典会变得太大而无法使用（搜索键）。节点不应该太多（30到500），那么字典中查找对应值的499次引用比较，会不会比每次只计算距离耗时更长？如果不是——这个字典搜索时间对多少节点有影响？下面是我使用的 class 的框架代码。

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

性能特征在很大程度上取决于您的实际数据集。您几乎不应该依赖您认为会更快的东西：profile profile profile。 C# Stopwatch class 非常适合这个目的。

话虽这么说，这里有一些关于您的案例的想法：

字典可能不会进行 499 次参考比较。根据 C# 字典的具体实现（根据 MSDN，它使用散列 table），您可以接近 O(1) 查找，而不是 O(n)（对于线性扫描）或 O( log(n)) （用于二进制搜索）。
使用 A*，您不需要使用节点之间的实际距离。任何充当 "metric" 的东西都可以。为了成为一个度量，它只需要始终为正（除非你比较相同的两个点，在这种情况下它必须为 0）并且从 A -> B -> C 的距离必须大于或等于A -> C。具体来说，您可以使用距离的平方，而不是距离。当您关心性能时，这可以为您节省昂贵的平方根计算。

我应该在不基于网格的 A* 算法中存储 2d 点之间的距离吗

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

c#

dictionary

unity3d

2d

a-star