A星算法详解-通俗易懂初学者必看(15)

仅因为路径短(但可能更危险)而持续把队伍和寻路者送到某一特定路径。

另一个可能得应用是惩罚周围移动单位路径上得节点。A*的一个底限是，当一群单位同时试图寻路到接近的地点，这通常会导致路径交叠。以为一个或者多个单位都试图走相同或者近似的路径到达目的地。对其他单位已经“认领”了的节点增加一些惩罚会有助于你在一定程度上分离路径，降低碰撞的可能性。然而，如果有必要，不要把那些节点看成不可通过的，因为你仍然希望多个单位能够一字纵队通过拥挤的出口。同时，你只能惩罚那些临近单位的路径，而不是所有路径，否则你就会得到奇怪的躲避行为例如单位躲避路径上其他已经不在那里的单位。 还有，你应该只惩罚路径当前节点和随后的节点，而不应处理已经走过并甩在身后的节点。

3. 处理未知区域：你是否玩过这样的PC游戏，电脑总是知道哪条路是正确的，即使它还没有侦察过地图？对于游戏，寻路太好会显得不真实。幸运的是，这是一格可以轻易解决的问题。

答案就是为每个不同的玩家和电脑（每个玩家，而不是每个单位－－那样的话会耗费大量的内存）创建一个独立的“knownWalkability”数组，每个数组包含玩家已经探索过的区域，以及被当作可通过区域的其他区域，直到被证实。用这种方法，单位会在路的死端徘徊并且导致错误的选择直到他们在周围找到路。一旦地图被探索了，寻路就像往常那样进行。

4. 平滑路径：尽管A*提供了最短，最低代价的路径，它无法自动提供看起来平滑的路径。看一下我们的例子最终形成的路径（在图7）。最初的一步是起始格的右下方，如果这一步是直接往下的话，路径不是会更平滑一些吗？

有几种方法来解决这个问题。当计算路径的时候可以对改变方向的格子施加不利影响，对G值增加额外的数值。也可以换种方法，你可以在路径计算完之后沿着它跑一遍，找那些用相邻格替换会让路径看起来更平滑的地方。想知道完整的结果，查看Toward More Realistic Pathfinding，一篇(免费，但是需要注册)Marco Pinter发表在的文章

5. 非方形搜索区域：在我们的例子里，我们使用简单的2D方形图。你可以不使用这种方式。你可以使用不规则形状的区域。想想冒险棋的游戏，和游戏中那些国家。你可以设计一个像那样的寻路关卡。为此，你可能需要建立一个国家相邻关系的表格，和从一个国家移动到另一个的G值。你也需要估算H值的方法。其他的事情就和例子中完全一样了。当你需要向开启列表中添加新元素的时候，不需使用相邻的格子，取而代之的是从表格中寻找相邻的国家。

类似的，你可以为一张确定的地形图创建路径点系统，路径点一般是路上，或者地牢通道的转折点。作为游戏设计者，你可以预设这些路径点。两个路径点被认为是相邻的如果他们之间的直线上没有障碍的话。在冒险棋的例子里，你可以保存这些相邻信息在某个表格里，当需要在开启列表中添加元素的时候使用它。然后你就可以记录关联的G值（可能使用两点间的直线距离），H值（可以使用到目标点的直线距离），其他都按原先的做就可以了。 Amit Patel 写了其他方法的摘要。另一个在非方形区域搜索RPG地图的例子，查看我的文章Two-Tiered A* Pathfinding。(译者注：译文： A*分层寻路)

6. 一些速度方面的提示：当你开发你自己的A*程序，或者改写我的，你会发现寻路占据了大量的CPU时间，尤其是在大地图上有大量对象在寻路的时候。如果你阅读过网上的其他材料，你会明白，即使是开发了星际争霸或帝国时代的专家，这也无可奈何。如果你觉得寻路太过缓慢，这里有一些建议也许有效：

* 使用更小的地图或者更少的寻路者。

* 不要同时给多个对象寻路。取而代之的是把他们加入一个队列，把寻路过程分散在几个游戏周期中。如果你的游戏以40周期每秒的速度运行，没人能察觉。但是当大量寻路者计算自己路径的时候,他们会发觉游戏速度突然变慢。