关于寻路算法的一些思考（5）：处理移动中的障碍物

一个寻路算法会计算出一条绕过静止障碍物的路径，但如果障碍物会移动呢？当一个单位移动到达某特定点时，原来的障碍物可能不在那点了，或者在那点上出现了新的障碍物。如果路线可以绕过典型的障碍物，那么只要使用单独的避障算法来配合你的寻路算法。寻路算法会寻找到期望的路径，并且在沿着路径的同时绕过障碍物。但是如果障碍物可以移动，进而导致路径不停地发生显著改变，就应考虑使用寻路算法来避障。

重新计算路径

我们希望游戏世界随着时间改变。一条一段时间之前发现的路径，可能不再是现在的最优路径。用新的信息更新旧路径是值得的。下面列出的是一些用来判断决定是否需要重新计算路径的标准：

• 每N步一次：这样保证用来计算路径的信息不会旧于N步。
• 当额外的CPU时间可用时：这样可以实现路径质量的动态调整。即使使用了更多的游戏单位，或者是在一台较慢的电脑上运行游戏，每个游戏单位的CPU使用率都可以降低。
• 当游戏单位转弯或者通过一个关键路径点的时候。
• 当游戏单位附近的世界发生改变的时候。

重新计算路线的主要缺点在于有很多路径信息被丢弃了。例如，如果路径长100步，并且每十步进行一次重新计算，那么路径的总步数是100+90+80+70+60+50+40+30+20+10 = 550。对于一个长M步的路径，总共大概进行了M^2步计算。因此，如果你想要得到很多条长路径，重新计算路线并不是一个好主意。重复使用路线信息，而非丢弃，这样会是更好的办法。

路径剪接

当一条路径需要被重新计算时，意味着世界正在改变。给定一个变化中的世界，地图上的邻近部分比远处的部分更好了解。我们可以遵循一个局部修正策略：找到附近的一条好路径，并且假定较远的路径直到我们靠近它了才需要重新计算。我们可以仅仅重新计算路径的前M步，而不是整条路径：

1. 设p[1]..p[N] 是路径剩余部分（N步）
2. 计算一条从p[1]到p[M]新路径
3. 剪接新路径到旧路径中，通过移除p[1]..p[M]然后插入新路径到这些空位置上。

因为p[1]和p[M]相距不到M步，所以新路线不太可能长。不幸的是，像新路径又长又不是非常好的情况，也有可能发生。上图展示了这样一个情况。原始的红色路径是1-2-3-4，棕色区域是障碍。如果我们到达2然后发现从2到3的路径被阻挡了，路径剪接会用绿色的路径2-5-3来替换2-3，导致这个单位循着路径1-2-5-3-4移动。我们可以看到这并不是一个好的路径，蓝色路径1-2-5-4是更好的选择。

不好的路径经常可以通过计算新路径的长度来判断。如果它明显比M长，它就可能是不好的路径。一个简单的解决方法，给寻路算法添加一个上限（最大路径长度）。如果找不到一条短的路径，这个算法返回一个错误代码，在这种情况下，使用重新计算路线而不是路线剪接来得到一条像1-2-5-4这样的路径。

对于没有涉及到这类情况的例子，对于一条N步的路径，路线剪接会计算2N到3N路径步数，取决于一条新路径进行剪接插入的频繁程度。这是一个相对低的代价，使得算法能对世界的改变作出反应。意想不到的是，这个花费的代价大小取决于M，也就是进行剪接的路径步数。M控制一个反馈和路径质量的平衡，而不是CPU时间的影响。如果M的值较大，单位的移动将不会快速地对地图的改变作出反馈。如果M太小，被剪接的路径可能太短，以至于不能得到可以绕过障碍的替换路径：更不优的路径（例如1-2-5-3-4）可能会被找到，尝试M的不同取值和不同的剪接标准（例如每隔3/4 M步），来看看怎样做最适合你的地图。

路径剪接比重新计算路径明显地快了许多，但它对于路径的重大改变并不能很好地应对。不过很多这种情况可以容易地发现，并直接使用重新计算路径来代替路径剪接。它同样有几个可以调整的变量，比如M和进行新路径的寻找的时间，所以它可以被调整为适合不同的情况（即使是在运行的时候）。但是路径剪接并不能处理游戏单位需要确定位置进而来互相穿过的情况。

监视地图的改变

选择重新计算全部或部分路径在特定的时间间隔，是对地图的改变来触发重新计算。地图可以分成不同的区域，每个游戏单位可以在特定的区域表现出兴趣。（所有包括部分路径的区域都可能是感兴趣的，或者仅仅是邻近的包含部分路径的区域）无论障碍进入或离开某个区域，那个区域就标记为已经改变，然后所有对那个区域感兴趣的游戏单位都会被通知，所以路径可以在考虑障碍发生变化这一前提下被重新计算。

这一技术有很多可能的变化。例如，我们可以仅仅在特定的时间间隔通知游戏单位而不是立即通知。并且多次改变可以被组合成一次通知，所以不再需要过多的进行重新计算路径。另一个变化是让游戏单位来查询地区的状态，而不是让地区来通知游戏单位。

监视地图的改变，避免了游戏单位在障碍物没有发生变化的时候进行重新计算，因此当你有很大地区不会经常发生改变的时候，可以考虑使用这种方法。

预测障碍物移动

如果障碍物的移动可以被预测，那就可以在进行寻路时把未来的障碍物位置纳入考虑。像A*这类算法有一个代价函数，来决定通过地图上某点的困难程度。A*可以被修改成实时更新到达一点所需要的时间（由当前的路径长度决定），这个时间也可以被传入代价函数中。代价函数就可以把时间纳入考虑，然后就可以使用在那个时刻的障碍物预测位置，来决定那个地图位置是否无法通过。但是这个修改并不完美，因为它不会考虑在某个点等待障碍物离开路径的可能性，另外A*并不是设计用来区分相同路线上的路径，而是时间不同的点。

原文：http://blog.jobbole.com/83499/