• Unity3D A* 寻路算法

    2017-05-15 14:31:29
    已出版书籍:《手把手教你架构3D游戏引擎》电子工业出版社和《Unity3D实战核心技术详解》电子工业出版社等。CSDN视频网址:http://edu.csdn.net/lecturer/144 A寻路算法通常是应用于大型网络游戏中,A*算法通常...

    笔者介绍:姜雪伟,IT公司技术合伙人,IT高级讲师,CSDN社区专家,特邀编辑,畅销书作者,国家专利发明人;已出版书籍:《手把手教你架构3D游戏引擎》电子工业出版社和《Unity3D实战核心技术详解》电子工业出版社等。

    CSDN视频网址:http://edu.csdn.net/lecturer/144

    A*寻路算法通常是应用于大型网络游戏中,A*算法通常应用在服务器中,在移动端游戏开发中,A*算法也可以在Unity端实现,下面给读者介绍一个插件A* PathFindingProject,它的下载地址:https://arongranberg.com/astar/download#,可以直接导入到Unity工程中,它目前支持直接寻路和网格寻路。在官网上有免费的版本和收费的版本,作为学习者可以下载免费的版本原理是一样的。下面通过它们提供的Demo,给读者介绍一下:

    在导入到Unity工程后,使用时首选建立一个空的GameObject,然后将AstarPath脚本挂接上去。如下图所示:


    这个AstarPath是整个A*寻路的核心组件,它计算了整个地面的寻路路径以及保存信息,它保存的是二进制文件格式,操作如下所示:

    该类提供了保存,加载等函数,详情可以查看类AstarPathEditor,函数接口如下所示:

    void DrawSerializationSettings () {
    			serializationSettingsArea.Begin();
    			GUILayout.BeginHorizontal();
    
    			if (GUILayout.Button("Save & Load", level0LabelStyle)) {
    				serializationSettingsArea.open = !serializationSettingsArea.open;
    			}
    
    			if (script.data.cacheStartup && script.data.file_cachedStartup != null) {
    				GUIUtilityx.PushTint(Color.yellow);
    				GUILayout.Label("Startup cached", thinHelpBox, GUILayout.Height(15));
    				GUILayout.Space(20);
    				GUIUtilityx.PopTint();
    			}
    
    			GUILayout.EndHorizontal();
    
    			// This displays the serialization settings
    			if (serializationSettingsArea.BeginFade()) {
    				script.data.cacheStartup = EditorGUILayout.Toggle(new GUIContent("Cache startup", "If enabled, will cache the graphs so they don't have to be scanned at startup"), script.data.cacheStartup);
    
    				script.data.file_cachedStartup = EditorGUILayout.ObjectField(script.data.file_cachedStartup, typeof(TextAsset), false) as TextAsset;
    
    				if (script.data.cacheStartup && script.data.file_cachedStartup == null) {
    					EditorGUILayout.HelpBox("No cache has been generated", MessageType.Error);
    				}
    
    				if (script.data.cacheStartup && script.data.file_cachedStartup != null) {
    					EditorGUILayout.HelpBox("All graph settings will be replaced with the ones from the cache when the game starts", MessageType.Info);
    				}
    
    				GUILayout.BeginHorizontal();
    
    				if (GUILayout.Button("Generate cache")) {
    					var serializationSettings = new Pathfinding.Serialization.SerializeSettings();
    					serializationSettings.nodes = true;
    
    					if (EditorUtility.DisplayDialog("Scan before generating cache?", "Do you want to scan the graphs before saving the cache.\n" +
    							"If the graphs have not been scanned then the cache may not contain node data and then the graphs will have to be scanned at startup anyway.", "Scan", "Don't scan")) {
    						MenuScan();
    					}
    
    					// Save graphs
    					var bytes = script.data.SerializeGraphs(serializationSettings);
    
    					// Store it in a file
    					script.data.file_cachedStartup = SaveGraphData(bytes, script.data.file_cachedStartup);
    					script.data.cacheStartup = true;
    				}
    
    				if (GUILayout.Button("Load from cache")) {
    					if (EditorUtility.DisplayDialog("Are you sure you want to load from cache?", "Are you sure you want to load graphs from the cache, this will replace your current graphs?", "Yes", "Cancel")) {
    						script.data.LoadFromCache();
    					}
    				}
    
    				GUILayout.EndHorizontal();
    
    				if (script.data.data_cachedStartup != null && script.data.data_cachedStartup.Length > 0) {
    					EditorGUILayout.HelpBox("Storing the cached starup data on the AstarPath object has been deprecated. It is now stored " +
    						"in a separate file.", MessageType.Error);
    
    					if (GUILayout.Button("Transfer cache data to separate file")) {
    						script.data.file_cachedStartup = SaveGraphData(script.data.data_cachedStartup);
    						script.data.data_cachedStartup = null;
    					}
    				}
    
    				GUILayout.Space(5);
    
    				GUILayout.BeginHorizontal();
    				if (GUILayout.Button("Save to file")) {
    					string path = EditorUtility.SaveFilePanel("Save Graphs", "", "graph.bytes", "bytes");
    
    					if (path != "") {
    						var serializationSettings = Pathfinding.Serialization.SerializeSettings.Settings;
    						if (EditorUtility.DisplayDialog("Include node data?", "Do you want to include node data in the save file. " +
    								"If node data is included the graph can be restored completely without having to scan it first.", "Include node data", "Only settings")) {
    							serializationSettings.nodes = true;
    						}
    
    						if (serializationSettings.nodes && EditorUtility.DisplayDialog("Scan before saving?", "Do you want to scan the graphs before saving? " +
    								"\nNot scanning can cause node data to be omitted from the file if the graph is not yet scanned.", "Scan", "Don't scan")) {
    							MenuScan();
    						}
    
    						uint checksum;
    						var bytes = SerializeGraphs(serializationSettings, out checksum);
    						Pathfinding.Serialization.AstarSerializer.SaveToFile(path, bytes);
    
    						EditorUtility.DisplayDialog("Done Saving", "Done saving graph data.", "Ok");
    					}
    				}
    
    				if (GUILayout.Button("Load from file")) {
    					string path = EditorUtility.OpenFilePanel("Load Graphs", "", "");
    
    					if (path != "") {
    						byte[] bytes;
    						try {
    							bytes = Pathfinding.Serialization.AstarSerializer.LoadFromFile(path);
    						} catch (System.Exception e) {
    							Debug.LogError("Could not load from file at '"+path+"'\n"+e);
    							bytes = null;
    						}
    
    						if (bytes != null) DeserializeGraphs(bytes);
    					}
    				}
    
    				GUILayout.EndHorizontal();
    			}
    
    			serializationSettingsArea.End();
    		}
    

    该函数调用了JsonSerializer类中的两个函数如下所示:

    		public static void SaveToFile (string path, byte[] data) {
    #if NETFX_CORE
    			throw new System.NotSupportedException("Cannot save to file on this platform");
    #else
    			using (var stream = new FileStream(path, FileMode.Create)) {
    				stream.Write(data, 0, data.Length);
    			}
    #endif
    		}
    
    		/** Load the specified data from the specified path */
    		public static byte[] LoadFromFile (string path) {
    #if NETFX_CORE
    			throw new System.NotSupportedException("Cannot load from file on this platform");
    #else
    			using (var stream = new FileStream(path, FileMode.Open)) {
    				var bytes = new byte[(int)stream.Length];
    				stream.Read(bytes, 0, (int)stream.Length);
    				return bytes;
    			}
    #endif
    		}

    场景通过AstarPath脚本布置完后,接下来开始寻路了,需要挂接如下的脚本:


    其中AI脚本是用于查询物体的,它会调用Seeker脚本中的函数,同时Seeker会对场景做一些标识操作,这样AI寻路基本完成,其中AI脚本是继承AIPath类,非常方便我们自己编写,扩展功能,它是通过递归的方式进行路径查询,锁定目标的,它运行的效果如下所示:






    展开全文
  • 这里我引用一篇文章来介绍A*算法文章内容如下 如图所示简易地图, 其中绿色方块的是起点 (用 A 表示), 中间蓝色的是障碍物, 红色的方块 (用 B 表示) 是目的地. 为了可以用一个二维数组来表示地图, 我们将地图...

    原文地址:blog.liujunliang.com.cn

    这里我先引用一篇详细文章来介绍A*算法

    本文源码链接:点击打开链接

    文章内容如下

    简易地图

     

    如图所示简易地图, 其中绿色方块的是起点 ( A 表示), 中间蓝色的是障碍物, 红色的方块 ( B 表示) 是目的地. 为了可以用一个二维数组来表示地图, 我们将地图划分成一个个的小方块.

    二维数组在游戏中的应用是很多的, 比如贪吃蛇和俄罗斯方块基本原理就是移动方块而已. 而大型

     游戏的地图, 则是将各种"地貌"铺在这样的小方块上.

    寻路步骤

    1. 从起点开始把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格

     的列表.

    2. 寻找起点周围可以到达的方格将它们放入"开启列表", 并设置它们的"父方格" A.

    3. 从"开启列表"中删除起点 A, 并将起点加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格

     

    图中浅绿色描边的方块表示已经加入 "开启列表" 等待检查. 淡蓝色描边的起点 A 表示已经放入

     "关闭列表" , 它不需要再执行检查.

    "开启列表" 中找出相对最靠谱的方块, 什么是最靠谱? 它们通过公式 F=G+H 来计算.

    F = G + H 

    G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动).

     H 表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以上下左右移动).


    我们假设横向移动一个格子的耗费为 10, 为了便于计算, 沿斜方向移动一个格子耗费是 14. 为了

    更直观的展示如何运算 FGH, 图中方块的左上角数字表示 F, 左下角表示 G, 右下角表示 H. 看看是否跟你心里想的结果一样?

    "开启列表" 中选择 F 值最低的方格 C (绿色起始方块 A 右边的方块), 然后对它进行如下处

    :

    4. 把它从 "开启列表" 中删除并放到 "关闭列表" .

    5. 检查它所有相邻并且可以到达 (障碍物和 "关闭列表" 的方格都不考虑的方格如果这些方格

    还不在 "开启列表" 里的话将它们加入 "开启列表", 计算这些方格的 G, H 值各是多少并设置它们的 "父方格"  C.

    6. 如果某个相邻方格 D 已经在 "开启列表" 里了, 检查如果用新的路径 (就是经过 C 的路径) 到达它的话, G 值是否会更低一些如果新的值更低那就把它的 "父方格" 改为目前选中的方格 C, 然后重新计算它的值和 (H 值不需要重新计算因为对于每个方块, H 值是不变的). 如果新的值比较高就说明经过再到达不是一个明智的选择因为它需要更远的路这时我们什么也不做.

     

    如图, 我们选中了 C 因为它的 F 值最小, 我们把它从 "开启列表" 中删除, 并把它加入 "关闭列表". 它右边上下三个都是墙, 所以不考虑它们. 它左边是起始方块, 已经加入到 "关闭列表" , 也不考虑. 所以它周围的候选方块就只剩下 4 . 让我们来看看 C 下面的那个格子, 它目前的 G  14, 

    果通过 C 到达它的话, G 将会是 10 + 10, 这比 14 要大, 因此我们什么也不做.

    然后我们继续从 "开启列表" 中找出 F 值最小的, 但我们发现 C 上面的和下面的同时为 54, 

    时怎么办呢? 这时随便取哪一个都行, 比如我们选择了 C 下面的那个方块 D.


    右边已经右上方的都是墙, 所以不考虑, 但为什么右下角的没有被加进 "开启列表" ? 

    因为如果 C 下面的那块也不可以走, 想要到达 C 右下角的方块就需要从 "方块的角" 走了, 在程序中设置是否允许这样走. (图中的示例不允许这样走)


    就这样, 我们从 "开启列表" 找出 F 值最小的, 将它从 "开启列表" 中移掉, 添加到 "关闭列表".

    再继续找出它周围可以到达的方块, 如此循环下去...

    那么什么时候停止呢? —— 当我们发现 "开始列表" 里出现了目标终点方块的时候, 说明路径已经

    被找到.

    如何找回路径


    如上图所示, 除了起始方块, 每一个曾经或者现在还在 "开启列表" 里的方块, 它都有一个 "父方块", 通过 "父方块" 可以索引到最初的 "起始方块", 这就是路径.

    Unity代码实现

    算法类

    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    
    public class AStarAlgorithm 
    {
        private const int mGridWidth = 20;    
        private const int mGridHeight = 10;
    
        //使用二维数组存储点网格    
        public AStarPoint[,] mPointGrid = new AStarPoint[mGridWidth,mGridHeight];
        //存储路径方格子
        public List<AStarPoint> mPathPosList = new List<AStarPoint>();
    
        private static AStarAlgorithm _instance;
        public static AStarAlgorithm GetInsatnce
        {
            get
            {
                if (_instance == null)
                {
                    _instance = new AStarAlgorithm();
                }
    
                return _instance;
            }
        }
    
        public AStarAlgorithm()
        {
            InitPoint();
        }
    
        //在网格上设置点的信息
        private void InitPoint()
        {
            for (int i = 0; i < mGridWidth; i++)
            {
                for (int j = 0; j < mGridHeight; j++)
                {                
                    mPointGrid[i, j] = new AStarPoint(i, j);
                }
            }
    
            //设置障碍物
            mPointGrid[4, 2].mIsObstacle = true;
            mPointGrid[4, 3].mIsObstacle = true;
            mPointGrid[4, 4].mIsObstacle = true;
            mPointGrid[4, 5].mIsObstacle = true;
            mPointGrid[4, 6].mIsObstacle = true;
    
            //显示障碍物
            for (int x = 0; x < mGridWidth; x++)
            {
                for (int y = 0; y < mGridHeight; y++)
                {
                    if (mPointGrid[x, y].mIsObstacle)
                    {
                        CreatePath(x, y, Color.blue);
                    }
                }
            }
        }
    
        public void ClearGrid()
        {
            for (int x = 0; x < mGridWidth; x++)
            {
                for (int y = 0; y < mGridHeight; y++)
                {
                    if (!mPointGrid[x, y].mIsObstacle)
                    {
                        if (mPointGrid[x, y].mGameObject != null)
                        {
                            GameObject.Destroy(mPointGrid[x, y].mGameObject);
                            mPointGrid[x, y].mGameObject = null;
    
                            //重新设置父节点
                            mPointGrid[x, y].mParentPoint = null;
                        }
                    }
                }
            }
        }
    
        //寻路
        public List<AStarPoint> FindPath(AStarPoint mStartPoint, AStarPoint mEndPoint)
        {
            if (mEndPoint.mIsObstacle || mStartPoint.mPosition == mEndPoint.mPosition)
            {
                return  null;
            }
    
            //开启列表
            List<AStarPoint> openPointList = new List<AStarPoint>();
            //关闭列表
            List<AStarPoint> closePointList = new List<AStarPoint>();
    
            openPointList.Add(mStartPoint);
    
            while (openPointList.Count > 0)
            {
                //寻找开启列表中最小预算值的表格
                AStarPoint minFPoint = FindPointWithMinF(openPointList);
                //将当前表格从开启列表移除 在关闭列表添加
                openPointList.Remove(minFPoint);
                closePointList.Add(minFPoint);
                //找到当前点周围的全部点
                List<AStarPoint> surroundPoints = FindSurroundPoint(minFPoint);            
                //在周围的点中,将关闭列表里的点移除掉
                SurroundPointsFilter(surroundPoints, closePointList);
                //寻路逻辑
                foreach (var surroundPoint in surroundPoints)
                {
                    if (openPointList.Contains(surroundPoint))
                    {
                        //计算下新路径下的G值(H值不变的,比较G相当于比较F值)
                        float newPathG = CalcG(surroundPoint, minFPoint);
                        if (newPathG < surroundPoint.mG)
                        {
                            surroundPoint.mG = newPathG;
                            surroundPoint.mF = surroundPoint.mG + surroundPoint.mH;
                            surroundPoint.mParentPoint = minFPoint;
                        }
                    }
                    else
                    {
                        //将点之间的
                        surroundPoint.mParentPoint = minFPoint;
                        CalcF(surroundPoint, mEndPoint);
                        openPointList.Add(surroundPoint);
                    }
                }
    
                //如果开始列表中包含了终点,说明找到路径
                if (openPointList.IndexOf(mEndPoint) > -1)
                {
                    break;
                }
            }
    
            return ShowPath(mStartPoint, mEndPoint);
        }
    
        private List<AStarPoint> ShowPath(AStarPoint start, AStarPoint end)
        {
            mPathPosList.Clear();
    
            AStarPoint temp = end;
            while (true)
            {
                mPathPosList.Add(temp);
    
                Color c = Color.white;
                if (temp == start)
                {
                    c = Color.green;
                }
                else if (temp == end)
                {
                    c = Color.red;
                }
                CreatePath(temp.mPositionX, temp.mPositionY, c);
    
                if (temp.mParentPoint == null)
                    break;
                temp = temp.mParentPoint;
            }
    
            return mPathPosList;
        }
    
        private void CreatePath(int x, int y, Color color)
        {
            GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
            go.transform.position = new Vector3(x, y, 0);
            go.GetComponent<Renderer>().material.color = color;
            go.transform.SetParent(GameObject.Find("Path").transform);
    
            if (mPointGrid[x, y].mGameObject != null)
            {
                GameObject.Destroy(mPointGrid[x, y].mGameObject);             
            }
            mPointGrid[x, y].mGameObject = go;
        }
    
        //寻找预计值最小的格子
        private AStarPoint FindPointWithMinF(List<AStarPoint> openPointList)
        {
            float f = float.MaxValue;
            AStarPoint temp = null;
            foreach (AStarPoint p in openPointList)
            {
                if (p.mF < f)
                {
                    temp = p;
                    f = p.mF;
                }
            }
            return temp;
        }
    
        //寻找周围的全部点
        private List<AStarPoint> FindSurroundPoint(AStarPoint point)
        {
            List<AStarPoint> list = new List<AStarPoint>();
    
            ////////////判断周围的八个点是否在网格内/////////////
            AStarPoint up = null, down = null, left = null, right = null;
            AStarPoint lu = null, ru = null, ld = null, rd = null;
            if (point.mPositionY < mGridHeight - 1)
            {
                up = mPointGrid[point.mPositionX, point.mPositionY + 1];
            }
            if (point.mPositionY > 0)
            {
                down = mPointGrid[point.mPositionX, point.mPositionY - 1];
            }
            if (point.mPositionX > 0)
            {
                left = mPointGrid[point.mPositionX - 1, point.mPositionY];
            }
            if (point.mPositionX < mGridWidth - 1)
            {
                right = mPointGrid[point.mPositionX + 1, point.mPositionY];
            }
            if (up != null && left != null)
            {
                lu = mPointGrid[point.mPositionX - 1, point.mPositionY + 1];
            }
            if (up != null && right != null)
            {
                ru = mPointGrid[point.mPositionX + 1, point.mPositionY + 1];
            }
            if (down != null && left != null)
            {
                ld = mPointGrid[point.mPositionX - 1, point.mPositionY - 1];
            }
            if (down != null && right != null)
            {
                rd = mPointGrid[point.mPositionX + 1, point.mPositionY - 1];
            }
            
    
            /////////////将可以经过的表格添加到开启列表中/////////////
            if (down != null && down.mIsObstacle == false)
            {
                list.Add(down);
            }
            if (up != null && up.mIsObstacle == false)
            {
                list.Add(up);
            }
            if (left != null && left.mIsObstacle == false)
            {
                list.Add(left);
            }
            if (right != null && right.mIsObstacle == false)
            {
                list.Add(right);
            }
            if (lu != null && lu.mIsObstacle == false && left.mIsObstacle == false && up.mIsObstacle == false)
            {
                list.Add(lu);
            }
            if (ld != null && ld.mIsObstacle == false && left.mIsObstacle == false && down.mIsObstacle == false)
            {
                list.Add(ld);
            }
            if (ru != null && ru.mIsObstacle == false && right.mIsObstacle == false && up.mIsObstacle == false)
            {
                list.Add(ru);
            }
            if (rd != null && rd.mIsObstacle == false && right.mIsObstacle == false && down.mIsObstacle == false)
            {
                list.Add(rd);
            }
    
            return list;
        }
    
        //将关闭带你从周围点列表中关闭
        private void SurroundPointsFilter(List<AStarPoint> surroundPoints, List<AStarPoint> closePoints)
        {
            foreach (var closePoint in closePoints)
            {
                if (surroundPoints.Contains(closePoint))
                {
                    Debug.Log("将关闭列表的点移除");
                    surroundPoints.Remove(closePoint);
                }
            }
        }
    
        //计算最小预算值点G值
        private float CalcG(AStarPoint surround, AStarPoint minFPoint)
        {
            return Vector3.Distance(surround.mPosition, minFPoint.mPosition) + minFPoint.mG;
        }
    
        //计算该点到终点的F值
        private void CalcF(AStarPoint now, AStarPoint end)
        {
            //F = G + H
            float h = Mathf.Abs(end.mPositionX - now.mPositionX) + Mathf.Abs(end.mPositionY - now.mPositionY);
            float g = 0;
            if (now.mParentPoint == null)
            {
                g = 0;
            }
            else
            {
                g = Vector2.Distance(new Vector2(now.mPositionX, now.mPositionY), new Vector2(now.mParentPoint.mPositionX, now.mParentPoint.mPositionY)) + now.mParentPoint.mG;
            }
            float f = g + h;
            now.mF = f;
            now.mG = g;
            now.mH = h;
        }
    }
    


    其中AStarPoint是存储点的信息(位置、父格子、实体对象)

    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    
    
    /// <summary>
    /// 存储寻路点信息
    /// </summary>
    public class AStarPoint
    {
        //父“格子”
        public AStarPoint mParentPoint { get; set; }
        //格子显示对象
        public GameObject mGameObject { get; set; }
    
        public float mF { get; set; }
        public float mG { get; set; }
        public float mH { get; set; }
        //点的位置
        public Vector2 mPosition { get; set; }
        public int mPositionX { get; set; }
        public int mPositionY { get; set; }
        //该点是否处于障碍物
        public bool mIsObstacle { get; set; }
    
        public AStarPoint(int positionX,int positionY)
        {
            this.mPositionX = positionX;
            this.mPositionY = positionY;
            this.mPosition = new Vector2(mPositionX, mPositionY);
            this.mParentPoint = null;
        }
    }
    


    寻路模拟

    创建一个DoPlayer测试类,用于模仿一个物体的寻路
    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    
    public class DoPlayer : MonoBehaviour
    {
        private GameObject mCubeParent;
    
        //存储路径点
        private List<AStarPoint> mPathPosList;
    
        //网格大小
        private const int mGridWidth = 20;
        private const int mGridHeight = 10;
    
        private AStarPoint[,] mPointGrid;
    
        private AStarPoint mStartPos;
        private AStarPoint mEndPos { get; set; }
    
        //每一秒发生位移
        private float mTime = 0.7f;
        private float mTimer = 0.0f;
    
        //目标点
        private int mTargetX { get; set; }
        private int mTargetY { get; set; }
    
        private void Start()
        {
            mCubeParent = GameObject.Find("Plane");
    
            mPointGrid = AStarAlgorithm.GetInsatnce.mPointGrid;
            mStartPos = mPointGrid[0, 0];
    
            InitBG();
        }
    
        private void Update()
        {
            mTimer += Time.deltaTime;
            if (mTimer >= mTime)
            {
                mTimer = 0;
                Walk();
            }
        }
    
        private void Walk()
        {     
            if (mPathPosList != null && mPathPosList.Count > 1)
            {
                mStartPos = mPathPosList[mPathPosList.Count - 1];
                Color color = mStartPos.mGameObject.GetComponent<Renderer>().material.color;
                mPathPosList.Remove(mStartPos);
                Destroy(mStartPos.mGameObject);
                mStartPos.mGameObject = null;
                
                mStartPos = mPathPosList[mPathPosList.Count - 1];
                mStartPos.mGameObject.GetComponent<Renderer>().material.color = color;
                
            }
        }
    
        private void InitBG()
        {
            for (int i = 0; i < mGridWidth; i++)
            {
                for (int j = 0; j < mGridHeight; j++)
                {
                    CreateCube(i, j, Color.gray);
                }
            }
        }
    
    
        private void CreateCube(int x, int y, Color color)
        {
            GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
            go.transform.SetParent(mCubeParent.transform);
            go.transform.position = new Vector3(x, y, 0);
            go.transform.localScale = new Vector3(0.9f, 0.9f, 0.9f);
            go.GetComponent<Renderer>().material.color = color;
    
            go.AddComponent<Cube>().FindPath = FindPath;
        }
    
        public void FindPath(int mTargetX, int mTargetY)
        {
            if (mPathPosList != null)
            {
                mPathPosList.Clear();
            }
            AStarAlgorithm.GetInsatnce.ClearGrid();
    
            //网格点对象重新刷新了  需要使用网格来索引到点 mPathPosList存储的点是之前的AStarPoint
            this.mEndPos = mPointGrid[mTargetX, mTargetY];
            this.mStartPos = mPointGrid[mStartPos.mPositionX, mStartPos.mPositionY];
    
            mPathPosList = AStarAlgorithm.GetInsatnce.FindPath(this.mStartPos, mEndPos);
        }
    }
    

    其中创建的Cube网格类代码如下
    using System.Collections;
    using System.Collections.Generic;
    using UnityEngine;
    
    public class Cube : MonoBehaviour
    {
        public delegate void VoidDelegate(int x, int y);
        public VoidDelegate FindPath;
    
        private void OnMouseDown()
        {
            if (FindPath != null)
            {
                FindPath((int)this.transform.position.x, (int)this.transform.position.y);
            }
        }
    }

    效果展示

    效果显示正常,绿色方块代表主角位置,红色方块代表目标点,白色方块代表路径




    原文地址:blog.liujunliang.com.cn


    展开全文
  • a*自动寻路算法详解

    2016-11-09 21:52:46
    A*算法主要是在父节点更新那个地方很容易误解,但是父节点的更新又是A*算法的核心,因为遍历到目标节点之后就是根据父节点回溯返回找到的路径的。 开始: 一只探路猫   让我们想象一下,有一款游戏,游戏中一只猫...

    这篇博文是在其他博客基础上加工的,主要原因是感觉原博客举得例子不太好,很多细节感觉没有描述。

    A*算法主要是在父节点更新那个地方很容易误解,但是父节点的更新又是A*算法的核心,因为遍历到目标节点之后就是根据父节点回溯返回找到的路径的。

    开始:

    一只探路猫

     

    让我们想象一下,有一款游戏,游戏中一只猫想要找到获取骨头的路线。

    为什么会有一只猫想要骨头?!你可能会这么想。在本游戏中,这是一只狡猾的猫,他想捡起骨头给狗,以防止被咬死!:]

    现在想像一下下图中的猫想找到到达骨头的最短路径:


    不幸的是,猫不能直接从它当前的位置走到骨头的位置,因为有面墙挡住了去路,而且它在游戏中不是一只幽灵猫!

    游戏中的猫同样懒惰,它总是想找到最短路径,这样当他回家看望它的女朋友时不会太累:-)

    但是我们如何编写一个算法计算出猫要选择的那条路径呢?A星算法拯救了我们!

     

    简化搜索区域

     

    寻路的第一步是简化成容易控制的搜索区域。

    怎么处理要根据游戏来决定了。例如,我们可以将搜索区域划分成像素点,但是这样的划分粒度对于我们这款基于方块的游戏来说太高了(没必要)。

    作为代替,我们使用方块(一个正方形)作为寻路算法的单元。其他的形状类型也是可能的(比如三角形或者六边形),但是正方形是最简单并且最适合我们需求的。

    像那样去划分,我们的搜索区域可以简单的用一个地图大小的二维数组去表示。所以如果是25*25方块大小的地图,我们的搜索区域将会是一个有625个正方形的数组。如果我们把地图划分成像素点,搜索区域就是一个有640000个正方形的数组了(一个方块是32*32像素)!

    现在让我们基于目前的区域,把区域划分成多个方块来代表搜索空间(在这个简单的例子中,7*6个方块 = 42个方块):

     

    OpenClosed列表

     

    既然我们创建了一个简单的搜索区域,我们来讨论下A星算法的工作原理吧。

    除了懒惰之外,我们的猫没有好的记忆力,所以它需要两个列表:

    1. 一个记录下所有被考虑来寻找最短路径的方块(称为open 列表)
    2. 一个记录下不会再被考虑的方块(成为closed列表)

    猫首先在closed列表中添加当前位置(我们把这个开始点称为点 “A”)。然后,把所有与它当前位置相邻的可通行小方块添加到open列表中。

    下图是猫在某一位置时的情景(绿色代表open列表):


    现在猫需要判断在这些选项中,哪项才是最短路径,但是它要如何去选择呢?

    A星寻路算法中,通过给每一个方块一个和值,该值被称为路径增量。让我们看下它的工作原理!

    路径增量

     

    我们将会给每个方块一个G+H和值:

    ·        G是从开始点A到当前方块的移动量。所以从开始点A到相邻小方块的移动量为1,该值会随着离开始点越来越远而增大。

    ·        H是从当前方块到目标点(我们把它称为点B,代表骨头!)的移动量估算值。这个常被称为探视,因为我们不确定移动量是多少仅仅是一个估算值。

    你也许会对移动量感兴趣。在游戏中,这个概念很简单仅仅是方块的数量。

    然而,在游戏中你可以对这个值做调整。例如:

    ·        如果你允许对角线移动,你可以针对对角线移动把移动量调得大一点。

    ·        如果你有不同的地形,你可以将相应的移动量调整得大一点例如针对一块沼泽,水,或者猫女海报:-)

    这就是大概的意思现在让我们详细分析下如何计算出GH值。

    关于G

     

    G是从开始点A到达当前方块的移动量(在本游戏中是指方块的数目)。

    为了计算出G的值,我们需要从它的前继(上一个方块)获取,然后加1。所以,每个方块的G值代表了从点A到该方块所形成路径的总移动量。

    例如,下图展示了两条到达不同骨头的路径,每个方块都标有它的G值:

     

    关于H

    H值是从当前方块到终点的移动量估算值(在本游戏中是指方块的数目)。

    移动量估算值离真实值越接近,最终的路径会更加精确。如果估算值停止作用,很可能生成出来的路径不会是最短的(但是它可能是接近的)。这个题目相对复杂,所以我们不会再本教程中讲解,但是我在教程的末尾提供了一个网络链接,对它做了很好的解释。

    为了让它更简单,我们将使用曼哈顿距离方法(也叫曼哈顿长或者城市街区距离),它只是计算出距离点B,剩下的水平和垂直的方块数量,略去了障碍物或者不同陆地类型的数量。

    例如,下图展示了使用城市街区距离,从不同的开始点到终点,去估算H的值(黑色字):


    A星算法

     

    既然你知道如何计算每个方块的和值(我们将它称为F,等于G+H),  我们来看下A星算法的原理。

    猫会重复以下步骤来找到最短路径:

    1. 将方块添加到open列表中,该列表有最小的和值。且将这个方块称为S吧。
    2. 将S从open列表移除,然后添加S到closed列表中。
    3. 对于与S相邻的每一块可通行的方块T:

    ·        如果Tclosed列表中:不管它。

    ·        如果T不在open列表中:添加它然后计算出它的和值。

    ·        如果T已经在open列表中:当我们使用当前生成的路径到达那里时,检查F和值是否更小。如果是,更新它的和值和它的前继。

    如果你对它的工作原理还有点疑惑,不用担心我们会用例子一步步介绍它的原理!:]


    如下图方格中左下角:G,方格右下角:H,左上角:F

    F=G+H (其实这个公式不用理解也行,主要是为了方便计算的)



    上图是第一步:计算起点周围邻域的代价,跨越一条边是10,对角是14,

    把周围节点的G和H计算出来之后,计算F(就是G+H)。然后再赋予父节点,其实可以想象初始的时候所有节点的F都是无穷大的,为什么要这么理解呢,主要是节点的父指针就是根据F来变化的。

    因为一开始都是无穷大,所以邻域节点的F计算出来之后都要比无穷大小,那么,这些节点的父指针就指向当前的起始节点。如上图所示。因为此时这几个邻域节点都没有在open列表中,于是就把这8个点加到open队列中,并且把当前节点也就是起始节点放到close中(也就是下次不再考虑了)。


    第二步:从open队列中选择F最小的那个节点,此时可能有F相同的(这种情况就随便选个,不影响最短路径长度),我们选择40的那个,于是,把F=40的这个节点作为当前节点,如下图所示:(此时我们把40抹去了,因为之后会把这个节点放到close队列中,close队列中的点都是不考虑的,也是为了描述方便,我们要的只是指针方向)


    关键:

    第三步:把40的那个节点周围8邻域的节点计算完F后,放到open队列中,注意,此时障碍物的节点和已经放入close队列的节点不放,那么此时没有新节点加入进来,由于把涂抹了的那个节点当成当前节点,所以需要重新计算它的8邻域节点的G值和F值,(也就是它的上方那个,坐上方节点,下方节点,左下方节点,一个4个),此时G值的计算是这样的:比如计算上方那个(54 14 40),由于从原点到当前节点的G为10,从当前节点到上方节点的G值为10,所以10+10=20(也就是所到上方节点需要先从原点到这个点,然后在从这个点到上面那个点),但是新计算的G=20<14(节点原来的G值),所以上方节点的指针方向不变,(如果计算出来小于原来的值,那么就把上方节点的指针指向当前这个节点了)!!

    同样计算剩下的三个节点的G值,发现都大于原来的G值,所以节点指针方向没有做任何改变。

    于是把当前节点放到close对列中,再从open队列中找F值最小的节点。(此时队列中有7个节点)

    于是把54那个节点(起始节点的右下方那个)当成当前节点,计算周围8邻域的G值和F值。但是障碍物下方的那个点不能加入计算,因为从当前节点到障碍物下方那个节点必须穿透墙角了!

    同样赋予节点父指针以及更新8邻域的G值和F值。



    当把起始节点下方的那个节点当成当前节点的时候,注意它下方那个节点的父指针变化了,因为它原来的G值为28,但是通过当前节点的时候G能变小到20,所以对应的F也小了,那么,它的父指针就指向当前节点,表示这样走更近。


    所以如此循环下去:不断从open队列中找最小的点作为当前节点并加入周围节点,不断更新周围8邻域的G和F,看看能不能比原来G值更小,如果小就更新,否则不更新,当前节点算完就放入close队列,然后再从open队列中找最小的点。。。。


    最后直到把终点加入open队列中,计算出父指针就完事了。

    所以最后的路径就是,从终点开始沿着父指针不断回缩,最后回到起始点,这样最短路径就找到了。




    展开全文
  • 原理A* 算法是一种启发式搜索算法,通过代价函数f = g+h,A*算法每次查找代价最低的点作为搜索点,并更新搜索节点列表。最终搜索到目标位置。需要定义两个列表 (Open和Closed列表): private List&lt;Tile&...

    原理

    A* 算法是一种启发式搜索算法,通过代价函数f = g+h,A*算法每次查找代价最低的点作为搜索点,并更新搜索节点列表。最终搜索到目标位置。

    需要定义两个列表 (Open和Closed列表)

        private List<Tile> openList = new List<Tile>();
        private List<Tile> closeList = new List<Tile>();
    •     一个记录下所有被考虑来寻找最短路径的格子(称为open 列表)
    •     一个记录下不会再被考虑的格子(成为closed列表)

    首先在closed列表中添加当前位置(我们把这个开始点称为点 “A”)。然后,把所有与它当前位置相邻的可通行格子添加到open列表中。

    引入二个概念:

    节点(Node):每个格子都可以称为节点。

    代价(Cost):描述角色移动到某个节点时所走的难易程度

    通常寻路过程中的代价用f,g,h来表示

    g代表从指定节点到相邻节点的代价

    h代表从指定节点到目标节点根据不同的估价公式估算出来的代价。

    而 f = g + h 表示节点的总代价

        public float FValue { get { return GValue + HValue; } }
        public float GValue { get; set; }
        public float HValue { get; set; }

    通常障碍物本身也可以看成是由若干个不可通过的节点所组成,所以 CanPass 是用来标记该节点是否为障碍物(节点)。

    在考查从一个节点移动到另一个节点时,总是拿自身节点周围的8个相邻节点来说事儿,相对于周边的节点来讲,自身节点称为它们的父节点

    之后根据父节点回溯返回找到路径

        public Tile FatherTile;
        public bool CanPass;
        public List<Tile> nearTiles=new List<Tile>();

    重复以下步骤来找到最短路径:

    1. 将Tile添加到open列表中,该列表有最小的和值。且将这个Tile称为T吧。
    2. 将T从open列表移除,然后添加T到closed列表中。
    3. 对于与T相邻的每一块可通行的方块nearT:

    ·        如果nearTclosed列表中或者是不可通过的:不管它。

    ·        如果nearT不在open列表中:添加它然后计算出它的和值。

    ·        如果T已经在open列表中:当我们使用当前生成的路径到达那里时,检查F和值是否更小。如果是,更新它的和值和它的父         节点。

        public List<Tile> SearchPath(Tile originTile, Tile targetTile)
        {
            Tile nowTile = originTile;
            openList.Add(nowTile);
            bool finded = false;
            while (openList.Count > 0)
            {
                nowTile = openList[0];
                for (int i = 0, max = openList.Count; i < max; i++)
                {
                    if (openList[i].FValue <= nowTile.FValue &&
                        openList[i].HValue < nowTile.HValue)
                    {
                        nowTile = openList[i];
                    }
                }
    
                openList.Remove(nowTile);
                closeList.Add(nowTile);
                
    
                // 找到的目标节点
                if (nowTile.Equals(targetTile))
                {
                    finded = true;
                    break;
                }
                List<Tile> nearTiles = nowTile.nearTiles;
                // 判断周围节点,选择一个最优的节点
                foreach (Tile near in nearTiles)
                {
                    // 如果是墙或者已经在关闭列表中
                    if (!near.CanPass|| closeList.Contains(near))
                        continue;
                    // 计算当前相领节点现开始节点距离
                    float newValue = nowTile.GValue + nowTile.ComputeHValue(near);
                    // 如果距离更小,或者原来不在开始列表中
                    if (newValue < near.GValue || !openList.Contains(near))
                    {
                        // 更新与开始节点的距离
                        near.GValue = newValue;
                        // 更新与终点的距离
                        near.HValue = near.ComputeHValue(targetTile);
                        // 更新父节点为当前选定的节点
                        near.FatherTile = nowTile;
                        // 如果节点是新加入的,将它加入打开列表中
                        if (!openList.Contains(near))
                        {
                            openList.Add(near);
                        }
                    }
                }
            }
            openList.Clear();
            closeList.Clear();
    
            List<Tile> route = new List<Tile>();
            if (finded)
            {//找到后将路线存入路线集合  
                Tile tile = targetTile;
                while (!tile.Equals(originTile))
                {
                    route.Add(tile);//将节点添加到路径列表里  
    
                    Tile fatherHex = tile.FatherTile;//从目标节点开始搜寻父节点就是所要的路线  
                    tile = fatherHex;
                }
                route.Add(tile);
            }
            route.Reverse();
            return route;
        }
    ComputeHValue方法用于计算hCost,hCost的计算方式是直接计算距离


    展开全文
  • 很多年以前(其实也就3年前),听到A*寻路,我一脸懵逼,不知道是个什么玩意。直到公司有个项目需要用到A*寻路,我才开始了解它。其实网上有很多关于A*寻路的文章,有一些写的特别好,有兴趣的同学可以搜一下。弄懂...

    很多年以前(其实也就3年前),听到A*寻路,我一脸懵逼,不知道是个什么玩意。直到公司有个项目需要用到A*寻路,我才开始了解它。其实网上有很多关于A*寻路的文章,有一些写的特别好,有兴趣的同学可以搜一下。弄懂了原理后,给项目写了一个最简单的A*寻路,这事也就过去了。不知道最近怎么了,想写一些文章了,所以在这里班门弄斧,有什么不足,希望大家指正。这是我的第一遍文章,请轻喷!

    A*寻路的原理


    这张图网上有很多,是A*经典图片

    注意:如图A到B,我们不能走红色的路线,绿色是正确路径之一。为什么不能走红色路线呢?刚开始,我郁闷了好久,后来才弄明白这里的方块就是最小的移动单位(这句话很重要),也就是说这里的方块已经是最小的移动单位了,不可再拆分。红色路线其实又再次的拆分了方块,这个是不对的(具体项目都有自己的最小移动单位,这个一定要弄清楚)。

    假设我们要从“绿色方块”到达“红色方块”。那么,从“绿色方块”开始,下次可移动的点有8个,即“绿色方块”周围的8个点。我们每次都需要计算周围8个方块的耗费。

    (方块左下角的数值是到“父节点”parentNode的距离,用G表示;右下角的数值是到“红色方块”的距离,用H表示;左上角的数值是G与H的和,用F表示(F=G+H)。

    一、首先把“绿色方块”放到一个列表里,我们称它为“开放列表”openList。

    二、寻找openList中F值最小的方块,我们称之为S;

    三、将S放入另一个列表里,我们称它为“关闭列表”closeList;

    四、S周围的8个方块:

          a)如果它在closeList中或者不可通过,忽略;

          b)如果它不在openList中,将它加入openList,并且设置父节点parentNode=S;

          c)如果它在openList中,则假设以S为父节点,重新计算F、G、H——如果新的F小于原来的F,

               则更换父节点parentNode=S,并更新F、G、H的值;

          d)重新对openList排序。

    五、重复步骤四,直到停止:1、“红色方块”已经加入到openList,找到目的地;2、openList为空,没有路径可以到达目地。如果是情况1,则我们从“红色方块”开始,沿着每块的父节点parentNode直到“绿色方块”,就是我们要找的路径。

    这只是最基础的算法,并没有优化什么的。至于代码,相信难不倒各位。可以上网寻找一些大神的文章,都写的很好,推荐链接:https://www.cnblogs.com/yangyxd/articles/5447889.html

    好了,以上就是个人对A*的理解,有什么不对的地方,欢迎指正!

    展开全文
  • 基于Unity5.4.4版本,随机障碍物,动态实现寻路,UnityA星寻路完整Demo
  • 欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来,用它写博客,将会带来全新的体验哦: Markdown和扩展Markdown简洁的语法 代码块高亮 图片链接和图片上传 LaTex数学公式 UML序列图和流程图 ...
  • 很显然,寻路算法在RPG游戏中的应用领域是很广泛的,最近在研究人工智能的同时,也不禁遇到很多迷茫和困惑,想着还是先从简单的算法开始实现,然后逐渐学习更难的知识,有句话说的好,心急吃不了热豆腐。首先贴一下...
  • A* Pathfinding Project 是基于Unity扩展编辑器开发的一款寻路插件,寻路原理是基于AStar寻路新算法,也称作A* 寻路算法。 一、A* 寻路 VS 导航网格NavMesh寻路: A*寻路: 动态寻路,适用于场景状态变化大的,...
  • 引言 寻路系统是当今众多游戏中不...在Unity3D中我们一般常用的寻路策略有: 1.路点寻路(WayPoint) 路点寻路是最简单,易理解,易操作的(如下图):需要预先设置好路径点坐标集合。然后对象按照规定的坐标集...
  • Unity 算法 之 A星(A Star/A*)寻路的算法法实现和封装,并带动态演示Demo 目录 Unity 算法 之 A星(A Star/A*)寻路的算法法实现和封装,并带动态演示Demo 一、简单介绍 二、 A星(A Star/A*)寻路算法相关...
  • A寻路原理:略,网上可搜到通过理解A星寻路的原理可以设计出以下流程图: 流程图通过processon制作Unity C#脚本实现代码:各个坐标节点为单独的gameObject,并自带脚本:using UnityEngine; using System....
  • 一、目录 【Unity3D从入门到进阶】文章目录及设置这个专栏的初衷
  • 2013-09-21 15:58:52| 分类: Unity教程 | 标签:unity3d 网格寻路 多边形寻路 |举报|字号 订阅 Unity3d本身自带有了NavMesh寻路功能。但用过这个功能的人,都会有各种的抱怨。比如,必须...
  • 刚好最近忙里偷闲,就来写写unity在2D下的AStar寻路算法。 地图用untiy的tilemap来贴。 大概的效果,没有去找好看的图片,将就弄点颜色表示: 黑色表示障碍,绿色表示路径,开头和结尾也是用的绿色,好懒o(╥﹏...
  • Unity3D引擎为例写一个底层c# NavMesh寻路。因为Unity3D中本身自带的NavMesh寻路不能很好的融入到游戏项目当中,所以重写一个NavMesh寻路是个必经之路。NavMesh在很多游戏中应用广泛,不同种类的框架下NavMesh寻路...
  • 这就是寻路算法的作用了。那么怎么实现寻路算法呢?现在比较流行的就有A*。其实unity有内置的寻路算法,那就是导航网格组件。有了它,我们就可以进行寻路了。 给大家推荐一个unity学习+交流705182843 首先我...
  • 最近两天刚好有空研究了下游戏中的自动寻路功能,收获颇丰,感觉用相应的算法去解决相应的问题真的非常重要啊!至少比自己想的流水账逻辑流程管用。看来以后得花多点时间研究下算法方面的知识了。  游戏中的自动...
1 2 3 4 5 ... 14
收藏数 271
精华内容 108