1.0 网格导航介绍
体验地址：
Github Page:Cocos Creator | Easy_Navi
Gitee Page:Cocos Creator | Easy_Navi
视频说明
B站地址：Cocos Easy NavMesh 使用说明_哔哩哔哩_bilibili
导航网格（Navigation Mesh），简称NavMesh，NavMesh会存储可行走区域的网格信息，用以在复杂的3D空间中实现导航寻路等功能，
导航网格是由多个多边形网格（Poly Mesh）组成的，以下简称为 Poly，即上图中的黑色描边的淡蓝色色块部分。
Poly 专门指的是导航网格的组成单位，在导航网格中的寻路是以 Poly 为单位的，在同一个 Poly 中的两点，在忽略地形高度的情况下， 是可以直线到达的；如果两个点位于不同的 Poly，那么就会利用寻路算法（比如A*算法）算出需要经过的 Poly，再算出具体路径。
为什么使用NavMesh，不使用路径点
在早期3D游戏中，路径点是一种常用的寻路方式，但路径点不光生成和配置比较麻烦，还有一个更严重的缺点。
以魔兽世界中的暴风城一角为例，当使用路径点时，AI的行为是有限的，只能在路径点之间的连线上移动。
当使用Navmesh时，通过计算人物的信息（如体积，行走高度，可上坡角度等），用以烘焙出NavMesh信息；地图上的可以行走区域，由淡蓝色的Poly组成。
通过Navmesh，人物的移动区域更加灵活，可以实现更复杂的AI行为。
如下图所示，可以在河边任何位置摸鱼，也可以实现人物出城和躲避到树林当中。
再举一个更有说服力的例子，在魔兽世界怀旧服纳格兰的哈兰岛上，使用NavMesh可以涵盖整个区域，AI的行为和表现也会比路径点更加智能，基本可以涵盖哈兰岛的各个角落。（当然有些特殊的情况，比如跳跃等，我们还是可以通过路径点实现）
NavMesh同时还可以通过高度参数和角度参数实现角色的斜坡移动，实现上桥，下桥等行为，以魔兽沙塔斯城为例，参考下图Poly部分。
当有了这些Poly网格，就可以借助A*算法来实现寻路功能。
这里使用了bgrin大佬的A*开源库，并翻译和修改了数学库，转换了成了TS版本。（https://github.com/bgrins/javascript-astar）
传统A 的搜寻路线如下图，基于网格，和网格中的障碍点网格，进行寻路算法。
在NavMesh生成的Poly块中，数据已经基于实现了基于地图的网格化，我们考虑的问题是，如果寻找最优的落地点，而不是让沿着下图Poly的黄线移动，或者直接从起点走到终点。
3.0 Cocos 的NavMesh解决方案
考虑到目前Cocos 3.0 有部分产品主要面向H5或者快游戏市场，对包体大小和性能消耗的需求都比较严格。
所以Easy NavMesh 采用了基于PatrolJS (https://github.com/nickjanssen/PatrolJS)方案实现的轻量级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格式导出，方便跨平台支持。
不同于其他引擎，比如在Unity中，有提供专门的Navigation, 用于寻路导航，玩家可以根据角色的高矮胖瘦，和角色能攀爬的最大角度，预先烘焙好NavMesh；或者在babylon.js 中，用户也可以通过wasm+recast.js 实现类似的需求。
3.1 NavMesh信息优化
EasyNavMesh 通过以下3中途径获取NavMesh的Json信息。
–支持recast.js 导出 json数据（recast.js+wasm 封装到了导出插件中，下文做详细介绍。
–支持 Unity NavMesh插件导出（可以使用CocosNavmesh.unityasset 进行安装，包含在插件当中，这里只导出需要的面和顶点信息等数据，同时支持小数点的精度调整，方便压缩Json的体积）
这里的导出方案我们使用了Cocos自带消息通知，支持导出整个场景或导出NavMesh需要的Json Mesh
–支持 Blender Navmesh 导出Obj，再使用 Python 脚本进行转换，这个脚本是基于OBJ to three.js Json Mesh 进行了修改，剔除了无用了normal，uv等信息。（原作者：AlteredQualia http://alteredqualia.com)
通过Cocos解析这些Json后，我们就可以使用Json中的定点信息和面的信息，构建导航网格的数据，为了灵活适配，这些网格信息也可以放在服务器或者通过脚本新建对象来储存。
3.2 其他优化
A. 剔除了第三方Vector3 的数学库，使用Cocos的Vec3替代，避免了Cocos 的Vec3类和其他V3坐标类之间的2次转换。（剔除其他引擎的V3类数学库，全部使用Cocos的Vec3）
B. 原库使用了OBJ格式，或者Three.js 的Json Model，这里一步到位，可以直接通过Cocos或者Unity导出Json信息，信息提前做了小数点精度保留，减少了Json体积和处理OBJ信息的运算量，Size Does Matter~
C. 提供了可视化的Cocos NavMesh烘焙工具和Unity 烘焙导出工具，目前Cocos NavMesh烘焙数据基于recast.js 参数较多，烘焙效果不如Unity理想。如果为了追求最佳效果，可以使用Cocos NavMesh导出工具，导出整个场景到OBJ文件，再在Unity内烘焙这个OBJ场景。整个工作流比Unity导出 NavMesh的OBJ，再通过Python转换，再做精度处理要节省了50%以上的时间。
4.0 更多内容
移植了ThreeJS的Plane和Triangle类，重新使用Cocos的 Vec3 Mat4数学库进行了编译。
实现了基于NavMesh ClampSteped的移动。
借助ClampSteped，无需使用 Cocos自带的Cannon或者Ammo物理引擎，人物也无需添加刚体，是基于ThreeJs的Plane和Triangle库的数学方法实现的。
ClampSteped是一个不太成熟的方案，目前只提供了基础Demo，后续的优化需要依靠各位大佬，使用ClampSteped替代物体，需要注意设置好物体半径，太小容易导致穿模，太大容易穿墙。
5.0 to-do-list
*加入更多基于NavMesh 的游戏Demo，比如捉迷藏
*clampstep 优化，实现基于clampstep 的FPS NavMesh Demo（下次一定！）
6.0 FAQ
Q1: 为什么有时候路径不是视觉上最近的？
A: 在NavMesh中A*算法是以Poly作为网格的，在复杂的网格地形中，到最近的距离点的Poly组数反而可能比较多。
Q2：为什么ClampStep这个东西容易穿墙
A: 目前数学库都是从Three.js翻译的，这个ClampStep在Three的项目中使用也较少，可以参考的demo不多，需要进一步适配cocos，后续版本会不停调优。
Q3：这么多导出NavMesh Json的方法，那个最好
A: 目前来Unity烘焙的NavMesh效果最好，但Cocos版本借助开源的recast.js，和编辑器结合紧密，更加方便，大佬们有更优的方案，请多多指导。
Q4: 为什么Unity 导出的无法像Demo里一样走楼梯
A: 这里使用的是A*算法，楼梯上Poly必须连到一起，可以通过改变人物的高度（Agent Height）和人物的移动高度（Step Height)使楼梯变成斜坡，解决这个问题
Q5：为什么这次不给白嫖？
A: 本文阐述了原理，为了能熬夜水更多，大佬们可以支持我一杯咖啡，从商店下载更方便喔~
7.0 Support Me
深圳疫情严重，居家隔离办公，开发不易，目前Cocos 商店已经上架了，限时骨折价（1 coffee only!），大佬们请多多支持。
！
