1.【Recast Navigation】SoloMesh源码分析（三）——行走面过滤
2.Recast Navigation 源码剖析 01 - Meadow Map论文解析与实验

【Recast Navigation】SoloMesh源码分析（三）——行走面过滤

       本文是源码对SoloMesh源码分析系列文章的第三部分，主题为行走面过滤。源码此阶段的源码处理是对体素化后Heightfield的修正和标记，旨在优化导航网格的源码构建过程。

       行走面过滤分为三个主要步骤：过滤悬空的源码可走障碍物、过滤高度差过大的源码菠菜源码可以干嘛span以及过滤不可通过高度span。

       首先，源码过滤悬空的源码可走障碍物通过函数rcFilterLowHangingWalkableObstacles实现。此过程识别上下两个体素，源码其中下体素可行走，源码而上体素不可行走。源码若上下两体素上表面相差不超过walkClimb，源码则将上体素标记为可行走。源码

       接着，源码过滤高度差过大的源码span通过rcFilterLedgeSpans函数完成。此过程寻找如图所示的两种情况。首先，确保上span与下span与邻居的上span下span之间存在超过walkHeight的空隙，表明可通过一个agent的Ucrop框架源码高度。然后，根据两种不同的情况，对体素进行判断，以解决转角台阶的识别问题。实际上，该步骤的目的是通过补充斜向体素的考虑，解决体素连接关系仅考虑4方邻居的问题。然而，该方法存在影响同方向体素的js弹窗源码副作用，即图示的错误例子。解决这一问题的方法是排除同方向的两个体素比较。

       最后，过滤不可通过高度span通过rcFilterWalkableLowHeightSpans实现。此过程检查上下两个span之间空隙，若小于等于walkHeight，则将下span标记为不可行走。

       总结：代码逻辑相对简单，具体实现细节可直接在github的人形时钟 源码wcqdong/recastnavigation项目中查看源码注释，以深入理解此阶段的详细处理流程。

Recast Navigation 源码剖析 - Meadow Map论文解析与实验

       本文深入解析了Meadow Map论文及其在Recast Navigation中的应用。Recast Navigation是一款常见的游戏开发寻路库，源于芬兰开发者Mikko Mononen的初始工作。Meadow Map方法，由Ronald C. Arkin于年提出，为现代Navmesh系统奠定了基础，特别强调长时间存储地图的有效策略。

       Meadow Map通过凸多边形化动机，基于地图 源码提出了一种优化存储和访问3D地图数据的方法。相较于传统的基于网格的寻路方法，Meadow Map采用凸多边形化来减少节点数量，从而提高性能效率，特别是针对平坦区域。凸多边形化的核心在于利用凸多边形内部任意两点直接相连的特性，构建寻路图。

       Recast Navigation系统使用凸多边形化来处理3D场景，通过算法自动将3D场景转换为2.5D形式，以便于寻路。与Meadow Map类似，Recast也采用了基于凸多边形边缘中点作为寻路节点的策略，构建寻路图以供A*算法使用。这种方法简化了搜索空间，提高了寻路效率。

       在实现Meadow Map时，需解决多边形分解成多个凸多边形的问题。此过程通过不断消除多边形中的非凸角，递归生成凸多边形，实现多边形化。同时，处理多边形内部的障碍物（holes）时，需找到与可见顶点相连的内部对角线，将空洞并入多边形内部。

       路径改进方面，Recast Navigation采用String Pulling方法，旨在优化路径，避免路径的抖动和非最优行为。这一策略在实际应用中提升了路径质量，使得寻路过程更为流畅。

       总之，Meadow Map和Recast Navigation在采用凸多边形化来构建寻路图的基础上，通过不同实现细节和优化策略，有效提高了游戏中的路径寻路效率和性能。通过深入理解这两种方法，游戏开发者可以更好地选择和应用合适的寻路库，以满足不同游戏场景的需求。