【游戏编程】A*寻路算法原理及编程实现（C++类封装）
广度优先搜索和深度优先搜索都属于盲目型搜索算法，在选择下一个搜索节点的时候没有一个准则，去选择最优的。很多情况下需要会穷举整个空间，因此只适用于规模较小的搜索。因此需要用到另外一种算法---启发式搜索。
一、A*算法原理
启发式搜索就是在状态空间中对每一个搜索位置进行评估，得到最好的位置，再从这个位置进行搜素直到目标。这样可以省略大量无谓的搜索路径。在启发式搜索中，对位置的估计尤其重要，采用不同的估计函数会有不同的效果。
启发式搜索中的估价函数为：
f(n) = g(n) + h(n)
f(n):节点n的估价函数。
g(n)：从起始点到n节点的实际代价。
h(n)：从节点n到目标节点最佳路径的估计代价。
在这里，h(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)才可（这一点特别的重要），即小于n到目标的实际代价值。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法，否则就不是A*算法。在这种情况下，搜索的范围大，效率低，但是能得到最优解。如果估价值>实际代价，搜索范围小，效率高，但是不能保证得到最优解。
注意：估价值与实际代价值越接近，估价函数选取得就越好。
关于h(n)启发函数的信息性的问题
h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。
关于启发函数h(n)的相容性
如果h(n)满足h(n1) - h(n2) <= c(n1,n2)，其中c(n1,n2)是n1节点到n2节点的实际代价，则称h(n)是相容的。也就是说状态转移时，下界h的减小值最多等于状态转移的实际代价，其实就是要求h不能减小得太快。
那么，对于节点n1以及其后继节点n2，有：
f(n1) = g(n1) + h(n1)
f(n2) = g(n2) + h(n2)
又由于：
g(n2) = g(n1) + c(n1,n2)，推导出：
f(n2) = g(n1) + c(n1,n2) + h(n2)
如果h(n)是相容的，则有h(n1) <= h(n2) + c(n1,n2)，两边同时加上g(n1)，推导出：
h(n1) + g(n1) <= h(n2) + g(n2) + c(n1,n2)，也就是：
f(n1) <= f(n2)
可以看出，如果启发函数h(n)相容，那么估价函数f(n)单调非递减。就是说按照此算法搜索最先生成的路径一定是最短的。这样的话，搜索过程中就不再需要维持一个CLOSED表，只需维护一个已访问节点表OPEN表。
在选择启发函数的时候，最好选择相容的启发式函数。
A星算法步骤：
1，把起始格添加到开启列表。
2，重复如下的工作：
a) 寻找开启列表中F值最低的格子。我们称它为当前格。
b) 把它切换到关闭列表。
c) 对相邻的8格中的每一个？
* 如果它不可通过或者已经在关闭列表中，略过它。反之如下。
* 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
* 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
d) 停止，当你
* 把目标格添加进了关闭列表(注解)，这时候路径被找到，或者
* 没有找到目标格，开启列表已经空了。这时候，路径不存在。
3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。
二、A*算法编程实现
本文通过迷宫寻路实例，实现了A*算法的C++类封装。
迷宫地图：
起始点是绿色方格，目标点是景色方格，蓝色方格表示障碍物，不可通过。
在搜索过程中，横向移动或者纵向移动的代价都是10，对角线上的移动代价是14.需要注意的是：障碍物的角落不可通过。
将迷宫信息写在一个文本文件里面：
第一行的两个整数代表迷宫的行数和列数。第二行是起始点和目标点的坐标（x,y）。x是所在的行，y是所在的列（均以0开始计算）。
接下来便是迷宫的具体信息，0表示可以通过，1表示障碍物。
下面贴出代码，如有错误，欢迎批评指正（邮箱：xiajunhust@gmail.com）。
程序代码（C++）：
AStarPathFinding.h：
注意：'#'代表该节点是路径上的点。
参考资料：
A*寻路初探 GameDev.net
