A*方法大全

好，现在你已经看完了整个说明，让我们把每一步的操作写在一起：

把起始格添加到开启列表。
重复如下的工作：
a) 寻找开启列表中F值最低的格子。我们称它为当前格。
b) 把它切换到关闭列表。
c) 对相邻的8格中的每一个？
如果它不可通过或者已经在关闭列表中，略过它。反之如下。
如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
d) 停止，当你
把目标格添加进了开启列表，这时候路径被找到，或者
没有找到目标格，开启列表已经空了。这时候，路径不存在。
保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。
离题一下，见谅，值得一提的是，当你在网上或者相关论坛看到关于A*的不同的探讨，你有时会看到一些被当作A*算法的代码而实际上他们不是。要使用A*，你必须包含上面讨论的所有元素－－特定的开启和关闭列表，用F,G和H作路径评价。有很多其他的寻路算法，但他们并不是A*，A*被认为是他们当中最好的。Bryan Stout在这篇文章后面的参考文档中论述了一部分，包括他们的一些优点和缺点。有时候特定的场合其他算法会更好，但你必须很明确你在作什么。好了，够多的了。回到文章。

实现的注解

现在你已经明白了基本原理，写你的程序的时候还得考虑一些额外的东西。下面这些材料中的一些引用了我用C++和Blitz Basic写的程序，但对其他语言写的代码同样有效。

维护开启列表：这是A*寻路算法最重要的组成部分。每次你访问开启列表，你都需要寻找F值最低的方格。有几种不同的方法实现这一点。你可以把路径元素随意保存，当需要寻找F值最低的元素的时候，遍历开启列表。这很简单，但是太慢了，尤其是对长路径来说。这可以通过维护一格排好序的列表来改善，每次寻找F值最低的方格只需要选取列表的首元素。当我自己实现的时候，这种方法是我的首眩
在小地图。这种方法工作的很好，但它并不是最快的解决方案。更苛求速度的A*程序员使用叫做“binary heap”的方法，这也是我在代码中使用的方法。凭我的经验，这种方法在大多数场合会快2～3倍，并且在长路经上速度呈几何级数提升(10倍以上速度)。如果你想了解更多关于binary heap的内容，查阅我的文章：Using Binary Heaps in A* Pathfinding。
其他单位：如果你恰好看了我的例子代码，你会发现它完全忽略了其他单位。我的寻路者事实上可以相互穿越。取决于具体的游戏，这也许可以，也许不行。如果你打算考虑其他单位，希望他们能互相绕过，我建议在寻路算法中忽略其他单位，写一些新的代码作碰撞检测。当碰撞发生，你可以生成一条新路径或者使用一些标准的移动规则(比如总是向右，等等)直到路上没有了障碍，然后再生成新路径。为什么在最初的路径计算中不考虑其他单位呢？那是因为其他单位会移动，当你到达他们原来的位置的时候，他们可能已经离开了。这有可能会导致奇怪的结果，一个单位突然转向，躲避一个已经不在那里的单位，并且会撞到计算完路径后，冲进它的路径中的单位。
然而，在寻路算法中忽略其他对象，意味着你必须编写单独的碰撞检测代码。这因游戏而异，所以我把这个决定权留给你。参考文献列表中，Bryan Stout的文章值得研究，里面有一些可能的解决方案(像鲁棒追踪，等等)。
一些速度方面的提示：当你开发你自己的A*程序，或者改写我的，你会发现寻路占据了大量的CPU时间，尤其是在大地图上有大量对象在寻路的时候。如果你阅读过网上的其他材料，你会明白，即使是开发了星际争霸或帝国时代的专家，这也无可奈何。如果你觉得寻路太过缓慢，这里有一些建议也许有效：
使用更小的地图或者更少的寻路者。
不要同时给多个对象寻路。取而代之的是把他们加入一个队列，把寻路过程分散在几个游戏周期中。如果你的游戏以40周期每秒的速度运行，没人能察觉。但是他们会发觉游戏速度突然变慢，当大量寻路者计算自己路径的时候。

尽量使用更大的地图网格。这降低了寻路中搜索的总网格数。如果你有志气，你可以设计两个或者更多寻路系统以便使用在不同场合，取决于路径的长度。这也正是专业人士的做法，用大的区域计算长的路径，然后在接近目标的时候切换到使用小格子/区域的精细寻路。如果你对这个观点感兴趣，查阅我的文章 ：Two-Tiered A* Pathfinding。
使用路径点系统计算长路径，或者预先计算好路径并加入到游戏中。
预处理你的地图，表明地图中哪些区域是不可到达的。我把这些区域称作“孤岛”。事实上，他们可以是岛屿或其他被墙壁包围等无法到达的任意区域。A*的下限是，当你告诉它要寻找通往那些区域的路径时，它会搜索整个地图，直到所有可到达的方格/节点都被通过开启列表和关闭列表的计算。这会浪费大量的CPU时间。可以通过预先确定这些区域（比如通过flood-fill或类似的方法)来避免这种情况的发生,用某些种类的数组记录这些信息，在开始寻路前检查它。在我Blitz版本的代码中，我建立了一个地图预处理器来作这个工作。它也标明了寻路算法可以忽略的死端，这进一步提高了寻路速度。
不同的地形损耗：在这个教程和我附带的程序中，地形只有两种－可通过的和不可通过的。但是你可能会需要一些可通过的地形，但是移动耗费更高－沼泽，小山，地牢的楼梯，等等。这些都是可通过但是比平坦的开阔地移动耗费更高的地形。类似的，道路应该比自然地形移动耗费更低。
这个问题很容易解决，只要在计算任何地形的G值的时候增加地形损耗就可以了。简单的给它增加一些额外的损耗就可以了。由于A*算法已经按照寻找最低耗费的路径来设计，所以很容易处理这种情况。在我提供的这个简单的例子里，地形只有可通过和不可通过两种，A*会找到最短，最直接的路径。但是在地形耗费不同的场合，耗费最低的路径也许会包含很长的移动距离－就像沿着路绕过沼泽而不是直接穿过它。
一种需额外考虑的情况是被专家称之为“influence mapping”的东西（暂译为影响映射图）。就像上面描述的不同地形耗费一样，你可以创建一格额外的分数系统，并把它应用到寻路的AI中。假设你有一张有大批寻路者的地图，他们都要通过某个山区。每次电脑生成一条通过那个关口的路径，它就会变得更拥挤。如果你愿意，你可以创建一个影响映射图对有大量屠杀事件的格子施以不利影响。这会让计算机更倾向安全些的路径，并且帮助它避免总是仅仅因为路径短(但可能更危险)而持续把队伍和寻路者送到某一特定路径。
处理未知区域：你是否玩过这样的PC游戏，电脑总是知道哪条路是正确的，即使它还没有侦察过地图？对于游戏，寻路太好会显得不真实。幸运的是，这是一格可以轻易解决的问题。
答案就是为每个不同的玩家和电脑（每个玩家，而不是每个单位－－那样的话会耗费大量的内存）创建一个独立的“knownWalkability”数组，每个数组包含玩家已经探索过的区域，以及被当作可通过区域的其他区域，直到被证实。用这种方法，单位会在路的死端徘徊并且导致错误的选择直到他们在周围找到路。一旦地图被探索了，寻路就像往常那样进行。
平滑路径：尽管A*提供了最短，最低代价的路径，它无法自动提供看起来平滑的路径。看一下我们的例子最终形成的路径（在图7）。最初的一步是起始格的右下方，如果这一步是直接往下的话，路径不是会更平滑一些吗？
有几种方法来解决这个问题。当计算路径的时候可以对改变方向的格子施加不利影响，对G值增加额外的数值。也可以换种方法，你可以在路径计算完之后沿着它跑一遍，找那些用相邻格替换会让路径看起来更平滑的地方。想知道完整的结果，查看 Marco Pinter 发表在 Gamasutra.com 的 一篇文章：Toward More Realistic Pathfinding (免费，但是需要注册)。
非方形搜索区域：在我们的例子里，我们使用简单的2D方形图。你可以不使用这种方式。你可以使用不规则形状的区域。想想冒险棋的游戏，和游戏中那些国家。你可以设计一个像那样的寻路关卡。为此，你可能需要建立一个国家相邻关系的表格，和从一个国家移动到另一个的G值。你也需要估算H值的方法。其他的事情就和例子中完全一样了。当你需要向开启列表中添加新元素的时候，不需使用相邻的格子，取而代之的是从表格中寻找相邻的国家。
类似的，你可以为一张确定的地形图创建路径点系统，路径点一般是路上，或者地牢通道的转折点。作为游戏设计者，你可以预设这些路径点。两个路径点被认为是相邻的如果他们之间的直线上没有障碍的话。在冒险棋的例子里，你可以保存这些相邻信息在某个表格里，当需要在开启列表中添加元素的时候使用它。然后你就可以记录关联的G值（可能使用两点间的直线距离），H值（可以使用到目标点的直线距离），其他都按原先的做就可以了。
另一个在非方形区域搜索RPG地图的例子，查看我的文章：Two-Tiered A* Pathfinding。

进一步的阅读

好，现在你对一些进一步的观点有了初步认识。这时，我建议你研究我的源代码。包里面包含两个版本，一个是用C++写的，另一个用Blitz Basic。顺便说一句，两个版本都注释详尽，容易阅读，这里是链接。
例子代码：A* Pathfinder (2D) Version 1.71

如果你既不用C++也不用Blitz Basic,在C++版本里有两个小的可执行文件。Blitz Basic可以在从Blitz Basic网站免费下载的 litz Basic 3D(不是Blitz Plus)演示版上运行。Ben O''Neill提供一个联机演示可以在这里找到。

你也该看看以下的网页。读了这篇教程后，他们应该变得容易理解多了。

Amit 的 A* 页面：这是由Amit Patel制作，被广泛引用的页面，如果你没有事先读这篇文章，可能会有点难以理解。值得一看。尤其要看Amit关于这个问题的自己的看法。
Smart Moves：智能寻路：Bryan Stout发表在Gamasutra.com的这篇文章需要注册才能阅读。注册是免费的而且比起这篇文章和网站的其他资源，是非常物有所值的。Bryan用Delphi写的程序帮助我学习A*，也是我的A*代码的灵感之源。它还描述了A*的几种变化。
地形分析：这是一格高阶，但是有趣的话题，Dave Pottinge撰写，Ensemble Studios的专家。这家伙参与了帝国时代和君王时代的开发。别指望看懂这里所有的东西，但是这是篇有趣的文章也许会让你产生自己的想法。它包含一些对mip-mapping，influence mapping以及其他一些高级AI/寻路观点。对"flood filling"的讨论使我有了我自己的“死端”和“孤岛”的代码的灵感，这些包含在我Blitz版本的代码中。
其它一些值得一看的网站：

aiGuru: Pathfinding
Game AI Resource: Pathfinding
GameDev.net: Pathfinding
其它参考文章：

Artificial Intelligence:Pathfinding and Searching
Featured Articles:Featured Articles