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

# 3D 寻路 NavBound

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

# 核心思想

通过构建「非障碍空间」下的八叉树,将空间分割为稀疏的立方体结构,再对立方体之间更新 connectregion 信息辅助 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 ,对 Spantopbot 做取反处理。

image-20211130103910057

image-20211130105441530

image-20211130105456147

# 生成八叉树

通过得到的非障碍体素空间来处理八叉树的生成,如果八叉树节点都在 Empty Span 内则不需要对节点继续细分。

受到配置项「Oct Min Node Size」影响。

  • 【Step.1】对场景进行切割,切割按照「Cell SizeCell SizeCell 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 ,判断 EmptySpanbottop 是否能够全部覆盖节点的包围盒空间
    • 【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_id0 的表示 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 ,事先可以通过 setsize 算出总大小,然后 dtNavBoundNodeHeaderconnect 就只记录数据在数组的 idxcount ,用 connData[idx~idx+count] 的方式遍历。

# 待优化项:

目前还不能很好评估最终的叶节点数量具体是多少,需要更具项目需要做进一步优化,目前很多数据都用 int 来存储,比较浪费。例如:

  • connect 里面 的 idxcount 考虑优化成前 24 位存 idx8 位存 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:查询节点,存储 costpos 和 父节点

# 寻路算法

用的是比较简单的 A_star ,计算 cost 用的是欧式距离,查询为了效果好点做了一个小优化,选点的时候用相邻节点相交面的中点作为目标点,能减少一定的穿墙问题(特殊情况下还是会出现)如下:

下面的情况看起来就像在节点表面寻路一样,有点穿帮,不过出现概率比较小后续可以考虑进一步优化。

image-20211130120724844

寻路效果图:

image-20211130140824577

更新于 阅读次数

请我[恰饭]~( ̄▽ ̄)~*

鑫酱(●'◡'●) 微信支付

微信支付

鑫酱(●'◡'●) 支付宝

支付宝