A*路径寻找算法
在这一章中，我们将要讨论A*寻路算法的基本原理。寻路是游戏AI最基本得问题之一。糟糕的寻路会让游戏中的角色看起来非常的不真实而且愚蠢。游戏中的人物无法自然的通过一组障碍物将会非常影响游戏的效果。有效的处理寻路问题将会给玩家愉快和身临其境的感觉。
幸运的是，A*算法为寻路问题提供了很好的解决办法。A*算法是在游戏开发中最常见的寻路算法，因为A*算法能够保证从一个指定的初始点找到一个存在的路径通往指定终点。当然它的高效性也是它被广泛使用的原因。当你不是在处理非常特殊的脚步情节时请尽量使用A*寻路算法。比如，当起点和终点直接没有任何的障碍物并且可以构成一条非常清楚的连线时就无需再用A*算法了，只要用直线连接两点就可以了。如果CPU的周期非常短是A*也就不是最有效的算法了。虽然它很高效但是它还是会占用一定得CPU周期，除非你要同时对大量的游戏角色进行寻路算法，就可以考虑牺牲CPU周期来换取寻路效率。总的来说A*算法是处理大部分寻路问题的最佳选择。但不幸的是，对于一个初学者来说A*算法是非常难以理解的。在本章中我们将深入的去探索A*算法是怎么去找到一条连接起始点和终点的路径的。一步一步去了解A*算法的构造将有助于我们揭开它的神秘面纱。
7.1定义搜索区域
寻路的第一步是定义搜索范围。我们需要一些方式去表现一个游戏世界从而可以在上面进行最短路径的超找。这个游戏世界需要游戏内的人物和物体都可占用的点，而寻路算法的工作就是找出连接两点并且躲避了障碍物最佳的路径。在真正的游戏中如何表现这些点或路径则取决于游戏的类型。有些情况下，游戏世界要尽量的简单。比如在一个环境连续的游戏中游戏世界是由大量的角色可占用的点构成，那么A*算法在这里就不适用了。他的游戏世界范围太大，当如果搜索范围可以缩小的话A*算法任然是可以用的，这将涉及到如何在游戏世界中铺设这些点。至此我们能够找出一个两点之间的最佳路径，但是不是在游戏世界中的任何两点都能够找到这么一条最佳路径。这一点在图7-1中阐明
Figure 7-1. Simplifying the search area
图7-1中的坦克可以占据坐标系中的任意一个点，为了更好的展示寻路算法我们只是在游戏世界中铺设很简单的几个点。这些点可以直接表示坦克的位置。我们需要尽量的减少我们所要管理（搜索）的点的数量，也就是说我们需要减小搜索的范围。
当然我们需要维持一个点的链表。搜索算法需要知道这些点是怎么连接的。当我们知道了点是怎么连接的话我们就能通过A*算法计算出连接任意两点的路径。当然点越多就需要更长的计算时间。如果寻路占了太多的CPU周期，那么我们就要考虑缩小搜索范围来减少需计算的点的数量了。
另一方面，如果游戏世界是在一个平面内这将非常有利于A*算法，当然这个世界千万不要太大。在平面中能够很好的对世界进行分割，就像Figure7-2一样每一块代表的是一个点。
Figure 7-2. Tiled search area
在如图7-2中的平面环境非常适合于使用A*算法。每一小块都代表搜索区域中的一个点。你不需要去维护一个节点关系的链表，因为他们已经在图中表现的非常规则了，就是一个挨这一个。如果需要的话你还可以在进行简化，让几个小块表示一个点。在一个非常大的平面中我们把多个单位的面积表示成为一个点则寻路算法将搜索将变的快速。如果在这些单位中没有找到路径你就可以认为没有合理的路径存在。
7.2开始搜索
一旦我们确定了一个小的搜索范围那么我就可以开始进行搜索了。我们将使用A*算法在两个任意节点中找到一条最短的路径。在此例中我们将使用一个已经分块的环境。环境中的每一块代表一个搜索节点当然有写节点代表的是障碍物。我们将使用A*算法找到一条绕过了障碍物的最短路径。例7-1显示了我们将要学习的基本算法。
Example 7-1. Example 7-1. A* pseudo code
将起始节点放入open表中
当open表为空
{
当前的节点=open表中到达目标节点代价最小的节点
If 当前节点=目标节点
路径找到
Else
把当前节点放到closed表中
检查当前节点的每个相邻节点
For each 相邻节点
如果该节点吧在open表中也不在closed表中并且也不是障碍物则把它放到open表中并计算其代价
}
在Example7-1中的代码的一些细节可能会让读者觉得和算法不相关，但在接下来的深入学习中我们将会去理解它的意思。
图7-3展示了我们要用到的平面搜索区域。中间的蜘蛛网就代表的是起点位置，而小人则代表的是终点位置，那些黑色的方块代表的是障碍物，蜘蛛只能在白色的方块中行走。
Figure 7-3. Creating a tiled search area
就像其他所有的寻路算法，A*算法需要做的是找到起始点和终点之间的一条路径。我们首先是从与起始点相邻的点开始搜索。就拿本例来说，我们首先就是从起始点开始然后再对它的相邻点进行搜索处理。这种向相邻的发散直到我们找到终点后才结束。当然，在我们的搜索之前，需要维护一张表，表中记录了每一个我们需要去搜索的点。在A*算法中这个表就是open表。我们有open表中的一个点开始，这个点就是我们的起始点，接下来我们将向open表中加入更多的节点。
一旦我们建立了open表，我们将遍历表中的点和与这些点相邻的节点。这样做事为了坚持这些相邻的点是否是一条有效路径中的一点。我们首先是检查这些相邻的点是不是可以让游戏角色在上面行走也就是说看它是不是障碍物。一条公路是有效的路径，但是对于中间有墙壁的路肯定是无效的。我们将继续去检测这8个相邻节点，然后把有效的节点放入open表中。如果一个节点代表的是障碍物我们通常是忽略它不把它加入open表。表7-4展示了我们需要去检测的点。
Figure 7-4. Adjacent tiles to consider
除了open表，A*算法还包含了一个closed表。closed表中装的是那些已经被检测并且被认为是没必要再检测的节点。通常情况下如果一个点的其他相邻点都被检测了则这个点将被放进closed表。入Figure7-5所示，我们已经把与其实点相邻的所有点全部检测了一遍，则把起始点放进closed表中。
Figure 7-5. Moving the starting tile to the closed list
因此，如图7-5所示，我们有8个节点被放进了open表而同时有一个节点从open表中移除了。到目前为止我们展示了一个A*算法的循环迭代，当然我们还需要做些其他的事情。我们需要一种方法来把这些节点连接起来。Open表中维持了一个角色可走的节点的链表，但是我们还要知道它是怎么连接的。我将追踪open表中节点的parent节点来达到我们的目的。一个parent节点是走到当前节点所经过的上一个节点。就如图7-6所示，在循环的第一次迭代中，每个节点都把起始节点当做parent节点。
Figure 7-6. Linking to the parents
最终我们将通过追溯parent节点的方法找到从终点到起始点的路径。我们需要做很多次的迭代才能到达终点。
让我们再回到算法的过程中来，我们需要在新的open表中选择一个节点出来。在第一次迭代中，open表中只有一个节点我们毫无疑问的选择了它，但现在我们有8个节点在open表中，我们要选择哪一个节点呢？接下来我们将对open表中的每一个点进行代价的评估。
//---------------------------------------这个中文版网上没找到 所以就决定自己翻译 诚求游戏爱好者共同翻译-------------------------------------