首页 学习 导航网格

个人设计开发的 3D 导航寻路方案

# 3D 寻路 NavBound

基于 RecastNavigation 的 3D 场景下寻路解决方案 ——NavBound。

# 核心思想

通过构建「非障碍空间」下的八叉树，将空间分割为稀疏的立方体结构，再对立方体之间更新 connect 和 region 信息辅助 A_star 实现 3D 场景下的寻路。

# 离线数据生成规则

# 初始化参数配置

# Rasterization

控制体素化的相关配置

image-20211130100358290

# Cell Size

单个体素的长宽或者八叉树最小单位的长宽

# Cell Height

单个体素的高或者八叉树最小单位的高

# Empty Span

控制非障碍空间的生成配置

image-20211130100848780

# Water Level

水位线，用于控制非障碍空间的生成最大高度和八叉树最大切分高度

# Agent

寻路对象的横截面大小配置

image-20211130101053871

# Agent Area Size

表示横截面边长，默认长宽一致。用于过滤接触面积较小的八叉树节点连通关系。

# OctTree

控制八叉树节点大小的配置

image-20211130101301658

# Oct Min Node Size

最小的节点大小，默认配置长宽高一致。

# 障碍空间体素化

该部分参考 RecastNavigation 自身的体素化生成方案，详细说明见传送门。

受到配置项「Cell Size」、「Cell Height」影响。

# 瑕疵

由于体素过程实际上是对三角形面片做的，所以分不清镂空的地形（溶洞，洞穴）和空心的模型之间的区别，会多生成一些非障碍空间在模型内部。

体素化：

image-20211130102449206

非障碍化：

image-20211130102534129

# 非障碍空间体素化

核心思路是对生成好的体素空间做一个取反，受到配置项「Water Level」影响。

  • 遍历每个 SpanCell ，对 Span 的 top 和 bot 做取反处理。

image-20211130103910057

image-20211130105441530

image-20211130105456147

# 生成八叉树

通过得到的非障碍体素空间来处理八叉树的生成，如果八叉树节点都在 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 node
    struct 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 3
    	set<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 是否能够全部覆盖节点的包围盒空间

    • 【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

八叉树生成结果：

image-20211130111215450

对较小节点过滤：

image-20211130110858584

# 待优化：

无 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

image-20211130112727097

剔除后的 region ，不同 region 间视作不可寻路

image-20211130113003674

# 转为 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
  • 等等...
# 数据结构介绍
寻路整体用的还是官方提供的数据结构
  • dtNodePool：定长的 HashTab ，用于解决数据缓存，顺带解决了内存分配， Size 大小可以直接用 leafcount ，由于 nid 大小实际远超 leafcount ，用 nid 做下标太大，而 HashTab 和算法比较契合。
  • dtNodeQueue：支持 modify 的优先队列，这点很重要。寻路过程需要更新 cost 为最优，C++ 库的 priority_queue 是不支持 modify 的。
  • dtNode：查询节点，存储 cost 和 pos 和 父节点
# 寻路算法
用的是比较简单的 A_star ，计算 cost 用的是欧式距离，查询为了效果好点做了一个小优化，选点的时候用相邻节点相交面的中点作为目标点，能减少一定的穿墙问题（特殊情况下还是会出现）如下：
下面的情况看起来就像在节点表面寻路一样，有点穿帮，不过出现概率比较小后续可以考虑进一步优化。
image-20211130120724844
寻路效果图：
image-20211130140824577