《火炬之光2》小细节：游戏中的寻路功能

用A星算法。

【自动寻路的使用方法】
　　一、使用附近玩家/NPC定位坐标点：
　　1、按“F”键打开“附近玩家/NPC”界面，切换到“NPC”一栏。
　　2、该地图所有NPC名称将显示在“附近玩家/NPC”界面的“NPC”一栏列表里。双击想要寻找的NPC名字，即自动行走到NPC身边。
　　二、使用大地图指定位置：
　　1、按“M”键打开游戏大地图，当前地理位置及地图分布一目了然。
　　2、鼠标单击大地图可走到的地点，即自动行走到该指定点。
　　3、按“M”键打开大地图后，鼠标在大地图上随意移动的同时，鼠标旁及时显示所移动到的地方坐标。　　【自动寻路的特点】

f(n)=g(n)+h(n) 从起始点到目的点的最佳评估值
– 每次都选择f(n)值最小的结点作为下一个结点，
直到最终达到目的结点
– A*算法的成功很大程度依赖于h(n)函数的构建
?;) = g(n? 在各种游戏中广泛应用 Open列表和Closed列表
– Open列表
A*算法
? h(n) = 从结点n到目的结点的耗费评估值，启发函数
?，程序返回n
else 生成结点n的每一个后继结点n;
foreach 结点n的后继结点n;{
将n’的父结点设置为n
计算启发式评估函数h(n‘)值，评估从n‘到node_goal的费用
计算g(n‘) = g(n) + 从n’到n的开销
计算f(n?? 在算法启动时，Closed列表为空 A* 算法伪代码初始化OPEN列表
初始化CLOSED列表
创建目的结点；称为node_goal
创建起始结点；称为node_start
将node_start添加到OPEN列表
while OPEN列表非空{
从OPEN列表中取出f(n)值最低的结点n
将结点n添加到CLOSED列表中
if 结点n与node_goal相等then 我们找到了路径;)
if n‘位于OPEN或者CLOSED列表and 现有f(n)较优then丢弃n’ ;) + h(n?? 包含我们还没有处理到的结点
? g(n) = 从初始结点到结点n的耗费
?? 包含我们已经处理过的结点
，处理后继n’
将结点n‘从OPEN和CLOSED中删除
添加结点n‘到OPEN列表
}
}
return failure （我们已经搜索了所有的结点?? 启发式搜索
– 在搜索中涉及到三个函数
??? 我们最开始将起始结点放入到Open列表中
– Closed列表
?

现在的大部分mmo游戏都有了自动寻路功能。点击场景上的一个位置，角色就会自动寻路过去。中间可能会有很多的障碍物，角色会自动绕过障碍物，最终达到终点。使用Unity来开发手游，自动寻路可以有很多种实现方式。
　　最近，一名海外开发者在博客中分享了自己用Unity引擎重做此前研发的Flash游戏寻路导航的心得，希望可以给大家带来帮助：
　　大家好，最近我一直都在忙于把2006年的一款Flash游戏用Unity引擎重做出来，尽管我们在《Arrival in Hell》这个项目已经工作了一年多，但这里我希望从头开始来写开发者博客，因为这样才能让读者们有比较完整的印象。
　　如果你们不太熟悉这款游戏的话，我这里做几句话的介绍，我们在对2006年我和朋友Eduardo Mojica以及Richard Rout三人研发的一款Flash游戏进行重做，这是一款点击式操作的冒险游戏，我们将用Unity引擎进行重做。我做编程和研发游戏已经有十年左右的经验，但这是我使用Unity引擎做的首款游戏。
　　在其他事情之前，我首先想要说的就是玩家角色的移动，由于这款游戏现在是真正的3D，因此玩家角色需要在3D空间里寻路。幸运的是，Unity引擎已经有了一些不错的内置寻路功能，你只要打开窗口-导航（Navigation），选择你想要使用的物体并且放到路径中，然后把他们标记为‘导航静态（Navigation static）’这就会告诉Unity这些物体是静态的（非移动），在寻路的时候应该被考虑进去。

把物体设置为‘导航静态’
　　这里我想要说一说这个功能有多么强大。过去，我和大多数的游戏开发者一样，都必须打造自己的寻路系统，我之前就做过一个A*tile和基于节点的寻路系统，在两种情况下，特别是基于节点系统的寻路所产生的walls让人非常头痛。在基于节点的寻路系统中，你必须手动地把AI使用的点在两者之间进行导航。Unity不仅做导航功能，还使用了导航网格（Navigation meshes），这比手动放置节点更有效率而且更流畅。更重要的是，你还可以一键重新计算整个导航网格，彻底摆脱了手动修改导航节点的做法。

我用基于节点系统做的失败的寻路系统之一
　　在把静态物体加入了导航网格之后，你可以选择一系列的设定然后点击bake按钮，比如在考虑加入一堵墙之前确定坡有多陡以及台阶应该多高。这样你就可以获得可以预览的视图。值得注意的一件事是，不要仅仅因为物体存在在场景中就意味着它是导航网格的一部分。比如说在这款游戏中，我不在乎玩家们是否会踩到瓦砾，所以我并没有把任何瓦砾标识为导航静态，这加快了当行网格的生成速度。

《Arrival in Hell》中其实是有数值的
　　在导航网格生成之后，我简单地给玩家模型增加了一个NavMeshAgent组件，这款游戏现在就可以进行寻路了，唯一剩下的就是增加鼠标输入控制NavMeshAgent的目的地。

用NavMesh做的bake

NavMeshAgent设定
　　为了告诉NavMeshAgent导航我做了以下指令：
　　1.注意听取鼠标输入
　　2.把鼠标放进屏幕空间
　　3.把屏幕空间转变成来自摄像头的一束光
　　4.在光达到地面的时候把它移除
　　5.把NavMeshAgent的目的地设定到地板的对应位置。
　　C#代码是这样的：

可视化视图下的目的地与路径
　　这就解决了我这款游戏的大多数导航需求，唯一的例外就是导航网格由于游戏内的一些活动而发生改变的时候。比如第一个房间的们最开始是关闭的，后来当它打开的时候，当行网格需要更新反映此次变化，允许玩家从新开的们中走过去。我并没有在游戏运行的时候rebake完整的静态导航网格，而是使用了NavMeshObstacle组件，该组件可以让你把寻路过程中的动态物体加进去，如果物体移动，Unity的寻路算法就会根据实际情况而更新。

导航路径会根据NavMeshObstacle的变化而自动发生改变

可视化视图
　　所以，游戏寻路导航就这么做好了，这就是《Arrival in Hell》游戏中的导航工作原理，这一些只需要Unity内自带的导航功能就可以完成了。

现在系统不是已经有了自动寻路了吗