Unity 算法 之 A星（A Star/A*）寻路算法实现和封装，并带动态演示Demo |
您所在的位置：网站首页 › 游戏地图转化为a星寻路地图怎么做 › Unity 算法 之 A星（A Star/A*）寻路算法实现和封装，并带动态演示Demo |
Unity 算法 之 A星（A Star/A*）寻路算法实现和封装，并带动态演示Demo
|
Unity 算法 之 A星（A Star/A*）寻路的算法法实现和封装，并带动态演示Demo
目录 Unity 算法 之 A星（A Star/A*）寻路的算法法实现和封装，并带动态演示Demo 一、简单介绍 二、 A星（A Star/A*）寻路算法相关知识 1、什么是A星（A Star/A*）寻路算法 2、寻路：寻找最短路径并避开障碍物 3、几个重要的概念 4、寻路结束的条件 5、寻路原理 6、如何找回路径 7、伪代码寻路过程 8、寻路步骤 三、实现A星（A Star/A*）寻路算法的效果预览 四、实现步骤 五、Demo 使用操作说明 1、按空格可以刷线地图，更新地图的障碍物位置（动态随机设置） 2、鼠标左键设置开始点位置 3、鼠标右键设置目标点位置 4、开始点和目标点都不为空，即会动态绘制路径 六、关键代码 1、Point 2、AStarWrapper 若有不对，希望指正骚扰，谢谢 一、简单介绍 算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 整理一些 Unity 游戏中常用的算法，便于后期使用和研究。 本片介绍A星（A Star/A*）寻路算法。 二、 A星（A Star/A*）寻路算法相关知识 1、什么是A星（A Star/A*）寻路算法 A星（A Star/A*）寻路算法俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。 2、寻路：寻找最短路径并避开障碍物 将地图虚拟化，将地图划分为一个一个的小方块，这样可以用二维数组来表示地图。如下所示，绿色块(A)是起点，红色块(B)是终点，中间黑色块是障碍物，白色块是空地，黄色块是计算传来的路径。
3、几个重要的概念 1）open 列表：一个记录下所有被考虑来寻找最短路径的格子 2）closed列表：一个记录下不会再被考虑的格子 3）G：G 表示从起点 A 移动到网格上指定方格的移动耗费 (可沿斜方向移动) 4）H：H 表示从指定的方格移动到终点 B 的预计耗费 (H 有很多计算方法, 这里我们设定只可以 上下左右移动) 5）F：F=G+H，表示该点的总耗费 6）Point 的定义（可根据需要扩展） public class Point { // 父亲节点 public Point Parent { get; set; } // F G H 值 public float F { get; set; } public float G { get; set; } public float H { get; set; } // 坐标值 public int X { get; set; } public int Y { get; set; } // 是否是障碍物（例如墙） public bool IsWall { get; set; } // 该点的游戏物体（根据需要可不用可删除） public GameObject gameObject; // 该点的空间位置（根据需要可不用可删除） public Vector3 position; }4、寻路结束的条件 1）目标格已经在 "开启列表", 这时候路径被找到 2）如果开启列表已经空了, 说明路径不存在 5、寻路原理 1）首先有一张一定宽高的地图 （定义好 Point 点的地图，其中 Point 中有 IsWall 属性） 2）设定开始点，和目标点 3）传入 FindPath 开始寻找较短路径，找到返回true，否则 false 4）为 true 就可以通过 目标点的父亲点的父亲点的父亲点，直到父亲点为开始点，这些点集合即是路径 5）FindPath 寻找原理 （1）开列表，关列表初始化 （2）添加开始点到开列表，然后获得周围点集合，接着又把开始点从开列表中移除，并添加到关列表 （3）判断这些周围点集合是否已经在开列表中，不在则更新这些点的F 和 父亲点，并添加到开列表；再则重新计算G值，G较小则更新GF 和父亲点 （4）从周围点集合中找到 F 最小的点，然后获得周围点集合，接着又把找到 F 最小的点从开列表中移除，并添加到关列表 （5）接着执行第 （3） 步骤 （6）直到目标点被添加到开列表中，则路径找到 （7）否则，直到开列表中没有了数据，则说明没有合适路径 6、如何找回路径
如上图所示, 除了起始方块, 每一个曾经或者现在还在 "开启列表" 里的方块, 它都有一个 "父方 块", 通过 "父方块" 可以索引到最初的 "起始方块", 这就是路径. 7、伪代码寻路过程
8、寻路步骤 1）总的步骤 步骤1.从起点A开始，把A作为一个等待检查的方格，放入到“开启列表”中，开启列表就是一个存放等待检车方格的列表 步骤2.寻找起点A周围可以到达的方格（最多八个），将它们放入到“开启列表”，并设置它们的父方格为A 步骤3.从“开启列表”中删除点A,并将A放入到“关闭列表”中，“关闭列表”存放的是不再需要检查的方格 步骤4.计算每个方格的F值 F=G+H: G 表示从起点A移动到指定方格的移动消耗，我们假设横向移动一个格子消耗10，斜向移动一个格子消耗14（具体值可以根据情况修改） H 表示从指定的方格移动到目标B点的预计消耗，我们假设H的计算方法，忽略障碍物，只可以纵横向计算 步骤5.从“开启列表”中选择F值最低的方格C，将其从“开启列表”中删除，放入到“关闭列表”中 步骤6.检查C所有临近并且可达的方格（障碍物和“关闭列表”中的方格不考虑），如果这些方格还不在“开启列表”中的话，将它们加入到开启列表，并且计算这些方格的F值，并设置父方格为C。 步骤7.如果某相邻的方格D已经在“开启列表”，计算新的路径从A到达方格D（即经过C的路径），G值是否更低一点，如果新的G值更低，则修改父方格为方格C，重新计算F值，H值不需要改变，因为方格到达目标点的预计消耗是固定的。但如果新的G值比较高，则说明新的路径消耗更高，则值不做改变。 步骤8.继续从“开启列表”中找出F值最小的，从“开启列表”中删除，添加到“关闭列表”，再继续找出周围可以到达的方块，如此循环 步骤9.当“开启列表”中出现目标方块B时，说明路径已经找到。除了起始方块A，每一个曾经或者现在还在“开启列表”中的方块，都存在一个“父方格”，可以从目标点B通过父方格索引到起始方块，这就是路径。 2）步骤拆解分析 步骤1,2,3：方块A已经放入到“关闭列表”，周围临近的8个方格（没有障碍物）已经放入到“开启列表”
步骤4：计算F=G+H 以方格C为例
为了方便统计，将左上角数字记为F值，左下角为G值，右下角为H值，则如下所示：（箭头的起点为该方格的父方格）
步骤5，6：我们发现C的F值最小，将其从“开启列表”中移除，加入到“关闭列表”中。C右边三个是障碍物不考虑，左边起始方块A已经加入到“关闭列表”，不考虑。则候选的方块也只有上下四个:，而且也已经存在“开启列表”中。 步骤7：从开启列表中找出F最小的，我们发现上下两个同为54，取哪个都可以，选择上面的方格D。重新计算G值，路径A-C-D 计算G值为20，比原来的A-D路径的G值14要大，则值不变，方格D的父方格不变。 步骤8：跳到步骤5开始，选择F值最小的D，将其从“开启列表”中移除，加入到“关闭列表”中。将周围可达方格加入到“开启列表”并计算F值 我们规定如果上下左右有障碍物，则对应的右上，右下，左上，左下不可到达，所以方格D右上角不可到达。将可到达的方格E1,E2加入“开启列表”，计算F值，然后再比较到达周围方格的G值是否存在更小值，最后发现 “开启列表”里F最小的方格是E3方格，然后再次跳到步骤5，继续执行
步骤9：当循环15遍后，如下图所示（图画得快吐了，其中打叉的方格表示在“关闭列表”中），目标方块B出现在“开启列表”中，结束循环！
通过目标点B的父方格索引到起始方块A，这就是路径,如下所示：
三、实现A星（A Star/A*）寻路算法的效果预览
四、实现步骤 1、打开Unity，新建一个空工程
2、在工程中新建脚本，AStarWrapper 封装 A 星算法的实现，Point A星中点的定义类，Test_AStarWrapper 生成地图，实现地图各个逻辑，并调用 AStarWrapper 算法绘制路线，Singleton 单例类
3、把 Test_AStarWrapper 测试脚本挂载到场景中
4、运行场景，效果如效果预览
五、Demo 使用操作说明 1、按空格可以刷线地图，更新地图的障碍物位置（动态随机设置） 2、鼠标左键设置开始点位置 3、鼠标右键设置目标点位置 4、开始点和目标点都不为空，即会动态绘制路径
Demo 下载地址：https://download.csdn.net/download/u014361280/12235133 六、关键代码 1、Point using UnityEngine; namespace AStar { /// /// AStar 中点的定义 /// public class Point { // 父亲节点 public Point Parent { get; set; } // F G H 值 public float F { get; set; } public float G { get; set; } public float H { get; set; } // 坐标值 public int X { get; set; } public int Y { get; set; } // 是否是障碍物（例如墙） public bool IsWall { get; set; } // 该点的游戏物体（根据需要可不用可删除） public GameObject gameObject; // 该点的空间位置（根据需要可不用可删除） public Vector3 position; /// /// 构造函数 /// /// /// /// /// /// public Point(int x, int y, GameObject go = null, Point parent = null, Vector3 position = default) { this.X = x; this.Y = y; this.gameObject = go; this.position = position; this.Parent = parent; IsWall = false; } /// /// 更新G，F 值，和父亲节点 /// /// /// public void UpdateParent(Point parent, float g) { this.Parent = parent; this.G = g; F = G + H; } } } 2、AStarWrapper using System.Collections.Generic; using UnityEngine; namespace AStar { /// /// A星寻路的单例封装 /// 实现原理 /// 1、首先有一张一定宽高的地图 （定义好 Point 点的地图，其中 Point 中有 IsWall 属性） /// 2、设定开始点，和目标点 /// 3、传入 FindPath 开始寻找较短路径，找到返回true，否则 false /// 4、为 true 就可以通过 目标点的父亲点的父亲点的父亲点，直到父亲点为开始点，这些点集合即是路径 /// 5、FindPath 寻找原理 /// 1）开列表，关列表初始化 /// 2）添加开始点到开列表，然后获得周围点集合，接着又把开始点从开列表中移除，并添加到关列表 /// 3）判断这些周围点集合是否已经在开列表中，不在则更新这些点的F 和 父亲点，并添加到开列表；再则重新计算G值，G较小则更新GF 和父亲点 /// 4）从周围点集合中找到 F 最小的点，然后获得周围点集合，接着又把找到 F 最小的点从开列表中移除，并添加到关列表 /// 5）接着执行第 3） 步骤 /// 6）直到目标点被添加到开列表中，则路径找到 /// 7）否则，直到开列表中没有了数据，则说明没有合适路径 /// public class AStarWrapper : Singleton { /// /// 根据开始点和结束点，取得较短路径 /// /// 开始位置 /// 结束位置 /// 地图 /// 地图宽 /// 地图高 /// bool 找到路线/false 没有 public bool FindPath(Point start, Point end, Point[,] map, int mapWidth, int mapHeight) { // 开列表（周围的点列表），关列表（每次比较后得到的最小 F 的点列表） List openList = new List(); List closeList = new List(); // 首先开始点添加进开列表 openList.Add(start); while (openList.Count > 0) { // 寻找开列表中最小的 F 值 Point point = FindMinFOfPoint(openList); // 把得到的 F 最小的点移除 开列表，添加到关列表中 openList.Remove(point); closeList.Add(point); // 获取当前最小 F 点周围的点集合 List surroundPoints = GetSurroundPoints(point, map, mapWidth, mapHeight); // 过滤掉关列表中的数据 PointFilter(surroundPoints, closeList); // 遍历获得的周围点 foreach (Point item in surroundPoints) { // 已存在开列表中的话 if (openList.IndexOf(item) > -1) { // 计算 G 值 float nowG = CalcG(item, point); // 得到的 G 值小的话，更新 G 值和点的父节点 if (nowG < item.G) { item.UpdateParent(point, nowG); } } else // 不在开列表中 { //把 最小 F 点，设置为他的父节点 item.Parent = point; // 计算更新 item的 FGH CalcF(item, end); // 添加到 开列表 openList.Add(item); } } // 判断 end 是否在 开列表中，即找到路径结束 if (openList.IndexOf(end) > -1) { return true; } } // 开列表没有了点，说明找不到路径 return false; } /// /// 把关列表中的点从周围点集合中过滤掉 /// /// 周围点集合 /// 关列表 private void PointFilter(List src, List closeList) { // 遍历，存在则移除 foreach (Point item in closeList) { if (src.IndexOf(item) > -1) { src.Remove(item); } } } /// /// 获得当前最小 F 的周围点 /// /// 当前最小 F 点 /// 地图点集合 /// 地图宽 /// 地图高 /// 返回获得的周围点集合 private List GetSurroundPoints(Point point, Point[,] map, int mapWidth, int mapHeight) { // 一个点一般会有上、下、左、右，左上、左下、右上、右下 八个点 Point up = null, down = null, left = null, right = null; Point lu = null, ru = null, ld = null, rd = null; // 如果 点 Y 小于 mapHeight - 1，则表明不是最顶端，有上点 if (point.Y < mapHeight - 1) { up = map[point.X, point.Y + 1]; } // 如果 点 Y 大于 0，则表明不是最下端，有下点 if (point.Y > 0) { down = map[point.X, point.Y - 1]; } // 如果 点 X 小于 mapWidth - 1，则表明不是最右端，有右点 if (point.X < mapWidth - 1) { right = map[point.X + 1, point.Y]; } // 如果 点 X 大于 0，则表明不是最左端，有左点 if (point.X > 0) { left = map[point.X - 1, point.Y]; } // 边角点 // 有上点和左点，说明有左上点 if (up != null && left != null) { lu = map[point.X - 1, point.Y + 1]; } // 有上点和右点，说明有右上点 if (up != null && right != null) { ru = map[point.X + 1, point.Y + 1]; } // 有下点和左点，说明有左下点 if (down != null && left != null) { ld = map[point.X - 1, point.Y - 1]; } // 有下点和右点，说明有右下点 if (down != null && right != null) { rd = map[point.X + 1, point.Y - 1]; } // 新建一个列表 List list = new List(); // 把点添加到列表 // 上点不为空，且不是障碍物，则添加到返回列表中，下面同理 if (up != null && up.IsWall == false) { list.Add(up); } if (down != null && down.IsWall == false) { list.Add(down); } if (left != null && left.IsWall == false) { list.Add(left); } if (right != null && right.IsWall == false) { list.Add(right); } // 添加边角到列表 // 左上点不为空且不是障碍物，并且 左点和上点都不是障碍物，则添加到返回列表，以下同理 if (lu != null && lu.IsWall == false && left.IsWall == false && up.IsWall == false) { list.Add(lu); } if (ru != null && ru.IsWall == false && right.IsWall == false && up.IsWall == false) { list.Add(ru); } if (ld != null && ld.IsWall == false && left.IsWall == false && down.IsWall == false) { list.Add(ld); } if (rd != null && rd.IsWall == false && right.IsWall == false && down.IsWall == false) { list.Add(rd); } // 返回列表 return list; } /// /// 比较开列表中所有点的 F 值，获得当前列表中最小的点 /// /// 开列表 /// private Point FindMinFOfPoint(List openList) { float f = float.MaxValue; Point tmp = null; foreach (Point p in openList) { if (p.F < f) { tmp = p; f = p.F; } } return tmp; } /// /// 计算 G 值 /// /// 当前点 /// 当前点的父节点 /// private float CalcG(Point now, Point parent) { return Vector2.Distance(new Vector2(now.X, now.Y), new Vector2(parent.X, parent.Y)) + parent.G; } /// /// 计算 F 值 /// /// 当前点 /// 结束点 private void CalcF(Point now, Point end) { // F = G + H // H 值的计算方式不唯一，有意义就行，这里是结束点X和Y的和 float h = Mathf.Abs(end.X - now.X) + Mathf.Abs(end.Y - now.Y); float g = 0; if (now.Parent == null) { g = 0; } else { // 当前点和父节点的距离 g = Vector2.Distance(new Vector2(now.X, now.Y), new Vector2(now.Parent.X, now.Parent.Y)) + now.Parent.G; } // 更新当前点FGH的值 float f = g + h; now.F = f; now.G = g; now.H = h; } } } 若有不对，希望指正骚扰，谢谢
|
【本文地址】
今日新闻 |
推荐新闻 |