概述

• A* = Dijkstra + 启发式函数

A*是Dijkstra的启发式改进版，目的在于解决Dijkstra效率低的问题。Dijkstra不知道目标节点的位置，所以只能向所有方向扩展直到发现目标节点。GBFS算法的缺点在于，过分关注目标点的位置，即GBFS每次访问的节点具有到目标节点的最小代价，但是在有障碍物的情况下路径不是最优解；

两者取长补短，诞生了A*算法，A*同时借鉴了两种算法，在Dijkstra基础上引入了启发式函数h(n)；

思路

• 定义待查找列容器toSearch， 已查找容器processed
• h(n)表示了当前节点到目标节点的成本。保证了最优性的同时，加入了目标节点的信息，提升了效率。
• 原代价函数g(n): 对从初始节点到节点n的累计成本的当前最佳估计。
• 目标代价函数h(n): 节点n到目标节点的代价估计（即目标代价），可以使用曼哈顿距离、欧几里得距离。
• f(n) = g(n) + h(n) ： 从初始节点，通过当前节点n，再到目标节点的代价估计。

策略：每次访问toSearch容器中f(n)最小的节点；

算法流程和Dijkstra一模一样，只不过访问的下一节点变成了 f(n) 最低的节点；

继续使用动态规划+贪心思想，但既考虑了当前成本，也考虑了目标成本；

代码实现

// C# 实现 Astar 寻路
List<NodeBase> FindPath(NodeBase startNode, NodeBase targetNode)
{
    // 待查找列表
    List<NodeBase> toSearch = new List<NodeBase>() { startNode };
    // 已查找列表
    List<NodeBase> processed = new List<NodeBase>();
    // 寻路
    while (toSearch.Any())
    {
        var current = toSearch[0];
        // 查找待访问容器中期望路径最短的点
        foreach (var t in toSearch)
        {
            if (t.F < current.F || t.F == current.F && t.H < current.H)
            {
                current = t;
            }  
            processed.Add(current);
            toSearch.Remove(current);
            // 如果当前找到节点为目标节点 寻路完成 构建路径并返回
            if (current == targetNode)
            {
                var currentPathTile = targetNode;
                var path = new List<NodeBase>();
                while (currentPathTile != startNode)
                {
                    path.Add(cureentPathTile);
                    currentPathTile = currentPathTile.Connection;
                }
                return path;
            }
            // 遍历当前点所有邻接 且可移动 且未找到最短路径的节点
            foreach (var neighbor in current.Neighbors.Where(t => t.walkable
            && !processed.Contains(t)))
            {
                var inSearch = toSearch.Contains(neighbor);
                // 前往该邻接节点的距离是当前节点的 G 加上当前节点到邻接节点的距离
                var costToNeighbor = current.G + current.GetDistane(neighbor);
                // 如果该邻接节点不在待搜索容器中 或 前往该节点距离小于该节点 G
                if (!inSearch || costToNeighbor < neighbor.G)
                {
                    // 设置邻接节点 G
                    neighbor.SetG(costToNeighbor);
                    // 设置连接 方便构建路径
                    neighbor.SetConnection(current);
                    if (!inSearch)
                    {
                        neighbor.SetH(neighbor.GetDistance(targetNode));
                        toSearch.Add(neighbor);
                    }
                }
            }
        }
    }
    return null;
}

参考资料