NavMesh 导航网格神级插件发布！高效实现 3D 自动寻路
寻路是游戏开发中不可忽视的功能之一，NavMesh 导航网格寻路则被广泛用于在复杂的 3D 游戏世界中实现动态物体自动寻路。开发者 iwae 创作了插件 Easy NavMesh，在 Cocos Creator 3.x 中实现了完善的 3D 自动寻路功能。
导航网格（Navigation Mesh，简称 NavMesh）能够存储可行走区域的网格信息，用以在复杂的 3D 空间中实现导航寻路等功能。
导航网格是由多个多边形网格（Poly Mesh，以下简称为 Poly）组成的，即上图中的黑色描边的淡蓝色色块部分。导航网格中的寻路以 Poly 为单位，同一个 Poly 中的两点，在忽略地形高度的情况下，是可以直线到达的；如果两个点位于不同的 Poly，那么就会利用寻路算法（比如 A* 算法）算出需要经过的 Poly，再算出具体路径。
NavMesh 与路径点
为什么选择使用 NavMesh，而不用路径点进行寻路呢？
在早期 3D 游戏中，路径点是一种常用的寻路方式，但路径点不光生成和配置比较麻烦，还有一个更严重的缺点。以下图《魔兽世界》中的暴风城一角为例，当使用路径点时，AI 的行为是有限的，只能在路径点之间的连线上移动。
而 Navmesh 则可以通过计算人物的信息（如体积、行走高度、可上坡角度等），用以烘焙出 NavMesh 信息，下图淡蓝色 Poly 即代表了地图上的可以行走的区域。
通过 Navmesh，人物的移动区域将更加灵活，可以实现更复杂的 AI 行为。如下图所示，人物可以在河边任何位置摸鱼，也可以实现出城和躲避到树林当中。
再举一个更有说服力的例子，在《魔兽世界》怀旧服纳格兰的哈兰岛上，使用 NavMesh 可以涵盖整个区域，AI 的行为和表现也会比路径点更加智能，基本可以涵盖哈兰岛的各个角落（当然有些特殊的情况，比如跳跃等，我们还是可以通过路径点实现）。
NavMesh 同时还可以通过高度参数和角度参数实现角色的斜坡移动，进行上桥、下桥等行为。以《魔兽》沙塔斯城为例，参考下图 Poly 部分。
当有了这些 Poly 网格，就可以借助 A* 算法来实现寻路功能。这里使用了 bgrins 大佬的 A* 开源库[1]，并翻译和修改了数学库，转换了成了 TS 版本。
传统 A* 的搜寻路线的方式是基于网格和网格中的障碍点网格，进行寻路算法，如下图所示。
在 NavMesh 生成的 Poly 块中，数据已经实现了基于地图的网格化，我们需要考虑的问题是：如何寻找最优的落地点，而不是让人物沿着下图 Poly 的黄线移动，或者直接从起点走到终点？
Easy NavMesh
Easy NavMesh 是一个用于 Cocos Creator 3.x 的轻量级网格导航库，采用了 A*+ 漏斗算法，整个库只有 40KB 不到，可以满足 H5/小游戏平台对包体大小和性能消耗的需求；同时预烘焙 NavMesh 网格信息保存为了 Json 格式，来确保加载和运行效率。
漏斗算法+A*
Easy NavMesh 采用了基于 PatrolJS[2] 实现的轻量级 TS 库，放弃了使用 recast.js+wasm 的组合，将库的大小控制在 40KB 以下。PatrolJs 采用了比较简单的漏斗算法(Simple Stupid Funnel Method)+A* 的组合，通过漏斗算法正好可以解决上一章我们遇到的 Poly 移动问题。
漏斗算法放弃了找寻 Poly 的边缘的中点（虽然这方法可以让路径变得平滑，在《生或死4》中有采取过类似方案），而是通过循环算法，不断缩小三角形漏斗的范围（可以理解为三角形的角度），这个方法计算频率高，但是更简单而有效。
下面我们通过几个实例图，演示漏斗算法通过算小漏斗角度，定位出路径点的过程。
检查 A 图的第一个 Poly 左右2个点，是否在红线和蓝线组成的三角形漏斗范围内，再依次走 B 图到 D 图的3个 Poly，我们看到，三角形漏斗的角度不断变小，漏斗的范围变得越来越小。
接着我们遍历 E 图和 F 图新增的2个 Poly，我们发现E图右边的端点（标记 x 的一边，为了方便理解，这里的位置都是图片上实际的位置，不是 Poly 顶点的位置）在之前 D 图生成的三角形漏斗之外，而且 D 图的红线能到达 E 图的第5个 Poly，这里漏斗就停止更新，不缩小角度。
E 图没有更新，接着 F 图新增的蓝线又在漏斗外，D 图的红线无法到达第6个 poly，这时候我们结束漏斗算法，把直接 A 到 D 生成的红线作为第一个路径，从 G 图开始，重新生成了一个新的三角形漏斗，开始新的漏斗算法。
有了漏斗算法之后，我们就可以使用 A* 配合漏斗，获取正确的路线。
static findPath(startPosition:Vec3, targetPosition:Vec3, zoneID:string, groupID:number) {
const allNodes = this.zone[zoneID].groups[groupID];
const vertices = this.zone[zoneID].vertices;
let closestNode = null;
let distance = Infinity;
let measuredDistance
for (let i = 0, len = allNodes.length; i < len; i++) {
const node = allNodes[i];
measuredDistance = Vec3.squaredDistance(node.centroid, startPosition);
if (measuredDistance < distance) {
closestNode = node;
distance = measuredDistance;
}
}
let farthestNode = null;
distance = Infinity;
for (let i = 0, len = allNodes.length; i < len; i++) {
const node = allNodes[i];
measuredDistance = Vec3.squaredDistance(node.centroid, targetPosition);
if (measuredDistance < distance &&
nUtils.isVectorInPolygon(targetPosition, node, vertices)) {
farthestNode = node;
distance = measuredDistance;
}
}
// If we can't find any node, just go straight to the target
if (!closestNode || !farthestNode) {
return null;
}
//A*寻路算法
const paths = Astar.search(allNodes, closestNode, farthestNode);
const getPortalFromTo = function (a, b) {
for (let i = 0; i < a.neighbours.length; i++) {
if (a.neighbours[i] === b.id) {
return a.portals[i];
}
}
};
//使用漏斗算法，结算出最佳路线
// Got the corridor,pull the rope
const channel = new Channel();
channel.push(startPosition);
for (let i = 0; i < paths.length; i++) {
const polygon = paths[i];
const nextPolygon = paths[i + 1];
if (nextPolygon) {
const portals = getPortalFromTo(polygon, nextPolygon);
channel.push(vertices[portals[0]], vertices[portals[1]]);
}
}
channel.push(targetPosition);
channel.stringPull();
// Return the path, omitting first position (which is already known).
return channel.path;
}
预烘焙方案
为了减少数据开销，Easy NavMesh 使用预烘焙方案，提前把 Navmesh 数据以 Json 格式导出，方便跨平台支持。
Easy NavMesh 提供了多种导出工具，支持 recast.js 动态导出 Json 数据、Blender Navmesh 导出 OBJ 等，开发者可以根据需求来选择：
支持 recast.js 导出 Json 数据。可以使用 Cocos Creator 提供的 NavMesh 导出面板，导出 NavMesh 信息为 Mesh Json 格式；也可以通过面板把整个场景导出为 OBJ，用 Blender 等工具进行 NavMesh 信息处理。
支持 Blender Navmesh 导出 OBJ 格式，再使用 Python 脚本进行转换（该脚本基于 OBJ to three.js Json Mesh 进行了修改，剔除了无用的 normal、UV 等信息，原作者：AlteredQualia[3]）。
引擎解析这些 Json 后，我们就可以使用 Json 中的定点信息和面的信息，构建导航网格的数据。为了灵活适配，这些网格信息也可以放在服务器或者通过脚本新建对象来储存。
ClampSteped
支持基于 ClampSteped 的移动。借助 ClampSteped，可以使用 NavMesh 烘焙好的网格信息，无需使用 Cocos 自带的 Cannon 或者 Ammo 物理引擎，人物也无需添加刚体，是基于 ThreeJs 的 Plane 和 Triangle 库的数学方法实现的（Easy NavMesh 移植了 ThreeJS 的 Plane 和Triangle 类，重新使用 Cocos 的 Vec3 Mat4 数学库进行了编译）。
ClampSteped 目前还是一个不太成熟的方案，现在只提供了基础 Demo，后续的优化需要依靠各位大佬，使用 ClampSteped 替代物体，需要注意设置好物体半径，太小容易导致穿模，太大容易穿墙。
其他优化
Easy NavMesh 剔除了第三方 Vector3 的数学库，使用 Cocos 的 Vec3 替代，避免了 Cocos 的 Vec3 类和其他 V3 坐标类之间的2次转换。
原库使用了 OBJ 格式，或者Three.js 的Json Model，这里一步到位，可以直接通过 Cocos 导出 Json 信息，信息提前做了小数点精度保留，减少了 Json 体积和处理 OBJ 信息的运算量，Size Does Matter~
常见问题 QA
Q1: 为什么有时候路径不是视觉上最近的？
A：在 NavMesh 中 A* 算法是以 Poly 作为网格的，在复杂的网格地形中，到最近的距离点的 Poly 组数反而可能比较多。
Q2: 为什么 ClampStep 容易穿墙？
A：目前数学库都是从 Three.js 翻译的，这个 ClampStep 在 Three 的项目中使用也较少，可以参考的 Demo 不多，需要进一步适配 Cocos，后续版本会不停调优。
Q3：后续有优化计划吗？
A：Easy NavMesh 会持续更新维护。首先我计划加入更多基于 NavMesh 的游戏 Demo，比如捉迷藏；此外优化 ClampSteped，实现基于 ClampSteped 的 FPS NavMesh Demo（下次一定！）。
资源链接
Easy NavMesh 现已发布，点击文末【阅读原文】至 Cocos Store 即可获取，大佬们多多支持~更多详细说明见论坛，也欢迎大家到帖子里交流反馈！
Easy NavMesh 下载-Store
https://store.cocos.com/app/detail/3641
论坛专贴
https://forum.cocos.org/t/topic/132913
福利时间
4月8日，我们将从本文评论区随机抽取3位走心留言的小伙伴，送出 Easy NavMesh 插件资源1个！欢迎多多转发给需要的朋友~
本文为社区第4期征稿活动参与作品
点击上图查看活动详情
参考资料
[1] A* 开源库丨bgrins
https://github.com/bgrins/javascript-astar
[2] PatrolJS
https://github.com/nickjanssen/PatrolJS
[3] AlteredQualia
https://alteredqualia.com/