【寻路】超级简单的A星寻路算法实现

A星寻路算法

A星寻路算法是一种计算最短路径的算法，通过遍历周围所有可以前进的点，计算出最优路径。
它吸取了Dijkstra 算法中的优点，为每个边长设置权值，不停的计算每个顶点到起始顶点的距离（G），以获得最短路线，同时也汲取贪婪最佳优先搜索算法中不断向目标前进优势，并持续计算每个顶点到目标顶点的距离（Heuristic distance），以引导搜索队列不断想目标逼近，从而搜索更少的顶点，保持寻路的高效。

伪代码：

1、将起点加入OpenList；
2、开始循环判断OpenList中是否有可前进的节点；
3、将F值最小的节点从OpenList取出，放入Close List；
4、判断该节点是否未终点，是则跳出循环，不是继续将该点周围可行进的节点添加到OpenList；
5、循环第3步直到查找到终点或遍历完所有OpenList；

公式：

f = g + h
f：寻路消耗；
g：离起点的移动消耗；G值的计算可以进行拓展
往上、下、左、右这4个格子走时，移动代价为10
往左上、左下、右上、右下这4个格子走时，移动代价为14；即走斜线的移动代价为走直线的1.4倍。

h：离终点的预估消耗，最常用最简单的方法就是使用曼哈顿距离进行预估
H = 当前方块到结束点的水平消耗 + 当前方块到结束点的垂直消耗

OpenList；用来存储可以前进并且没有计算过的节点。
Close List：用来存储不再考虑的节点。

核心代码

public List<AstarNode> FindPath(int _startX, int _startY, int _endX, int _endY)
    {
        List<AstarNode> _path = new List<AstarNode>();
        m_openList.Clear();
        closeList.Clear();
        bool findPathFlag = false;
 
        AstarNode currNode = null;
        addToOpenList(null, _startX, _startY, _endX, _endY);//将起点加入OpenList；
 
        while (m_openList.Count > 0)
        {
            currNode = OpenList[0];//取F值最小的节点
            m_openList.Remove(currNode);//将当前节点移出OpenList
            closeList.Add(currNode);//将当前节点加入CloseList
            if (currNode == null)
            {
                break;
            }
 
            if (currNode.X == _endX && currNode.Y == _endY)//如果找到重点，退出循环
            {
                findPathFlag = true;
                break;
            }
 
            genAroundNode(currNode, _endX, _endY);//将周围满足条件的节点加入OpenList
        }
        if (!findPathFlag)
        {
            currNode = findNearPointFromList(closeList, endX, endY);//如果没有找到终点，在CloseList找一个最近的点。
        }
        if (currNode == null)
        {
            return null;
        }
        while (true)//递归父节点，找到所有路径
        {
            _path.Add(currNode);
 
            if (currNode.X == _startX && currNode.Y == _startY)
            {
                break;
            }
            currNode = currNode.Parent;
        }
 
        _path.Reverse();
 
        return _path;
 
    }

A星寻路算法Demohttps://download.csdn.net/download/qq_33461689/14928453