RecastNavigation 路径寻路实战笔记：从体素栅格化到瓦片热更新

RecastNavigation 路径寻路实战笔记从体素栅格化到瓦片热更新【免费下载链接】recastnavigationIndustry-standard navigation-mesh toolset for games项目地址: https://gitcode.com/GitHub_Trending/re/recastnavigationRecastNavigation 是游戏行业用得最广的导航网格NavMesh工具集一套库同时覆盖导航网格构建、路径寻路和人群模拟三件事。这篇笔记不堆 API而是沿着一条三角形进来、一条路径出去的数据流走一遍重点记录踩过的坑和参数取舍。一条三角形怎么变成可寻路的导航网格先说结论Recast 的构建顺序是固定的栅格化 → 紧凑高度场 → 距离场 → 区域划分 → 轮廓提取 → 多边形生成每一步都吃上一步的输出。顺序不能换因为后一级的输入粒度依赖前一级已经收敛的分辨率。这套逻辑的入口在 Recast 核心构建。核心调用链是这样的每一步只传上一步的产物rcRasterizeTriangles(ctx, verts, nverts, tris, triareas, ntris, solid, walkableClimb); rcBuildCompactHeightfield(ctx, walkableHeight, walkableClimb, solid, chf); rcBuildDistanceField(ctx, chf, 0); rcBuildRegions(ctx, chf, borderSize, minRegionArea, mergeRegionArea); rcBuildContours(ctx, chf, maxError, maxEdgeLen, cset); rcBuildPolyMesh(ctx, cset, maxVertsPerPoly, pmesh);栅格化为什么必须走在最前面栅格化把连续的三角形投影到一个固定分辨率的体素格子上。它必须在最前面因为后面所有算法高度场、区域、轮廓都假设世界已经被量化成整数坐标。三角形本身带着浮点坐标和任意拓扑直接拿去做区域划分没有任何意义——你得先有一张像素图。这一步也是耗时大头因为三角形数量是输入规模的上界三角形再多、再碎体素格子的总数是被 cellSize 锁死的所以它天然可被分辨率摊薄。区域划分卡在 watershed 的走廊病区域划分把可行走体素切成一块块连通域每块后续会变成一个多边形。这里有个坑默认的 watershed 算法在斜向走廊里容易切出比必要更小的碎片区域走廊越斜碎得越厉害。源码注释里写得很直白它会在水道处overflow再简化。两个参数负责兜底minRegionArea过滤掉太小的碎片mergeRegionArea把紧邻的小块合并回去。如果你发现走廊里多边形碎得像马赛克先调大mergeRegionArea别急着改分辨率。想彻底避开走廊碎片可以切到rcBuildRegionsMonotone的单调划分代价是多边形会更横平竖直。从轮廓到多边形谁决定了寻路走廊的粒度轮廓提取先沿着区域边界描出一条原始轮廓再按maxError做简化得到带拐角的折线。rcBuildPolyMesh再把这些折线拼成多边形maxVertsPerPoly控制单个多边形最多几个顶点——这个值直接决定寻路走廊的粒度。值越小单个多边形覆盖范围越大findPath返回的走廊多边形数量越少、寻路越快但高度细节丢失越多。简单场景给 6室内外混合、需要贴地更准的场景才往上加。单网格扛不住之后瓦片网格怎么接管单网格把整个场景一次性栅格化小场景很爽。但场景一大内存和重建时间会一起爆而且任何一处改动都得重建整张网格。瓦片网格把场景切成固定大小的块每块独立构建、独立更新这就是 Detour 瓦片缓存 要解决的流式加载与热更新问题。瓦片边界重叠量 borderSize 到底给多少先问一句那瓦片交界处的路径为什么会断因为每个瓦片只栅格化自己边界内的三角形靠边界的几何在相邻瓦片里看不到两边各建各的多边形交界就裂开了。解法是让每个瓦片向外多算一圈 padding。m_cfg.tileSize (int)m_tileSize; m_cfg.borderSize m_cfg.walkableRadius 3; // 关键半径余量 m_cfg.width m_cfg.tileSize m_cfg.borderSize * 2; m_cfg.height m_cfg.tileSize m_cfg.borderSize * 2; m_cfg.bmin[0] - m_cfg.borderSize * m_cfg.cs; // 四边各外扩rcBuildContours在输出时会把这个 padding 从边界里扣掉所以最终多边形仍然严格落在瓦片真实范围内但构建时的体素是带重叠的交界处的多边形才能对得上、连得上。为什么 borderSize 要跟着 walkableRadius 走walkableRadius是体素化时按角色半径做的腐蚀距离——离障碍太近小于半径的格子直接判为不可走。如果 padding 小于这个腐蚀距离交界处的可行走区域会在两个瓦片里被腐蚀掉一部分留下走不过去的窄缝。所以borderSize walkableRadius 3里的3是安全余量walkableRadius是硬底线。角色半径越大padding 必须跟着变大这是硬约束不是经验值。单网格和瓦片网格的取舍我一般这么记维度单网格瓦片网格实现复杂度低一次构建高要管坐标与连接局部更新要重建整张只重建该瓦片内存峰值随场景线性涨可流式加载卸载适用规模中小型静态场景开放世界、动态障碍路径寻路的两种输出多边形走廊与直线Detour 查询接口 里有个容易误解的点findPath并不直接返回一串坐标点它返回的是一条多边形走廊——一串有序的多边形引用polyRef。真正的坐标是第二步findStraightPath沿着这条走廊做的视线投影输出带DT_STRAIGHTPATH_*标志的拐点数组。query-findPath(startRef, endRef, startPos, endPos, filter, path, pathCount, maxPath); // 第一步多边形走廊 query-findStraightPath(startPos, endPos, path, pathSize, straight, flags, refs, count, maxSP, DT_STRAIGHTPATH_AREA_CROSSINGS); // 第二步投影成拐点分两步的意义在于走廊是拓扑结果和具体坐标无关可以缓存、可以做局部修正而投影出的拐点才是渲染和驱动角色用的。把两者拆开你才能在目标变了但还没重算走廊的中间态先做局部避障。人群模拟为什么把寻路切成切片DetourCrowd 人群模拟 里上百个 agent 每帧都要重新寻路如果每个都同步跑完整findPath主线程直接卡死。所以它用了 sliced切片寻路initSlicedFindPath初始化updateSlicedFindPath每帧跑有限迭代finalizeSlicedFindPath取结果再配合dtPathQueue把异步寻路排队摊到多帧。dtCrowd::update里还能看到它把拓扑优化、邻域网格、避障、分离、位移拆成一串小步骤每步都能单独开关——这套拆解就是为了把一帧内的寻路预算做平。构建耗时卡在哪个阶段参数怎么救rcContext给每个阶段都挂了独立计时器RC_TIMER_RASTERIZE_TRIANGLES、RC_TIMER_BUILD_CONTOURS等DebugUtils 调试工具 能把每段耗时打出来所以耗时卡在哪不用猜先看报告。经验上栅格化和轮廓简化是两个大头而它们对同一组参数敏感。cellSize 和 agentHeight 的换算关系先记死这两条换算错了一切都错walkableRadius ceil(agentRadius / cellSize)walkableHeight ceil(agentHeight / cellHeight)。cellSize越大体素总数越少构建和内存都降但代价是可行走区域被量化得更粗细窄通道可能整条消失。agentHeight必须小于实际可通行净高否则高度场会把本该能走的格子判成不可走。一个常见误区是把cellSize一味调大到 1.0 以上来换速度结果窄门、台阶全被吞掉。我的习惯是先用 0.25~0.3 保证几何保真确认导航网格质量后再逐步放大压耗时而不是反过来。所以选型其实就三个判据场景能不能一次装进内存、有没有动态障碍、寻路预算卡不卡主线程。三者都否单网格 直连findPath最省心只要有动态障碍或超大场景就上瓦片网格 切片寻路再按角色半径把borderSize卡到walkableRadius 3。参数调优永远先看计时报告定位瓶颈再去动cellSize和mergeRegionArea别在没数据的地方瞎试。【免费下载链接】recastnavigationIndustry-standard navigation-mesh toolset for games项目地址: https://gitcode.com/GitHub_Trending/re/recastnavigation创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考