导航网格
在游戏中，我们经常需要寻路系统，想到寻路算法，我们就想到了寻路算法需要生成图。但是如果不借助其他工具，我们通常只能手写给定一些节点并设定相互的拓扑关系，或者在一些扁平的tile地图中，读取所有(x,y)位置上是否为障碍物的数据来生成图的邻接表，这两种方式并不是太方便，同时，在3D游戏里，场景里的几何体一般都比较复杂，单位节点之间的拓扑关系也比较复杂，上述的两种方式，都不能较好应对3D游戏中的这种情况，在Cocos-2dx中我们提供了NavMesh，专门用来通过对整个场景生成图，同时又提供了非常简单的寻路接口。
首先我们需要使用一款编辑器来编辑整个网格的寻路信息，我们可以在github上找到这个repo下载并编译：https://github.com/memononen/recastnavigation
编辑器的用法：编译源码完成后找到名为RecastDemo的可执行程序(Windows下为RecastDemo.exe)，在右侧属性栏中的sample一栏选择TempObstacles(其他两个Sample生成的信息不全，不要使用)。并在Input Mesh一栏中选择需要处理的场景模型文件，编辑器目前只支持obj文件。注意，模型文件需要放到和执行程序同级的Meshs文件夹下。之后就可通过编辑器编辑导航网格的相关参数(参数的用法请参看官方文档)，如下图所示：
编辑好参数以后，可以通过右下角的build按钮生成NavMesh，并通过Save按钮把数据保存到磁盘，但这个文件并没有保存offmesh的信息，还需要通过按键盘上的“9”键生成相关数据。
此时我们可以得到两个文件，一个是导航网格的bin文件，一个是带有额外几何信息(主要是offmesh的信息)的geomset.txt文件，我们通过这两个文件来创建在程序里创建NavMesh：
auto navMesh = NavMesh::create(“NavMesh/all_tiles_tilecache.bin”, “NavMesh/geomset.txt”);
在创建完NavMesh后，我们要通过Scene：：setNavMesh方法，将其设置到场景中：
setNavMesh(navMesh);
Agent
在创建完NavMesh后，我们要单独将几个概念，首先是agent
Agent主要是指需要进行寻路的游戏中的实体，通常可以是一群敌人，或者主角等等，我们来看看如何创建Agent以及如何跟场景中的模型联系起来：
std::string filePath = “Sprite3DTest/girl.c3b”;
NavMeshAgentParam param;
param.radius = 2.0f;
param.height = 8.0f;
auto agent = NavMeshAgent::create(param);
auto agentNode = Sprite3D::create(filePath);
agent->setOrientationRefAxes(Vec3(-1.0f,0.0f, 1.0f));
AgentUserData *data = new AgentUserData{ 0.0f };
agent->setUserData(data);
agentNode->setScale(0.05f);
agentNode->addComponent(agent);
我们首先通过NavMeshAgentParam来初始化agent对象，这里面有两个参数比较关键，第一个是radius半径，第二个hegiht是高度，通过这两个参数我们可以构建出一个圆柱形的agent，使用当我们创建完agent后，便可将其添加为sprite3D的组件。OrientationRefAxes是agent的旋转参考轴，也就是假定该轴方向为agent的forward方向。AgentUserData是一个自定义的用户数据类型，你可以将agent有关的数据打包到这个userdata中，在接下的小节里我们会看到userData的使用
Obstacle
有时候，在游戏中我们需要动态的添加障碍物，在这时，光靠通过编辑器生成的导航网格是远远不够的，因为它无法预先知道游戏中会出现什么，这时候，我们就可以使用NavMeshObstacle这个类来动态的往场景中添加障碍物，我们来看一下如何操作：
其实obstalce类和agent有些类似，它本身也是一个圆柱形的，通过create里传递其半径和高度来创建，然后也将作为一个组件添加到Sprite3D上：auto obstacle = NavMeshObstacle::create(2.0f,8.0f);
auto obstacleNode = Sprite3D::create(“Sprite3DTest/cylinder.c3b”);
obstacleNode->setPosition3D(pos + Vec3(0.0f,-0.5f, 0.0f));
obstacleNode->setRotation3D(Vec3(-90.0f, 0.0f, 0.0f));
obstacleNode->setScale(0.3f);
obstacleNode->addComponent(obstacle);
注意：setScale只影响渲染模型的大小，不影响Obstacle的大小，Agent也是同样的性质。
寻路导航
在布置好NavMesh, Agent以及若干Obstacle之后，我们就可以开始寻路导航了，事实上整个寻路过程是已经封装好了的，我们只要通过其自带的move方法就使指定的agent行动了，同时Sprite3D的位置以及朝向会自动被同步到Agent当前的状态。
一般情况下，我们将所有的Agent存放到一个表里：
for (auto iter : _agents){ ……… iter.first->move(des,callback); }
这里注意move的第一个参数就是目的地的位置，第二个参数是一个回调函数，这个函数会在寻路时被触发，可以通过它来更精密的控制寻路的具体行为。例如，自定义通过offmesh的方式，见下文介绍。
OffMesh
在之前的情况下，我们都假设的是整个场景构成的图中，只拥有一个强连通分量，并没有出现，如断桥悬崖等、场景中间存在不连接区域的情况。
事实上这种情况也是可以处理的。在NavMesh中，两个没有交集的连通分量相互被称作OffMesh，在两个OffMesh中，添加一条边，能使两个联通分量变为一个桥边称为OffMesh Link，通过在编辑器中编辑OffMesh link我们就可以让整个导航网格系统知道如何从一个分离的网格移动至另一个。
默认情况，会以匀速直线的方式通过offmesh，当然，如果使用默认的方式的话，可能并不是特别的美观，因为在游戏场景里，通常需要的是玩家从块区域“跳跃”到另一块区域，有可能还需要设置骨骼动画，为了达到跳跃的效果，我们需要在之前说的move的一个回调函数里做文章：
NavMeshAgent::MoveCallback callback =](NavMeshAgent *agent, float totalTimeAfterMove){
AgentUserData *data = static_cast<AgentUserData *>(agent->getUserData());
if (agent->isOnOffMeshLink()){
agent->setAutoTraverseOffMeshLink(false);
agent->setAutoOrientation(false);
OffMeshLinkData linkdata = agent->getCurrentOffMeshLinkData();
agent->getOwner()->setPosition3D(jump(&linkdata.startPosition, &linkdata.endPosition, 10.0f, data->time));
Vec3 dir = linkdata.endPosition - linkdata.startPosition;
dir.y = 0.0f;
dir.normalize();
Vec3 axes;
Vec3 refAxes = Vec3(-1.0f, 0.0f,1.0f);
refAxes.normalize();
Vec3::cross(refAxes, dir, &axes);
float angle = Vec3::dot(refAxes, dir);
agent->getOwner()->setRotationQuat(Quaternion(axes, acosf(angle)));
data->time += 0.01f;
if (1.0f time){
agent->completeOffMeshLink();
agent->setAutoOrientation(true);
data->time = 0.0f;
}
}
};
iter.first->*move(des,callback);
}
在这个回调函数里，首先我们拿Agent的UserData来存储从OffMeshLink跳跃完成的百分比，用以来调整位置，
然后我们通过isOnOffMeshLink来判断当前的Agent是否处在一条OffMeshLink上面，如果处在link上，则我们通过setAutotraverseOffMeshLink(false)以及setAutoOrientation(false)禁用了导航网格的自动寻路以及自动更改Agent朝向的功能，改为使用回调函数接管。然后我们通过getCurrentOffMeshLinkData来获取当前的Link的数据，然后使用jump函数来获得当前跳跃的位置，这里jump中输入的参数即为agent的data。因为我们同时朝向也设为手动的了，所以我们需要获取link起始点到结束点的方向重新计算朝向。
最后我们接着用data记录当前的跳跃完成的百分比，如果百分比完成之后，则通过completeOffMeshLink以及setAutoOrientation(true)，将状态复原，并继续让NavMesh系统来接管整个寻路，整个处理OffMeshLink的处理大致是这样，最后在运行时，只要在move中将该回调传入即可。
