估计是因为我在上大学时在网上留过一篇文章，里面有一个简单的使用 A* 算法寻路的源程序，导致了这近七年来，不段的收到 email 和我讨论这个算法。
对，毫不夸张。那个简陋的代码。在七年前我随手写出来扔在网上后，已经遍布中文网络世界的犄角旮旯，让我在痛恨那段代码的时候，想收回都不可能。
我最大的困惑在于，为什么课堂上最为基础的算法知识，却有如此多的人行入误区。难道写游戏的程序员都不去读读基本的课本？
A* ，读作 A-Star 。它仅仅是一个启发式搜索算法。就是说在一个可以被穷举的有限解空间集中，用比较有效的方法（主要是利用估价函数）求出最优解的算法。A* 跟寻路算法没有太多关系，我们只是借助了这个方法来解决寻路这个问题，正如四则运算对于无数的数学题一样，它只是一个基本工具。寻路算法本身有很多种，我们找到算法后，借助 A* 这个工具实现这个算法而已。
我的那篇文章中提到的，也是传统意义上的地图寻路，其实依据的是这样一种算法：把地图分成若干个格子，把起始点的格子上标作 0 。然后根据将周围一圈可以通畅的格子上标为1。然后再把所有标上 1 的格子周围可以通达的格子标为 2 ，当然，如果那些格子上已经有过数字了（一定比 2 小）就不用标了。
如此反复跌代下去，我们地图上的终点只要可以通达，就一定会被标上数字。而这个数字就是理论最短的距离，而标记过的每个格子都有一个前导的入口（即它由附近一个比它小 1 的格子引导过来）整个标记的过程逆推，也就找到了最短路径。
这种一步步尝试的过程，就是一种搜索过程。如果加上启发函数，不让它盲目的寻找，就衍生出很多启发式搜索算法。A* 是其中的一种。之所以加一个 * 号，是因为它的启发式函数是有限制的，这个限制确保它能找到绝对最优解，去掉这个限制，就是 A 算法了。
我们可以看到，把地图分格子，给格子间的路径一个权值（前面的例子中，格子间的距离都是相等的，我们也可以根据地形划分成不等的距离，即权值，或者定义单向道路，这都是可以的），这是解决寻路问题的关键，但都不是 A* 算法的范畴。
如果你想出某种算法，比如把地图划分成不规则的区域，或者把地图矢量化。依然可以再此基础上用 A* 算法这个工具来从中求到最优解。如果想别的方法来寻路，比如拟人的判断，预设路点等等，甚至按走迷宫的方法一样，分叉右转，碰壁回头，那些可以算是对分格寻路方法的一些改进，却都不关 A* 什么事情。
A* 算法理论上是时间最优的，不过我们可以通过选择一个更好的估价函数，或是减少了解空间来提高性能。 A* 算法也有最大的缺点就是，空间需求太大。我们可以用一些时间换空间的方法改进。但是如果不存在解（比如在寻路问题中，根本不存在一条通达的路），采用 A* 算法求解，势必会穷举所有的可能。所以一般在游戏里，我们一般会采用额外的手法避免这个问题。
ps. 如果用 waypoint 的方法来解决寻路问题，实际上将地图化成了一个图，经典的最段路径算法是 dijkstra 算法。若是把地图的阻挡物用凸多边形描述，有一道 10 年前的 ACM 赛题可以参考：Cutting Corners。
评论