[游戏开发]A*算法在Unity中的实现

一、A*算法是什么

?? A星算法是一种搜索策略，是一种启发式图搜索策略。不同于深度优先搜索或广度优先搜索等盲目搜索策略，它能够利用与问题有关的启发信息进行搜索。和迪杰斯特拉算法类似，它们之所以是启发式的，是因为融入了人们既嗤之以鼻又甘之如饴的思想：“贪心”。
?? 为什么说是“贪心”的呢？是因为每次扩展节点的时候都尽可能的选择路径最短的节点，而Dijkstra算法更看重的是已扩展的节点到起点的路径最短，而A星算法兼顾已扩展节点到起点的路径最短和到终点的路径最短，所以说A星算法应该可以说更高级一点。
?? 如何记录已扩展节点到起点的路径和已扩展节点到终点的路径呢？A星算法的每个节点通过G(n)和H(n)分别记录到起点的花销和到终点的最佳路径的估计代价，两者的和F(n)便是这个节点的估价函数——估价函数也就是该节点到终点的最小代价的估计值，是我们评判某一个节点优越与否的唯一参考标准。
?? A星算法一定就是最好的吗？我们定义H*(n)是某个节点到终点的最优路径的代价，即真实的代价，而非估计值，且有H(n)≤H*(n)恒成立。我觉得某人写的A星算法的程序好与不好，主要看H(n)跟H*(n)是否足够接近，如果H(n)=H*(n)的话，我们就不会扩展任何无关的节点，那么这个算法就绝对是最好的。但我们接下来的算法使用节点到终点的对角距离当作H(n)的，所以是会扩展一些不必要的节点的。但瘦死的骆驼比马大，肯定比宽度优先搜索和深度优先搜索还是要快的。

二、为什么要在Unity中用A*

?? 如果只是用Vector2.MoveTowards，或者只是用transform.position+=方向向量×速度×Time.deltaTime的话，那么这种怪的AI就有点太蠢了，一不会绕开障碍，二只会往主角脸上突。如果一种两种怪的AI是这样那么还可以，如果所有怪的AI都是这种单调乏味的移动方式，那么玩家就会感到疲劳。

这两只怪只能隔着障碍喷我

?? 想象一下，如果有怪物绕开了障碍物跑到你旁边给你来个背刺，是不是游戏难度一下就加大了？各位高级玩家是不是立马就兴奋起来了♂？
?? 当然，A星算法在游戏中的应用远远不止这些，欢迎大家来补充。

三、代码实现

?? 废话说了很多，还是直接上代码吧。我这个程序呢是参考了一个YouTube博主的视频的，大家如果感兴趣的话可以去看那个博主的视频学习。贴一下网址：
https://www.youtube.com/watch?v=alU04hvz6L4

1.创建节点类

public class Node
{
    private Grid<Node> grid;
    public int gridX;
    public int gridY;
    public int gCost;
    public int hCost;
    public bool isBarrier;
    public Node cameFromNode;
    public int FCost { get { return gCost + hCost; } }
    public Node(Grid<Node> _grid,int x,int y)
    {
        this.grid = _grid;
        this.gridX = x;
        this.gridY = y;
        isBarrier = false;
    }
    public void SetIsBarrier(bool _isBarrier)
    {
        this.isBarrier = _isBarrier;
        grid.TriggerGridObjectChanged(gridX, gridY);
    }
}

?? 解释一下：每个节点有我们之前说的估价函数h(n)节点与起点的实际代价g(n)，F(n)直接设一个getter返回它俩的和就好了。
?? gridX和gridY是该节点在网格中的位置，我们节点的位置并不是用的World Position，而是一个非负的整型，就像下图这样，左下角的坐标是[0,0]，往右x加一，往上y加一，以此类推。

?? cameFrom节点很重要，也就是它的父节点，通过这个节点一直向上回溯才能找到我们最终要走的路。
?? isBarrier这个布尔值用来记录该节点是不是有障碍物，有障碍物的话直接放到closed表里就不管它了。不是的话再考虑放到open表里扩展。

2.创建网格类

public class Grid<T>
{
    
    public event EventHandler<OnGridValueChangedEventArgs> OnGridValueChanged;
    public class OnGridValueChangedEventArgs:EventArgs
    {
        public int x;
        public int y;
    }
    private int width;
    private int height;
    private T[,] gridArray;//创建一个二维数组用来存储网格的每一个节点，大小为网格长度乘以网格宽度
    private float cellSize;
    private Vector3 originPosition;
    public Grid(int _width, int _height,float _cellSize,Vector3 _originPosition,Func<Grid<T>,int,int,T> _createGridObject)
    {
        this.width = _width;
        this.height = _height;
        this.cellSize = _cellSize;
        this.originPosition = _originPosition;
        gridArray = new T[this.width, this.height];
        for (int x = 0; x < width; x++)
        {
            for (int y = 0; y < height; y++)
            {
                gridArray[x, y] = _createGridObject(this,x,y);
                Debug.DrawLine(GetWorldPosition(x, y), GetWorldPosition(x, y + 1));
                Debug.DrawLine(GetWorldPosition(x, y), GetWorldPosition(x + 1, y));
            }
        }
        Debug.DrawLine(GetWorldPosition(width, 0), GetWorldPosition(width, height));
        Debug.DrawLine(GetWorldPosition(0, height), GetWorldPosition(width, height));
    }
    public int GetWidth()
    {
        return this.width;
    }
    public int GetHeight()
    {
        return this.height;
    }
    public float GetCellSize()
    {
        return this.cellSize;
    }
    public T[,] GetGridArray()
    {
        return this.gridArray;
    }
    public Vector3 GetOriginPosition()
    {
        return this.originPosition;
    }

    private Vector3 GetWorldPosition(int x,int y)
    {
        return new Vector3(x, y) * cellSize+originPosition;
    }
    public Vector2 GetXY(Vector3 _worldPosition)
    {
        return new Vector2(_worldPosition.x - originPosition.x / cellSize,
            _worldPosition.y - originPosition.y /cellSize);
    }
    public void SetValue(int x, int y, T value)
    {
        if(x>=0 && y>=0 && x<width && y<height)
        {
            gridArray[x, y] = value;
            OnGridValueChanged?.Invoke(this, new OnGridValueChangedEventArgs { x = x, y = y });
        }
    }
    public void TriggerGridObjectChanged(int x,int y)
    {
        OnGridValueChanged?.Invoke(this, new OnGridValueChangedEventArgs { x = x, y = y });
    }
    public void SetValue(Vector3 _worldPosition, T value)
    {
        int x, y;
        x = Mathf.FloorToInt(GetXY(_worldPosition).x);
        y = Mathf.FloorToInt(GetXY(_worldPosition).y);
        SetValue(x, y, value);
    }
    public T GetValue(int x,int y)
    {
        if (x >= 0 && y >= 0 && x < width && y < height)
        {
            return gridArray[x, y];
        }
        else
        {
            return default;
        }
    }
    public T GetValue(Vector3 _worldPosition)
    {
        int x, y;
        x= Mathf.FloorToInt(GetXY(_worldPosition).x);
        y = Mathf.FloorToInt(GetXY(_worldPosition).y);
        return GetValue(x, y);
    }
}

??主要就是网格的初始化，World Position和网格坐标的转来转去，以及一些getter和setter。

3.PathFinding核心代码

public class PathFinding
{
    private const int MOVE_STRAIGHT_COST=10;
    private const int MOVE_DIAGONAL_COST = 14;//本A*算法使用对角距离
    private List<Node> openList;
    private List<Node> closedList;
    public static PathFinding Instance { get; private set; }
    public Grid<Node> Grid { get; set; }
    public Node GetNode(int x, int y)
    {
        return Grid.GetValue(x, y);
    }
    public PathFinding(string sceneName)
    {
        Instance = this;
        Vector3 barrierGridPosition = Vector3.zero;
        switch (sceneName)
        {
            case "Hell_Mid":
                Grid = new Grid<Node>(13, 12, 1, new Vector3(-3, -8, 0), (Grid<Node> g, int x, int y) => new Node(g, x, y));
                break;
        }
        
    }
    public List<Vector3> FindPath(Vector3 _startWorldPosition,Vector3 _endWorldPosition)
    {
        Vector2 startPosition=Grid.GetXY(_startWorldPosition);
        Vector2 endPosition=Grid.GetXY(_endWorldPosition);
        List<Node> path = FindPath(Mathf.FloorToInt(startPosition.x), Mathf.FloorToInt(startPosition.y), 
            Mathf.FloorToInt(endPosition.x), Mathf.FloorToInt(endPosition.y));
        if(path==null)
        {
            return null;
        }else
        {
            List<Vector3> worldPath=new List<Vector3>{ };
            foreach(Node node in path)
            {
                worldPath.Add(Grid.GetOriginPosition()+new Vector3(node.gridX, node.gridY) * Grid.GetCellSize() + new Vector3(1, 1, 0) * Grid.GetCellSize() * .5f);
            }
            return worldPath;
        }
    }
    public List<Node> FindPath(int _startX,int _startY,int _endX,int _endY)
    {
        Node startNode = Grid.GetValue(_startX, _startY);//定义起始节点，起始节点将作为Open表中的第一个元素
        Node endNode = Grid.GetValue(_endX, _endY);
        openList = new List<Node> { startNode};
        closedList = new List<Node>();
        #region
        //初始化所有节点，让每个节点的gCost设为无穷大，前一节点设为空值
        for(int x=0;x<Grid.GetWidth();x++)
        {
            for(int y=0;y<Grid.GetHeight();y++)
            {
                Node node = Grid.GetValue(x,y);
                node.gCost = int.MaxValue;
                node.cameFromNode = null;
            }
        }
        #endregion
        startNode.gCost = 0;
        startNode.hCost = CaculateDistanceCost(startNode, endNode);
        while(openList.Count>0)
        {
            SortList();
            Node currentNode = openList[0];
            if (currentNode==endNode)
            {
            	openList.Remove(currentNode);
                closedList.Add(currentNode);
                return CaculatePath(currentNode);
            }
            else
            {
                openList.Remove(currentNode);
                closedList.Add(currentNode);
                foreach (Node neighbourNode in GetNeighbourList(currentNode))
                {
                    if (closedList.Contains(neighbourNode)) continue;
                    if(neighbourNode.isBarrier)
                    {
                        closedList.Add(neighbourNode);
                        continue;
                    }
                    int tentativeGCost = currentNode.gCost + CaculateDistanceCost(currentNode, neighbourNode);
                    if(tentativeGCost<neighbourNode.gCost)
                    {
                        neighbourNode.cameFromNode = currentNode;
                        neighbourNode.gCost = tentativeGCost;
                        neighbourNode.hCost = CaculateDistanceCost(neighbourNode, endNode);
                        if(!openList.Contains(neighbourNode))
                        {
                            openList.Add(neighbourNode);
                        }
                    }
                }
            }
        }
        return null;
    }
    private List<Node> GetNeighbourList(Node _currentNode)
    {
        List<Node> neighbourList = new List<Node> { };
        if((_currentNode.gridX-1)>=0)
        {
            neighbourList.Add(GetNode(_currentNode.gridX - 1, _currentNode.gridY));//左邻居
            if((_currentNode.gridY-1)>=0)
            {
                neighbourList.Add(GetNode(_currentNode.gridX - 1, _currentNode.gridY - 1));//左下邻居
            }
            if((_currentNode.gridY+1)<Grid.GetHeight())
            {
                neighbourList.Add(GetNode(_currentNode.gridX - 1, _currentNode.gridY + 1));//左上邻居
            }
        }
        if((_currentNode.gridX+1)<Grid.GetWidth())
        {
            neighbourList.Add(GetNode(_currentNode.gridX + 1, _currentNode.gridY));//右邻居
            if((_currentNode.gridY-1)>=0)
            {
                neighbourList.Add(GetNode(_currentNode.gridX + 1, _currentNode.gridY - 1));//右下邻居
            }
            if((_currentNode.gridY+1)<Grid.GetHeight())
            {
                neighbourList.Add(GetNode(_currentNode.gridX + 1, _currentNode.gridY + 1));//右上邻居
            }
        }
        if((_currentNode.gridY-1)>=0)
        {
            neighbourList.Add(GetNode(_currentNode.gridX, _currentNode.gridY - 1));//下邻居
        }
        if((_currentNode.gridY+1)<Grid.GetHeight())
        {
            neighbourList.Add(GetNode(_currentNode.gridX, _currentNode.gridY + 1));//上邻居
        }
        return neighbourList;
    }
    private List<Node> CaculatePath(Node node)
    {
        List<Node> path = new List<Node>();
        path.Add(node);
        Node currentNode = node;
        while(currentNode.cameFromNode!=null)
        {
            path.Add(currentNode.cameFromNode);
            currentNode = currentNode.cameFromNode;
        }
        path.Reverse();
        return path;
    }
    private int CaculateDistanceCost(Node a,Node b)
    {
        int distanceX = Mathf.Abs(a.gridX - b.gridX);
        int distanceY = Mathf.Abs(a.gridY - b.gridY);
        int remaining = Mathf.Abs(distanceX - distanceY);
        return MOVE_DIAGONAL_COST * Mathf.Min(distanceX, distanceY) + MOVE_STRAIGHT_COST * remaining;
    }
    private void SortList()
    {
        for(int i=0;i<this.openList.Count-1;i++)
        {
            int lowestIndex = i;
            for(int j=this.openList.Count-1;j<i;j--)
            {
                if(this.openList[j].FCost<this.openList[lowestIndex].FCost)
                {
                    lowestIndex = j;
                }
            }
            Node tempNode = this.openList[lowestIndex];
            this.openList[lowestIndex] = this.openList[i];
            this.openList[i] = tempNode;
        }
    }
}

?? 真正的PathFinding核心实现代码。首先从头开始看，上面说过我们使用的是对角距离，那么我们就定义两个常数，两节点的对角距离是14（√2的十倍），直线距离是10，先定义，后续会用到。open表和closed表，我觉得这个不用多说。
?? 构造函数，这个自己随意，我的程序是通过传一个场景名称的参数，来实现不同的场景建立不同的网格。
?? 先从第二个FindPath方法看起，根据A星算法，我们首先要知道我们的起始节点和目的节点，这四个参数分别是初始节点在网格里的坐标和目的节点在网格里的坐标。先把初始节点不由分说地扔进open表里，下面来初始化网格里的每个节点，注意初始化的是节点而不是网格，网格已经初始化了。
?? while循环里的判断条件是open表是否为空，若为空则搜索失败。我们通过选择排序把FCost最小的节点放在open表的首位，即重排open表。首先判断一下open表的第一个节点N是否是目标节点，是的话则搜索成功。否则的话将N移出open表里，扔到closed表里，然后试图去扩展N，即找它的邻居，它的邻居都有谁呢？无非是八个：上面的、下面的、左面的、右面的、左上的、左下的、右上的、右下的。
?? 遍历邻居，两个之前提到过的判断，判断该节点是否在closed表里，是否是障碍。
?? 注意注意！下面这个if语句就比较重要了。

if(tentativeGCost<neighbourNode.gCost)
                    {
                        neighbourNode.cameFromNode = currentNode;
                        neighbourNode.gCost = tentativeGCost;
                        neighbourNode.hCost = CaculateDistanceCost(neighbourNode, endNode);
                        if(!openList.Contains(neighbourNode))
                        {
                            openList.Add(neighbourNode);
                        }
                    }

?? 如果新扩展的邻居节点有N的先辈节点，那么我们需要判断一下走当前N走的这条路代价小还是之前的代价小，比较一下新先辈节点节点的g(n)和老先辈节点节点的g(n)。也就是说我们的open表里面有可能已经存在这些新扩展的邻居节点了，我们需要更新它们的值，如何更新呢？就是通过选F(n)小的路径走。用个不恰当的比喻，N生的子节点可能是它的祖宗，到底用哪个当N的祖宗呢？F(n)小的当它的祖宗，现在不都是说小祖宗小祖宗嘛，估计就是这么来的:)。

public List<Vector3> FindPath(Vector3 _startWorldPosition,Vector3 _endWorldPosition)

?? 第一个FindPath方法是传入World Position的起点和终点，转换成网格里的起点和终点，调用第二个FindPath方法，返回类型为Vector3的World Position路径，方便我们直接使用。

private List<Node> GetNeighbourList(Node _currentNode)

?? 找邻居的代码我就不再解释了，非常的简单，无非是if套if。

private List<Node> CaculatePath(Node node)

?? CaculatePath方法，一路找爹，找目标节点的爹，找目标节点的爹的爹……直到找到没有爹的起始节点。

private int CaculateDistanceCost(Node a,Node b)

?? 感觉这个算距离的方法比较有意思，总共有几个对角距离14和几个直线距离10呢？先算出两节点的x坐标的距离和y坐标的距离，具体如下。

int distanceX = Mathf.Abs(a.gridX - b.gridX);
int distanceY = Mathf.Abs(a.gridY - b.gridY);

?? 然后呢？我们看x的距离能和y的距离能抵消几个。假如说x距离是5，y距离是3，那就说是抵消3个；假如说x距离是3，y距离是1，那就说是抵消1个。被抵消的走对角线，剩下的走直线，不难发现，被抵消的总是x和y里的最小值，剩下的就是它们的差了！记得加上绝对值。

4.物体运动脚本EnemyPathFinding

?? 不能跑的代码说得再天花乱坠也没用，让它跑起来吧！

public class EnemyPathFinding : MonoBehaviour
{
    private int currentPathIndex;
    private List<Vector3> pathVectorList;
    private PathFinding pathFinding;
    private GameObject target;
    private Grid<Node> grid;
    [SerializeField]private float moveSpeed;
    void Awake()
    {
        pathVectorList = new List<Vector3> { };
        pathFinding = new PathFinding(SceneManager.GetActiveScene().name);
        target = GameObject.FindGameObjectWithTag("Player");
    }
    // Start is called before the first frame update
    void Start()
    {
        SetTargetPosition(target.transform.position);
    }

    // Update is called once per frame
    void FixedUpdate()
    {
        HandleMovement();
    }
    public void SetTargetPosition(Vector3 targetPosition)
    {
        currentPathIndex = 0;
        pathVectorList = PathFinding.Instance.FindPath(transform.position, targetPosition);
        if(pathVectorList!=null && pathVectorList.Count>1)
        {
            pathVectorList.RemoveAt(0);
        }
    }
    private void HandleMovement()
    {
        if(pathVectorList!=null)
        {
            Vector3 targetPosition = pathVectorList[currentPathIndex];
            if (Vector3.Distance(transform.position,targetPosition)>=0.1f)
            {
                Debug.DrawLine(transform.position, targetPosition);
                Vector3 moveDir = (targetPosition - transform.position).normalized;
                float distanceBefore = Vector3.Distance(transform.position, targetPosition);
                transform.position = transform.position + moveDir * moveSpeed * Time.deltaTime;
            }else
            {
                currentPathIndex++;
                if(currentPathIndex>=pathVectorList.Count)
                {
                    StopMoving();
                }
            }
        }else
        {
            StartCoroutine(FindTarget());
        }
        
    }
    private void StopMoving()
    {
        pathVectorList = null;
    }
    IEnumerator FindTarget()
    {
        yield return new WaitForSeconds(1.5f);
        SetTargetPosition(target.transform.position);
    }
}

?? 这个我不再解释了，还是要根据个人的工程去写代码吧。就是有个小提醒，不要把寻路的代码写到Update里面了，每一帧都寻路，CPU和内存多少有点蚌埠住。我用的是协程，大家可以按自己的喜好来。

四、运行、测试

?? 终于到了我们最爱的测试阶段了，我没有合适的东西能跑，就让一块儿肉去追我们的主角吧！

?? 看起来这块儿肉绕开了墙壁和障碍！很不错！
?? 接下来大家就可以尽情地发挥，让这块儿肉灵活走位，然后背刺我们的主角啦！

?? 还是让它收了神通吧。

五、总结

这里对文章进行总结：
A星算法在游戏中的应用非常广泛，很多游戏都有自己独特的寻路算法，比如说玩MOBA游戏的时候，玩家只需要单击右键，角色就会自动往目标去走，而且路径在地图上也画得清清楚楚；玩吃鸡的时候，总有一些电脑人，它们能穿越千山万水找到你，然后点爆你的一级头。以上只是一个比较基础的算法，通过C#写脚本，在Unity中运行。我关于障碍判断的算法还是比较蠢的，欢迎大家给我指正。
人工智能在游戏中的应用能够大大地增加游戏的趣味性，当一个NPC的行为非常接近真人，或者非常诡谲的时候，我们便会不由自主地沉浸其中想要探索它的奥秘，因此玩家对手的代理的控制逻辑要尽量复杂些才更好。但这些复杂的逻辑不是一蹴而就的，要像搭积木一样一步一步地尝试，才能建造一整幢大楼。