2023-08-16 10:44

企业号

关注

图形引擎实战：轻功寻路

大家好，我是来自搜狐畅游引擎部的codemouse，近期在维护我们的3D世界寻路的工作，因此这次给大家分享一下我们的3D世界自动寻路的扩展，展示一下我们的项目是如何让NPC或者玩家在3D世界中更自由的漫游。

## 项目介绍

总体介绍一下，我们的寻路是基于体素系统（可以通过该链接简单了解一下体素系统https://zhuanlan.zhihu.com/p/530739294以及我们对NavMesh的改造）构建生成出来的NavMesh寻路系统，利用这个寻路系统，让NPC或者玩家轻松的走到世界的每一个角落。

在传统的寻路中，通常是识别出路面，在一些路面上行走，但是在一些有轻功攀爬的游戏系统中，其实玩家可以通过攀爬和轻功的方式，抄近道，直达目的地，因此如果还是使用传统方法生成的寻路路线，就会显得自动寻路很呆，不太聪明的样子。因此即使是自动寻路，也需要让其学会抄近道，让其显得聪明一点，特别是如果要构建一个比较聪明的NPC世界，这种抄近道的行为，必不可少。同时还能让原先的自动行走，走到原先走不到的位置，例如屋顶，隔离开的岛屿等。

项目需求：

自动寻路遇到很高的墙面能攀爬上去。
自动寻路能在两个屋檐或者两个断桥间进行飞跃寻路。
自动寻路识别箱子或者屋檐上，并跳跃上去。
自动寻路能识别从屋顶、箱子或者悬崖能跳下去。
生成的寻路网格面与障碍体素存在相交问题。

## 关于NavMesh中如何制作传送阵

在NavMesh中，存在dtOffMeshConnection结构体，通过存储起点和终点以及一些配置，可以让NavMesh的寻路方法把其作为一个多边形去搜索，从而和原先的navMesh中的多边形浑然一体，只要获取到建立的其中一个端点，就可以获取到相连端点的位置。我们可以利用该特性，建立连接点，来达到制作传送阵的目的地。

例如下图，下面这两座岛屿，两者不互通，直接使用NavMesh生成出来的导航网格面就无法找出可以行走到对面岛屿的路线，只能找到一个接近对面岛屿的点，但始终是无法达到对面，需要玩家主动的通过轻功来帮助其跳越到对面，才能继续自动导航到目的端，对于玩家操控的角色还好，但是对于游戏NPC来说，就没有办法通过玩家去干预跳越了，只能干瞪眼。

但是通过创建一个dtOffMeshConnection结构，制作出传送阵（跳点），此时NavMesh就可以将这个传送阵当作是Navmesh中的多边形去搜索，从而找出一条合理的路线来。

例如下图，在两个岛屿上分别取出一个位置来作为传送阵的起点和终点，重新烘焙出新的寻路数据后，找出了一条可行走的路线。

通过这种方法，只要搜索到了传送阵一端的点，那么我们就知道另一端的位置，那么我们就可以通过项目对应的方法去控制NPC角色的动作，例如瞬移、轻功跳越等方式，从而到达对面岛屿的目的地。

那么我们知道了传送阵（后面称作跳点），我们还能用利用它的特性来做什么呢？

## 自动生成跳点

那么我们知道了如何在NavMesh中制作跳点之后，我们就可以扩展出更多的内容，例如给出寻路的起点和终点后，发现路径上从屋檐之间跳越，我们行走的距离更短，我们人为的可以利用轻功飞跃过去，如果一堵无法飞跃的悬崖，那么我们可以利用攀爬给攀爬上去等等，那么我们只要人为的给这些特定的地点也设置上了跳点的结构，寻路的时候，就会自动获取到这些点，然后就可以开始自动寻路。

既然原理都清楚了，那么直接在编辑器上建立一套手动编辑传送点的功能不就好了，这有什么好讲的呢？

那么问题就来了，如果是一个小地图还好，可能也就几个地方需要这种跳点，但是如果是数百张小地图呢？亦或者是一张超级大的地图呢？这时候美术的工作量就会变得无比的庞大，每多加一个地图，就得费好多时间去编辑这些跳点，大部分时间都投入在这，这不现实，因此我们需要一个自动化的程序去帮助在场景中识别出这些特殊的地方，并给这些地方坐标直接存储下来，供寻路使用。此时美术的工作只需要一键点击即可完成这个繁琐而又机械化的工作。（后面的图中，跳点的起始点通过绿色箭头连接表示，方便展示。）

对于我们的自动生成的跳点，也是基于我们的体素系统，我们可以通过体素系统中的体素，了解到每格体素与周围场景的关系（高度差，距离等），通过这些信息，我们可以将一个圆柱体放到场景中去模拟，查看该位置适不适合人物站立，并是否可以通过移动，跳越的方式，抵达一个设定的地点。

### 跳上/跳下屋檐的寻路

我们通过体素系统，就可以了解到，什么地方存在着高度差，通过高度差与自身角色的跳越能力进行比较，可以了解到，哪些地方是需要跳，并且是可以跳越上去的地方。

如下图所示，可以看出，角色是可以站在屋檐下的，同时屋檐与底面的高度差超出我们设定的角色能直接走上去的高度，但是又小于我们角色的跳越/轻功的高度，那么我们就可以取地面对应的位置和屋檐上的对应的位置作为我们跳点的起始点。

而我们通过搜索体素系统中，存在高度差，且向内前进角色半径且可以站立的位置，就可以搜索出这一系列的点。

如下图，我们可以明显看出如果游戏中如果由轻功的话，角色是可以从下往上跳到屋檐上的，或者从屋檐跳到地面。

但是也不能无限制的每个体素格能满足的都让他生成跳点，这样的话，跳点就过于密集，可以对一个跳点周围人物半径的区域，让它不存在相同方向的跳点，减少密集度，即减少了跳点存储的内存消耗量，也不太影响寻路的实际效果。

如下图，这个我们生成的，经过稀疏后的跳点。

### 攀爬高墙

在跳上跳下屋檐识别的基础上，同时判断落点处向上是否为能通行，并判断出高点的下面是否为阻挡，如果是，且该墙壁无法通过轻功或者跳越越过，那则设定为攀爬跳点。

如下图所示，该位置就是角色无法直接跳越的位置，我们将其设置为攀爬跳点。

但是对于NavMesh来说，它只会返回该点是一个跳点，我们为了解决这个问题，对它的生成过程做了一定的修改，让其在得到该点的时候，让其返回给我们的是，该跳点是一个攀爬跳点的标记，从而给前端角色进行自动攀爬的时候，提供一个可参考的标记，从而可以灵活的让NPC进行攀爬运动。

### 跳越断桥/屋檐

通过简单的了解过体素系统后，我们应该可以知道，体素对于传统的mesh来说，是非常粗糙的，并且它在平面就像也给像素网格面一样，非常的整齐。由于这个体素的特性，我们在前后左右四个方向很方便获取数据，但是获取斜向位置的数据，异常的不方便。因此如果还和前面一样简单的通过体素系统去获取体素位置的跨n个区域是桥面或者屋檐就非常的困难（因为有可能是斜着摆放的，体素不好斜着获取）。

因此我用了一个比较取巧的办法去获取对面是否为断桥或者屋檐，通过生成场景的多边形网格面，找到多边形网格面中，没有相邻边的多边形的边，在这个多边形的边上做水平的垂直线，搜索这个垂直线（长度也就是可跳越最大距离）所经过的体素，找到路径中与自己高度位置相差不大的体素作为目的端，也就是我们所要搜索的断桥或者屋檐的位置。

如下图是没有旋转过的桥，就是通过多边形的边找到了对面的桥。

如下图是旋转了45°以后的桥，也是通过多边形的边找到了对面的桥，然后建立了跳点。

## 生成的寻路网格面与障碍体素存在相交问题

NavMesh导航生成是基于体素系统，体素中那些不可行走的地方，可以认为就是游戏中的障碍物或者说是不允许过去的地方。但是在NavMesh生成的导航数据中，存在导航网格与不可行走区域产生相交的问题，在实际的项目运行中，这些不可行区域可能是个坑洞，或者一个箱子的内部区域，如果角色导航到这种位置下线再上线，就可能出现坠落到里世界的问题，因此我们需要解决这个导航网格与不可行走体素相交的问题。

在翻阅NavMesh的源代码可以发现，产生相交这个问题是因为在NavMesh生成导航网格的轮廓的时候，有一个简化轮廓的过程（也就是消除锯齿的过程），里面的关键点的连接会根据设定的最大偏离值去判断是否需要连接。

简化轮廓的计算方法：

经典的Douglas-Peucker算法步骤如下：

（1）在曲线首尾两点A，B之间连接一条直线AB，该直线为曲线的弦；

（2）得到曲线上离该直线段距离最大的点C，计算其与AB的距离d；

（3）比较该距离与预先给定的阈值threshold的大小，如果小于threshold，则该直线段作为曲线的近似，该段曲线处理完毕。

（4）如果距离大于阈值，则用C将曲线分为两段AC和BC，并分别对两段取弦进行1~3的处理。

（5）当所有曲线都处理完毕时，依次连接各个分割点形成的折线，即可以作为曲线的近似。

我们设定寻路角色的半径在一个单位的寻路生成长度，再根据数学上的计算，可以得到一个尽量让其锯齿尽量消除，但又不会与体素不可行走产生生成相交的一个值。该值的设定也与设定寻路角色的半径有关，半径越大，则该值可以设定的越大。该值越小，那么锯齿越大，寻路网格生成出来的多边形就会越多，造成内存占用的增大。反之锯齿就会越少，越顺滑，多边形越少，内存占用越少。该值小到一定程度的时候，该导航面就是完全贴合体素系统的锯齿的样子了。

下图是我们设定好合适的“最大偏离值”后的轮廓样式，实线是简化的轮廓，虚线是简化前的，生成的导航网格面就不会与体素系统的不可行走面产生相交。