recastnavigation

背景

常见实现服务端地形的方式有使用数组保存地形的方式。例如使用一个二维数组，value为0表示不可行走，为1表示可以行走地板。也可以支持扩展其它地表，例如沙漠，水。此种方式优点是实现方式简单，缺点是寻路成本较大，只支持2d地形。

还有一种方式是使用著名的recastnavigation库，使用导航网格navmesh来实现。库的地址是 https://github.com/recastnavigation/recastnavigation 。此方式可以大幅度减少网格数量，在寻路上具有较大优势，而且支持3d地形。但是也不是所有3d地形也是支持的，如果是角度小于90度的墙，是生成不了导航网格的。

导航网格

导航网格生成的参数

cellSize 体素在XZ轴上的大小，越小越精细
cellHeight 体素在Y轴上的高度，越小越精细，但可能引起网格之间断裂
minTraversableHeight 最低可通过高度
maxTraversableStep 可跨越不同地形时的高度，多用于楼梯阈值
maxTraversableSlope 最大可通过的斜坡倾斜度
clipLedges 边缘突出部分是否可以行走
traversableAreaBorderSize 可行走区域与阻挡之间的距离大小，贴墙的程度，越小可能交叠越多
smoonthingThreshold 距离场
useComservativeExpansion
minUnconnectedRegionSize 最小的无法被链接的区域，可以避免孤岛的网格的产生
mergeRegionSize 合并区域尺寸，低于改数值，可能会被大区域吞并
maxEdgeLength 网格边界的多边形最大的边
edgeMaxDeviation 网格边界与原始集合图形的偏移量，越小产生的三角形越多，越贴近于原始图形
maxVertsPerPoly 每个多边形的最大定点数，通常情况下6个顶点能够平衡需求和性能
contourSampleDistance 采样距离

NavMesh的生成过程

Voxelization 体素化，把原始几何转换成高度域
Generate Regions 生成各个多边形区域
Generate Contours 生成各个多边形的边界轮廓并标记起来
Generate Polygon Mesh 合并重复边界轮廓信息，整合到网格里面去
Generate Detailed Mesh

gamescene_map 方案

navmesh 方案

对象概念

navmesh
navmesh agent
navmesh obstacle
off-mesh link

这个图用于解释数据结构非常有用

tile - 片
poly - 多边形
vert - 顶点

使用

有了navmesh之后，就可以使用Detour进行寻路等操作。

构建一个 dtNavMeshQuery 实例
findPath 查询到经过的多边形
findStraightPath 将多边形转换成寻路坐标

接口

todo

导出lua接口