* 尽量使用更大的地图网格。这降低了寻路中搜索的总网格数。如果你有志气，你可以设计两个或者更多寻路系统以便使用在不同场合，取决于路径的长度。这也正是专业人士的做法，用大的区域计算长的路径，然后在接近目标的时候切换到使用小格子/区域的精细寻路。如果你对这个观点感兴趣，查阅我的文章Two-Tiered A* Pathfinding。(译者注：译文 :A*分层寻路)
* 使用路径点系统计算长路径，或者预先计算好路径并加入到游戏中。
* 预处理你的地图，表明地图中哪些区域是不可到达的。我把这些区域称作“孤岛”。事实上，他们可以是岛屿或其他被墙壁包围等无法到达的任意区域。A*的下限是，当你告诉它要寻找通往那些区域的路径时，它会搜索整个地图，直到所有可到达的方格/节点都被通过开启列表和关闭列表的计算。这会浪费大量的CPU时间。可以通过预先确定这些区域（比如通过flood-fill或类似的方法)来避免这种情况的发生,用某些种类的数组记录这些信息，在开始寻路前检查它。
* 在一个拥挤的类似迷宫的场合，把不能连通的节点看作死端。这些区域可以在地图编辑器中预先手动指定，或者如果你有雄心壮志，开发一个自动识别这些区域的算法。给定死端的所有节点可以被赋予一个唯一的标志数字。然后你就可以在寻路过程中安全的忽略所有死端，只有当起点或者终点恰好在死端的某个节点的时候才需要考虑它们。
7. 维护开启列表：这是A*寻路算法最重要的组成部分。每次你访问开启列表，你都需要寻找F值最低的方格。有几种不同的方法实现这一点。你可以把路径元素随意保存，当需要寻找F值最低的元素的时候，遍历开启列表。这很简单，但是太慢了，尤其是对长路径来说。这可以通过维护一格排好序的列表来改善，每次寻找F值最低的方格只需要选取列表的首元素。当我自己实现的时候，这种方法是我的首选。
在小地图。这种方法工作的很好，但它并不是最快的解决方案。更苛求速度的A*程序员使用叫做二叉堆的方法，这也是我在代码中使用的方法。凭我的经验，这种方法在大多数场合会快2～3倍，并且在长路经上速度呈几何级数提升(10倍以上速度)。如果你想了解更多关于二叉堆的内容，查阅我的文章，Using Binary Heaps in A* Pathfinding。(译者注：译文：在A*寻路中使用二叉堆)
另一个可能的瓶颈是你在多次寻路之间清除和保存你的数据结构的方法。我个人更倾向把所有东西都存储在数组里面。虽然节点可以以面向对象的风格被动态的产生，记录和保存，我发现创建和删除对象所增加的大量时间，以及多余的管理层次减慢的整个过程的速度。但是，如果你使用数组，你需要在调用之间清理数据。这中情形你想做的最后一件事就是在寻路调用之后花点时间把一切归零，尤其是你的地图很大的时候。
我通过使用一个叫做whichList(x,y)的二维数组避免这种开销，数组的每个元素表明了节点在开启列表还是在关闭列表中。尝试寻路之后，我没有清零这个数组。取而代之的是，我在新的寻路中重置onClosedList和onOpenList的数值，每次寻路两个都+5或者类似其他数值。这种方法，算法可以安全的跳过前面寻路留下的脏数据。我还在数组中储存了诸如F,G和H的值。这样一来，我只需简单的重写任何已经存在的值而无需被清除数组的操作干扰。将数据存储在多维数组中需要更多内存，所以这里需要权衡利弊。最后，你应该使用你最得心应手的方法。
8. Dijkstra的算法：尽管A*被认为是通常最好的寻路算法(看前面的“题外话”),还是有一种另外的算法有它的可取之处-Dijkstra算法。Dijkstra算法和A*本质是相同的，只有一点不同，就是Dijkstra算法没有启发式(H值总是0)。由于没有启发式，它在各个方向上平均搜索。正如你所预料，由于Dijkstra算法在找到目标前通常会探索更大的区域，所以一般会比A*
更慢一些。
那么为什么要使用这种算法呢？因为有时候我们并不知道目标的位置。比如说你有一个资源采集单位，需要获取某种类型的资源若干。它可能知道几个资源区域，但是它想去最近的那个。这种情况，Dijkstra算法就比A*更适合，因为我们不知道哪个更近。用A*，我们唯一的选择是依次对每个目标许路并计算距离，然后选择最近的路径。我们寻找的目标可能会有不计其数的位置，我们只想找其中最近的，而我们并不知道它在哪里，或者不知道哪个是最近的。
进一步的阅读
好，现在你对一些进一步的观点有了初步认识。这时，我建议你研究我的源代码。包里面包含两个版本，一个是用C++写的，另一个用Blitz Basic。顺便说一句，两个版本都注释详尽，容易阅读，这里是链接。
* 例子代码： A* Pathfinder (2D) Version 1.9
如果你既不用C++也不用Blitz Basic,在C++版本里有两个小的可执行文件。Blitz Basic可以在从Blitz Basic网站免费下载的Blitz 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/寻路观点。对\filling\的讨论使我有了我自己的“死端”和“孤岛”的代码的灵感，这些包含在我Blitz版本的代码中。 其他一些值得一看的网站：
* aiGuru: Pathfinding
* Game AI Resource: Pathfinding * GameDev.net: Pathfinding
我同样高度推荐下面这几本书, 里面有很多关于寻路和其他AI话题的文章。 它们也附带了实例代码的CD。这些书我都买了。另外，如果你通过下面的链接购买了它们，我会从Amazon得到几个美分
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库A星算法详解-通俗易懂初学者必看(4)在线全文阅读。
相关推荐：