A星算法
-
什么是A star
A*搜索算法，俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或网络游戏的BOT的移动计算上。
该算法综合了Best-First Search和Dijkstra算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（基于评估函数）。
-
核心公式
f(n)=g(n)+h(n) 一般简写为: F=G+H
g(n)表示从起点到任意顶点n的实际距离
h(n)表示任意顶点n到目标顶点的估算距离（根据所采用的评估函数的不同而变化）如果g(n)为0,即只计算任意顶点n到目标的评估函数h(n),则算法转化为使用贪心策略的Best-First Search，速度最快，但可能得不出最优解
如果h(n)不高于实际到目标顶点的距离，则一定可以求出最优解，而且h(n)越小，需要计算的节点越多，算法效率越低，常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离
如果h(n)为0,即只需求出起点到任意顶点n的最短路径g(n),则转化为单源最短路径问题，即Dijkstra算法，此时需要计算最多的顶点
-
核心逻辑
通过公式我们知道主要需要计算的节点分为两类,已被估算过的节点和将要估算的节点,分别放入关闭列表和开启列表开启列表 OpenList
OpenList中主要存在已搜寻过且未被作为待选的路径节点,在开始需要将起始点加入OpenList。关闭列表 ClosedList
主要存在已被选中的节点,有时也可以加入不能通过的点来简化筛选逻辑。领近点
作为搜寻节点的主要驱动范围，通常以某个已选节点出发搜寻周围除自身外的八个格子，然后进入待选列表OpenList中或刷新OpenList中节点更小的估值。
对于领近点有时会根据需要限定是否可以斜行或某种情况下才能斜行。-
估值
- 领近点估值Val
一般对角点Val为2的开方,而非对角点为1 - 目标点估值H
一般使用曼哈顿距离算法,也就是abs(x1-x2)+abs(y1-y2)
- 领近点估值Val
路径回溯
寻找最优路径只是第一步，接下来需要通过回溯各个前后节点的关系得到这个路径。由于是通过各个节点前后关系得到的路径，这里最好的选择就是链表了,每次得到下一个最优节点时都可以为当前节点和下一个节点绑定父子关系,这样通过普通的链表遍历方式就能从起始点或终止点得到整个路径。边界判断
在寻找领近点时需要先将那些超出地图边界的点优先排除掉。终止点
当你选择到的下一个最优点为终点时,路径搜寻结束。-
主要步骤
- 在开启列表中找到F最小的节点,记录为CurrentNode
- 如果CurrentNode是终点则返回最佳路径,执行结束,否则继续执行
- 将CurrentNode从OpenList中移除,并加入ClosedList
- 寻找CurrentNode周围节点,若周围节点X在ClosedList中或不能通过则跳过X节点
- 未被跳过则计算X节点的估值 nG=CurrentNode.G+Val;
- 若X节点不在OpenList中则加入OpenList，并暂时标记为更优,若在OpenList中则比较nG与X.G的值,如果
nG<X.G则标记为更优。 - 若6中被标记为更优则更新X点的G和H数据信息,并标记父子关系。(其中H为X到终点的曼哈顿距离)
-
基础应用
基础应用一般为三部分创建地图(或者说网格)
实例化出 n*m的网格,一般使用二维数组Node[,]nodes ,每个格子都是一个节点Node实例,每个节点都有自身基础信息和下一个节点的引用信息,可以先对不能通过的地方进行标记,也可以在寻路过程中动态标记。位置映射
节点坐标通常只会使用整数索引,如果要用于地图中则需要增加一个映射关系，用于计算在实际地图中的具体坐标。核心逻辑
需要不断刷新执行.
可进一步根据实际情况进行变型，如增加算法权重,设置领近点搜索的驱动方式。
参考资料:1.*