导航:从一点走向另一点,需要模拟阻挡，路径选择，可行走形，地形特点，行走行为拟人化的现实表现.

A*算法:起点到终点探测代价最小路径的广度优先搜索. Navigation mesh属于A*算法的变种,将A*算法的格子变成三角形或者多边形网格,如何构建合理高效的三角形网格,即Navigation mesh.(处于某个三角形内,确定向相邻三角形内行走的代价)

深度优先搜索按照我的理解是:当你进入一个迷宫时,①你随便选择一个入口,进入这个入口时,②一直向右走,如果走到结尾没有走到目的地,③需要返回上一个岔路口,④向左行走,⑤重复②到④,深度优先搜索,是按照道路进行递进行走,缺点是这条路径不一定是最优的,并且可能是消耗时间较长,优点是只需要记录岔路口的节点,不需要对全局地图进行排查记录.

广度优先搜索按照我的理解是:当你进入一个迷宫时,①你随便选择一个入口,进入这个入口时,②当你遇到了岔路口,③需要把岔路口每条路径(上下左右前后)都走一边,④然后记录下来那一条路径距离最终目的地最近,然后选择这条路行走.⑤重复②到④,广度优先搜索,是按照每条路的权重值(即距离最终目的地最近的权重值)进行行走,缺点是基本对全局的路径全部排查并且记录了下来,每个格子距离最终目的地的距离也在计算,消耗内存.优点是路径最短.A*算法就是广度优先搜索算法.

NAVMesh将其多边形/三角形网格当成2d中的格子进行计算

如何制作导航网格:在真实场景中,不直接使用场景地形进行烘焙,而利用场景中的道路在上面铺满平面(或者其他3D图形)进行烘焙,然后禁用平面,这样当行网格不会产生巨大的消耗,并且可以完成任务.

选择static

制作NavMesh

控制角色利用NavMesh进行移动:简单测试,不管目标点在不在导航网格中,都会走到离目标点最近的地方

代码展示

测试1

NavMeshAgent的参数含义:    radius(半径)  height(高度)  baseOffset(基于中心点的偏移量) 参与导航网格的寻路,如果Collider碰撞盒子和这些参数相差较大,会出现诸如路过2个物体中间的路而走不过去,计算爬坡错误等等问题,需要和Collider保持一致.特殊需求再特殊处理.    speed 运动速度 angularSpeed 转弯速度    acceleration 加速度     stoppingDistance 距离目的地多进就停止运动,不会在有刚体和碰撞盒时产生问题.    autoBraking 自动刹车,false:接近目的时,当没有找到这个点时会一直寻找,true当走到目的地附近时,就会停止寻找.     autoRepath   选择true时当现有路径变为无效，代理尝试获得一条新路径.    areaMask 表示可以运动的范围,使用Layer来选择,如果不选择这个layer层,则不会在上面运动.

导航烘焙参数

导航烘焙时的参数的含义: Agent Radius 表示身体的厚度,比如是否可以在计算的时候穿过某个狭窄的路径;Agent Height 表示当前导航可以容纳的高度,比如当角色太高,房间顶和房间底无法撑下这个身体,则角色走不进这个房间.MaxSlope 当地图里面有台阶/坡度的地形,而这个物体的爬坡能力较低,则走不过去.Step Height 地图中的2个物体在这个高度之内,则可以烘焙在一起,如果超过这个高度,则这2个物体不能烘焙在一起(断层).    Advanced/ManualVoxelSize 越小时表示当前的障碍物在当行计算的时候占用的面积会越来越越符合当前障碍物占用的大小,一般不动.Advanced/Height Mesh 在不同高度的地形中进行烘焙,比如楼梯,当false时,上楼梯不会贴着楼梯的表面上楼,而是贴着烘焙出来的模进行行走,如果是true则是贴着楼梯的表面上楼,代价较高,一直在计算数据.Jump和Drop是跳跃和降落的高度值,在高地不平的地方使用,比如天空降落,河岸两边.

Off-mesh Links

实现在navmesh上不连接的表面的行走连通（如跳过河岸,悬崖两侧进行跳跃）

2个点

传入起点和终点,一个物体具有这个OffMeshLink组件即可,重新烘焙,即可跳跃寻路. Cost override 寻路代价,代价值越大,则选择这条路的可能性越低;BiDirectional true时是双向,false是单向.

lyaer层

Cost层,这个值越大,消耗的资源越多,越不容易被选择.在A*算法中表示这个格子的本身的权重值.

使用导航网格的层动态控制门开关

当角色在一个房间内清理完怪物之后,需要进入下一个房间,则需要打开房间门,这个时候我们将门这一块区域设置一个层,在没有清理完怪物的时候,当前角色的寻路组件NavMeshAgent的AreaMask不包括门这一层layer,当清理完怪物的时候包括了门这一层layer,这时候角色就会自动寻路.

通过NavMeshObstacle实现动态有无的阻挡

中间cube可以动态移动,并且产生新的导航

U3D的导航网格数据导出

navmesh.CalculateTriangulation()接口/CAINav:c++版本的mavmesh库,有UNITY3D的mavmesh导出接口;导出之后需要发送给服务器,然后再客户端使用.

导航与阻挡

可以通过障碍阻挡进行寻路,也可以根据导航进行寻路,都可以走到最终目的地(ps:是不是和深度优先搜索和广度优先搜索有联系呢!).

主角的寻路和怪物/其他NPC的寻路是不一样的,主角通过玩家进行控制,或者通过自动寻路进行控制.

完全使用导航寻路

完全使用阻挡寻路,需要配合避障算法进行寻路,遇到阻挡进行转弯操作.https://www.jianshu.com/p/370f3d751b27