2D数组构建网格
- 使用数组存储网格，其中的每个单元可以代表多种状态，比如 0 代表可行走，1 代表不可行走，2代表草地等等。
- 每个单元的尺寸需要与地图的大小对应起来，比如每个单元代表地图上的 10 米。要综合考虑地图的大小和障碍物的大小，来确定地图的匹配关系。如果单元格很大，无法实现细腻的路径与障碍；如果单元格很小，过大的数组会造成内存的浪费。
邻接点
- 每个点的邻接点就是其周围的4个点或者8个点，与目的地的期望值可以通过计算方块之间的距离得到。
几种编辑数组网格的方式：
- 使用 [[Excel]] 表。使用颜色或数字区分不同的单元格，导出到文件，游戏内读取。
- 使用 [[UnityEditor]] 制作地图编辑器。
- 在具体的3D场景中编辑地图。
- 使用贴图存储地图。其中每个像素代表一个区域，用Alpha值区分不同的类型，这样整张地图可以被压缩成只有A通道的8比特图。当加载数组作为可行走数据时，会加载该图片读取像素中的每个元素并录入内存中，然后根据内存中的二维数组判定是否是可行走区域，以及相邻的格子是否是障碍物。
- 存储在内存中时使用一维数组更好，仅仅在读取时多了个行偏移，但是大大提高了缓存命中率，加快了指令运算速度。
缺点
- 场景特别大时，数组也会特别大，比较占用内存。
- 场景特别大时，编辑可行走区域的工作量也会特别多，还容易出错。
- 场景内障碍物分布不规则时，会在空旷的地方浪费掉很多内存。
路点网格
- 路点系统弥补了数组形式的缺点，它由很多点构成，这些点连起来构成寻路网。寻路时根据A星算法计算出路径，沿路点的连线移动就能够到达终点。
- 路点系统要在既有的地图上编辑，需要有可视化的编辑器实现路点的编辑功能。
邻接点
- 路点系统中点的邻接点就是与该节点有线条连接的点，与目的地的期望值可以通过计算点与点之间的距离得到。
优点
- 路点的数量比其他方式的网格少很多，所以内存消耗和CPU消耗都比较少。
缺点
- 当设置大范围的可行走区域时，需要大量的工作来编辑可寻路的路点信息和连线。
- 在大块空地寻路时，需要添加比较多的路点，才能平滑地适应各种寻路路径。
- 行走路线的平滑程度依赖于添加路点的密度。
- 路点系统的寻路方式无法识别障碍区域，行走的路线依赖于路点之间的连线
2D平面三角形网格
- 三角形网格方式使用算法自动生成寻路网格，无需手动编辑就能避开障碍区域。
三角形剖分算法
[[切耳(Ear Clipping)算法]]
- 大多数项目中平面三角形网格已经够用，即使有起伏的地面寻路，可以采用2D寻路+Y轴射线碰撞检测地面的形式获得位置坐标。
邻接点
- 平面三角形网格中的基本单位是三角形，其邻接三角形是与其共享边的三角形，与目的地的期望值可以通过计算三角形的中点与目的地之间的距离得到。
三角形网格寻路方法
- 如果把三角形中点作为寻路路径点，会导致中点与中点的连线路径不够平滑，寻路路线会非常诡异。
- 可以考虑使用边的中点记录路径，因为相邻三角形之间的穿越都是靠邻边来实现的，所以邻边的中点更适合三角形穿越，这样比使用三角形中点得到的路径更平滑，但是依然会有很多折现。
- 使用
射线优化路径算法，找到拐点，通过拐点拼接寻路路径，会减少很多折线。
2D多层级网格
- 多层级网格需要把所有可行走区域分成多个层级，每一层都有自己的网格数据，每层数据可以分别使用数组网格或者平面三角形网格。
- 例如4层楼房，每一层都有自己的网格数据，在楼梯部分记录各层之间的连接点。
- 寻路时，每一层只关心自己的数据，如果要跨层寻路，就需要通过连接点。
3D体素化寻路网格
- 为了支持3D高度上的自由寻路，引入“体素化”的概念，体素化是指将空间分割成一个个的立方体方块，每个立方体都标志着一种可行走状态，如果人物太高或者太宽，则角色就无法通过狭窄的门缝或者矮小的洞穴。
Recast Navigation Navmesh
- Recast 是指把三角形网格表示的空间场景转化为可供寻路使用的导航数据（NavMesh）。
Recast 大体流程
把场景网格体素化。即把空间分割成三维方块，每一块是一个立方体，标记了是否可以行走。生成可行走的区域。整理体素，把不能行走的体素过滤掉，去除障碍物周围角色宽度的体素，整理剩下的体素连接成一个个的区域。把区域拆分成多个凸多边形。检测划分区域的轮廓并构造成 [[简单多边形]]。再将轮廓分割成多个凸多边形。生成三角形导航网格。对所有的凸多边形进行三角化，并且基于多边形中高低不平的地面部分插入顶点，构建三角形。