文档介绍：. 浅谈游戏自动寻路 A* 算法寻路是游戏中非常重要的一个元素, 如何找到一条最短的路径是程序需要设计的算法,现在最为流行的寻路算法是 A* 算法。 A* 算法与状态空间搜索结合的相当紧密。状态空间搜索, 就是将问题求解的过程表现为从初始状态到目标状态寻找这个路径的过程, 通俗的说就是在解一个问题的时候找到一条解题过程可以从求解的开始到问题的结束。由于求解过程中求解条件的不确定与不完备性使得问题的求解过冲中的分支有很多, 这就产生了多条求解的路径, 这些路径过程一个图这个图就是状态空间。问题的求解时机上就是在这个图中找个一个路径可以从开始到结束,这个过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先, 广度优先是从初始状态一层一层的向下找, 知道找到结果目标为止, 深度优先是按照一定的顺序先查找完一个分支再查找另一个分支, 知道找到目标结果为止。这两种搜索方法有的很大缺陷是它们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很适合的算法, 但是当空间很大并且不可预测的情况下就不可取。这个时候这两种算法的效率太低甚至有时是无法完成, 所以要用到另一种算法--- 启发式搜索。启发式搜索就是在状态空间中对每一个搜索为止进行评估,指导找到最好的为止, . 再从这个位置进行搜索直到目标位置为止。在启发式搜索中对为止的评估是十分重要的,采用不同的估价可能有不同的结果。启发式搜索中的估价函数表示为: f(n)=g(n)+h(n) 其中 f(n) 是节点 n 的估价函数, g(n) 是在状态空间中从初始点到 n 节点的实际代价, h(n) 是从 n 节点到目标节点最佳路径的估价代价。这个里主要是 h(n) 体现了搜索的启发信息,因为 g(n) 是己知的。换个说法就是 g(n) 代表了索索的广度优先趋势但是当 h(n)>>g(n) 时,可以省略 g(n) ,从而提高效率。启发式搜索其实也有很多算法, 比如局部择优搜索, 最好优先搜索等。 A* 也是如此, 这些算法都启用了启发函数, 但在具体的选取最佳搜索节点时的策略不同。比如局部择优算法就是在搜索的过程中选取了最佳节点候舍弃了其他的兄弟节点, 父亲节点并且一直搜索下去。这种搜索结果很明显, 由于舍弃了其他的节点因此可能也把最佳的节点舍去偶尔。最好优先就聪明一点搜索的时候并没有舍去节点, 除非该节点是死节点。在没一步的估价中都吧当前的节点和以前的节点的估价值进行比较从而得到最佳节点, 这样防止了最佳节点的丢失。 A* 算法也是一种最好优先的算法,只是加上了一些特定的约束条件,由于在一些问题求解时,希望能够求解出状态空间搜索的最短路径也就是用最快的方法求解出问题, A* 算法的目的就是这样。其估价的函数可以表示为: f'(n)=g'(n)+h'(n) 这里的 f'(n) 是估价函数, g'(n) 是起点到终点的最短路径值, h'(n) 是n 到目标的最短路径的启发值。由于 f'(n) 是无法提前预先知道的,因此用前面的估价函数 f(n )做近似 g(n) 代表 g'(n) , 但是 g(n) ≥ g'(n) 才可以通常都是大于所以不要考虑, 但是 h(n) 代替 h'(n) 时候需要 h(n) ≤ h'(n) 才可以。可以证明应用这样的评估函数是可以找到最短路径的,因此应用这种评估函数的最好的优先算法