NavMesh
生成
- 首先对地图进行栅格化（分成一个个小格），然后就可以根据栅格化的地图获取到内边缘
- 接下来对边缘进行简化首先找到两个点连线得到简化的边缘
- 然后找到距离该线最远的点，加入顶点集合中
重复该过程，直到所有不在简化轮廓集合中的点距离简化的边缘距离都小于某阈值。 - 由于角色体型不同时，路径应该不同，在提取地图区域边缘时，向内多取一个角色体型半径生成特殊的寻路地图（即每种半径生成一个寻路网格）。
- 进行空间的划分
首先设置一个阈值，当两点间直线距离/两点边界距离小于该值时，进行区域分割。
该过程可使用递归进行。
完成分割后，每块区域作为图的一个节点，每两个点之间都可以通过简单的直线路径连通。
可以用最短路径算法（如 Dijkstra ）来解决图节点间的寻路问题，而图节点内的路径可以简单的通过两点间连线完成。
对于有空洞的地图，在进行边缘简化后，对每个空洞区域，找到其和地图边界点距离最近的点，连接起来作为边界。
- 动态障碍
可在运行时，修改地图与动态障碍物重叠的节点数据。
寻路
Unity中使用的基础算法是A*。漏斗算法
- 使用A*之类的算法计算出从起点到终点所走过的多边形/三角形的集合。
- 使用漏斗算法，将多边形集合转换成最优路径。
- 首先计算出三角形列表中的邻接边列表，所谓邻接边就是两个三角形公用的边
图中橙色边即邻接边，绿色为漏斗边。 - 将漏斗边移至下一条邻接边的两端，如果漏斗边的夹角变小或不变就算此次移动有效。
- 继续移动，如果出现了漏斗角的度数变成负数，例如右漏斗边移动到了左漏斗边的左侧，那么被盖过去的那条边的终点就成为了结果中的第一个点。同时将漏斗边的起点移到该点，构建出新漏斗。
- 如果遇到度数变大的情况，不动（虽然发生了移动但终点和起点一致）的那条边移动成功，导致度数变大的边移动失败（即其不发生移动）。
- 结束时，算法已经移动到了最后一条邻接边，但是从现在的漏斗底直接连一条线到终点肯定是不可行的。随后我们以终点一个点，当作一条两条端点相同的边。用它继续前进漏斗口。右边的漏斗边如果移动，会使漏斗口变大，因此不移动，左边的漏斗边移动，会盖过右边的漏斗边，因此右边的漏斗边终点成为了结果中的另一个点。
- 同样，以该点所在三角形的出邻接边重新构造漏斗，继续算法，很快就会发现漏斗口到终点，收到了最小，算法结束。
