github源码：https://github.com/boycy815/fastAStar
这几天在天地会上看到有算法比赛，比的是谁实现的A*寻路速度快，虽然比赛不是那么正规，但是这种展现实力的机会咱也不能落后是不，于是咱也折腾出一个算法提交上去，帖子在此：http://bbs.9ria.com/forum.php?mod=redirect&goto=findpost&ptid=172851&pid=1668442&fromuid=64655
128*128地图规模下1000个随机障碍，在我的电脑上一般不会超过1毫秒，只有一些奇葩的情况下会是1毫秒，没出现过2毫秒的情况。然后我尝试过5000个随机障碍，一般不超过2毫秒，偶尔2毫秒，不存在路径的情况下一般不超过8毫秒。
另外，虽然产生的路径看起来是8方向的，实际计算的时候是使用4方向展开，再通过简单的方式合并四个斜方向和同方向路径，让路径尽量看起来自然。
合并斜方向 合并同方向
鉴于参赛程序写得过于装逼，部分同学反映看着累，所以也就有了本文。本文不打算讲得太细致，默认读者已经掌握基本的数据结构并了解了A*搜索的大概流程。不了解A*搜索的请移步：http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html
启发式搜索
A*搜索是一种启发式搜索（可移步：http://baike.baidu.com/view/1237243.htm）。我们通常做寻路的时候，是把起点作为一个树结构的根节点进行遍历，直到找到终点。对于树的遍历，通常的我们有深度优先遍历和广度优先遍历，这个是数据结构的基础。但是通过这些方法做寻路往往显得盲目，有时候眼看终点就在眼前，我们仍然需要先对其他节点展开遍历。然而启发式搜索虽然对树做的也是遍历，可它对节点展开的顺序既不是深度优先也不是广度优先，而是“估计值优先”。这个估计值是树中每个节点绑定的一个值，这个值通过启发式结合节点的一些属性计算出来。好的启发式能产生对搜索目标有导向性的估计值，估计值更优的节点在概率上应更接近搜索目标。通过启发式我们能优化树的节点展开顺序从而更早找到目标节点，减少无谓的节点展开数量，提高效率。
A*的启发式
A*搜索采用f(n) = g(n) + h(n)作为启发式，其中g(n)为起点通过某个路径到达地图格子n的确定耗损，h(n)为地图格子n到达终点的估计耗损。我们通常采用的h(n)有曼哈顿式，欧几里得式等。曼哈顿式为h(n) = dx + dy，其中dx和dy为n点到终点的水平和竖直距离。欧几里得式为h(n) = sqrt(dx^2 + dy^2)，代表n点到终点的欧几里得距离。这两个启发式的特点会在下文中讲到。
最佳路径定理
当任何格子n，其h(n)不大于格子其到终点的最小实际耗损时，A*搜索必然会得到最佳路径。我们可以这么理解：当一个格子a为最佳路径上的节点，其当前耗损为i，其到终点的实际耗损为j（假设已经知道），那么最佳路径的耗损为i+j，那么当h(a)不大于j时，f(a)将不大于i+j，在路径搜寻过程中，可能存在很多通往终点的路径，只要其路径长度不是最佳，那么当到达终点（估计耗损等于实际耗损），其耗损必将大于最佳路径的耗损，根据“估计值”小先展开的顺序，f(a)由于不大于最佳路径耗损，所以必定会被先展开，同理所有最佳路径上的格子都会在得到最佳路径之前被展开，所以此定理就成立了。
高效启发式原则
h(n)值的大小将影响A*搜索的效率，更大的值将更有效得减少无谓的分支展开，更快得找到终点。其原因是增加启发式中估计值的权重，可让启发式对消耗的路程不敏感而对终点的方向更加敏感。在不得已时不会去展开大方向不对的格子。但是如果h(n)大于b格子到终点的最小路径损耗，那么寻找出来的路径就不一定是最短。所以结合最佳路径定理，从搜索效率和质量上看，h(n)等于n格子到终点的最小实际损耗是最好的。
启发式选择
从上面的规律来看，曼哈顿式似乎优于欧几里得式。曼哈顿式在没有障碍的时候满足h(n)等于n格子到终点的最小实际损耗。而欧几里得式似乎得到的值小了一点。但是通常人们更愿意使用欧几里得式，因为欧几里得式会优先选择n格子到终点连线上的展开节点。而曼哈顿式对n格子到终点范围内的点都一视同仁。
如图曼哈顿式在n点和终点围城的矩形启发式值都相同，由于程序的循环顺序是固定的，所以会产生这样的路径，虽然正确但不符合人的习惯。
而欧几里得式会在如图的对角线上有更低的启发式值，所以程序会优先选择对角线位置的路径，如果将得到的路径合并斜方向会得到非常符合人习惯的路径。虽然曼哈顿式在效果上逊色于欧几里得式，但是由于曼哈顿式计算简单，拥有不少良好的性质非常适合优化，并且其效果不好的问题可以在前期预处理地图的时候解决，故程序中使用曼哈顿式。