导航网格寻路与路点寻路

翻译老外的文章，原文地址：http://www.ai-blog.net/archives/2008_07.html

由于本人英文水平有限，难免有翻译不当的地方，欢迎批评指正，如转载请注明出处。

 

我尽我所能不说那些被认为是对产业中游戏或开发者进行批评的话，但是在这里我要提一些不同意见。我要讨论一些在寻路中面临的问题，为了证明这些问题现在仍然存在，有必要来制作这个轻松幽默的视频。

Can not load video

正如你所看到的，距离拥有一套强壮的寻路算法还有很长的路要走，甚至在百万销量和三A认证的产品中也存在这个问题。这可能并不是普遍性的问题，现有的许多游戏都有高质量的寻路系统，在这里列出的游戏中也表现良好，但是也有许多游戏中的寻路和90年代使用相同的方式。

就我所掌握的知识而言，大多数游戏采用了路点进行寻路，我想这就是视频中提到的寻路问题的原因，也涵盖了产业中遇到的大多数寻路问题。我相信路点寻路现在已经被淘汰了，这篇文章列出了路点寻路的局限性，并为一种更好的方法提出了五点论据。场景使用路点寻路已经有一段时间了，回退到80到90年代，我们在有严重技术局限性的环境下工作，不得不回避许多问题。但是现在的产业规模已达到数十亿美元，目标平台已经具有多核和不断增长的内存环境，这让我们有能力来实现正确的寻路。

在业界的AI开发者中有这样的说法：寻路已经被解决了。当今游戏面临的每个寻路问题都有好的解决办法，只是我们不常用到。在任何时段，任何游戏中不使用寻路是没有任何理由的。

为什么路点不适合寻路。

让我来给你展示一个典型的路点寻路是什么样的。下面是魔兽世界暴风城中的一个场景。

图1：魔兽世界中暴风城的一个区域

下面是典型的路点寻路在场景的展现

图2：用路点注释相同的区域

有另外一种方法来实现，它涉及到使用凸多边形来描述哪些地形AI角色可以穿过。这种表示方法提供给AI角色更多的周围世界信息，并提供了更多的智能决策选择。

下图展示了什么是导航网格

图3：使用导航网格注释的相同区域

接下来就是路点寻路存在缺陷的五点原因。

1.       某些种类的游戏世界中需要大量的路点信息

大型开阔的区域往往需要大量的路点贯穿于游戏世界中来满足适当移动的需要。另一方面来说，导航网格只需要几个大的凸多边形，这样可以使寻路更加迅速。

下面得例子显示了魔兽世界中被称为Halla的城市。这个一块相当庞大开阔的区域，并且NPC需要能够穿过它。为了这个例子我已经删除了当中的一些细节，比如城市中的旗帜和山峰。

图4：经过简单修改的魔兽世界Halaa城俯视图

如果使用基于路点的寻路系统，我们需要大量的路点来覆盖整个区域，即使是那样，NPC在移动过程中将以Z字形结束，除非我们指定更多的路点信息。

图5：路点注释的Halaa城

另一方面，使用导航网格我们可以使用少量的凸多边形来描述相同的区域：

图6：导航网格描述的Halaa城

简单的导航网格意味着当我们实时调用寻路算法的时候并不需要搜寻过多的节点，这样寻路也能够更快速。

2.       角色移动时会走Z字形

路点寻路将角色绑定在创建的图形中，这意味着角色在边缘有效，同时从A到B也不会使用最佳路径，这是因为大多数直通路径几乎不会和图形匹配，这就导致了不正常的寻路结果，特别是角色行走时路径为忽左忽右的Z字形。

下面是一个例子，我们想让一个角色从A走到B：

图7：Halaa城的两个点

下图显示了使用路点寻路的效果：

图8：使用路点寻路从A导航到B

正如你所看到的，角色在沿着黄线行走时会转向多次。在理想情况下，我们在创建路径后可以把它调整得更加平滑，也许可以通过沿着路径点创建的方式。问题是路点网络不包换网络外物体的任何信息，也就不可能具有平滑路径并使路径安全可靠的功能。

如果曲线在路点图形之外如何来创建它呢，事实上沿着曲线可能使你落入桥下面吗？你可能会想应该有简单的方法创建一条路径，不幸的是使用路点图形，无解。同时如果相对路点图形哪怕只有一点点偏离，那寻路结束时很容易落入悬崖或者撞进墙里面。我们没有办法来知道这些，因为地形中并不包含那些数据。因此为了保证安全，我们不得不使用最悲观的看法，并且一直呆在地图上面。

然而使用导航网格如下图所示：

图9：使用导航网格从A导航到B

因为我们知道角色从哪里走是安全的，可以使用任何方法来使路径更加平滑，只要保证路径在导航网格上面。导航网格告诉我们角色可以从哪里行走意味着我们可以很容易的使用曲线来平滑化路径。我们需要做的就是保证曲线在导航网格之中。

回到暴风城的例子当中，下图显示了路点路径（红色）和基于导航网格的平滑路径（蓝色）。

图10：路点路径（红色）和平滑的导航网格路径（蓝色）

3.       它们不允许路径修正，如果场景中有动态阻挡，处理将会变得十分困难。

路点地形不包含任何地形外的物体数据，即使一英寸外的角色它也不知道哪些区域可以行走。这导致了寻路系统在处理动态阻挡的时候无法修改路点路径。

让我们来设想一下有一个巨大的箱子在暴风城的桥上。使用路点路径的情况下，我们是被束缚的，如果箱子和路点地形重叠，我们不知道从左还是从右面穿过它，或者如果路径被完全阻塞需要绕行。我们经常进行猜测，但是如果做了错误的猜测，角色将会落入桥下并掉到水里。

图11：一个巨大、无法移动的箱子在桥上

使用导航网格将会变的非常简单，因为我们知道哪些区域是可以通行的。通过射线透射并调整路径，保证在导航网格上的路径安全。

图12：导航绕过箱子

当然你也可以把它置于路点地形中，然后放置大量的像草丛一样的路点，我宁愿选择在一个大多边形中使用A*，而不是在几百路点之中。

4.       不能根据角色特征改变路径

路点地形在处理不同长、宽、转速的角色以及其他寻路参数时表现很差，这意味着它无法针对游戏中所有类型的物体使用单独统一的路点地形。当我们想到AI寻路的时候，趋向于想到游戏世界中的人物导航。但是AI系统需要控制许多不同种类的个体，如坦克、飞机等等。在许多情况下，这些个体需要根据它们的大小、形状和移动能力来进行不同的寻路。一个好的寻路系统需要解决所有问题。

下面是一个例子。假设沙漠中有一个沙袋围绕的混凝土地堡。

图13：沙漠中的地堡

假设有一个士兵可以沿着沙袋移动（红色箭头），一辆装甲坦克需要与沙袋保持距离行驶以避免碰撞。

图14：士兵（红色）和坦克（蓝色）可以围绕沙袋移动的路径

如果使用路点地形，将无法使用单一方式解决问题，需要针对士兵和坦克使用完全分离的路点网络。增加一个新的摩托车个体，就需要一个新的网络。对每一种不同类型的个体都有不同的移动能力。使用导航网格就会变得非常简单：

图15：地堡外围的导航网格

注意下从沙袋转角处发出的两条淡绿边，因为我们知道士兵的碰撞半径为1米，装甲坦克的半径为5米，使用相同的网格创建两条不同的路径变得不再重要。我们只需要计算沿着沙袋的路径，把它设置为距离转角1米或者5米的距离，这取决于我们是为士兵还是坦克进行寻路。

图16：地堡外围的导航网格

下面为另外一个例子。假设一个士兵骑在摩托车上，和士兵不同，摩托车在移动时不能转小弯。在下面的例子中，明显地摩托车驾驶员可以从当前位置行驶到顶端的房间中（红色线），但是不能转入右边的走廊汇总，因为角度太小（橙色线）。不管使用哪种寻路，我们希望能解决这个问题。

图17：摩托车可以进入顶部的房间（红）但是不能进入右侧的房间（橙）。

使用导航网格将会变得简单。当进行寻路时测试一下旋转角度和距离，拒绝在短距离内进行大角度转弯的路径。使用路点方式，基本上是无法解决的。至少我们需要为摩托车上的士兵使用完全分离的路点地形，因为我们无法使用和步行的士兵一样的地形。为每个具有不同寻路能力的个体增加新的地形是完全没有必要的。

5.       不能保存AI寻路时所需要的所有数据

AI寻路空间并不仅仅用来导航，它们需要使用寻路数据来知道如何在世界中移动。一个游戏角色需要不断查询寻路系统是否可以行走。

下面是一个例子：这个剑客有四个动作，左刺，右刺，后退，跃起20尺并在前方8尺处。

图18：有四个动作的剑客包括平移

为了保证剑客跳跃、刺杀、后退后不碰壁，我需要在导航网格中检测各个动作的结束位置。当然也可以碰撞系统进行射线透射，这经常会给你有用的信息，而且一般是找到游戏世界中动态物理个体的唯一途径。但是射线投射的开销很大，当你只关心静态游戏世界而不是动态物理个体时，导航网格是简单快速的。

尽管可以使用射线投射来确定从当前位置到点（X,Y,Z）之间是否有路径，但是碰撞系统不能告诉我剑客是否停留在合法位置上，只有导航网格能够确定这一点。