A*, A Star A星算法详解( 七 ) _a星算法

类似的，你可以为一张确定的地形图创建路径点系统，路径点一般是路上，或者地牢通道的转折点。作为游戏设计者，你可以预设这些路径点。两个路径点被认为是相邻的如果他们之间的直线上没有障碍的话。在冒险棋的例子里，你可以保存这些相邻信息在某个表格里，当需要在开启列表中添加元素的时候使用它。然后你就可以记录关联的G值（可能使用两点间的直线距离）， H值（可以使用到目标点的直线距离），其他都按原先的做就可以了。
Amit Patel 写了其他方法的摘要。另一个在非方形区域搜索RPG地图的例子，查看我的文章Two- A*。(译者注：译文： A*分层寻路)
6. 一些速度方面的提示：当你开发你自己的A*程序，或者改写我的，你会发现寻路占据了大量的CPU时间，尤其是在大地图上有大量对象在寻路的时候。如果你阅读过网上的其他材料，你会明白，即使是开发了星际争霸或帝国时代的专家，这也无可奈何。如果你觉得寻路太过缓慢，这里有一些建议也许有效：
* 使用更小的地图或者更少的寻路者。
* 不要同时给多个对象寻路。取而代之的是把他们加入一个队列，把寻路过程分散在几个游戏周期中。如果你的游戏以40周期每秒的速度运行，没人能察觉。但是当大量寻路者计算自己路径的时候,他们会发觉游戏速度突然变慢。
* 尽量使用更大的地图网格。这降低了寻路中搜索的总网格数。如果你有志气，你可以设计两个或者更多寻路系统以便使用在不同场合，取决于路径的长度。这也正是专业人士的做法，用大的区域计算长的路径，然后在接近目标的时候切换到使用小格子/区域的精细寻路。如果你对这个观点感兴趣，查阅我的文章Two- A*。(译者注：译文 :A*分层寻路)
* 使用路径点系统计算长路径，或者预先计算好路径并加入到游戏中。
* 预处理你的地图，表明地图中哪些区域是不可到达的。我把这些区域称作“孤岛” 。事实上，他们可以是岛屿或其他被墙壁包围等无法到达的任意区域。A*的下限是，当你告诉它要寻找通往那些区域的路径时，它会搜索整个地图，直到所有可到达的方格/节点都被通过开启列表和关闭列表的计算。这会浪费大量的CPU时间。可以通过预先确定这些区域（比如通过flood-fill或类似的方法)来避免这种情况的发生,用某些种类的数组记录这些信息，在开始寻路前检查它。
* 在一个拥挤的类似迷宫的场合，把不能连通的节点看作死端。这些区域可以在地图编辑器中预先手动指定，或者如果你有雄心壮志，开发一个自动识别这些区域的算法。给定死端的所有节点可以被赋予一个唯一的标志数字。然后你就可以在寻路过程中安全的忽略所有死端，只有当起点或者终点恰好在死端的某个节点的时候才需要考虑它们。
7. 维护开启列表：这是A*寻路算法最重要的组成部分。每次你访问开启列表，你都需要寻找F值最低的方格。有几种不同的方法实现这一点。你可以把路径元素随意保存，当需要寻找F值最低的元素的时候，遍历开启列表。这很简单，但是太慢了，尤其是对长路径来说。这可以通过维护一格排好序的列表来改善，每次寻找F值最低的方格只需要选取列表的首元素。当我自己实现的时候，这种方法是我的首选。