后使用快捷导航没有帐号？
只需一步，快速开始
&加载中...
查看: 3098|回复: 4
一篇关于网格导航
TA的其他好贴
马上注册，加入CGJOY，让你轻松玩转CGJOY。
才可以下载或查看，没有帐号？
在本教程中，我们将通过介绍内置的导航系统来深入学习3D的人工智能。我将展示如何在场景中定义一个NavMesh，并创建一个agent（智能体）来穿越地形到达不同的目标，以及如何连接场景中不同的区域。
NavMesh是一种在游戏AI环境中定义可行动区域的常用技术。它也常常用于计算两点之间的路径，使NPC从它自己的位置跑到目标位置，让敌人到达玩家那里，或者移动玩家到目的地。（例如：点击式的冒险游戏或者RTS（即时战略）游戏）。
Unity提供了navigation system（导航系统）的内置实现方法，免费版和专业版都包含。但是有些高级功能，比如off-mesh links（分离网格连接）只有专业版才有。
依次点击菜单项Window-Navigation打开Navigation面板进入navigation系统，它会显示在Inspector（检视面板）旁边。
0.jpg (36.32 KB, 下载次数: 15)
18:20 上传
我们将使用3D项目完成本教程。这里假设你熟悉Unity编辑器并且知道一些基本操作比如在scene中加入物体，组件及C#脚本等。注意: 本教程基于Unity4。截图来自于4.5.1版本。新版编辑器分布、菜单、名称或布局可能有所不同。
标记场景对象以及烘焙
事有先后。在对象选项卡中，定义选中的物体是否是Navigation Static。墙壁，地面以及平台都应该是静态物体。
确保你已经检查过hierarchy（层次面板）中的所有物体，并已适当地设置它们。你可以在Navigation 面板中使用Scene过滤器来只显示Mesh Renderer或者Terrain地形。在使用这个功能的时候，确保你选中了一个真实的带有mesh 的物体，而不是其父物体。
当生成NavMesh时，未勾选Navigation Static的物体将被忽略。
接下来，在下拉列表中设置物体的NavigationLayer。你可以选择Default（walkable），Not Walkable或Jump。如果你希望地形更多样也可以自定义layers（层）—更多将在后文介绍。
我们现在已经准备好在场景中烘焙NavMesh。在这里你可以看到没有NavMesh的最初场景：
1.jpg (39.76 KB, 下载次数: 18)
18:20 上传
在点击烘焙按钮后，你会看到场景中的某些区域覆盖上了一层蓝色的东西，那就是NavMesh：
2.jpg (28.89 KB, 下载次数: 16)
18:20 上传
玩家只能在地图上的蓝色区域行走。要注意的是，每一次对场景做了修改，都需要再次烘焙NavMesh。
在这个例子中，地面是由一个个相邻的小块组成。当我们希望关卡中不同区域的遍历成本不同时，这将会变得很方便。
设置NavMesh属性
你可以在Bake选项卡中自定义NavMesh。
Radius 是指墙壁与navigation mesh（导航网格）之间的距离，并代表了智能体的半径。如果你还是觉得智能体移动时会碰到墙壁或者其它物体，增加半径使其更平滑。
Height 代表智能体的高度，并指定智能体能进入的区域最小高度。Max slope指定表面可行走的最大坡度，而Step Height是行走连接的两个表面之间的高度差。
在高级组下，你可以设置大概的宽度和高度，用于指定生成NavMesh的近似值。该值越小NavMesh质量越高，同时计算消耗越大。生成更精确的NavMesh耗时也会更长。
NavMeshAgent
既然我们已经在场景中生成了NavMesh，接下来就需要一个方法通知角色在上面走动。这就得使用NavMeshAgent组件。你可以在Navigation下的组件菜单中找到它。
正如之前图中所示，我们在场景中有两个cube，蓝色的那个代表玩家，红色标注的位置则是目标。
在角色上添加NavMeshAgent组件，此组件负责智能体的寻路以及实际的运动控制。
3.jpg (39.43 KB, 下载次数: 16)
18:20 上传
你可以在这个组件里设置很多属性。再一次说明，Radius 指定智能体的半径（并定义了是否能通过狭窄的通道），Height就是智能体的高度并决定它们能否通过障碍。
Speed, Acceleration 和Angular Speed自然不用多说，它们定义了智能体如何移动，Stopping Distance定义了智能体在停止之前会离目标位置多近。
我们现在需要告诉智能体通过脚本做什么。下面是一个简单示例，告诉你如何让智能体移动到目的地。[C#] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important][backcolor=rgb(108, 226, 108) !important][color=white !important]
using UnityE
using System.C
public class AgentWalkScript : MonoBehaviour
& & public T
& & private NavMeshA
& & void Start ()
& && &&&agent = gameObject.GetComponent&NavMeshAgent&();
& && &&&agent.SetDestination(destination.position);
当运行场景时，脚本会获取游戏物体上的NavMeshAgent组件的引用，然后使用SetDestination告诉它移动到目的地。
在编辑器中将这个脚本绑定到角色物体，并确保场景中有另一个物体作为目标（在我这个例子中，我使用了红色cube）。点击play，就会看到角色朝着目的地移动。如果智能体无法到达目的地（比如你把它放入一个死循环），它就会停在最靠近目标点的位置。
如果你在Inspector（检视面板）勾选了Auto Braking ，智能体会在即将到达目的地时放慢速度，平滑地在该位置停下来。如果因为某种原因路径被破坏了，智能体可以即时创建一条新的路径，要想有这样的功能，就勾选Auto Repath。
如果你想重新创作出类似RTS（即时战略）风格的控制（比如你在场景中通过点击来移动智能体），你需要用摄像机从屏幕点中投出一条射线，并用射线检测Raycast 在世界中的碰撞。如果检测到碰撞，智能体将会尝试向那边移动。[C#] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important][backcolor=rgb(108, 226, 108) !important][color=white !important]
void Update()
& & if (Input.GetMouseButtonDown(0))
& && &&&Ray screenRay = Camera.main.ScreenPointToRay(Input.mousePosition);
& && &&&RaycastH
& && &&&if (Physics.Raycast(screenRay, out hit))
& && && && &agent.SetDestination(hit.point);
手动创建路径
某些情况下你可能想更好地控制智能体开始向目标移动时生成的路径。寻路是一个相对复杂的操作，有时候最好在使用之前先将路径计算好并存储。这可以使用Calculate Path来解决：[C#] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important][backcolor=rgb(108, 226, 108) !important][color=white !important]
agent = gameObject.GetComponent&NavMeshAgent&();
NavMeshPath path = new NavMeshPath();
bool hasFoundPath = agent.CalculatePath(destination.position, path);
if(path.status == NavMeshPathStatus.PathComplete)
& & print(&The agent can reach the destionation&);
else if(path.status == NavMeshPathStatus.PathPartial)
& &&&print(&The agent can only get close to the destination&);
&&else if(path.status == NavMeshPathStatus.PathInvalid)
& &&&print(&The agent cannot reach the destination&);
& &&&print(&hasFoundPath will be false&);
在这个例子中，我手动计算了一条路径，并检查该路径的状态判断是否可以让智能体到达目的地。注意在本例中智能体不会移动。随后，当你想让智能体开始移动，你可以使用SetPath 并传入之前生成的路径。
[C#] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important][backcolor=rgb(108, 226, 108) !important][color=white !important]
agent.SetPath(path);
如果想清除路径，可以使用ResetPath：[C#] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important][backcolor=rgb(108, 226, 108) !important][color=white !important]
agent.ResetPath();
就算智能体正在移动也会停止，因为有效路径不存在了。
Stop，Resume和Wrap& && && &
当智能体正向目标移动时，可以使用Stop临时停止它。默认情况下在停止时，游戏物体还是将减速并受到回避系统的影响。为了避免这种情况，传递true 作为参数。[C#] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important][backcolor=rgb(108, 226, 108) !important][color=white !important]
if(shouldStopImmediately)
& &agent.Stop(true); // Stops immediately
& &agent.Stop(); // Decelerate
随后可以使用Resume 来使智能体恢复移动：[C#] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important][backcolor=rgb(108, 226, 108) !important][color=white !important]
agent.Resume();
在某些情况下你可能希望移动智能体到另一个目的地。此时，你应该使用Warp传递一个新位置，而不是用transformation代替它的Transform[C#] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important][backcolor=rgb(108, 226, 108) !important][color=white !important]
agent.Warp(newPosition);
在这个例子中，智能体将停止移动，所以你需要手动计算新路径或者使用SetDestination。
Layers cost
正如我们之前所说，每一个可走动的mesh都有一个指定的layer，以及相关的遍历成本。默认layer 的成本是1，自定义layer需要与之不同，比如，定义一个智能体可能会遇到危险的区域。
为了实现这些，让我们回到Navigation面板的Layer选项卡。在这里我们已经自定义了三个更高成本的layer：
4.jpg (43.64 KB, 下载次数: 17)
18:20 上传
回到Object选项卡并在Navigation Layer下拉列表中使用新的layer。更高成本的区域将会显示不同颜色，记住每次你更改并应用了一个layer，都需要再次烘焙NavMesh。
例如，这里我将地图上浅褐色部分的layer设置为MoreExpensive：
5.jpg (39.24 KB, 下载次数: 17)
18:20 上传
该图描绘的当前场景中，蓝色的智能体将会围绕着目标一路向上走，来避免地图中的成本较高的区域。
可以使用GetLayerCost检查一个navigation layer的成本，传递layer索引，默认layer的索引是0，以此类推。举个例子，这里我检查Expensive layer的成本：floatlayerCost = agent.GetLayerCost(3);
你也可以使用SetLayerCost重新设置layer的成本：[C#] [color=rgb(51, 102, 153) !important]纯文本查看 [color=rgb(51, 102, 153) !important]复制代码
[color=white !important][backcolor=rgb(108, 226, 108) !important][color=white !important]
agent.SetLayerCost(4, 10);
在这里，我改变了MoreExpensive 的layer成本，索引从4变成了10,。注意当智能体禁用时，它的成本将会被重置为在编辑器中的默认值。
默认情况下，一个NavMeshAgent 能在任何已在NavMesh中定义的layer上行走。如果你不希望智能体走在某一个layer上，你可以使用组件属性中的&NavMesh Walkable&下拉列表来设置。
动态障碍物
在地图中定义静态物体是很有用的，但同时在这个场景中智能体还要考虑避免动态物体。它们可能是移动的物体，或者在运行时生成的物体，它们无法再烘焙NavMesh时考虑进来。要实现这点，我们需要使用NavMeshObstacle组件。
在示例中，我创建了另一个游戏物体（褐色的那个），并绑定了NavMeshObstacle组件：
6.jpg (42.6 KB, 下载次数: 17)
18:20 上传
可以在Inspector（检视面板）中改变障碍物的半径和高度。
NavMeshObstacle并不会影响NavMesh，但是智能体将避开障碍物从他们的半径旁边绕过去，如果它们不能从障碍物的周围找到一条有效路径则直接停止。基于这个原因，NavMeshObstacle在生成路径时并不会被考虑进去。
如果你想在寻路时检查障碍物，可以在Inspector（检视面板）中勾选Carve 。在这种情况下，障碍物会在NavMesh上创建一个洞，而智能体将尝试找一条替代路经，以免障碍物阻挡其到达目的地。
默认情况下，智能体的Obstacle Avoidance被设置成High Quality。这使得在两个障碍物之间能做平滑移动，但是消耗太大了。如果你想测试低质量但更快的Obstacle Avoidance类型，可以在游戏物体的NavMeshAgent组件里改变它，在Inspector（检视面板）中。设置成None 会禁用ObstacleAvoidance，你的智能体将忽略这个场景中的动态障碍物。
如何让别人关注你？
感謝分享這麼好的資源!
本楼回复(<span id="dp_count_)
如何让别人关注你？
看到好的文章与好的东西，就要与大家共享，希望一起进步
本楼回复(<span id="dp_count_)
如何让别人关注你？
哥顶的不是帖子，是寂寞！
本楼回复(<span id="dp_count_)
如何让别人关注你？
好好好好好好好好好
本楼回复(<span id="dp_count_)
如何让别人关注你？
Powered by留言簿(20)
随笔分类(186)
随笔档案(194)
积分与排名
阅读排行榜
评论排行榜7343人阅读
unity（20）
一劳永逸地解决寻路问题
作者：PaulT
译者：trcj
&&&&&&&&&通常我都会尽量避免对业内游戏产品或开发者们评头论足。
&&&&&&&&&但这回我不得不破一次例。
&&&&&&&&&我要讨论一些关于寻路的问题。为了证明这些问题至今仍然存在，我本着娱乐的精神制作了这个视频。
&&&&&&&&&（译注：原视频缺失。）
&&&&&&&&&所有片段都录自对应游戏的最新版本。
&&&&&&&&&正如你所看到的，我们在构建一个健壮的寻路系统上还有很长的路要走，这些方方面面的问题甚至存在于一些顶级产品中。
&&&&&&&&&并不是说这是当今游戏的通病。因为时下许多游戏确实拥有高质量的寻路，而且视频里的寻路大部分时间也表现良好。
但是仍有太多的游戏还在使用九十年代的方法。
（说明：为了录制之便，视频里出现的大多数游戏都属于PC平台角色扮演类型，因为当时我的电脑上就只安装了这些游戏。事实上，这些问题不限于任何类型或平台，甚至在主机平台的游戏里也多有出现。）
&&&&&&&&&就我所知，大多数游戏使用路径点（waypoint graph）来实现寻路，它正是我们所碰到的这些问题的首因。
&&&&&&&&&我认为路径点这一做法已经过时。这篇文章将阐述路径点的缺陷，同时通过五条主要论据介绍另一种更为可行的方法。
&&&&&&&&&我曾经在八、九十年代使用过路径点寻路，当时我们面对诸多苛刻的技术限制，不得不舍弃很多东西。
&&&&&&&&&现如今我们身处一个亿万美元的产业之中。面对的平台拥有多核处理器和与日俱增的海量内存，完全具备了实现一个合理的寻路系统的条件。
&&&&&&&&&业内AI开发者中有一句话：“寻路已不是问题。”我们有针对各种寻路问题的各种解决办法，只不过不常使用而已。
而我想说的是，没有任何理由不一劳永逸地总结出一套放之四海而皆准的寻路方案。
为什么路径点不适合用于寻路
让我们来看看一个路径点系统究竟是什么样子。下面是魔兽世界里暴风城一隅。
图1.&魔兽世界暴风城一隅
这是该区域典型的路径点分布图。
图2.&同一区域的路径点分布图
现在我们介绍另一种实现方法，使用凸多边形来表示AI单位可以移动的范围。这种方式可以为AI提供大量的关于周围世界的额外信息，赋予其极大的灵活性。
&&&&&&&&&这种寻路网&#26684;（navigation mesh）看上去是这个样子的：
图3.&使用寻路网&#26684;来标识的同一个区域
现在，我们来逐一列举路径点寻路的五大缺陷。
1.&一些游戏需求的路径点数目过大。
&&&&&&&&&大型开放性区域通常需要散布大量的路径点来实现丰富的移动效果。
&&&&&&&&&如果使用寻路网&#26684;，数个多边形足矣，且寻路更为快捷。
&&&&&&&&&举个例子。下图展示了魔兽中的重镇“哈兰”。这是一大块开放型区域，NPC漫游其间。为了方便演示，我移除了镇子中的旗帜、喷泉。
图4.&哈兰（略修改）
&&&&&&&&&在路径点系统中，我们需要放置众多路径点以覆盖整个地区。即便如此，NPC仍会选择到一些曲曲折折的路径，除非我们继续添加比下图多得多的路径点。
图5.&覆遍路径点的哈兰
&&&&&&&&&如果使用寻路网&#26684;，寥寥数个多边形即可描述整片区域。
图6.&寻路网&#26684;描述的哈兰
寻路网&#26684;使我们免于遍历众多的路径点，效率自然也提高很多。
2.&路径点让结果路径呈现“锯齿状”的弯折。
&&&&&&&&&路径点把寻路单位限制在你创作的路径图中。这意味着单位始终沿着固定轨迹运动，并且几乎永远不会选择由A到B的最短路径，因为最优的直线路径很少能与路径图吻合。
&&&&&&&&&这将导致不自然的寻路，寻路单位走动时会在一段锯齿状的曲折路径上忽左忽右。
&&&&&&&&&以A至B取径点为例。
图7.&哈兰的两个路径点
&&&&&&&&&这是按照前述路径点图得出的取径结果。
图8.由A至B使用路径点进行取径
可以看出，AI单位沿着黄色的路径行走时会经历数次弯折。
理想情况下，在我们选好路径后，可以做一些平滑处理，比如沿着路径点构建出一条。
&&&&&&&&&问题在于，路径点网络没有任何线路以外的信息，很难安全可信地对路径进行平滑调整。
试想一下在线路之外如何创建出一条平滑路径，而保证这条新路径不会引导你摔下索桥。
&&&&&&&&&你或许会寻思是否有其他方法可循，不幸的是，在路径点的体制下，没有。如果我们冒险偏离路线哪怕一点，都有可能酿成坠崖或撞墙的惨剧。我们像路径点图一样对路线之外的东西一无所知。
&&&&&&&&&所以安全起见，我们只好采用最悲观的策略，老老实实待在路线中。
&&&&&&&&&如果使用寻路网&#26684;，取径结果则会大为不同：
图9.&在寻路网&#26684;中由AB漫游
&&&&&&&&&因为能够通过寻路网&#26684;得知寻路单位的安全活动范围，我们得以以任意方式调整取径结果，只要保证在网&#26684;之内即可。
&&&&&&&&&（“哦，”你可能会说，“但是我可以在路径点图中开启更多的连接来达到平滑目的！如果需要NPC直行，我会打开镇中所有节点之间的连接。”
&&&&&&&&&“但是这会导致数据指数级的爆炸，”我回应…“在这个例子里或许额外40或50连接已经足够。但是随着区域增大，你需要应付的节点间的连接数会直&#36924;O(N^2)。”
&&&&&&&&&“好吧，”你又说，“那样的话，我就把相邻三点围成的区域标记为‘开放’，这样AI就可以在这块区域中自由行动啦。”
&&&&&&&&&“这正是一个多边形…而你刚创建了一个寻路网&#26684;，”我提醒道）。
&&&&&&&&&寻路网&#26684;包含活动范围的精确大小，这意味着可以随意使用样条曲线平滑我们的路径，唯一要注意的就是保持曲线在网&#26684;内。
&&&&&&&&&回到暴风城一例，下图分别展示了路径点取径（红色）和经过平滑处理的寻路网&#26684;取径（蓝色）结果。
图10.&路径点取径（红色）及经平滑处理的寻路网&#26684;取径（蓝色）
3.&路径点取径不允许路径修正，这使得动态避开障碍物变得极其困难。
&&&&&&&&&路径点图缺少路线之外的数据，即便对于偏离分毫的区域也无法给出参考信息。
&&&&&&&&&这意味着你不大可能通过修改路径来动态避开障碍物。
&&&&&&&&&想象一个搁置在暴风城石桥上的沉重大木箱。
&&&&&&&&&使用路径点寻路，我们将束手无策。如果箱子横在路线上，我们完全不知道从左边还是右边绕开它，如果箱子完全挡住了去路，我们也不知道是否应该改道。我们只能猜，盼望不要落入水中。
图11.&难以移动的大箱子横在桥当中
&&&&&&&&&如果使用寻路网&#26684;，事情就好办多了。参照网&#26684;提供的活动范围，我们对箱子进行碰撞检测，调整路径绕过障碍，并可以始终保持在网&#26684;的安全区域中。
图12.&绕过箱子行进
&&&&&&&&&当然，你也可以在路径点图中新加路径点来解决问题，直到你的路径点像野草一样稠密（而你的寻路性能像蜜糖一样粘滞）。
&&&&&&&&&不知你意下如何，我倒是宁可在大多边形里运行我的，也不愿在数以百计的路径点中。
4.&路径点不支持寻路参数不同的多个单位。
&&&&&&&&&寻路点不支持寻路单位具有不同的高度、宽度、旋转角度等寻路参数。这意味着你不能仅用一张统一的路径图来匹配游戏中所有的单位类型。
&&&&&&&&&当说起AI寻路，一般我们会想到角色在游戏中漫游。
&&&&&&&&&但是AI系统需要控制多种寻路单位---坦克、飞机、轮船、气垫船、摩托车、兽人、地精、龙、伐木巨人、浮空游荡的生物、等等。很多时候，单位需要根据各自的大小、体型和运动参数来寻路。这些都需要寻路系统给予支持。
&&&&&&&&&举个例子。设想沙漠中有一座掩体，四周环绕沙袋。
图13.&沙漠中的掩体
&&&&&&&&&如果是一名士兵，他大可以沿着沙袋行走（下图红色箭头）。
&&&&&&&&&但如果是一辆装甲坦克，就不得不与沙袋保持一定距离以避免碰撞（蓝色箭头）。
图14.&士兵和坦克沿沙袋行进的路线
&&&&&&&&&使用路径点方法，你无法仅使用一张路径图同时处理两种情况。你需要为坦克和士兵各建一张图。如果加入一个摩托车单位，你还要再建一张。以后每加入一个不同单位你都得新建一张。
&&&&&&&&&如果使用寻路网&#26684;，就简单多了。
图15.&覆盖掩体外围的寻路网&#26684;
&&&&&&&&&注意上图中沙袋弯角处两个浅绿色拐点。假设士兵碰撞半径为1米，坦克碰撞半径为5米，仅使用同一个寻路网&#26684;我们也能容易地可以生成两种规&#26684;的路径。我们只需要计算一条顺着沙袋外沿的路径，然后移出来1米或5米即可。
图16.&覆盖掩体外围的寻路网&#26684;
&&&&&&&&&再举一个例子。想象一名驾驶摩托车的士兵。不比徒步，摩托车很难在行驶时小角度转弯。
&&&&&&&&&下图中，很明显摩托车手可以从当前位置驶进上方的房间（红线），却很难拐进右侧的过道中，因为角度刁钻（橙线）。不论何种寻路，都需要解决这个问题。
图17.&摩托车可以驶进上面房间（红线）却无法进入右边（橙线）
&&&&&&&&&如果使用寻路网&#26684;，仍然简单。在寻路过程中我们只要留意转弯角度及距离，剔出那些短距离小角度的路径即可。
&&&&&&&&&但使用路径点寻路，则基本上不大可能。因为无法使用徒步士兵的路径点，我们至少要为摩托车单独新建一张路径点图。而这种做法无疑导致冗余。
5.&路径点没有足够信息以支持AI除寻路以外的功能。
&&&&&&&&&AI寻路其实不仅仅是为了漫游，还需要从路径信息中得知在世界中如何移动。
&&&&&&&&&游戏角色需要向寻路系统频繁查询：是否可以移动到这里？那里又如何？
&&&&&&&&&如今游戏日渐演变出靠动画驱动的移动系统，开始允许动画师们通过动作控制角色的移动。这意味着如果要知道播放某个动画会产生什么后果，就需要知道动画结束时角色的位置，同时需要知道该位置是否恰巧在一堵墙中，或是掉出了悬崖，又或是关卡设计师不想让玩家进入的地方。
&&&&&&&&&举个例子。下图中的剑客有四种位移：左右平移、后退、腾空20英尺后于8英尺开外落地。
图18.&一个包含四种位移动作的剑客
&&&&&&&&&为了确保这个剑客做动作时不会一头扎进砖墙里，我需要预先根据碰撞网&#26684;，监测每个动作是否可行。
&&&&&&&&&是的，你可以使用碰撞系统，它总能提供有用的信息，对于游戏世界中动态运动的物体，它通常也是知会AI相关信息的唯一办法。
&&&&&&&&&但是碰撞检测代价高昂，如果你只关心静态物体，使用寻路网&#26684;无疑更为快捷。
&&&&&&&&&另外，尽管我可以使用碰撞检测来计算角色和某点间是否有墙体遮挡，碰撞系统却无法告诉我剑客落地的位置是否正处于关卡设计师设定的禁区…这些只有通过寻路网&#26684;来判断。
&&&&&&&&&如果上述内容仍不能让你信服，下面就让我通过一些关于路径点和寻路网&#26684;的问答，来打消你的疑虑吧。
在寻路网&#26684;上取径是否会降低效率？
&&&&&&&&&一点也不会。寻路网&#26684;其实也是一张图（graph），正如路径点图一样，它们的核心寻路过程也极为相&#20284;。不同之处在于寻路网&#26684;图中每一个节点都关联一个多边形。
&&&&&&&&&下图展示了被图结构关联起来的多边形。
图19.&寻路网&#26684;的构架是一张图（红色）
&&&&&&&&&A*算法始终运行在某个图结构中，无论它是方&#26684;、路径点图还是寻路网&#26684;图。
&&&&&&&&&大多数情况下，寻路网&#26684;的性能和路径点接近。在使用寥寥数个节点覆盖一片区域时（例如图6），寻路网&#26684;性能提升显著。
寻路网&#26684;是否会耗费更多内存？
&&&&&&&&&手法正确的话，不会。
&&&&&&&&&寻路网&#26684;结构精简。总的来说，相比用于供渲染的模型网&#26684;，寻路网&#26684;不足其数分之一。相比碰撞模型，寻路模型关心的面数更少（它忽略墙、顶棚和其他脚力不可及的区域），而且往往使用更大号的多边形覆盖给定区域。
&&&&&&&&&最坏情况下，寻路网&#26684;在每个图节点上使用的顶点数目也许会多于路径点图。但很多时候，如图6的哈兰，寻路网&#26684;要比路径点简洁许多。
大多数你展示的例子都出自角色扮演游戏。为什么没看到第一人称射击游戏存在这类问题？
&&&&&&&&&很多FPS游戏都存在这个问题，不过缘于该类游戏本身玩法，此类问题不易被定位。
&&&&&&&&&-&大多数AI都不会存活太久，难以发现其寻路缺陷。
&&&&&&&&&- AI通常在你进入视线后即停下射击，寻路一般偏短。
&&&&&&&&&-&许多单人FPS游戏中，AI少动，更倾向于原地朝你放枪。
&&&&&&&&&-&当今许多FPS游戏提供AI队友，它们击毙敌方AI，不留任何长距离跑路的机会。
&&&&&&&&&这里有一个半条命2的例子。通过一点小实验，不难发现梯子上的卫兵被限制在梯子中间直上直下的一条路线上，始终寻找着照面时刻射杀你的机会。
&&&&&&&&&（译注：原视频再次缺失。）
&&&&&&&&&如果你取消远程武器强制角色们近身肉搏---《光晕》里的星盟士兵，《先头部队》里的克隆杀手，或者《银河战士》里的浮游者---便会发现路径点突然成为了一个极其不堪的选择（这也是上述三个游戏使用寻路网&#26684;替代路径点的原因之一）。
瞧，我理解你的意思，但是设计师们需要在游戏里放置掩体点、巡逻路径等。这对我们游戏的AI来说必不可少。
&&&&&&&&&当然！即便使用了寻路网&#26684;，你仍然可以这么做。
&&&&&&&&&关键在于分离两个系统。你使用一个（寻路网&#26684;）来实现寻路及漫游，使用另一个（设计师放置的这些点）告诉AI如何与游戏世界交互。
&&&&&&&&&寻路网&#26684;不应该成为你使用任何系统的障碍，它只是简单地为丰富AI寻路提供了额外信息。
&&&&&&&&&举个例子。我们设置了巡逻路径（紫色）让卫兵在城镇附近巡逻，为一个老家伙设置特殊的点让他每天到护城河边垂钓（红色）。掩体点方便暴风城的法师和术士们做FPS式的决斗时寻找掩护。
图20.&多种地标点（所有颜色）和寻路网&#26684;共存
好吧，但是放置寻路网&#26684;难道不会花费很多时间吗？
&&&&&&&&&整体来说，手动放置寻路网&#26684;的工作量不会比设置路径点来的更繁重。两种体制下，放置寻路信息的时间都远远小于游戏中测试它们的时间。
&&&&&&&&&以我的经验来说，放置一个中等规&#26684;的FPS关卡寻路网&#26684;需要花费1-3小时时间。
&&&&&&&&&创建一个寻路网&#26684;编辑器相对比较简单。你要实现的功能就是放置顶点到游戏世界中，选取并将他们组织成多边形。你可以通过多边形邻边共享的顶点来决定寻路网&#26684;之间的连通性。
&&&&&&&&&同时，有一些中间件可以帮你完成构建寻路网&#26684;和实时寻路的工作，例如，&，及。这些解决方案都在日渐完善中。
如果我有一个爬楼梯的AI怎么办？我们的设计师可不喜欢为楼梯上每个台阶铺设一个寻路网&#26684;。
&&&&&&&&&寻路网&#26684;只是标识了Ai可以行动的区域。它不能用于代替碰撞检测模型---你的NPC仍然需要碰撞系统来支持游戏中的碰撞。
&&&&&&&&&你只需一个大矩形覆盖整个楼梯即可。
难道我不能给每个路径点赋一个半径信息，用圆来替代点？这样我就可以知道那些区域可以走动。这是正他们在robotics里的做法…
&&&&&&&&&这个方法在某些场合行得通，但是游戏中的大多数区域遍布弯弯角角的街道和建筑。圆形无法和这些空间契合得很好，在覆盖该类型区域的便利性上较使用多边形相去甚远。
&&&&&&&&&下方展示了在暴风城使用圆形扩展路径点进行寻路的示意图。
图21.&路径点扩展为圆
&&&&&&&&&（小轶事：当我在《机甲战士4：复仇》小组工作时，我们发现在户外表现良好的圆形系统一旦应该用到城镇中立刻不再适用。我们最终解决了这个问题，但是得到一个教训：圆和城市水火不容！）
&&&&&&&&&与此同时，留下边角也是很重要的。在图16的沙漠掩体一例中，我们使用寻路网&#26684;的边角针对士兵和坦克不同的形体、大小和运动参数生成不同的路径。圆图不支持边角，所以为不同单位创建不同路径也会变得相当困难。
我的游戏已经有了碰撞模型，我能用它作为寻路网&#26684;吗？
&&&&&&&&&你可以试试，但这可不是个好主意。
&&&&&&&&&碰撞模型被优化以便于碰撞、而非寻路。它往往包含比寻路需要的多得多的多边形，因此你的寻路算法会变得很慢。
&&&&&&&&&例如，一条鹅卵石街道上的碰撞模型也许有1000个多边形，而只需一个寻路矩形。一个建筑顶棚的碰撞模型含50个多边形，但根本不需要寻路网&#26684;（因为我们的角色或许永远不会走上屋顶）。
&&&&&&&&&同时，寻路网&#26684;的一部分优势在于它不仅仅告诉你寻路单位可以移动的范围；还告诉你设计师想让他们在哪里移动。
&&&&&&&&&如果你让你的设计师手动创建寻路网&#26684;，他就可以标识某处“AI免进。这里拒绝任何单位进入，因为这个游戏设定如此。”这些信息是碰撞模型永远给不了的。
上面所有的例子里寻路网&#26684;&#20284;乎都是到2D空间的投射。我如何处理道路穿过桥洞，何时能够通过何时不能，或者多楼层建筑的情况？
&&&&&&&&&寻路网&#26684;能优雅地解决这些问题。下面是魔兽世界沙塔斯寻路网&#26684;分布的样子（简便起见，我省略了桥远侧的部分网&#26684;）。
图22.&沙塔斯，覆盖桥上或穿行桥下的寻路网&#26684;
&&&&&&&&&在寻路网&#26684;中，每个多边形通常存储有一个表示通行高度的参数。例如，穿行于桥下的多边形被标识为7英尺，那么那些高于7英尺的单位将无法从桥洞通过。
&&&&&&&&&对于多楼层建筑的情况，每个楼层有独立的寻路网&#26684;，之间通过楼梯的寻路网&#26684;连接（当然，电梯略棘手）。
我不相信会有放之四海而皆准的办法。不同的游戏需求不同的寻路之法。
&&&&&&&&&如果你正制作一个纯2D策略类游戏，那么一个基于方&#26684;的寻路算法更为合适，因为&#26684;子允许更快捷地访问任意地块。
&&&&&&&&&否则，寻路网&#26684;真的是3D世界中解决寻路及地形物理的最佳方法。
我想在自己的游戏中实现寻路网&#26684;。有没有资料可以帮助我理清如何生成网&#26684;，如何在其上寻路，以及如何在游戏中优化它们？
我所知道的资料如下：
&Simplified 3D Movement and Pathfinding Using Navigation Meshes& by Greg Snook ()
&Polygon Soup for the Programmer's Soul: 3D Pathfinding& by Greg Hjelstrom and Patrick Smith ()
&Building a Near-Optimal Navigation Mesh& by Paul Tozour ()
&Efficient Navigation Mesh Implementation& by John C. O'Neill ()
&Search Space Representations& by Paul Tozour ()
&A Fast Approach To Navigation Meshes& by Stephen White and Christopher Christensen ()
&Choosing a Relationship Between Path-Finding and Collision& by Thomas Young ()
&Improving on Near-Optimality: More Techniques for Building Navigation Meshes& by Fredrik Farnstrom ()
&Smoothing a Navigation Mesh Path& by Geraint Johnson ()
&Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision& by Paul Marden and Forrest Smith ()
&Intrinsic Detail in Navigation Mesh Generation& by Colt McAnlis and James Stewart ()
&Navigation Mesh Generation: An Empirical Approach& by David Hamm ()
&Navigation Mesh Generation in Highly Dynamic Worlds& by Ramon Axelrod ()
&Crowds in a Polygon Soup: Next-Gen Path Planning& by David Miles ()
注意：如果你有相关资料想在此列出，请。
实际有多少游戏成功应用了寻路网&#26684;？
这里有一个名单：
…更多的例子枚不胜举。
看起来所有扮酷的同学都用了这个。
好吧，它或许对你适用，但是我们之前所有的游戏使用的都是路径点寻路，表现良好。
如大家所说，如果它还能用，就别去管它…而且你说的那些问题我们一个都还没碰到哩。
&&&&&&&&&目光放长远点，想象一二十年以后的光景。
&&&&&&&&&到那时，你认为你的游戏会不会包含众多不同的AI控制的不同角色，各自又有不同的体型、大小、运动参数？
&&&&&&&&&玩家们会不会想要和他们一样聪明的AI伙伴？
&&&&&&&&&你的游戏会不会比今天更庞大、更复杂、更具变化性？
&&&&&&&&&你会不会同时拥有有数量众多的AI角色---多到简单的转向和规避障碍已经不足以满足AI间丰富高效的交互？
&&&&&&&&&你的游戏会不会引入高仿真的物理系统，玩家们会不会随心所欲地使用物理和AI角色打成一片？
&&&&&&&&&玩家们可不可以把游戏世界改造得面目全非？
&&&&&&&&&会不会有AI在多人游戏中完全替代真实玩家？
&&&&&&&&&二十年后的游戏会是什么样子我们无从得知，可以预见的是我们需要更高级的AI，虚拟角色们需要更多的数据来演绎环境，优化寻路，应对千变万化的游戏世界。
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：37486次
排名：千里之外
转载：36篇
(1)(9)(1)(1)(1)(2)(15)(8)(30)}