一劳永逸地解决寻路问题
作者：PaulT
译者：trcj
原文：http://www.ai-blog.net/archives/000152.html
通常我都会尽量避免对业内游戏产品或开发者们评头论足。
但这回我不得不破一次例。
我要讨论一些关于寻路的问题。为了证明这些问题至今仍然存在，我本着娱乐的精神制作了这个视频。
（译注：原视频缺失。）
所有片段都录自对应游戏的最新版本。
正如你所看到的，我们在构建一个健壮的寻路系统上还有很长的路要走，这些方方面面的问题甚至存在于一些顶级产品中。
并不是说这是当今游戏的通病。因为时下许多游戏确实拥有高质量的寻路，而且视频里的寻路大部分时间也表现良好。
但是仍有太多的游戏还在使用九十年代的方法。
（说明：为了录制之便，视频里出现的大多数游戏都属于PC平台角色扮演类型，因为当时我的电脑上就只安装了这些游戏。事实上，这些问题不限于任何类型或平台，甚至在主机平台的游戏里也多有出现。）
就我所知，大多数游戏使用路径点（waypoint graph）来实现寻路，它正是我们所碰到的这些问题的首因。
我认为路径点这一做法已经过时。这篇文章将阐述路径点的缺陷，同时通过五条主要论据介绍另一种更为可行的方法。
我曾经在八、九十年代使用过路径点寻路，当时我们面对诸多苛刻的技术限制，不得不舍弃很多东西。
现如今我们身处一个亿万美元的产业之中。面对的平台拥有多核处理器和与日俱增的海量内存，完全具备了实现一个合理的寻路系统的条件。
业内AI开发者中有一句话：“寻路已不是问题。”我们有针对各种寻路问题的各种解决办法，只不过不常使用而已。
而我想说的是，没有任何理由不一劳永逸地总结出一套放之四海而皆准的寻路方案。
为什么路径点不适合用于寻路
让我们来看看一个路径点系统究竟是什么样子。下面是魔兽世界里暴风城一隅。
图1. 魔兽世界暴风城一隅
这是该区域典型的路径点分布图。
图2. 同一区域的路径点分布图
现在我们介绍另一种实现方法，使用凸多边形来表示AI单位可以移动的范围。这种方式可以为AI提供大量的关于周围世界的额外信息，赋予其极大的灵活性。
这种寻路网格（navigation mesh）看上去是这个样子的：
图3. 使用寻路网格来标识的同一个区域
现在，我们来逐一列举路径点寻路的五大缺陷。
1. 一些游戏需求的路径点数目过大。
大型开放性区域通常需要散布大量的路径点来实现丰富的移动效果。
如果使用寻路网格，数个多边形足矣，且寻路更为快捷。
举个例子。下图展示了魔兽中的重镇“哈兰”。这是一大块开放型区域，NPC漫游其间。为了方便演示，我移除了镇子中的旗帜、喷泉。
图4. 哈兰（略修改）
在路径点系统中，我们需要放置众多路径点以覆盖整个地区。即便如此，NPC仍会选择到一些曲曲折折的路径，除非我们继续添加比下图多得多的路径点。
图5. 覆遍路径点的哈兰
如果使用寻路网格，寥寥数个多边形即可描述整片区域。
图6. 寻路网格描述的哈兰
寻路网格使我们免于遍历众多的路径点，效率自然也提高很多。
2. 路径点让结果路径呈现“锯齿状”的弯折。
路径点把寻路单位限制在你创作的路径图中。这意味着单位始终沿着固定轨迹运动，并且几乎永远不会选择由A到B的最短路径，因为最优的直线路径很少能与路径图吻合。
这将导致不自然的寻路，寻路单位走动时会在一段锯齿状的曲折路径上忽左忽右。
以A至B取径点为例。
图7. 哈兰的两个路径点
这是按照前述路径点图得出的取径结果。
图8.由A至B使用路径点进行取径
可以看出，AI单位沿着黄色的路径行走时会经历数次弯折。
理想情况下，在我们选好路径后，可以做一些平滑处理，比如沿着路径点构建出一条Catmull-Rom样条曲线。
问题在于，路径点网络没有任何线路以外的信息，很难安全可信地对路径进行平滑调整。
试想一下在线路之外如何创建出一条平滑路径，而保证这条新路径不会引导你摔下索桥。
你或许会寻思是否有其他方法可循，不幸的是，在路径点的体制下，没有。如果我们冒险偏离路线哪怕一点，都有可能酿成坠崖或撞墙的惨剧。我们像路径点图一样对路线之外的东西一无所知。
所以安全起见，我们只好采用最悲观的策略，老老实实待在路线中。
如果使用寻路网格，取径结果则会大为不同：
图9. 在寻路网格中由AB漫游
因为能够通过寻路网格得知寻路单位的安全活动范围，我们得以以任意方式调整取径结果，只要保证在网格之内即可。
（“哦，”你可能会说，“但是我可以在路径点图中开启更多的连接来达到平滑目的！如果需要NPC直行，我会打开镇中所有节点之间的连接。”
“但是这会导致数据指数级的爆炸，”我回应…“在这个例子里或许额外40或50连接已经足够。但是随着区域增大，你需要应付的节点间的连接数会直逼O(N^2)。”
“好吧，”你又说，“那样的话，我就把相邻三点围成的区域标记为‘开放’，这样AI就可以在这块区域中自由行动啦。”
“这正是一个多边形…而你刚创建了一个寻路网格，”我提醒道）。
寻路网格包含活动范围的精确大小，这意味着可以随意使用样条曲线平滑我们的路径，唯一要注意的就是保持曲线在网格内。
回到暴风城一例，下图分别展示了路径点取径（红色）和经过平滑处理的寻路网格取径（蓝色）结果。
图10. 路径点取径（红色）及经平滑处理的寻路网格取径（蓝色）
3. 路径点取径不允许路径修正，这使得动态避开障碍物变得极其困难。
路径点图缺少路线之外的数据，即便对于偏离分毫的区域也无法给出参考信息。
这意味着你不大可能通过修改路径来动态避开障碍物。
想象一个搁置在暴风城石桥上的沉重大木箱。
使用路径点寻路，我们将束手无策。如果箱子横在路线上，我们完全不知道从左边还是右边绕开它，如果箱子完全挡住了去路，我们也不知道是否应该改道。我们只能猜，盼望不要落入水中。
图11. 难以移动的大箱子横在桥当中
如果使用寻路网格，事情就好办多了。参照网格提供的活动范围，我们对箱子进行碰撞检测，调整路径绕过障碍，并可以始终保持在网格的安全区域中。
图12. 绕过箱子行进
当然，你也可以在路径点图中新加路径点来解决问题，直到你的路径点像野草一样稠密（而你的寻路性能像蜜糖一样粘滞）。
不知你意下如何，我倒是宁可在大多边形里运行我的A*算法，也不愿在数以百计的路径点中。
4. 路径点不支持寻路参数不同的多个单位。
寻路点不支持寻路单位具有不同的高度、宽度、旋转角度等寻路参数。这意味着你不能仅用一张统一的路径图来匹配游戏中所有的单位类型。
当说起AI寻路，一般我们会想到角色在游戏中漫游。
但是AI系统需要控制多种寻路单位---坦克、飞机、轮船、气垫船、摩托车、兽人、地精、龙、伐木巨人、浮空游荡的生物、等等。很多时候，单位需要根据各自的大小、体型和运动参数来寻路。这些都需要寻路系统给予支持。
举个例子。设想沙漠中有一座掩体，四周环绕沙袋。
图13. 沙漠中的掩体
如果是一名士兵，他大可以沿着沙袋行走（下图红色箭头）。
但如果是一辆装甲坦克，就不得不与沙袋保持一定距离以避免碰撞（蓝色箭头）。
图14. 士兵和坦克沿沙袋行进的路线
使用路径点方法，你无法仅使用一张路径图同时处理两种情况。你需要为坦克和士兵各建一张图。如果加入一个摩托车单位，你还要再建一张。以后每加入一个不同单位你都得新建一张。
如果使用寻路网格，就简单多了。
图15. 覆盖掩体外围的寻路网格
注意上图中沙袋弯角处两个浅绿色拐点。假设士兵碰撞半径为1米，坦克碰撞半径为5米，仅使用同一个寻路网格我们也能容易地可以生成两种规格的路径。我们只需要计算一条顺着沙袋外沿的路径，然后移出来1米或5米即可。
图16. 覆盖掩体外围的寻路网格
再举一个例子。想象一名驾驶摩托车的士兵。不比徒步，摩托车很难在行驶时小角度转弯。
下图中，很明显摩托车手可以从当前位置驶进上方的房间（红线），却很难拐进右侧的过道中，因为角度刁钻（橙线）。不论何种寻路，都需要解决这个问题。
图17. 摩托车可以驶进上面房间（红线）却无法进入右边（橙线）
如果使用寻路网格，仍然简单。在寻路过程中我们只要留意转弯角度及距离，剔出那些短距离小角度的路径即可。
但使用路径点寻路，则基本上不大可能。因为无法使用徒步士兵的路径点，我们至少要为摩托车单独新建一张路径点图。而这种做法无疑导致冗余。
5. 路径点没有足够信息以支持AI除寻路以外的功能。
AI寻路其实不仅仅是为了漫游，还需要从路径信息中得知在世界中如何移动。
游戏角色需要向寻路系统频繁查询：是否可以移动到这里？那里又如何？
如今游戏日渐演变出靠动画驱动的移动系统，开始允许动画师们通过动作控制角色的移动。这意味着如果要知道播放某个动画会产生什么后果，就需要知道动画结束时角色的位置，同时需要知道该位置是否恰巧在一堵墙中，或是掉出了悬崖，又或是关卡设计师不想让玩家进入的地方。
举个例子。下图中的剑客有四种位移：左右平移、后退、腾空20英尺后于8英尺开外落地。
图18. 一个包含四种位移动作的剑客
为了确保这个剑客做动作时不会一头扎进砖墙里，我需要预先根据碰撞网格，监测每个动作是否可行。
是的，你可以使用碰撞系统，它总能提供有用的信息，对于游戏世界中动态运动的物体，它通常也是知会AI相关信息的唯一办法。
但是碰撞检测代价高昂，如果你只关心静态物体，使用寻路网格无疑更为快捷。
另外，尽管我可以使用碰撞检测来计算角色和某点间是否有墙体遮挡，碰撞系统却无法告诉我剑客落地的位置是否正处于关卡设计师设定的禁区…这些只有通过寻路网格来判断。
如果上述内容仍不能让你信服，下面就让我通过一些关于路径点和寻路网格的问答，来打消你的疑虑吧。
Q & A
在寻路网格上取径是否会降低效率？
一点也不会。寻路网格其实也是一张图（graph），正如路径点图一样，它们的核心寻路过程也极为相似。不同之处在于寻路网格图中每一个节点都关联一个多边形。
下图展示了被图结构关联起来的多边形。
图19. 寻路网格的构架是一张图（红色）
A*算法始终运行在某个图结构中，无论它是方格、路径点图还是寻路网格图。
大多数情况下，寻路网格的性能和路径点接近。在使用寥寥数个节点覆盖一片区域时（例如图6），寻路网格性能提升显著。
寻路网格是否会耗费更多内存？
手法正确的话，不会。
寻路网格结构精简。总的来说，相比用于供渲染的模型网格，寻路网格不足其数分之一。相比碰撞模型，寻路模型关心的面数更少（它忽略墙、顶棚和其他脚力不可及的区域），而且往往使用更大号的多边形覆盖给定区域。
最坏情况下，寻路网格在每个图节点上使用的顶点数目也许会多于路径点图。但很多时候，如图6的哈兰，寻路网格要比路径点简洁许多。
大多数你展示的例子都出自角色扮演游戏。为什么没看到第一人称射击游戏存在这类问题？
很多FPS游戏都存在这个问题，不过缘于该类游戏本身玩法，此类问题不易被定位。
- 大多数AI都不会存活太久，难以发现其寻路缺陷。
- AI通常在你进入视线后即停下射击，寻路一般偏短。
- 许多单人FPS游戏中，AI少动，更倾向于原地朝你放枪。
- 当今许多FPS游戏提供AI队友，它们击毙敌方AI，不留任何长距离跑路的机会。
这里有一个半条命2的例子。通过一点小实验，不难发现梯子上的卫兵被限制在梯子中间直上直下的一条路线上，始终寻找着照面时刻射杀你的机会。
（译注：原视频再次缺失。）
如果你取消远程武器强制角色们近身肉搏---《光晕》里的星盟士兵，《先头部队》里的克隆杀手，或者《银河战士》里的浮游者---便会发现路径点突然成为了一个极其不堪的选择（这也是上述三个游戏使用寻路网格替代路径点的原因之一）。
瞧，我理解你的意思，但是设计师们需要在游戏里放置掩体点、巡逻路径等。这对我们游戏的AI来说必不可少。
当然！即便使用了寻路网格，你仍然可以这么做。
关键在于分离两个系统。你使用一个（寻路网格）来实现寻路及漫游，使用另一个（设计师放置的这些点）告诉AI如何与游戏世界交互。
寻路网格不应该成为你使用任何系统的障碍，它只是简单地为丰富AI寻路提供了额外信息。
举个例子。我们设置了巡逻路径（紫色）让卫兵在城镇附近巡逻，为一个老家伙设置特殊的点让他每天到护城河边垂钓（红色）。掩体点方便暴风城的法师和术士们做FPS式的决斗时寻找掩护。
图20. 多种地标点（所有颜色）和寻路网格共存
好吧，但是放置寻路网格难道不会花费很多时间吗？
整体来说，手动放置寻路网格的工作量不会比设置路径点来的更繁重。两种体制下，放置寻路信息的时间都远远小于游戏中测试它们的时间。
以我的经验来说，放置一个中等规格的FPS关卡寻路网格需要花费1-3小时时间。
创建一个寻路网格编辑器相对比较简单。你要实现的功能就是放置顶点到游戏世界中，选取并将他们组织成多边形。你可以通过多边形邻边共享的顶点来决定寻路网格之间的连通性。
同时，有一些中间件可以帮你完成构建寻路网格和实时寻路的工作，例如xaitment， NavPower，PathEngine及Kynapse。这些解决方案都在日渐完善中。
如果我有一个爬楼梯的AI怎么办？我们的设计师可不喜欢为楼梯上每个台阶铺设一个寻路网格。
寻路网格只是标识了Ai可以行动的区域。它不能用于代替碰撞检测模型---你的NPC仍然需要碰撞系统来支持游戏中的碰撞。
你只需一个大矩形覆盖整个楼梯即可。
难道我不能给每个路径点赋一个半径信息，用圆来替代点？这样我就可以知道那些区域可以走动。这是正他们在robotics里的做法…
这个方法在某些场合行得通，但是游戏中的大多数区域遍布弯弯角角的街道和建筑。圆形无法和这些空间契合得很好，在覆盖该类型区域的便利性上较使用多边形相去甚远。
下方展示了在暴风城使用圆形扩展路径点进行寻路的示意图。
图21. 路径点扩展为圆
（小轶事：当我在《机甲战士4：复仇》小组工作时，我们发现在户外表现良好的圆形系统一旦应该用到城镇中立刻不再适用。我们最终解决了这个问题，但是得到一个教训：圆和城市水火不容！）
与此同时，留下边角也是很重要的。在图16的沙漠掩体一例中，我们使用寻路网格的边角针对士兵和坦克不同的形体、大小和运动参数生成不同的路径。圆图不支持边角，所以为不同单位创建不同路径也会变得相当困难。
我的游戏已经有了碰撞模型，我能用它作为寻路网格吗？
你可以试试，但这可不是个好主意。
碰撞模型被优化以便于碰撞、而非寻路。它往往包含比寻路需要的多得多的多边形，因此你的寻路算法会变得很慢。
例如，一条鹅卵石街道上的碰撞模型也许有1000个多边形，而只需一个寻路矩形。一个建筑顶棚的碰撞模型含50个多边形，但根本不需要寻路网格（因为我们的角色或许永远不会走上屋顶）。
同时，寻路网格的一部分优势在于它不仅仅告诉你寻路单位可以移动的范围；还告诉你设计师想让他们在哪里移动。
如果你让你的设计师手动创建寻路网格，他就可以标识某处“AI免进。这里拒绝任何单位进入，因为这个游戏设定如此。”这些信息是碰撞模型永远给不了的。
上面所有的例子里寻路网格似乎都是到2D空间的投射。我如何处理道路穿过桥洞，何时能够通过何时不能，或者多楼层建筑的情况？
寻路网格能优雅地解决这些问题。下面是魔兽世界沙塔斯寻路网格分布的样子（简便起见，我省略了桥远侧的部分网格）。
图22. 沙塔斯，覆盖桥上或穿行桥下的寻路网格
在寻路网格中，每个多边形通常存储有一个表示通行高度的参数。例如，穿行于桥下的多边形被标识为7英尺，那么那些高于7英尺的单位将无法从桥洞通过。
对于多楼层建筑的情况，每个楼层有独立的寻路网格，之间通过楼梯的寻路网格连接（当然，电梯略棘手）。
我不相信会有放之四海而皆准的办法。不同的游戏需求不同的寻路之法。
如果你正制作一个纯2D策略类游戏，那么一个基于方格的寻路算法更为合适，因为格子允许更快捷地访问任意地块。
否则，寻路网格真的是3D世界中解决寻路及地形物理的最佳方法。
我想在自己的游戏中实现寻路网格。有没有资料可以帮助我理清如何生成网格，如何在其上寻路，以及如何在游戏中优化它们？
我所知道的资料如下：
"Simplified 3D Movement and Pathfinding Using Navigation Meshes" by Greg Snook (Game Programming Gems)
"Polygon Soup for the Programmer's Soul: 3D Pathfinding" by Greg Hjelstrom and Patrick Smith (GamaSutra.com)
"Building a Near-Optimal Navigation Mesh" by Paul Tozour (AI Game Programming Wisdom)
"Efficient Navigation Mesh Implementation" by John C. O'Neill (Journal of Game Development, March 2004)
"Search Space Representations" by Paul Tozour (AI Game Programming Wisdom 2)
"A Fast Approach To Navigation Meshes" by Stephen White and Christopher Christensen (Game Programming Gems 3)
"Choosing a Relationship Between Path-Finding and Collision" by Thomas Young (Game Programming Gems 3)
"Improving on Near-Optimality: More Techniques for Building Navigation Meshes" by Fredrik Farnstrom (AI Game Programming Wisdom 3)
"Smoothing a Navigation Mesh Path" by Geraint Johnson (AI Game Programming Wisdom 3)
"Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision" by Paul Marden and Forrest Smith (AI Game Programming Wisdom 4)
"Intrinsic Detail in Navigation Mesh Generation" by Colt McAnlis and James Stewart (AI Game Programming Wisdom 4)
"Navigation Mesh Generation: An Empirical Approach" by David Hamm (AI Game Programming Wisdom 4)
"Navigation Mesh Generation in Highly Dynamic Worlds" by Ramon Axelrod (AI Game Programming Wisdom 4)
"Crowds in a Polygon Soup: Next-Gen Path Planning" by David Miles (http://www.navpower.com/gdc2006_miles_david_pathplanning.ppt)
注意：如果你有相关资料想在此列出，请邮件联系我。
实际有多少游戏成功应用了寻路网格？
这里有一个名单：
光晕2
光晕3
先头部队
反恐精英：起源
银河战士
银河战士2：回声
银河战士3：堕落
杰克与达斯特：旧世界的遗产
杰克2
杰克3
神秘海域：德雷克船长的宝藏
疤面煞星：掌握世界
…更多的例子枚不胜举。
看起来所有扮酷的同学都用了这个。
好吧，它或许对你适用，但是我们之前所有的游戏使用的都是路径点寻路，表现良好。
如大家所说，如果它还能用，就别去管它…而且你说的那些问题我们一个都还没碰到哩。
目光放长远点，想象一二十年以后的光景。
到那时，你认为你的游戏会不会包含众多不同的AI控制的不同角色，各自又有不同的体型、大小、运动参数？
玩家们会不会想要和他们一样聪明的AI伙伴？
你的游戏会不会比今天更庞大、更复杂、更具变化性？
你会不会同时拥有有数量众多的AI角色---多到简单的转向和规避障碍已经不足以满足AI间丰富高效的交互？
你的游戏会不会引入高仿真的物理系统，玩家们会不会随心所欲地使用物理和AI角色打成一片？
玩家们可不可以把游戏世界改造得面目全非？
会不会有AI在多人游戏中完全替代真实玩家？
二十年后的游戏会是什么样子我们无从得知，可以预见的是我们需要更高级的AI，虚拟角色们需要更多的数据来演绎环境，优化寻路，应对千变万化的游戏世界。
