RecastNavigation中的Recast功能是如何实现复杂地形导航的？

本文共计8038个文字，预计阅读时间需要33分钟。

0. 介绍：在现实应用中，导航网格常以邻接的多边形集合表示，因为独立的凸多边形内部，任意两点直线可达。而寻路算法的关键是通过算法找到一组凸多边形。

0. 介绍

在实际应用中，导航网格是以邻接的凸多边形集合来表示的，因为在独立的凸多边形内部，可以保证任意两点直线可达。
而寻路算法的关键是通过算法找到一组凸多边形，这组多边形满足这样的条件：

1. 第一个和最后一个多边形包含了寻路的起始点和终点
2. 中间的多边形负责所有多边形的连通性

因此导航网格寻路可以粗略的分成两大部分：

1. 将 3D 场景转化为邻接的凸多边形集合
2. 在凸多边形集合上寻路

在 RecastNavigation 项目中， Recast 工程对应第一部分，Detour 工程对应第二部分，这里主要利用 RecastDemo 对 Recast 生成导航网格的流程进行介绍。