游戏中经常会用到寻径算法，最简单的寻径算法就是走直线或者总是往最接近目的地的方向走，遇到障碍物就不可以继续前进。这样虽然得到的路线一定是最短的，但是一旦碰到障碍物就被卡住了，显然不够灵活。BFS、A*是最常见的路径寻找算法。BFS算法从起始点一直向周围辐射扩张盲目地寻找目的地，虽然找到的路径一定是最短路，但是效率不高。A*算法加入了对每个发现了的位置的评估，选择与目的地接近的方向搜索，比较灵活，效率也很高。

A*算法是改进的BFS（宽度优先搜索）算法，区别在于A*算法在搜索下一个点的时候，会在等待搜索的点中寻找一个最优的。这里最优的意味着，最容易到达目的地。最简单的一个评估方法是，看当前位置到目的地还有多远。

设f(x, y)为对位置(x, y)的评估函数，g(x, y)为从起始点到当前点所经过的路程，h(x, y)为从当前点到目的地还需要的大概路程。则f的表达式可以为f(x, y) = g(x, y) + h(x, y)

以下面这个地图为例，比较BFS和A*的差异。

19 33
 ############################### 
 #                       #     # 
 #                       #     # 
 #                       #  @  # 
 #                       #     # 
 #                       #     # 
 #     #     #######     ### ### 
 #     #     #           #     # 
 #     #     #           #     # 
 #     #     #        x  #     # 
 #     #     #           #     # 
 #     #     #           #     # 
 #     #     #######     #     # 
 #                             # 
 #                             # 
 #                             # 
 #                             # 
 #                             # 
 ############################### 

地图中，#表示障碍物，x表示起始位置，@表示终点，.表示搜索过的位置，*表示最终找到的路径。
假设地图上的怪物只可以上下左右四个方向移动。
继续阅读 →