c# - 维基百科 A* 寻路算法需要大量时间

Question

我已经在 C# 中成功实现了 A* 寻路，但是速度很慢，我不明白为什么。我什至尝试不对 openNodes 列表进行排序，但它仍然是一样的。

map 是80x80，有10-11个节点。

我从这里获取了伪代码 Wikipedia

这是我的实现:

 public static List<PGNode> Pathfind(PGMap mMap, PGNode mStart, PGNode mEnd)
    {
        mMap.ClearNodes();

        mMap.GetTile(mStart.X, mStart.Y).Value = 0;
        mMap.GetTile(mEnd.X, mEnd.Y).Value = 0;

        List<PGNode> openNodes = new List<PGNode>();
        List<PGNode> closedNodes = new List<PGNode>();
        List<PGNode> solutionNodes = new List<PGNode>();

        mStart.G = 0;
        mStart.H = GetManhattanHeuristic(mStart, mEnd);

        solutionNodes.Add(mStart);
        solutionNodes.Add(mEnd);

        openNodes.Add(mStart); // 1) Add the starting square (or node) to the open list.

        while (openNodes.Count > 0) // 2) Repeat the following:
        {
            openNodes.Sort((p1, p2) => p1.F.CompareTo(p2.F));

            PGNode current = openNodes[0]; // a) We refer to this as the current square.)

            if (current == mEnd)
            {
                while (current != null)
                {
                    solutionNodes.Add(current);
                    current = current.Parent;
                }

                return solutionNodes;
            }

            openNodes.Remove(current);
            closedNodes.Add(current); // b) Switch it to the closed list.

            List<PGNode> neighborNodes = current.GetNeighborNodes();
            double cost = 0;
            bool isCostBetter = false;

            for (int i = 0; i < neighborNodes.Count; i++)
            {
                PGNode neighbor = neighborNodes[i];
                cost = current.G + 10;
                isCostBetter = false;

                if (neighbor.Passable == false || closedNodes.Contains(neighbor))
                    continue; // If it is not walkable or if it is on the closed list, ignore it.

                if (openNodes.Contains(neighbor) == false)
                {
                    openNodes.Add(neighbor); // If it isn’t on the open list, add it to the open list.
                    isCostBetter = true;
                }
                else if (cost < neighbor.G)
                {
                    isCostBetter = true;
                }

                if (isCostBetter)
                {
                    neighbor.Parent = current; //  Make the current square the parent of this square. 
                    neighbor.G = cost;
                    neighbor.H = GetManhattanHeuristic(current, neighbor);
                }
            }
        }

        return null;
    }

这是我正在使用的启发式方法:

    private static double GetManhattanHeuristic(PGNode mStart, PGNode mEnd)
    {
        return Math.Abs(mStart.X - mEnd.X) + Math.Abs(mStart.Y - mEnd.Y);
    }

我做错了什么？我一整天都在看同一个代码。

Answer 1

首先，使用分析器。使用工具告诉你什么是慢的；缓慢的事情常常令人惊讶。并且使用调试器。制作一个包含五个节点的 map ，并在尝试找到路径时逐步执行代码的每一行。有没有发生什么意想不到的事情？如果是这样，请弄清楚发生了什么。

其次，抛开你的性能问题不谈，我认为你也有正确性问题。您能向我们解释一下为什么您认为曼哈顿距离是一种合理的启发式方法吗？

(对于那些不熟悉该度量标准的阅读本文的人，“曼哈顿距离”或“出租车距离”是指如果您住在一个网格化的城市中，您必须经过的两点之间的距离。也就是说，要向正东北方向行驶 14 英里，您必须向北行驶 10 英里，然后向东行驶 10 英里，总共 20 英里。)

A* 算法的正确性要求启发式总是低估两点之间行进所需的实际距离。如果图中有任何“对角线捷径”街道，则曼哈顿距离高估这些路径上的距离，因此算法不一定会找到最短路径。

您为什么不使用欧几里德 距离作为启发式？

您是否尝试过使用“始终为零”作为启发式的算法？这肯定是低估了。 (这样做可以让您实现 Dijkstra 算法。)

第三，您似乎在此实现中进行了大量排序。当然，您可以使用优先级队列；这比排序便宜很多。

第四，我的博客上有一个 C#3 中的 A* 实现，欢迎您使用；没有明示或暗示的保证，使用风险自负。

http://blogs.msdn.com/b/ericlippert/archive/tags/astar/

我的代码非常简单；我的实现中的算法如下所示:

var closed = new HashSet<Node>();
var queue = new PriorityQueue<double, Path<Node>>();
queue.Enqueue(0, new Path<Node>(start));
while (!queue.IsEmpty)
{
    var path = queue.Dequeue();
    if (closed.Contains(path.LastStep)) continue;
    if (path.LastStep.Equals(destination)) return path;
    closed.Add(path.LastStep);
    foreach(Node n in path.LastStep.Neighbours)
    {
        double d = distance(path.LastStep, n);
        var newPath = path.AddStep(n, d);
        queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
    }
}

我们的想法是维护一个优先路径队列；也就是说，路径队列总是能够告诉您到目前为止距离最短的路径。然后我们检查是否已经到达目的地；如果是这样，我们就完成了。如果不是，那么我们会根据它们到目标的(低估)估计距离将一堆新路径排入队列。

第五，维基百科中的伪代码可以改进。事实上，我的实际代码在很多方面都比伪代码更容易理解，这表明伪代码中的细节可能太多了。