?
前言
在游戏开发过程中，寻路可能是大多数游戏都必不可少的功能。2d游戏中最常用的就是A* 寻路了。在3d游戏中，对于一些简单的，没有高度地面A* 寻路同时也是可以使用的，但是对于一些地面比较复杂的游戏，寻路功能怎样实现比较好呢！
效果展示
Cocos Creator3.x:NavMesh 导航网格寻路
1.RecastNavigation
相信了解过3d寻路的小伙伴都有听说过RecastNavigation。RecastNavigation是一款非常强大的寻路系统，被广泛的应用于各大游戏引擎中。如Unreal，Unity等。
NavMesh的生成基本原理：
-
体素化。从源几何体构造实心的高度场，用来表示不可行走的空间。
-
生成地区。将实心高度场的上表面中连续的区间合并为地区。
-
生成轮廓。检测地区的轮廓，并构造成简单多边形。
-
生成多边形网格。将轮廓分割成凸多边形。
-
生成高度细节。将多边形网格三角化，得到高度细节。
感兴趣的小伙伴们可以去了解一下，甚至可以去了解了解源码。源码也去看过，奈何自己C++实在太差
2.耳切法+A*
大概了解了导航寻路的原理，觉得整个寻路的关键可以分为两部分：网格画与寻路，所以决定自己尝试一下，现从最简单的没有高度的地图入手
大概步骤：
-
1.基于耳切法实现地图的网格化
-
2.基于A* 实现寻路
-
3.基于漏斗算法将三角形集合进行路径最优解 在最终的尝试下，
-
?
-
基本的寻路功能是实现了，但是在路径的优化方面会存在一些问题，所以决定去寻找一些现成的js库来实现这个功能
3.NavMesh 导航
在github闲逛的时候发现了recast.js这个库，于是乎就开始花时间去了解了一下具体功能和API，同时还发现在Babylon.js这个3d游戏引擎中已经将其集成进去了，并且这个游戏引擎也是开源的，简直太完美了，
3.1 Cocos Creator3.x
花了点时间，成功将recast.js 移到了Cocos Creator3.x
-
recast.js js库
-
NavMesh.ts 功能实现
3.2 基础功能实现
1.初始化
import?Recast?from?"./lib/recast.js"...public?init(cb:?Function?=?null):void{??new?Recast().then((recast)?=>?{??????this._recast?=?recast;??????this._navMesh?=?new?this._recast.NavMesh();??????this.setDefaultConfig();??????this._tempVec=new?this._recast.Vec3();??????this._tempVec1=new?this._recast.Vec3();??????this._tempVec2=new?this._recast.Vec3();??????if?(cb)?cb();??});}2.添加静态物体
/**?*?添加静态的模型?*/public?addStaticModle(node:?Node):?void?{????if(!node||!node.getComponent(MeshRenderer))?return;????let?render:?MeshRenderer?=?node.getComponent(MeshRenderer);????if?(!render?||?!render.mesh)?return;????let?matrix:?math.Mat4?=?node.getWorldMatrix();????this.updateBaseDatas(render.mesh,?matrix);}场景中一些固定不变的，比如地面，障碍物之类的可以通过这个结构进行添加，代码中对传入节点的网格信息进行处理，处理为recast所需要的格式，
3.添加Terrain 地形
?/**?*?添加cocos的地形??*?@param?terrain?地形组件?*/public?addTerrain?(terrain:?Terrain,):?any?{???...}terrain 地形组件同时也是游戏开发过程中会常用到的组件，所以听取了大佬的建议，将咱们的寻路对terrain进行了支持，大家可以在demo中看见对terrain数据处理的一些逻辑
4.构建导航网格
/**?*?构建导航网格?*/public?build():?void?{????var?rc?=?new?this._recast.rcConfig();????rc.cs?=?this._config.cs;????rc.ch?=?this._config.ch;????....????this._navMesh.build(this._positions,?this._positions.length?/?3,?this._indices,?this._indices.length,?rc);}5.可视化调试
在构建完导航网格后，为了方便大家调试，需要将最终的数据以可视化的效果展现给大家，方便大家开发过程的调试，代码中已经做好了处理，提供了两种调试方式：
export?enum?MeshDebugDataType?{????SURFACE?=?0,?//面????LINE?=?1,???//线}let?navMeshData:?NavMeshDebugData?=?this._navMeshMgr.getNavMeshDebugData(MeshDebugDataType.LINE);this.createDebugMesh(navMeshData.positions,?navMeshData.normals);private?createDebugMesh?(positions:?number[],?normals:?number[]):?void?{????this.line.node.destroyAllChildren();????let?node?=?new?Node();????let?render?=?node.addComponent(MeshRenderer);????let?mesh?=?utils.createMesh({????????positions:?positions,????????primitiveMode:?gfx.PrimitiveMode.TRIANGLE_LIST,????????normals:?normals,????});????render.mesh?=?mesh;????this.line.node.addChild(node);}
6.Crowd和Agent
首先来谈谈本人对这两个概念的理解吧。Crowd，从字面意识大概就能猜到，这是人群。Agent则表示的是这群人里边的其中一个。可以存在多个人群。本人猜测每个Crowd中的Agent在移动的时候会进行彼此之间距离的一些检测，但是不同Crowd的Agent则不会检测（还未验证），
-
创建Crowd
public?initCrowd?(maxAgents:?number,?maxAgentRadius:?number):?NavMeshCorwd?{????return?new?NavMeshCorwd(this,?maxAgents,?maxAgentRadius);}-
添加一个Agent
public?addAgent?(pos:?Vec3,?parameters:?AgentConfig):?number?{????let?config?=?new?this._navMeshMgr.recast.dtCrowdAgentParams();????...????let?agentIndex:?number?=?this._recastCrowd.addAgent(new?this._navMeshMgr.recast.Vec3(pos.x,?pos.y,?pos.z),?config);????...????return?agentIndex;}7.寻路移动
导航网格的关键点就是为了获取两点之间的最有路径。
private?findPath?(pos):?void?{????let?targetPos:?Vec3?=?this._navMeshMgr.getClosestPoint(pos);????//设置指定的Agent移动到特定位置????this._navMeshCrowd.agentMoveTarget(this._playerAgentIndex,?targetPos);}通过agentMoveTarget()函数去置顶Agent的目标点，同时还需要去实时刷新Crowd来更新Agnet的实际位置，
?update?(deltaTime:?number)?{????if(!?this._navMeshCrowd)?return;????//刷新Crowd????this._navMeshCrowd.update(deltaTime);????//获取指定Agent当前的位置????let?agentPosition?=?this._navMeshCrowd.getAgentPosition(this._playerAgentIndex);????this.player.position?=?agentPosition;????}
?
?
4.总结
希望以上内容对小小伙伴们可以有所帮助
demo地址：Cocos Creator3.x NavMesh导航网格寻路 | Cocos Store
?