A星寻路算法

Unity C#

导入

在许多游戏中，我们经常要处理人物的移动——玩家移动由玩家自己控制自然不需要我们考虑，但是涉及到AI的移动的时候，寻路算法的写法就是一个大难题了——如何让AI像一个正常的生物去思考，去求得最短路径呢？

这时候就需要用到目前最被广泛使用的一种寻路算法——A星算法。

参考文献

基于Unity的A星寻路算法（绝对简单完整版本） - 知乎 (zhihu.com)

A-Star（A*）寻路算法原理与实现 - 知乎 (zhihu.com)

游戏中的寻路之A*寻路 - 知乎 (zhihu.com)

思维介绍

A星算法的实现思路

为了方便算法的展示，我们不妨先把游戏地图进行抽象化——将地图列为一个个正方形格子组成的地图（实际上在大部分游戏里你都可以这么做）——但是我需要强调的是，不同类型的游戏完全可以不采用正方形，只需要有一个判断两点之间最短和最长的依据就可以实现A星算法。

在介绍A星寻路算法前，先介绍另外一种算法：Dijkstra寻路算法，简单的来说是一种A星寻路的基础版。Dijkstra作为一种无启发的寻路算法，通过围绕起始点向四周扩展遍历，一直到找到目标点结束，简单来说就是暴力破解，由近到远遍历所有可能，从而找到目标点

很明显，这种寻路方式是很的消耗性能的，非常的不高效，有没有更好的解决方式呢

从实际生活中出发，如果你要到达某地，却不知道具体的路该怎么办呢，是不是先大概确定方向，边靠近目标点边问路呢

A星寻路算法也是基于这样的思路，通过一定的逻辑找到可以靠近物体的方向，然后一步步的走进目标点，直到到达目的地。

确定直角斜角权重：

本质上来讲，A星寻路是基于一种网格的地图来实现的寻路的方式，在网格中，一个点可以到达的位置为周围的八个方向。而由于水平与垂直和倾斜的方向距离不一样，所以我们在寻路时需要设置不同的长度：

通过图片可以看出，直线距离与斜线距离是分别等腰直角三角形直角边与斜边。根据勾股定理我们可以得知两者的比例关系约为1.41：1，为了方便计算和照顾性能(浮点数性能差)，我们就将斜边权重为14，而直角边权重为10，这样的话，要得到最短的路径，可以按照下面的思路去考虑：

遍历移动格子消耗：

接下来需要考虑第二个问题，在对起始点周围的可移动格子遍历完成后，如何找到最短路径上的那个格子呢，即下一步该走哪一个格子，这里就是整个A星寻路算法的核心：

寻路消耗公式：
f（寻路消耗）=g（离起点距离/行走消耗）+h（离终点距离）
离终点距离采用曼哈顿街区算法

g 用两点之间直接距离横10 斜14
h 用曼哈顿算法横向距离 + 竖向距离 (数格子)

运用上文的公式，我们就可以计算一组格子中每个格子的消耗，然后我们通过不断的遍历和筛选消耗最小的格子，每次筛选出来小个子后就自动夸大周围的新格子进入筛选队列，通过这个思路，我们就可以实现该算法。

实现

重要概念

OpenList （开放列表）

又称为备用列表，存储下一步寻路的坐标节点，每次从开发列表获取 F值最小的节点坐标

CloseList

又称 关闭列表，已经走过的坐标节点会被放入其中，用来判断某个坐标节点是否已经走过。

Parent

父亲节点，标记父节点，记录是是由哪个节点搜索过来。

G

表示从起点移动到网格上指定方格的移动耗费 (可沿斜方向移动) ，我们规定，上下左右移动一格路径值为1，斜方向4个方向规定为1或者1.4（三角形斜边长度的计算）。

H(Heuristics)

估计值，是对当前坐标到目标节点（终点）的距离的一种估算，具体的估算方法被称为 启发函数

F

权值，由 G + H计算得出，数值越小，表明离目标节点越近，备选列表里 F值最小的节点，有可能是到目标节点的最短路径节点。

启发函数

当前坐标到目标节点（终点）的距离的一种估算方法，常见的有如下几种：

曼哈距离：两点间 X坐标差绝对值与 Y坐标差的绝对值相加；
H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )
欧几里得距离：两点之间直线连接的距离。
h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)优点放入关闭列表时，我们会创建最优点周围的新格子到开启列表，这时候新对象被新格子记录下来。

当寻找到终点的时候，通过父对象来一路回溯到起点，最终才可以获得最终路径。

实现思路

1.将起点放入OpenList中

2.利用While(OpenList.Count)循环，只要OpenList.Count大于0，就一直循环执行3， 4， 5步骤。

3.寻找开启列表中的F最小的节点MinFNode，如果F相同，选取H最小的。同时把MinFNode从OpenList移除，放入ClosedList中

4.遍历MinFNode周围的节点，忽略障碍节点和已在ClosedList中的节点，这里会有3种情况

相邻点不在OpenList中的，计算H值和G值（MinFNode的G值加上移动所产生的G值），并且把该相邻点的父节点设置为MinFNode (后期找到终点后，需要用父节点进行路径回溯，画出路线。)，加入到开启列表OpenList中。
相邻点已在OpenList中的，则判断从MinFNode节点的G值加上到相邻点移动所产生的G值之和，是否小于该相邻点的G值，假设小于了，则更新该相邻点的G值为较小的那个，然后重新设置该相邻点的父节点为MinFNode
假设遍历到的节点是终点，则按MinFNode的父节点进行回溯，获取到起点的路径，找到最终路径

5.如果没有找到终点，回到第3步，继续执行

代码

namespace S
{
    public class ANode 
    {
        public ANode priviour;//上一个节点
        public int x;
        public int y;
        public int f => h + g;//预估代价
        public int h;//预估到终点的代价
        public int g;//从开始节点到此节点的代价

        public ANode(int x,int y) {
            this.x = x;
            this.y = y;
        }
    }

    class AStar
    {
        private List<ANode> openList = new List<ANode>();
        private List<ANode> closeList = new List<ANode>();
        private ANode startNode;
        private ANode endNode;
        private bool canCorner;//可以走斜角
        private Func<int,int, bool> onWalkNode;

        /// <summary>
        /// 获取从开始点到结束点的路径
        /// </summary>
        /// <param name="startNode">开始点</param>
        /// <param name="endNode">结束点</param>
        /// <param name="canCorner">是否可以斜着走</param>
        /// <returns></returns>
        public ANode GetPath(ANode startNode,ANode endNode,bool canCorner) {

            if (openList == null) openList = new List<ANode>();
            else openList.Clear();

            if (closeList == null) closeList = new List<ANode>();
            else closeList.Clear();

            this.startNode = startNode;
            this.endNode = endNode;
            this.canCorner = canCorner;

            openList.Add(startNode);

            return SearchOpenList();
        }

        /// <summary>
        /// 注册位置点的可走状态
        /// </summary>
        /// <param name="onWalkNode">（位置点x坐标，位置点y坐标，返回值是否可走）</param>
        /// <returns></returns>
        public AStar OnWalkNode(Func<int, int, bool> onWalkNode)
        {
            this.onWalkNode = onWalkNode;
            return this;
        }

        /// <summary>
        /// 遍历openList
        /// </summary>
        ANode SearchOpenList() {

            while (openList.Count>0) {
                ANode bestNode = GetBestNodeOfOpenList();
                openList.Remove(bestNode);
                closeList.Add(bestNode);
                List<ANode> rangeList = GetRangeNodes(bestNode);
                ANode node = null;
                ANode tryNodeOfOpenList = null;
                for (int i = 0; i < rangeList.Count; i++)
                {
                    node = rangeList[i];
                    tryNodeOfOpenList = GetNodeOfOpenList(node.x, node.y);//试图从openList中得到这个Node

                    if (tryNodeOfOpenList==null)//这个Node不在openList中
                    {
                        ConnectNode(bestNode,node);
                        openList.Add(node);
                    }
                    else { //此节点已经存在于OpenList中

                        int tryG = bestNode.g + GetDistance(bestNode,node);
                        int tryH = GetDistance(node,endNode);
                        int tryF = tryG + tryH;
                        if (tryF<tryNodeOfOpenList.f)//从bestNode去往当前点的代价更低
                        {
                            ConnectNode(bestNode,node);
                        }
                    }
                }
                ANode tryEndNode = GetNodeOfOpenList(endNode.x,endNode.y);
                if (tryEndNode != null) return tryEndNode;//如果结束点已经在openList中则直接返回结束点
            }
            return null;
        }

        /// <summary>
        /// 在OpenList中找到代价最小的Node
        /// </summary>
        ANode GetBestNodeOfOpenList() {
            if (openList.Count == 0) return null;
            ANode bestNode = null;
            ANode curNode = null;
            for (int i = openList.Count-1; i >=0; i--)
            {
                curNode = openList[i];
                if (bestNode==null)
                {
                    bestNode = curNode;
                    continue;
                }
                if (curNode.f > bestNode.f) continue;
                if (curNode.f < bestNode.f) bestNode = curNode;
                else if (curNode.h < bestNode.h) bestNode = curNode;
            }
            return bestNode;
        
        }

        /// <summary>
        /// 获取Node周围不在CloseList中的所有Node
        /// </summary>
        List<ANode> GetRangeNodes(ANode node) {
            if (node == null) return null;
            List<ANode> list = new List<ANode>();

            ANode newNode = null;
            for (int i = node.x-1; i <=node.x+1; i++)
            {
                for (int j = node.y-1; j <=node.y+1; j++)
                {
                    if (i == node.x && j == node.y) continue;//node本身
                    if (!CanWalk(node, i, j)) continue;//不可行至的节点
                    if (HasNodeOfCloseList(i,j)) continue;//已经在CloseList中
                    newNode = GetNodeOfOpenList(i,j);
                    if (newNode == null) newNode=new ANode(i,j);
                    list.Add(newNode);
                }
            }
            return list;
        }

        /// <summary>
        /// 连接Node
        /// </summary>
        /// <param name="begainNode">开始Node</param>
        /// <param name="targetNode">目标Node</param>
        void ConnectNode(ANode begainNode,ANode targetNode) {
            targetNode.priviour = begainNode;
            targetNode.g = begainNode.g+GetDistance(begainNode, targetNode);
            targetNode.h = GetDistance(targetNode, endNode);
        }

        /// <summary>
        /// 获取两个Node之间的移动代价
        /// </summary>
        /// <param name="begainNode">开始Node</param>
        /// <param name="targetNode">目标Node</param>
        /// <returns></returns>
        int GetDistance(ANode begainNode, ANode targetNode) {
            // 直着走代价为10 斜着走代价为14 预判代价时不考虑斜着走
            int disX = Math.Abs(begainNode.x-targetNode.x);
            int disY = Math.Abs(begainNode.y-targetNode.y);
            int step = disX + disY;
            int dis = 0;
            if (step == 2)
            {
                if (canCorner)//可以走斜角
                {
                    if (disX == disY) dis = 14;//斜对角
                }
                else dis = step * 10;
            }
            else dis=step * 10;

            return dis;
        }

        /// <summary>
        /// 从CloseList中寻找指定位置点的ANode
        /// </summary>
        ANode GetNodeOfCloseList(int x,int y) {
            if (closeList == null || closeList.Count == 0) return null;
            ANode node = null;
            for (int i = closeList.Count-1; i >=0; i--)
            {
                node = closeList[i];
                if (x == node.x && y == node.y) return node;
            }
            return null;
        }

        /// <summary>
        /// 从OpenList中寻找指定位置点的ANode
        /// </summary>
        ANode GetNodeOfOpenList(int x,int y) {
            if (openList == null || openList.Count == 0) return null;
            ANode node = null;
            for (int i = openList.Count - 1; i >= 0; i--)
            {
                node = openList[i];
                if (x == node.x && y == node.y) return node;
            }
            return null;
        }

        /// <summary>
        /// CloseList中是否包含指定位置点的ANode
        /// </summary>
        bool HasNodeOfCloseList(int x, int y) {
            if (closeList == null || closeList.Count == 0) return false;
            ANode node = null;
            for (int i = closeList.Count - 1; i >= 0; i--)
            {
                node = closeList[i];
                if (x == node.x && y == node.y) return true;
            }
            return false;
        }

        /// <summary>
        /// OpenList中是否包含指定位置点的ANode
        /// </summary>
        bool HasNodeOfOpenList(int x, int y)
        {
            if (openList == null || openList.Count == 0) return false;
            ANode node = null;
            for (int i = openList.Count - 1; i >= 0; i--)
            {
                node = openList[i];
                if (x == node.x && y == node.y) return true;
            }
            return false;
        }

        /// <summary>
        /// 从指定Node能否走到目标坐标
        /// </summary>
        /// <param name="begainNode">指定Node</param>
        /// <param name="endX">目标坐标X</param>
        /// <param name="endY">目标坐标Y</param>
        /// <returns></returns>
        bool CanWalk(ANode begainNode,int endX,int endY) {
            bool canWalk = onWalkNode == null ? true : onWalkNode(endX,endY);
            if (canWalk)
            {
                int disX = Math.Abs(begainNode.x-endX);
                int disY = Math.Abs(begainNode.y-endY);
                int dis = disX + disY;
                if (dis < 2) canWalk = true;
                else if (dis == 2)
                {
                    if (canCorner) canWalk = disX == disY;
                    else canWalk = false;
                }
                else if (dis > 2) canWalk = false;
            }
            return canWalk;
        }

    }
}

使用例

namespace S
{
    class Program
    {
        static void Main(string[] args)
        {
            AStar aStar = new AStar().OnWalkNode(WalkNode);
            ANode node=aStar.GetPath(new ANode(2,2),new ANode(6,0),false);
            while (node!=null)
            {
                Console.WriteLine(node.x + "," + node.y);
                node = node.priviour;
            }
            
            Console.ReadKey();
        }

        static bool WalkNode(int x,int y) {
            if (x < 0 || x > 6) return false;
            if (y < 0 || y > 6) return false;
            if (x == 3 && y == 0) return false;
            if (x == 3 && y == 1) return false;
            if (x == 3 && y == 2) return false;
            if (x == 3 && y == 3) return false;
            if (x == 3 && y == 4) return false;
            if (x == 3 && y == 5) return false;
           // if (x == 3 && y == 6) return false;
            return true;
        }
    }
}

难点

public AStar OnWalkNode(Func<int, int, bool> onWalkNode)
        {
            this.onWalkNode = onWalkNode;
            return this;
        }

这个写法的返回值是为了干什么呢？

答：
这个方法是定义了一个公共的 AStar 类的方法，它的作用是注册位置点的可走状态。它的参数是一个委托，也就是一个函数指针，它接受两个整数作为位置点的坐标，返回一个布尔值表示是否可走。这个方法将这个委托赋值给 AStar 类的一个字段 onWalkNode，然后返回 AStar 类的实例本身，以便于链式调用。例如：

AStar astar = new AStar(); astar.OnWalkNode((x, y) => x > 0 && y > 0).FindPath(…);

如果觉得文章对你有用，请随意赞赏

A星寻路算法

http://www.klned.com/archives/1694273131012

作者

Zhang

发布于

2023-09-09

更新于

2023-09-11

许可协议

CC BY 4.0