A*寻路算法 教程(三)（转）

实现时的注意事项

现在你已经理解了基本的算法，下面将讨论一些你在写自己的程序时要考虑的东西。下面一些材料和我用C++和Blitz Basic写的程序有关，但是那些要点是适用于任何其他语言的。

1.
开放列表的维护：实际上是A*算法中最耗时的因素。每次你处理开放列表时你都要从中找出具有最小F值的方格。有几种方法可以做到。你可以保存所需的路径元素，简单的遍历列表来找出最小F值的方格。这种方法是很简单，但是在路径很长的时候会很慢。也可以改进一下，变成维护一个有序列表，这样在需要最小F值方格的时候仅须获取该有序列表的第一个元素。我在写我那个程序的时候，开始就是用的这个办法。
这种方法很适合于地图不大的情况。但这还不是最快的解决办法。真正追求速度的认真的程序员往往会使用二叉堆。这也是我在我的代码中用的方法。据我的经验，这种方法会比大多数解决方案快至少2－3倍，在路径很长的时候更快（快10倍以上）。如果你有兴趣了解更多二叉堆的内容，去看看我的这篇文章，Using Binary Heaps in A* Pathfinding。


2.
其他单位。如果你仔细看了我的例子代码，你会注意到它完全忽略了地图上的其他单位。我的寻路者实际上是直接穿过彼此的。这样行得通行不通是取决于游戏的。如果你要考虑地图上的其他单位并且它们还能够移动，我建议你在路径寻找算法中忽略它们而另外写一些代码去检测它们是否发生了碰撞。当碰撞发生时，你可以马上生成一个新的路径或者应用一些标准移动规则（比如总是靠右走等等）直到路径上不再有障碍物或，然后再生成一个新的路径。为什么在你最初计算路径的时候就把这些单位考虑进去呢？那其实是因为其他单位也会移动，它们的位置在不停的改变。这样会导致产生一些不可思议的结果，比如某个单位会突然转向来避免一个实际上已经不在那儿的另一个单位，或者撞上一个后来移动到它的预定路径上的单位。
在寻路算法中忽略其他单位意味着你将不得不写一些单独的代码来避免冲突。这完全是由游戏特性决定的。所以我把解决方案留给你自己去琢磨。本文末尾参考文章一节Bryan Stout的一些地方提供了几个解决方案（比如鲁棒式跟踪等等），不妨去看看。


3.
一些提速技巧：你在开发你自己的A*程序或者改变我写的那个时，总会发现这个寻路算法很耗CPU，特别是地图上有大量的寻路者和地图相当大的时候。如果你在网上读过一些资料你会知道这个对于像星际争霸或者帝国时代这样专业的游戏也不例外。当你发现你的寻路算法使你写的东西变慢了的话，可以参考下面这些提速的办法：

• 用小一点的地图或者寻路者少一点。
• 
  不要在同一时间为很多个寻路者计算路径。不如把它们放进一个队列里并分散在几个游戏循环中。如果你的游戏运行时大约是，比如说，40个循环/秒的话，没人会注意到。但是要是有一堆寻路者在同一时间计算路径而导致游戏在短时间内变慢的话，就非常引人注意了。
• 
  将地图的区块划分得大一些。这样会减少搜索路径时的区块总数。如果你够强，可以设计两种以上的寻路系统来适应于路径长度不同的情况。这正是那些专业人士所做的，路径长的时候用大区块，当接近目标路径变短的时候又用小区块来进行精确些的搜索。要是你对这个概念感兴趣，不妨读读我的文章Two-Tiered A* Pathfinding
• 考虑采用路标系统来处理长路径的情况，或者预先处理一些对游戏来说很少变化的路径。
• 对地图进行预处理并计算出哪些区域是从其他地方根本到达不了的。我把这些区域叫做“岛”。实际中这些区域可能是岛也可能是墙围起来的地方。A*算法的一个缺陷是当你在找到这样一个不可达区域的路径时，几乎会把整个地图都搜个遍，直到地图上每一个区块都被搜索过了才会停。这样会浪费很多CPU时间。解决这个问题的办法是预先得出哪些区域是根本不可达的（通过洪泛法或者其他方式），用一个数组记录下这些数据并在寻找路径前先检查一下。在我那个Blitz版本的代码中，我创建了一个地图预处理器来完成这样的处理。这个预处理器还能提前找到可在寻路算法中忽略的死角，因而大大提高了算法速度。

4.
地形多样化的开销：在这个入门教程和我附带的程序中，地形地貌只包括两种情况：可通过的和不可通过的。但是假如还有一些地形那是可以通过的只是移动的开销更大一点呢？比如沼泽、山丘、地牢里的梯子等等呢？这些都是可以通行的地形的例子，只不过比开阔的平地具有更高的开销。类似的，公路地形会比路郊的移动开销小。
这个问题很容易解决。只要在计算给定区块的G值时把地形的开销加上去就行。把某个区块加上额外的开销，A*算法仍然有效。在我描述的那个简单例子里，地形只分可通过和不可通过两种，A*算法会找到最直接最短的路径。但当在一个地形多样化的环境里时，最小开销路径可能会是比较长的一段路程。例如从公路上绕过去显然比直接通过沼泽地开销要小。
还有一个有趣的办法是专业人士们叫做“感应映射”的东西。如同上面描述的多样化地形开销一样，你可以创建一个额外的点数制度并将之应用于AI方面的路径中。假设在一张地图上有一堆家伙在守卫一个山区要道，每次电脑派遣某人通过那条要道时都会被困住。那你就可以创建一个感应地图使得发生很多战斗冲突的那些区块开销增大，以此来告知电脑去选一个更安全的路径，并避免仅凭着是最短路径（但是更危险）就持续派遣人员通过某条路径的愚蠢情形。


5.
处理未探索区域：你有玩过电脑总是知道怎么走，甚至地图都还没探索过的PC游戏吗？由此看来这个路径寻找算法真是好得不现实。还好这个问题可以很容易解决。
方法就是为不同的玩家和电脑（不是每个单位，不然会耗掉好多内存）创建一个独立的“已知可通行”数组。每个数组包含了玩家已探索区域和未知区域的信息，并把未知区域全部视为可通行区域来对待，除非后来发现是其他的地形。使用这种方法的话，移动单位就会绕到死角或犯类似错误，直到它们发现了周围的路。一旦地图都被探索过了，路径寻找算法就会正常运行了。6.
平滑路径：A*算法会得出开销最小路程最短的路径，但没法得到看起来最平滑的路径。看看那个例子的最终路径（图七），该路径的第一步是起始点的右下方的方格。如果第一步是正下方那个方格，那得到的路径不是就要平滑很多吗？
有几种方法可以处理这个问题。如在计算路径的时候你可以给那些改变了路径方向的方格一个额外开销，使其G值增大。这样，你可以沿着所得路径看看哪些取舍能使你的路径看起来更平滑。对于这个话题，可以看看Toward More Realistic Pathfinding（是免费的，但是查看需要注册）来了解更多。


7.
非方格的搜索区域：在上面的例子中，我们用的是简单的二维方格布局。你可以不这样弄，不规则区域也行。想想棋盘游戏Risk和Risk里的那些国家。你可以设计一个那样的寻路的关卡。要做这样的关卡，你得创建一个查找表来存储每个国家对应的邻国，和从一个国家移动到另一个国家的开销G。另外也得选一种计算估计值H的方法。其他的处理就和前面的例子差不多了。只是当对新区域进行检验时，即添加新项目到开放列表中的时候，是从表中查找邻近国家而不是选择邻近方格。
类似的，你可以针对固定地形的地图来创建一个路标系统。路标通常是横穿路径的点，可能是在公路上也可能是在地牢的主隧道里。对于游戏设计者来说，需要提前设置好这些路标。如果两个路标所成的直线路径之间没有障碍物的话就称之为“相邻的”。在Risk游戏的例子中，你会将相邻信息保存在一个查找表中，并会在新增开放列表元素时用到这个查找表。然后你会用到相关的G值（可能通过两个节点间的直线距离得到）和H值（可能通过该节点到终点的直线距离得到）其他的运算就和普通的差不多。
另外一个使用非方格搜索区域的斜视角RPG游戏的例子参见我的文章Two-Tiered A* Pathfinding。

进阶阅读

好了！现在你基本上掌握了基础知识，并对高级的概念也有了些印象。在此我建议把我的代码拿来研究研究。压缩包里有两个版本，分别是C++的和Blitz Basic的。它们的注释都很详细，我想应该很容易理解。下面是链接：

• Sample Code: A* Pathfinder (2D) Version 1.71

如果你没法用C++或者Blitz Basic，在C++版里有两个程序文件可以直接运行。而Blitz Basic版本要在Blitz Basic的网站上下载免费演示版的Blitz Basic 3D才能运行。这里还有Ben O’Neill写的在线示例。
你也应通读一下下面的网页。这些在你读了本文之后应该很好理解了。

• Amit's A* Pages:这是Amit Patel的一篇广为引用的文章。不过如果你没读先读本文的话看他这个可能会有些困惑。非常值得一读。特别是Amit对此的独特观点。
• Smart Moves: Intelligent Path Finding: Gamasutra.com网站上Bryan的这篇文章是需要注册才能阅读的。不过注册是免费的而且为了这篇文章麻烦一点也值得。Bryan用Delphi写的那个程序帮助我了解了A*，那也是我的A*程序的灵感来源。这篇文章也写了一些A*的变种
• Terrain Analysis:这是一篇高阶的文章，不过很有趣，它是由Ensemble Studios的专家Dave Pottinger所写。这家伙负责协调帝国时代II：Age of Kings的开发。要想把这里所有东西都看明白是不可能的，不过它或许会给你自己的项目带来一些有趣的想法。文章还包括一些关于材质贴图，感应映射和其他一些高级AI/路径寻找概念。其中关于“洪泛（flood filling）”的讨论是我的死角和岛屿等地图预处理代码的灵感来源。在我的Blitz Basic版的程序中包含了这个东西。。

其他值得一读的文章：

• aiGuru: Pathfinding
• Game AI Resource: Pathfinding
• GameDev.net: Pathfinding

 

转自:http://www.eb163.com/club/thread-2458-1-3.html