A*寻路算法学习和Unity实现

首先贴一下大佬博客，我的就是照着大佬做的

https://www.cnblogs.com/yangyxd/articles/5447889.html

1.      首先，去理解一下A*算法的原理，这里的话就先借用一下大佬的图

图上有什么，黑方块，白方块，蜘蛛，人，和问号，白方块嘛，能走的区域，黑方块不能走的区域，蜘蛛，起始点，人，最终点，那么我们的A*算法是个什么逻辑呢？寻找周围的8个点（当然这是砖块游戏，很多时候我们可能也是事先规划好的路径点），然后每次移动到一个点，都会计算当前的cost，cost由这个，也就是f,g,h来决定你的消耗，我们每次移动到cost较小的点再计算消耗值

对于这个问题的话给出了三种算法去实现，第一种曼哈顿算法，就是笔直走，到和重点同一水平线的时候再笔直走

第二种的话 几何算法，计算两点直线距离给出估价因子，走路的话就是对角线走法

第三种的话是对角算法，会先一直对角线走直到走到同一水平，就开始直线走

下面是模仿大佬的例子，很显然，通过这个办法，我们确实计算出了两个点之间的路径，当然，目前这种测试还只是在这种规定了像素点的，后续还可不可以用，这个还需要思考

然后的话，我讲一下我对代码的理解吧，贴一下代码

using UnityEngine;

using System.Collections;

using System.Collections.Generic;

 

 

  public  classGrid:MonoBehaviour

  {

    public GameObjectNodeWall;

    public GameObjectNode;

 

    //节点半径

    publicfloat NodeRadius = 0.5f;

    //过滤墙体所在的层

    public LayerMaskWhatLayer ;

    //玩家

    public Transformplayer;

    //目标

    public TransformdestPos;

    publicclassNodeItem

    {

        //这里的f,g,h都是用来计算代价的

        ///寻路节点

        //是否是障碍物   

        publicbool isWall;

        //位置

        public Vector3 pos;

        //格子坐标

        publicint x, y;

        //与起点的长度

        publicint gCost;

        //与目标点的长度

        publicint hCost;

        //总的路径长度

        publicint fCost

        {

            get { return gCost + hCost; }

        }

        //父节点就是当前节点了，一个节点移动到另一个节点往往是拿周围的八个节点说事

        public NodeItem parent;

        public NodeItem(bool isWall, Vector3 pos, int x, int y)

        {

            this.isWall = isWall;

            this.pos = pos;

            this.x = x;

            this.y = y;

        }

    }

    //存放子节点的二维数组

    private NodeItem[,]grid;

    privateint w, h;

    //路径和墙体

    private GameObjectWallRange, PathRange;

    privateList<GameObject> pathObj = newList<GameObject>();

 

 

    void Awake()

    {

        //初始化格子

        w =Mathf.RoundToInt(transform.localScale.x * 2);

        h =Mathf.RoundToInt(transform.localScale.y * 2);

        grid = new NodeItem[w, h];

        //新建两个物体，路径格子和墙体格子

        WallRange = new GameObject("WallRange");

        PathRange = new GameObject("PathRange");

        //把墙体的信息写入格子中

        for (int x = 0; x < w; x++)

        {

            for (int y = 0; y < h; y++)

            {

                Vector3 pos = new Vector3(x * 0.5f, y * 0.5f, -0.25f);

                //射线检测是不是墙体

                bool isWall = Physics.CheckSphere(pos, NodeRadius, WhatLayer);

                //构建一个节点

                grid[x, y] = new NodeItem(isWall, pos, x, y);

                //如果是墙体，则画出不可行走区域

                if (isWall)

                {

                    GameObject obj =GameObject.Instantiate(NodeWall, pos, Quaternion.identity) as GameObject;

                    obj.transform.SetParent(WallRange.transform);

                }

 

 

            }

        }

 

 

 

    }

    //这个是根据坐标得到一个节点，节点的作用也是用来计算权值的

    public NodeItemgetItem(Vector3 position)

    {

        int x = Mathf.RoundToInt(position.x) * 2;

        int y = Mathf.RoundToInt(position.y) * 2;

        x = Mathf.Clamp(x, 0, w - 1);

        y = Mathf.Clamp(y, 0, h - 1);

        return grid[x, y];

    }

    //取得周围的节点,也就是除自身以外的8个点了

    publicList<NodeItem> getNeibourhood(NodeItem node)

    {

        List<NodeItem> list = new List<NodeItem>();

        for (int i=-1; i<=1 ; i++)

        {

            for (int j =-1; j <=1 ; j++)

            {

                //如果是自身节点，则跳过

                if (i == 0 && j == 0)

                {

                    continue;

                }

                int x = node.x + i;

                int y = node.y + j;

                //判断是否越界，如果没有，加到列表中

                if (x < w && x >= 0 && y < h && y >= 0)

                {

                    list.Add(grid[x, y]);

                }

 

            }

        }

        return list;

    }

    //更新路径

    publicvoid updatePath(List<NodeItem> lines)

    {

        int curListSize = pathObj.Count;

        for (int i = 0,max=lines.Count; i<max;i++)

        {

            //这个在没有初始路径的时候肯定会被跳过了，如果有节点的话我们就更新路径并且重新设置active

            if (i < curListSize)

            {

                pathObj[i].transform.position =lines[i].pos;

                pathObj[i].SetActive(true);

            }

            //没有初始路径的话我们就在0号也就是第一个节点位置生成物体，并且设置在PathRange父物体下,然后添加到list里

            else

            {

                GameObject obj =GameObject.Instantiate(Node, lines[i].pos, Quaternion.identity) as GameObject;

               obj.transform.SetParent(PathRange.transform);

                pathObj.Add(obj);

            }

        }

    }

    //然后这里再给出我们的寻路算法,这里的返回值就是代价

    intgetDistanceNodes(Grid.NodeItem a,Grid.NodeItem b)

    {

        int cntX = Mathf.Abs(a.x - b.x);

        int cntY = Mathf.Abs(a.y - b.y);

        //判断到底是哪个轴相差的距离更远,实际上，为了简化操作，我们将代价*10变成了整数

        if (cntX > cntY)

        {

            return 14 * cntY + 10 * (cntY - cntX);

        }

        else

        {

            return 14 * cntX + 10 * (cntY - cntX);

        }

    }

 

}

好了，上面是代码，各位嘛可看可不看，当然想复刻的话自然是可以原班放Unity里去测试，这里的话我整体写下来，核心就是感觉A*的核心思路就是两个，理解了两个感觉不看上面代码也是可以的，第一，通过起始点和结束点计算确定在每个格子的估价，假设我在起始点，我望向周围八个点，我把它们全部获取到然后遍历一遍看看哪个的代价最低，这里代价用上面的getDistance就可以轻松计算出来了，也就是我们上面提到的对角算法，当然这里为了简化用了math函数将点都变成整数点

 

然后我走到一个点，我肯定就该思考我该怎么走了，这里的话首先我们将走过的点给加入一个list，每次走的时候我们都要判断得到的点是不是墙和走过的点，所谓好马不吃回头草，剔除掉走过的点，再遍历，再加入，再走，重复这样的操作，我们就获得了所有的路径点，接下来的话如果要寻路，沿着这条路走就对了

这里的话就是我照着大佬的复刻的了，红色区域的话是画出的不可行走的区域，位置的话是由射线检测的来决定的，当然要注意忽视墙体本身所在的层，还有一部分的话是我们的寻路算法实现，注释很详细，我就贴出来了，当然还是一点，这里只是学习笔记，看大佬博客更靠谱，我就不发工程了，因为还有一些地图细节设置，虽然无关紧要但是赘述也很麻烦，大家自行前往看，这里的话也是我人工智能学习的第一步，希望未来我的游戏能够更加智能，更加好玩

using UnityEngine;

using System.Collections;

using System.Collections.Generic;

 

publicclassFindPath : MonoBehaviour {

         private Grid grid;

 

         // Use this for initialization

         void Start () {

                   grid =GetComponent<Grid> ();

         }

        

         // Update is called once per frame

         void Update () {

                   FindingPath(grid.player.position, grid.destPos.position);

         }

 

         // A*寻路

         void FindingPath(Vector3 s, Vector3 e) {

                   Grid.NodeItem startNode =grid.getItem (s);

                   Grid.NodeItem endNode =grid.getItem (e);

 

                   List<Grid.NodeItem>openSet = new List<Grid.NodeItem> ();

                   HashSet<Grid.NodeItem>closeSet = new HashSet<Grid.NodeItem> ();

                   openSet.Add (startNode);

 

                   while (openSet.Count > 0) {

                            Grid.NodeItemcurNode = openSet [0];

 

                            for (int i = 0, max = openSet.Count;i < max; i++) {

                                     if (openSet [i].fCost <= curNode.fCost&&

                                         openSet [i].hCost < curNode.hCost) {

                                               curNode= openSet [i];

                                     }

                            }

 

                            openSet.Remove(curNode);

                            closeSet.Add(curNode);

 

                            // 找到的目标节点

                            if (curNode == endNode) {

                                     generatePath(startNode, endNode);

                                     return;

                            }

 

                            // 判断周围节点，选择一个最优的节点

                            foreach (var item in grid.getNeibourhood(curNode)) {

                                     // 如果是墙或者已经在关闭列表中

                                     if (item.isWall || closeSet.Contains (item))

                                               continue;

                                     // 计算当前相领节点现开始节点距离

                                     int newCost = curNode.gCost + getDistanceNodes(curNode, item);

                                     // 如果距离更小，或者原来不在开始列表中

                                     if (newCost < item.gCost ||!openSet.Contains (item)) {

                                               // 更新与开始节点的距离

                                               item.gCost= newCost;

                                               // 更新与终点的距离

                                               item.hCost= getDistanceNodes (item, endNode);

                                               // 更新父节点为当前选定的节点

                                               item.parent= curNode;

                                               // 如果节点是新加入的，将它加入打开列表中

                                               if (!openSet.Contains (item)) {

                                                        openSet.Add(item);

                                               }

                                     }

                            }

                   }

 

                   generatePath (startNode, null);

         }

 

         // 生成路径

         void generatePath(Grid.NodeItem startNode, Grid.NodeItem endNode) {

                   List<Grid.NodeItem>path = new List<Grid.NodeItem>();

                   if (endNode != null) {

                            Grid.NodeItem temp =endNode;

                            while (temp != startNode) {

                                     path.Add(temp);

                                     temp =temp.parent;

                            }

                            // 反转路径

                            path.Reverse ();

                   }

                   // 更新路径

                   grid.updatePath(path);

         }

 

         // 获取两个节点之间的距离

         int getDistanceNodes(Grid.NodeItem a, Grid.NodeItem b) {

                   int cntX = Mathf.Abs (a.x - b.x);

                   int cntY = Mathf.Abs (a.y - b.y);

                   // 判断到底是那个轴相差的距离更远

                   if (cntX > cntY) {

                            return 14 * cntY + 10 * (cntX - cntY);

                   } else {

                            return 14 * cntX + 10 * (cntY - cntX);

                   }

         }

 

 

}