个人设计开发的 3D 导航寻路方案
# 3D 寻路 NavBound
基于 RecastNavigation 的 3D 场景下寻路解决方案 ——NavBound。
# 核心思想
通过构建「非障碍空间」下的八叉树，将空间分割为稀疏的立方体结构，再对立方体之间更新 connect 和 region 信息辅助 A_star 实现 3D 场景下的寻路。
# 离线数据生成规则
# 初始化参数配置
# Rasterization
控制体素化的相关配置
# Cell Size
单个体素的长宽或者八叉树最小单位的长宽
# Cell Height
单个体素的高或者八叉树最小单位的高
# Empty Span
控制非障碍空间的生成配置
# Water Level
水位线，用于控制非障碍空间的生成最大高度和八叉树最大切分高度
# Agent
寻路对象的横截面大小配置
# Agent Area Size
表示横截面边长，默认长宽一致。用于过滤接触面积较小的八叉树节点连通关系。
# OctTree
控制八叉树节点大小的配置
# Oct Min Node Size
最小的节点大小，默认配置长宽高一致。
# 障碍空间体素化
该部分参考 RecastNavigation 自身的体素化生成方案，详细说明见传送门。
受到配置项「Cell Size」、「Cell Height」影响。
# 瑕疵
由于体素过程实际上是对三角形面片做的，所以分不清镂空的地形（溶洞，洞穴）和空心的模型之间的区别，会多生成一些非障碍空间在模型内部。
体素化：
非障碍化：
# 非障碍空间体素化
核心思路是对生成好的体素空间做一个取反，受到配置项「Water Level」影响。
- 遍历每个
SpanCell，对Span的top和bot做取反处理。
# 生成八叉树
通过得到的非障碍体素空间来处理八叉树的生成，如果八叉树节点都在 Empty Span 内则不需要对节点继续细分。
受到配置项「Oct Min Node Size」影响。
- 【Step.1】对场景进行切割，切割按照「Cell Size ✖ Cell Size ✖ Cell Height」大小来，并计算二的上取整次方大小
- 并取最大边长作为八叉树根节点的边长。
// example | |
// 3 -> 4 | |
// 10 -> 16 | |
// 21 -> 32 | |
inline int nextPow2(int v) | |
{ | |
v--; | |
v |= v >> 1; | |
v |= v >> 2; | |
v |= v >> 4; | |
v |= v >> 8; | |
v |= v >> 16; | |
v++; | |
return v; | |
} |
【Step.2】构建八叉树
- 节点数据定义：
// tree nodestruct rcOctTreeNode {
int nid;
int cmin[3]; ///< The minimum bounds space. [(x, y, z)] / ch or cs
int cmax[3]; ///< The maximum bounds space. [(x, y, z)] / ch or cs
int region_id; /// > -1:leaf 0:root
int subNode[8]; /// top 1 2 bot 1 2
/// 4 3 4 3set<int>* con[6]; /// y+ x+ z+ y- x- z-
rcOctTreeNode();
~rcOctTreeNode();
};
【Step.2.1】过滤越界节点（坐标超过了 AABB 包围盒）
【Step.2.2】过滤较小节点（节点边长小于「Oct Min Node Size」）
【Step.2.3】判断节点非障碍性
- 遍历 xz-plane 的全部
SpanCell，判断EmptySpan的bot和top是否能够全部覆盖节点的包围盒空间
- 遍历 xz-plane 的全部
【Step.2.4】对有障碍的节点进一步细分
// 伪代码createOctTreeNode(){
if (!rcIsEmptySpan()) {
createOctTreeNode(0);
createOctTreeNode(1);
createOctTreeNode(2);
createOctTreeNode(3);
createOctTreeNode(4);
createOctTreeNode(5);
createOctTreeNode(6);
createOctTreeNode(7);
}}【Step.2.5】对所有得到的节点进行标记，
region_id为0的表示root， 为-1的表示leaf
八叉树生成结果：
对较小节点过滤：
# 待优化：
无 leaf 节点的父节点可以移除，减少存储开销
# 更新八叉树节点连接情况
更新叶节点之间的连接情况，受到配置项「Agent Area Size」影响。
【Step.1】遍历所有叶节点
【Step.2】对叶节点六个方向求相邻节点（上、前、右、下、后、左）
【Step.3】相邻计算比较粗暴：
- 【Step.3.1】计算六个方位面的中心点，根据方向再做一个微小的偏移，避免重叠两个面的情况
- 【Step.3.2】然后用得到的坐标查询相邻叶节点，DFS 查询八叉树
- 【Step.3.3】计算相邻两节点重叠面的面积 ——Intersection Area。根据「Agent Area Size 」做筛选
![image-20211130112536338]()
# 更新八叉树 region 信息
这里比较简单，做了一个 BFS 查询，然后标记了一下 region_id
不剔除重叠面的 region ，同颜色表示同 region
剔除后的 region ，不同 region 间视作不可寻路
# 转为 NavBound 格式
主要是对数据做了一个压缩，先看 NavBound 的定义：
struct dtNavBoundNodeHeader | |
{ | |
float bmin[3]; ///< The min world space. [(x, y, z)] | |
float bmax[3]; ///< The max world space. [(x, y, z)] | |
unsigned int region_id; | |
int nid; | |
int connDataCell[12]; // 6 dir * 2 first idx second size | |
int subNode[8]; | |
}; | |
struct dtNavBoundCreateParams | |
{ | |
float agentSize; | |
float nodeMinSize; | |
float waterLevel; | |
float cs; | |
float ch; | |
float bmin[3]; | |
float bmax[3]; | |
dtNavBoundNodeHeader* m_nodes; | |
int nodeCount; | |
int* leafNodes; | |
int leafNodeCount; | |
int* connData; | |
int connDataSize; | |
}; |
由于每个节点的 connect 数据是一不一样的，越大的节点，单个面的连接数就越多，这点比较蛋疼，很难规定一个最大范围来做为数组大小，而且更新 connect 的时候会有重复，又不想像官方那样先生成，再去重，再 resize 。所以生成八叉树的时候，用 set 来做的。
但是序列化就比较麻烦，最终决定序列化的时候把所有 connect 存在一个数组内 connData ，事先可以通过 set 的 size 算出总大小，然后 dtNavBoundNodeHeader 的 connect 就只记录数据在数组的 idx 和 count ，用 connData[idx~idx+count] 的方式遍历。
# 待优化项：
目前还不能很好评估最终的叶节点数量具体是多少，需要更具项目需要做进一步优化，目前很多数据都用 int 来存储，比较浪费。例如：
connect里面 的idx和count考虑优化成前24位存idx后8位存count，就能缩减一倍大小- AABB 包围盒也可以考虑用
int来表示，查询的时候再转成float，然后int可以用short代替 region_id也可以考虑转成short- 等等...
# NavBound 的 3D 寻路
# 数据结构介绍
寻路整体用的还是官方提供的数据结构
- dtNodePool：定长的
HashTab，用于解决数据缓存，顺带解决了内存分配，Size大小可以直接用leafcount，由于nid大小实际远超leafcount，用nid做下标太大，而HashTab和算法比较契合。 - dtNodeQueue：支持
modify的优先队列，这点很重要。寻路过程需要更新cost为最优，C++ 库的priority_queue是不支持modify的。 - dtNode：查询节点，存储
cost和pos和 父节点
# 寻路算法
用的是比较简单的 A_star ，计算 cost 用的是欧式距离，查询为了效果好点做了一个小优化，选点的时候用相邻节点相交面的中点作为目标点，能减少一定的穿墙问题（特殊情况下还是会出现）如下：
下面的情况看起来就像在节点表面寻路一样，有点穿帮，不过出现概率比较小后续可以考虑进一步优化。
寻路效果图：
