算法：Astar寻路算法改进

AStar算法总结与实现（附Demo）

关于A Star Algorithm

A star算法最早可追溯到1968年，在，是把启发式⽅法（heuristic approaches）如BFS，和常规⽅法如Dijsktra算法结合在⼀起的算法。有点不同的是，类似BFS的启发式⽅法经

常给出⼀个近似解⽽不是保证最佳解。然⽽，尽管A star基于⽆法保证最佳解的启发式⽅法，A star却能保证找到⼀条最短路径。

公式表⽰为：f(n)=g(n)+h(n)

f(n)是节点n从初始点到⽬标点的估价函数

g(n)是在状态空间中从初始节点到n节点的实际代价

h(n)是从n到⽬标节点最佳路径的估计代价

观察A*寻路算法的运⾏轨迹

假设起点为A（浅蓝⾊的个字） 终点为B（深蓝⾊的格⼦）

红⾊代表该格⼦为障碍物

地图为20x20的格⼦

显⽰FGH值的格⼦代表经过A*算法搜索并⽣成路径的格⼦

有透明度变化的格⼦代表该格⼦有被搜索。

绿⾊格⼦代表的是搜索完成后A*得到的最优的路径

A直接抵达B的情况下

A越过直线障碍到达B

A越过U型障碍到达B

B为障碍物所包围着，A到达不了B的情况下

总结与思考

由4组图可以得到

1.A*的消耗是⼀个及其不稳定的过程，消耗的最⼩值不低于直线路径上的消耗，消耗的最⼤值不⾼于遍历整张地图的消耗。

2.A*的消耗主要在搜索的搜索格⼦，以及对其FGH的操作上。

3.由1，2可以得出，在对运⾏速率和效率有要求的场景下，A*可能不是⼀个⽐较好选择。

算法步骤

横向纵向的格⼦的单位消耗为10，对⾓单位消耗为14。

定义⼀个OpenList，⽤于存储和搜索当前最⼩值的格⼦。

定义⼀个CloseList，⽤于标记已经处理过的格⼦，以防⽌重复搜索。

开始搜索寻路

1.将起点加⼊OpenList

2.从OpenList中弹出F值最⼩的点作为当前点

3.获取当前点九空格（除去⾃⼰）内所有的⾮障碍且不在CloseList内的邻居点

4.遍历上⼀步骤得到的邻居点的集合，每个邻居点执⾏以下逻辑

A*算法

A*算法，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。

A* [1] （A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法，之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。

公式表示为： f(n)=g(n)+h(n),

其中， f(n) 是从初始状态经由状态n到目标状态的代价估计，

g(n) 是在状态空间中从初始状态到状态n的实际代价，

h(n) 是从状态n到目标状态的最佳路径的估计代价。

（对于路径搜索问题，状态就是图中的节点，代价就是距离）

h(n)的选取

保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取（或者说h(n)的选取）。

我们以d(n)表达状态n到目标状态的距离，那么h(n)的选取大致有如下三种情况：

1. 如果h(n)< d(n)到目标状态的实际距离，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

2. 如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的。

3. 如果 h(n)>d(n)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。 [2]

一劳永逸的固定寻路

平时我尽我所能，以避免可能被解释为一个在行业中的其他游戏或开发的批评说的事情。

但在这种情况下，我不得不做出一个异常的位。

我要谈谈我们与寻路面临的一些问题。为了证明，这些问题仍然存在，我觉得有必要使这个视频... ...在幽默和轻松愉快的精神，它的目的是，希望在采取

所有这些片段在上周录得最新，最最近修补的每场比赛的版本。

正如你可以看到，我们仍然是一个强大的寻路全线长的路要走... ...它甚至在一些万元的单位销售，AAA级质量职称的问题。

它不一定是一个普遍性的问题。许多现代游戏有高品质的寻路，寻路经常在这里显示的一些游戏。

但仍有太多的游戏，寻路，游戏在20世纪90年代，以同样的方式。

（注：只是你看到大量的PC角色扮演游戏的唯一原因归结到便利，这些都是我当时安装的游戏，问题是不特定的任何类型或任何发挥想象力的平台。。有类似的问题，大量的游戏机游戏）。

据我所知，这些游戏大多使用寻路航点图。我认为这几个寻路的问题，您在这个视频中看到，许多我们在整个行业面临的寻路问题的原因。

我相信航点图现在已经过时。这篇文章解释了航点图方法的局限性，并勾画出了一个更好的方法五点的说法。

曾经有一段时间，这是有意义的，使用寻路航点。早在20世纪80年代和90年代，我们的工作受到严重的技术限制，我们不得不削减了很多弯道。

但是我们现在一个多亿美元的产业。我们的目标平台多内核和日益增加的大量的内存，我们可以做不起寻路正确。

有一个行业AI开发中说：“寻路是解决了。”我们每一个寻路的问题，面临着现代游戏的好方法。我们只是不经常使用它们。

我们没有理由不寻路，在每场比赛，每次。

打跳了详细的解释。

为什么航点对于寻路

让我告诉你什么是一个典型的航点图看起来。下面是一个在魔兽世界暴风城的小片：

图1。魔兽世界暴风城的一部分，

下面是一个典型的航点图可能看起来在这方面想。

图2。同一地区的一个航点图注释

A*算法介绍

路径寻找

单个物体的移动看起来简单。 但路径寻找时复杂的。 为什么要为路径寻找烦恼呢？譬如下述情况：

移动单位被初始化在地图的底部，并准备移动到地图上方。这时它探测周围没有任何障碍物（以粉红色标出）阻碍单位向上移动，因此它就可以不断地向上。在地图上方附近，它遇到了障碍，随即改变了方向。随着移动它发现在路上有个U型的障碍。相对的，一个路径寻找者会探测较大的区域（以浅蓝色表示），但能够发现一条最短的路径（以蓝色表示），从不会让单位移动到凹形障碍物内。

但是你能够扩展你的移动算法来解决像上述的情况。比如回避凹形的障碍，或者把他们标记为危险的凸包（只有当目标在内部时才进入）：

路径寻找者让你向前看并做出计划，而不是等待直到最后发现了问题。路径寻找者的制定计划和移动反应算法之间有一个权衡。制定计划常常是缓慢的，但是能够得到更好的结果；而移动一般比较快，但可能会被阻塞。如果游戏世界是不断变化的时候，那么在一开始制定计划只有较少的价值。我建议同时使用他们：路径寻找应对大地图，缓慢变化的障碍和长路径；而移动应对当前区域，快速的变化和短路径。

算法

在计算机科学教科书中，路径寻找算法在数学上的意义是一个用边连接起来的顶点集合。砖块游戏地图能够被看做一个图，其中每个砖块为一个顶点，相邻的砖块之间由一条边连接：

现在，我假定我们使用二维的网格。后面，我们会讨论怎么建立其他类型的图来表示你的游戏世界。

来自AI或算法研究的大多数的路径寻找算法是为任意图设计的而不是基于网格的游戏。我们想要找到一些有利于网格地图的算法。有些我们认为是常识的事情，算法却不明白。例如，关于方向，我们知道一般情况下，两个物体越远，那么从一个移动到另一个所花费的时间就越长；并且没有任何秘密的虫洞能让你到地图上从一个点传送的另一个点。（嗯，我们假设没有；如果有，那么找到一条好的路径会变得很困难，应为你不知道从哪里看起。）

Dijkstra的算法和最佳优先搜索