A*：感谢 Seunghyop Back 的介绍

致谢与介绍

我写这篇文章是为了回应 seunghyop back 之前发表的一篇文章《Very simple A* algorithm implementation》。我更喜欢直接的沟通方式，但一直找不到直接向 Code Project 用户发送消息并交换源代码的方法，所以希望通过撰写文章来按预期使用此网站。本文无意批评，而是表达感谢。我最初并没有打算分享这些修改，但后来觉得与其让它们闲置在硬盘上，不如分享出来。我希望我的做法符合所有适用的礼仪。我认为这些修改主要是建议性的，属于个人品味问题。我无意在此与原代码展开竞争。

背景

说来惭愧，尽管我从事软件工程师多年，直到最近才熟悉 A*。根据我这段时间所了解到的，A* 至今仍有广泛的应用，并且在许多流行的游戏大作中都有使用，这只是其中一个例子。我一直在寻找一种最快的 A* 入门方法，以及一个可以用来进行实验的可用实现，以确保我能完全理解其算法。sounghyop 的文章是我偶然发现的。在没有具体目标的情况下（这里故意用了“寻路”的双关语），我开始尝试修改提供的源代码，并做了一些小的改动。

对原代码的修改

以下是我进行的一些修改列表，顺序不分先后，不保证完整性。

我发现了将容器“SortedCostNodeList”替换为 .Net 的 SortedSet 的机会。这里的一个挑战是，节点需要按照 A* 定义的成本进行排序，因此传递给 SortedSet 的 IComparer 实现应该根据该属性区分节点。但是，SortedSet 会忽略它认为值相等的多个元素的插入，而 A* 实现则必须允许为给定的地图位置存在多个节点，每个节点具有不同的成本。这是因为 A* 在生成到目标节点的路径时，可以生成多个可能的路径，这些路径有时会在同一位置相交。如果 NodeComparer 没有被修改，算法很可能会陷入死胡同，因为未经修改的集合会丢弃那些与列表中“开放”（尚未完全探索）的先前节点相等的节点。

我希望上面对以下修改的解释是有道理的。如果没有，请尝试使用带有旧 IComparer 实现的新实现，运行一些示例，我相信您很快就会遇到算法在障碍物前结束路径，无法绕行的示例。

class NodeComparer : IComparer<Node>
{
    int IComparer<Node>.Compare(Node n1, Node n2)
    {
        if (n1.TotalCost == n2.TotalCost)
        {
            if (n1.X == n2.X && n1.Y == n2.Y)
            {
                return 0;
            }

            // Allow multiple nodes of equal cost but different coordinates.
            return -1;
        }

        return n1.TotalCost - n2.TotalCost;
    }
}

我之所以给出如此详细的解释，部分原因在于 NodeComparer 的这项更改现在允许将大约 75 行代码的原始“SortedCostNodeList”简单地替换为以下内容：

public class NodeSet : SortedSet<Node>
{
    public NodeSet() : base(new NodeComparer()) { }
}

 

SortedSet 提供了 A* 所需的所有操作和属性，并保证了它们的可用性。我选择这个集合是因为它似乎为简化现有代码提供了最简单的接口。我试图简化算法的编码，并且在此不考虑或讨论渐进运行时复杂度。尽管如此，我认为可以通过过滤节点集中的候选节点，只保留那些成本较低的节点，来改进当前确定优于当前后继节点（或相邻节点）的线性查找。节点集已经按节点成本排序，因此可以避免遍历整个节点迭代器。特别是，“GetViewBetween”这个方法，我还没有花时间研究它可能的优点。

通过这些修改、一些重构以及少量使用 Linq 来提高对集合操作的表达能力，A* 实现的顶层被简化为以下内容：

public static Node FindPath(Location start, Location goal)
{
    Node goalNode = new Node(goal);
    Node startNode = new Node(start, goalNode);

    NodeSet open = new NodeSet() {startNode};
    NodeSet closed = new NodeSet();

    while (open.Any())
    {
        Node best = open.Min;
        open.Remove(best);

        if (best.Coincides(goalNode))
        {
            goalNode.Parent = best.Parent;
            break;
        }

        foreach (Node successor in best.ConnectedNodes())
        {
            Node betterOpen = open.NodesBetterThan(successor);
            if (betterOpen != null)
            {
                continue;
            }

            Node betterClosed = closed.NodesBetterThan(successor);
            if (betterClosed != null)
            {
                continue;
            }

            if (betterOpen != null)
            {
                open.Remove(betterOpen);
            }

            if (betterClosed != null)
            {
                closed.Remove(betterClosed);
            }

            if (betterClosed == null && betterOpen == null)
            {
                open.Add(successor);
            }
        }

        closed.Add(best);
    }

    return goalNode;
}

与原版相比，我保留了主要的代码流程。我想将尽可能多的非 A* 算法核心代码移出主方法，希望能让其机制更加清晰易懂。

根据我的经验，Linq 代码很容易占据总运行时时间的很大一部分，因此需要特别小心，尤其是在此类算法的主循环中使用它时。我没有对这个实现进行性能分析，所以不知道它实际占用了多少时间，但在这里使用它，是因为我觉得通过使用 Linq，算法的某些操作可以以特别富有表现力和简洁的方式实现，例如以下操作：

public static class NodeSetExtensions
{
    public static Node NodesBetterThan(this NodeSet set, Node node)
    {
        return set.Where(n => node.TotalCost > n.TotalCost && n.Coincides(node)).FirstOrDefault();
    }
}

上面的代码实现为一个扩展方法，因为我认为“所有优于给定节点的节点”这个概念，作为节点集的属性比作为节点集上的独立操作（可以实现为常规静态方法）更清晰地表达。请参考上面 A* 主循环的代码，看看它的用法，并比较如果它是一个常规方法而不是扩展方法，代码会有什么样的“感觉”。

还有其他修改。大多数都是实现了等效的功能。据我回忆，只有一个修改是为了方便：您现在可以将起点和终点“绘制”到地图上。如果这样做，实际上会导致一个我迄今为止尚未处理的异常。

使用代码

绘制地图以查看 A* 的工作原理！地图现在是一个字符串数组，所以您不再需要到处设置逗号。示例如下：

static string[] MapData = 
{
"    #######################              #####                      ",
"                  ####             #############  #####     ",
"     ####                #####        ##########                   ",
"     S###   ######            ##      ##############                   ",
"     ########    #                 #############                   ",
"            # #  #########                                        ",
"            # #        ###    ###   ###### ######                   ",
"            #G########  ##            #### ##########                 ",
"            #####      ###    ###########  ####                         ",
"             #        ############  ###                          ",
"             #                                    ",
};

在上面，“S”代表“Start”（不是“sucks”），“G”代表“Goal”。最终得到的路径如下：

    #######################              #####
     oooo     o   ####             #############  #####
    o####oo oo ooo       #####oo      ##########
     o###  o######o  oo oo  oo##o     ##############
     ######## oo # oo  o  oo     o #############
            #o# o#########        oooooooo
            #o#  ooooo ###    ###   ######o######
            #o########o ##            ####o##########
            #####     o###    ###########o ####
             #       o############  ### o
             #        oooooooooooooooooo

关注点

我亲身体验了 A* 据称会产生的曲折路径，这很有趣。对于那些比我更熟悉 A* 的人来说，这可能显而易见，但看到具体的例子比单独在脑海中推测这些情况要直观得多。如果您看上面的例子，可以看到它们很清楚，主要是在障碍物周围。

理解这些曲折路径不会影响路径的总长度很重要。如果您将每个曲折路径与完成直线所需的节点数进行比较，您会满意地发现每种情况下的节点数都是相同的。上面例子中尤其是在路径中间的部分，乍一看似乎是一个完整的绕行。然而，如果路径是通往右边“狭窄走廊入口”的直线，那么这四个向右上方斜向插入的步骤是必需的。如果我们不允许对角线移动（这可以通过限制“Node::ConnectedNodes”方法很容易做到），A* 会在探索到目标节点的路径时，放弃这些路径，转而选择更短、更直的路径。