UE 补完计划（四） 导航系统-3

前言：区域生成

UE4的导航使用的是RecastDetour组件，这是一个开源组件，主要支持3D场景的导航网格导出和寻路，或者有一个更流行的名字叫做NavMesh。不管是Unity还是UE都使用了这一套组件。

Github上有更为详细的源码、Demo和说明：https://github.com/recastnavigation/recastnavigation

本文使用的UE4源码版本为4.24.3，2020年2月25日的版本。

Recast采用了体素化的方式，来生成导航网格。大致分为三个步骤：

1. 将场景体素化。形成一个多层的体素模型。

2. 将不同层的体素模型划分为可重叠的2D区域。不同层的2D区域不同

3. 沿着边界区域剥离出导航凸多边形。

在上一篇文章，讲述了场景体素化的过程。现在我们已经有了rcHeightField数据，标记了场景中所有的span以及每个span的可行走标记。接下来会根据这些数据来生成实际使用的导航网格区域。

区域生成流程

这一部分会使用之前生成的rcHeightField数据。大致分为两个步骤：

1. 初始化CompactHeightfield数据。记录所有的连续的span的高度，并计算与周围span的连通关系。逻辑主要在rcBuildCompactHeightfield()函数中

2. 裁剪可行走区域。会根据walkableRadius，从边缘开始计算，压缩可行走区域的范围。

3. 划分区域。将一个或者多个巨大的连续空间划分为一个个小区域。有三种划分区域的算法：Watershed、Monotone、Chunky。区域划分算法会在下一篇用单独一篇来详细讲解。

初始化 CompactHeightfield 数据

这部分逻辑主要在rcBuildCompactHeightfield()函数中。

其实主要就干了两件事：

1. 找出空心区域

2. 计算空心区域与邻居空心区域的连通性。

找出空心区域

遍历所有span，记录这个span的顶部与其上方的span的底部的距离作为高度。我们可以理解为span是一个实心连续区域，而这一步的目的就是找出空间中实心区域之外的空心区域。

一个空心区域的结构体如下：

struct rcCompactSpan
{
	unsigned short y;			// 空心区域的底部坐标
	unsigned short reg;			// 区域id。如果没有区域则为0
	unsigned int con;			// 邻居的连通性。一个32bit的位域。分别记录四个方向上的索引值。如果是0，那么表示该方向上没有邻居
	unsigned char h;			// 空心区域的高度
};

整个函数的实现也很简单。核心代码如下：

while (s)
{
	if (s->data.area != RC_NULL_AREA)
	{
		const int bot = (int)s->data.smax;
		const int top = s->next ? (int)s->next->data.smin : MAX_HEIGHT;
		chf.spans[idx].y = (unsigned short)rcClamp(bot, 0, 0xffff);
		chf.spans[idx].h = (unsigned char)rcClamp(top - bot, 0, 0xff);
		chf.areas[idx] = s->data.area;
		idx++;
		c.count++;
	}
	s = s->next;
}

计算连通性

计算连通性的方法与上一篇所述的过滤不可行走的突起类似。如果开放空间的高度大于walkableHeight，且邻居空间与本空间的高度差小于walkableClimb，则认为是连续的。

注意这里使用一个con位域来记录连通性信息。con是一个32bit的位域。分别记录四个方向上的索引值。如果是0，那么表示该方向上没有邻居。

计算连通性时，会遇到一个情况，如果邻居有多个联通的开放空间怎么办？就像这张图所示：

实际采取的方案是：取最上方的空间。

可以看看设置连通性的函数：

inline void rcSetCon(rcCompactSpan& s, int dir, int i)
{
	// con是一个32bit的位域。分别记录四个方向上的i值。如果是默认值，那么表示该方向上没有邻居，就不会调用到这个函数中来
	const unsigned int shift = (unsigned int)dir * 8;
	unsigned int con = s.con;
	s.con = (con & ~(0xff << shift)) | (((unsigned int)i & 0xff) << shift);
}

整个计算连通性的函数核心代码如下：

// 遍历所有邻居节点上的开放空间
// ...
const rcCompactSpan& ns = chf.spans[k];
const int bot = rcMax(s.y, ns.y);
const int top = rcMin(s.y+s.h, ns.y+ns.h);

// 如果开放空间的高度大于walkableHeight，且邻居空间与本空间的高度差小于walkableClimb，则认为是连续的
if ((top - bot) >= walkableHeight && rcAbs((int)ns.y - (int)s.y) <= walkableClimb)
{
	// lidx表示真实的索引。
	const int lidx = k - (int)nc.index;
	if (lidx < 0 || lidx > MAX_LAYERS)
	{
		// 记录超过最大数量的节点数量
		tooHighNeighbour = rcMax(tooHighNeighbour, lidx);
		continue;
	}
	// 设置连通性
	rcSetCon(s, dir, lidx);
	break;
}

裁剪可行走区域

寻路的对象（比方说人）是有宽度的。如果一个路径过窄，那么这个路径对于大胖子来说相当于是不可寻路的。这一步就是预处理这个。主要是通过walkableRadius，来对可行走区域进行重新赋值。

处理逻辑在rcErodeWalkableArea()中。

基本算法可以分为三个遍历：

1. 第一次遍历：标记边界cell。dist表示某个开放空间离边界的距离。如果这个开放空间本身不可走，或者其有一个或多个邻居空间不可达，那么便将dist设为0，认为这个点是边界。

2. 第二次遍历：从左下方开始压缩可行走区域。这里需要注意的地方有两点：

   1. dist最后会与直径比较，而传入的radius是半径，会乘以2。因此沿着轴方向dist的值也是以2为基数增加。

   2. 斜下方向精确的值应该为 $\sqrt{2} * 2$ ，这里为了快速计算，直接近似为3。

   3. x和z的坐标均从0开始。dist会从最左下累加。

3. 第三次遍历：从右上方开始压缩可行走区域。基本算法和第二次遍历一样，只不过遍历的起始坐标不同。

核心源码如下:

// 两个pass，需要从八个方向来压缩。
// Pass 1。注意遍历是从0开始，是从左下开始递归累加dist值
for (int y = 0; y < h; ++y)
{
	for (int x = 0; x < w; ++x)
	{
	    const rcCompactCell& c = chf.cells[x + y*w];
		for (int i = (int)c.index, ni = (int)(c.index + c.count); i < ni; ++i)
		{
			const rcCompactSpan& s = chf.spans[i];

			if (rcGetCon(s, 0) != RC_NOT_CONNECTED)
			{
				// (-1,0)
				const int ax = x + rcGetDirOffsetX(0);
				const int ay = y + rcGetDirOffsetY(0);
				const int ai = (int)chf.cells[ax + ay*w].index + rcGetCon(s, 0);
				const rcCompactSpan& as = chf.spans[ai];
				// 这里加2，是因为dist最后需要与直径比较。而radius是半径，转化为直径需要乘以2。
				nd = (unsigned char)rcMin((int)dist[ai] + 2, 255);
				if (nd < dist[i])
				{
					dist[i] = nd;
				}

				// (-1,-1)
				if (rcGetCon(as, 3) != RC_NOT_CONNECTED)
				{
					const int aax = ax + rcGetDirOffsetX(3);
					const int aay = ay + rcGetDirOffsetY(3);
					const int aai = (int)chf.cells[aax + aay*w].index + rcGetCon(as, 3);
					// 这里加3，是快速近似模拟1.414*2为整数。
					nd = (unsigned char)rcMin((int)dist[aai] + 3, 255);
					if (nd < dist[i])
						dist[i] = nd;
				}
			}
			// 同样处理(0,-1)和(1,-1)方向
			...
		}
	}
}

// Pass 2。注意是从h-1和w-1开始，是从右上开始递归累加dist值
for (int y = h - 1; y >= 0; --y)
{
	for (int x = w - 1; x >= 0; --x)
	{
	    // 处理(1,0)、(1,1)、(0,1)、(-1,1)方向
	    ...
	}
}

区域划分算法

现在我们得到了一个或者多个巨大的联通区域。但是寻路我们需要拥有粒度更细的数据。那么我们需要将这个巨大的联通区域划分为多个小区域。UE4（或者说Recast组件）提供了三种划分区域的算法：Watershed、Monotone和Chunky。

• Watershed：中文名称为分水岭算法，是一种传统的划分区域的算法，在图像处理上也经常用于利用灰度值划分一张图片上的不同色块（想象一下Photoshop的魔棒工具）。
  基本原理是将场景看做一张高度图。不连通的地方看做山脉，联通的区域看做盆地。向场景灌水，水会优先流入盆地。在灌水的过程中，如果两个盆地汇合，那么在汇合的交界处我们可以修一道堤坝，看做是这两个区域的交界处。

• Monotone：是一种快速的划分区域的算法。基本原理是利用直线与多边形相交的几何性质。但是相比Watershed算法，并没有那么精确。

• Chunky：针对小区域的Monotone算法。

区域划分算法会在下一篇用单独的篇章详细讲解。这里大致放出区域划分的结果：

对于如图所示的区域：

使用Watershed划分的区域如下：

使用Monotone划分的区域如下：

为3D场景分层

现在我们有了全部的region数据。但是还有两个问题：

1. 每个region是根据cellsize生成的，粒度有可能很小。实际游戏场景可能是一块大平地，整个区域的粒度不需要那么小。

2. 游戏场景是3D的，每个region都有可能有不同的高度。要适配3D游戏的寻路需求，就需要将目前已有的region数据适配为3D适用的数据。

Recast的解决方案是：

1. 寻找大区域的边界线。边界线中间包含的区域都可以看做是一个相连通的大区域。

2. 在竖直方向上分层。

以下均以Watershed算法实现源码来讲述。

寻找边界线

算法可以概括为：

1. 遍历所有span，找到位于边界旁边的span

2. 如果某个方向是边界，那么标记，沿着顺时针方向找下一个。

3. 如果某个方向不是边界，那么沿着逆时针方向找下一个。

4. 当方向和坐标都与起始点相同时，跳出循环。

下图是一个完整的寻找边界线的过程：

核心源码在walkContour()中。

static void walkContour(int x, int y, int i, int dir, rcCompactHeightfield& chf, unsigned short* srcReg, rcIntArray& cont)
{
	// 如果是标准xy轴，dir=0代表-x方向，1代表y方向，2代表-x方向，3代表-y方向
	// dir从0到3相当于顺时针旋转
	// 外部保证传入的是一个边界格子点
	// 如果指定方向是边缘，那么顺时针转向。如果指定方向是空地，那么逆时针转向。
	
	//... 初始化

	int iter = 0;
	while (++iter < 40000)
	{
		const rcCompactSpan& s = chf.spans[i];

		if (isSolidEdge(chf, srcReg, x, y, i, dir))
		{
			// Choose the edge corner
			unsigned short r = 0;
			if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
			{
				const int ax = x + rcGetDirOffsetX(dir);
				const int ay = y + rcGetDirOffsetY(dir);
				const int ai = (int)chf.cells[ax+ay*chf.width].index + rcGetCon(s, dir);
				r = srcReg[ai];
			}
			// 将边界点加入cont集合
			if (r != curReg)
			{
				curReg = r;
				cont.push(curReg);
			}

			// 沿着某个方向找到边界之后，顺时针方向找下一个边
			dir = (dir+1) & 0x3;  // Rotate CW（Clockwise）
		}
		else
		{
			int ni = -1;
			const int nx = x + rcGetDirOffsetX(dir);
			const int ny = y + rcGetDirOffsetY(dir);
			if (rcGetCon(s, dir) != RC_NOT_CONNECTED)
			{
				const rcCompactCell& nc = chf.cells[nx+ny*chf.width];
				// rcGetCon可以获取到某个方向上相连的span的索引。因为在构建体素的阶段，所有的联通信息都存在了con字段中。
				ni = (int)nc.index + rcGetCon(s, dir);
			}
			if (ni == -1)
			{
				// Should not happen.
				return;
			}
			x = nx;
			y = ny;
			i = ni;

			// 如果该方向不是边界，沿着逆时针找下一个边界
			dir = (dir+3) & 0x3;	// Rotate CCW
		}

		if (starti == i && startDir == dir)
		{
			// 寻找完毕
			break;
		}
	}

	//... 去重
}

竖直方向分层

以上很多步骤，都是以二维平面来举例。包括传统的A*寻路算法也是二维平面。但是3D游戏的场景都是3D的，如何将3D游戏与传统的寻路结合起来？

整个RecastDetour组件做了这么几件事来保证支持3D寻路：

1. 3D体素化的阶段记录span的信息，并会记录相邻span的连接信息

2. 区域划分是以span为单元来遍历

3. 为整个场景分layer

4. 寻路算法依然采用A*算法，并以layer为单位

1、2是基础，3是关键。这里介绍一下分层的算法。

层的概念，就是上一步找到的一个边界线内部就是一层。分层有一个基础，就是每个span都有一个regionId。算法说起来也是很简单：

遍历所有的span，找到每个span竖直方向的其它span，将其regionId记录在layers当中。

1. 遍历所有的span，找到每个span竖直方向的其它span，将其regionId记录在layers当中。

   // 当前span的竖直方向如果有其它span的话，将其它span所属的regionid全部记录在reg.layers中
   for (int j = (int)c.index; j < ni; ++j)
   {
       unsigned short nri = srcReg[j];
       if (nri == 0 || nri >= nreg)
           continue;
   
       if (nri != ri)
       {
           addUniqueLayerRegion(reg, nri);
       }
   }

2. 上一步已经介绍过的：找到每个region的边界线。

3. 遍历边界线，找到边界线上的每个region，将所有region的竖直方向上的layer都合并到自己的layers中。这就是这个边界线所对应的层竖直方向有交集的其它层的集合。

   unsigned short layerId = 0;
   rcIntArray stack(64);
   for (int i = 0; i < nreg; i++)
   {
       // 遍历所有的区域
       rcLayerRegion& reg = regions[i];
       if (reg.visited || !reg.hasSpans)
           continue;
   
       reg.layerId = layerId;
       reg.visited = true;
       // 每一层只有一个region的base是true
       reg.base = true;
   
       stack.resize(0);
       stack.push(i);
   
       while (stack.size())
       {
           int ri = stack.pop();
           rcLayerRegion& creg = regions[ri];
           // 遍历当前区域的边界区域
           for (int j = 0; j < creg.connections.size(); j++)
           {
               const unsigned short nei = (unsigned short)creg.connections[j];
               if (nei & RC_BORDER_REG)
                   continue;
   
               rcLayerRegion& regn = regions[nei];
               // Skip already visited.
               if (regn.visited)
                   continue;
               // Skip if the neighbor is overlapping root region.
               if (reg.layers.contains(nei))
                   continue;
               // Skip if the height range would become too large.
               const int ymin = rcMin(reg.ymin, regn.ymin);
               const int ymax = rcMax(reg.ymax, regn.ymax);
               if ((ymax - ymin) >= 255)
                   continue;
   
               // visit
               stack.push(nei);
               regn.visited = true;
               regn.layerId = layerId;
               // add layers to root
               // 把所有边界的竖直方向的layers全部加到自己的layers中。这一步可以保证之后按照layer为单位来合并
               for (int k = 0; k < regn.layers.size(); k++)
                   addUniqueLayerRegion(reg, regn.layers[k]);
               reg.ymin = rcMin(reg.ymin, regn.ymin);
               reg.ymax = rcMax(reg.ymax, regn.ymax);
           }
       }
   
       layerId++;
   }
   // 这个遍历过后，所有联通的区域都有着相同的layers。意味着在竖直方向上，所有区域全部分层完毕。

4. 合并高度相差过小的层

   // 高度相差很小的layer直接合并
   // Merge non-overlapping regions that are close in height.
   const unsigned short mergeHeight = (unsigned short)walkableHeight * 4; 
   {
       //...双重遍历所有region
       // 所有的region两两比较。遍历的时间复杂度是O(n^2)
       
       //...过滤边界条件以及一层高度过大的情况
       
       // 如果两者距离相差过大，直接continue
       if (!overlapRange(ri.ymin,ri.ymax+mergeHeight, rj.ymin,rj.ymax+mergeHeight))
           continue;
       
       // 运行到这里说明这两个layer之间的高度相差小于mergeHeight
       
       bool overlap = false;
       for (int k = 0; k < nreg; ++k)
       {
           if (regions[k].layerId != rj.layerId)
               continue;
           // 如果ri区域的竖直方向包含区域k，说明ri和k有overlap
           if (ri.layers.contains(k))
           {
               overlap = true;
               break;
           }
       }
       // Cannot merge of regions overlap.
       if (overlap)
           continue;
       
       // Can merge i and j.
       oldId = rj.layerId;
       break;
   }
   //...遍历结束
   
   // 真正的合并操作
   for (int j = 0; j < nreg; ++j)
   {
       rcLayerRegion& rj = regions[j];
       if (rj.layerId == oldId)
       {
           // 合并的操作，就是清除base、更新layerId、合并layers，三个步骤
           rj.base = 0;
           // Remap layerIds.
           rj.layerId = newId;
           // Add overlaid layers from 'rj' to 'ri'.
           for (int k = 0; k < rj.layers.size(); ++k)
               addUniqueLayerRegion(ri, rj.layers[k]);
           // Update height bounds.
           ri.ymin = rcMin(ri.ymin, rj.ymin);
           ri.ymax = rcMax(ri.ymax, rj.ymax);
       }
   }

5. 重新分配layerid

   这一步是因为合并layer之后，有些layerid已经失效。因此会重新分配从0开始的layerid

初始化rcHeightfieldLayer结构

将上述的数据写入到rcHeightfieldLayer类，可以供寻路算法使用。

小结

这一篇讲述了整个Recast生成导航区域数据的过程。总体来看，根据体素化过程得到的实心span数据，生成open span数据，再通过计算邻居span之间的连通性，划分出不同的区域，并在竖直方向分层，以保证3D寻路的要求。

下一篇将会着重讲述UE4用到的区域划分算法：Watershed和Monotone。