效果动画如上,下方是项目下载链接:
github下载链接
A* 算法，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。----百度百科
在玩游戏的时候我们在地图上点击目的地,我们角色可以自动绕过障碍物,以最短路径到达目的地,这种寻路功能通常就使用是A*算法实现的。
启发式搜索
启发式探索是利用问题拥有的启发信息来引导搜索，达到减少探索范围，降低问题复杂度的目的。
A*算法是一种启发式搜索算法,我们给每个节点绑定一个估计值,在对节点的遍历过程中是采取估计值优先原则，估计值更优的节点会被优先遍历。所以估计函数的定义十分重要，显著影响算法效率。
简化搜索区域 我们首先需要将一张地图简化成一个个网格,这个网格可以是任意大小形状的,这取决于你的需求。一般情况下分成一个个方格就行了。
在这里,红色的节点代表起点,蓝色的代表终点,黑色的代表障碍,障碍不可通行。
算法流程 准备 我们需要准备两个列表open和close. open列表存放我们将要探索的节点。 close列表存放我们已经探索过的节点 步骤
我们要将起点加入open列表中。检查open列表,如果open列表为空,这表示我们找不到可以搜索的节点了,搜索失败,如果open中存在终点,则搜索成功。然后,依据估计值F,从open列表取出F值最小的节点(如果F值有相同的就选择H值更小的),加入close中,同时我们把这个节点设置为当前节点。遍历当前节点的所有可到达的相邻节点,对每个相邻节点进行处理。 4.1 如果该节点在close中,代表已经探索过,丢弃该节点 4.2 如果该节点已经在open节点中,通过当前节点重新计算F值,和原来的F值进行比较,如果更小,则更新其F值，并将其父节点设置为当前节点。 4.3 如果该节点不在open列表中，则将其加入到open列表，并计算F值，设置其父节点为当前节点。回到第二步详解 要计算每个节点的估计消耗值我们需要一个估计函数,用F = G + H表示。 G表示的是起点到当前探索节点的消耗。 H表示的是当前探索节点到终点的估计消耗
G的值是很好求的,就是父节点的G值加上父节点到该节点的消耗G(n) = G(n-1) + 两点之间消耗 H的值有多种求法,例如曼哈顿距离H(n) = x + y，或者欧几里得距离H(n) = sqrt(x^2 + y^2)。本例中采用曼哈顿式。
///<summary> ///导航 ///</summary> ///<param name="mapData">地图数据</param> ///<param name="from">起点</param> ///<param name="to">终点</param> ///<param name="path">路径</param> ///<param name="searched">搜索过但未采用的节点</param> public bool Navigate(MapData mapData, GridUnitData from, GridUnitData to, out List<GridUnitData> path, out List<GridUnitData> searched) { //输出参数赋初值 path = new List<GridUnitData>(); searched = new List<GridUnitData>(); //没有地图或者起点或终点则结束导航 if (mapData == null) { Debug.Log("mapData is null!"); return false; } if (from == null || to == null) { Debug.Log("from or to is null!"); return false; } //open储存将要探索的节点 List<NavigationData> open = new List<NavigationData>(); //close储存已经探索的节点 List<NavigationData> close = new List<NavigationData>(); //1.把起点加入open open.Add(GetEmptyNavigationData(from, null, 0, from.Distance(to))); //最多尝试尝试 int trytimes = 9999; //主体循环 while (trytimes--!=0) { //2.判断open列表,如果为空则搜索失败,如果终点在里面则搜索成功 if (open.Count == 0) return false; NavigationData temp = Exits(open, to); if (temp != null) { //从终点回溯至起点 while (temp != null) { path.Add(temp.thisGrid); temp = temp.preGrid; } for (int i = 0; i < close.Count; ++i) searched.Add(close[i].thisGrid); return true; } //3.从open列表取出F值最小的节点(F值相同则取H值最小的),将其设为当前节点,并加入close列表中 NavigationData nowGrid = open[0]; int minF = open[0].F, minH = open[0].H; for(int i = 1; i < open.Count; ++i) { if (open[i].F < minF || (open[i].F == minF && open[i].H < minH)) { nowGrid = open[i]; minF = open[i].F; minH = open[i].H; } } close.Add(nowGrid); open.Remove(nowGrid); //4.获取当前节点的所有相邻可到达节点 List<GridUnitData> neighbor = mapData.GetNeighbor(nowGrid.thisGrid); //对于每个节点 for(int i = 0; i < neighbor.Count; ++i) { //4.1 如果该节点在close列表中,删除open中的该节点 NavigationData t = Exits(close, neighbor[i]); if (t != null) { open.Remove(t); continue; } t = Exits(open, neighbor[i]); //int G = from.Distance(neighbor[i]); int G = nowGrid.G + 1; int H = to.Distance(neighbor[i]); //4.2 如果该节点不在open中,计算G,H值,设置父节点为当前节点,加入open列表 if (t == null) { NavigationData target = GetEmptyNavigationData(neighbor[i], nowGrid, G, H); open.Add(target); } //4.3 如果该节点在open中且以当前节点求F值更小,则更新G,H,设父节点为当前节点 else if (t.F > G + H) { t.G = G; t.H = H; t.preGrid = nowGrid; } } } Debug.Log("尝试次数耗尽."); return false; }
慢放寻路
A*算法就是通过给每个节点绑定一个估计值,以估计值为启发,每次都在所有可探索的节点中选择那个到终点估计消耗最小的节点优先搜索。 在本例中,由起点到已经探索的节点的消耗G是已知的,因为探索到这里,算法把绕开障碍的消耗也考虑进去了,但是当前节点到终点的消耗H是未知的,只能估计,因为我们不知道还会遇到多少障碍。 在每一次选择下次探索节点时,我们遍历所有可以探索的节点,根据已知情况G和估计情况H,综合得到F,以最小的F为优先。 在这个过程中我们要记下每个节点是通过哪个节点走过来的,设为父节点(preGird),这样当我们找到终点的时候,我们从终点回溯到起点,得到的路径就是我们要找的最短路径了。
我们还可以给不同类型的节点配置权重,例如通过山地,或者河流单位格的消耗是平地的十倍,这样A*算法在寻路的时候也会把这种消耗考虑进去,如果绕路更快就会选择绕路,如果直接过河更快就会选择过河。
如果觉得哪里讲到不清楚的,可以在评论区指出。 Unity实现可视化Astar寻路项目 github下载链接
