背景最近在实现一个3D沙盒游戏。基本功能是在3D平面中建造建筑物，可以添加或编辑建筑物，然后平面中有人物模型，他可以在建筑物之间行走。在实现人物行走功能的时候，我们很自然地想到，取终点坐标和起点坐标，然后沿着直线行走。这个创意在没有建筑的时候确实不错，但是一旦在地图上出现了建筑之后，你就会发现：Temeow的角色都是穿着模特！至此，寻找避障方案的旅程开始了。使用Babylon.js内置的避障功能由于我们的项目是使用Babylon.js框架开发的，所以我们首先想到的是使用Babylon.js内置的避障功能。简介简单介绍一下Babylon.js中内置的避障功能，该功能是框架的扩展功能，需要配合RecastJS依赖使用。使用RecastJS生成NavigationMesh。然后使用RecastJS中的CrowdAgents模块进行自动寻路避障。看到这里大家可能会有疑问，什么是导航网格，这里是我在其他博客看到的一个定义和介绍：“导航网格（NavigationMesh），也俗称行走面，是一个多边形的用于在复杂空间中导航寻路和标记步行位置的网格数据结构。”一个导航网格是由很多个凸多边形组成的，说白了就是把地图切割成N份，每份都是一个凸多边形，我们称一个多边形为Poly。那么当角色在导航网格中行走时，会判断起点和终点是否在同一个Poly中，如果是，则直接将起点和终点连成一条直线，即为角色的行走路线；否则，需要使用相应的寻路算法计算路径，计算出角色需要经过哪些polys，然后用这些polys来计算具体的路径，当应用程序知道babylon.js有这样的功能时，我当时欣喜若狂，于是按下了键盘随意按照官网上的例子，刷新页面，添加了一个建筑，点击地图，期待角色模型自动绕过建筑，结果：发生了什么？我的经验告诉我at应该是导航网格没有正常生成导致的。幸运的是，RecastJS提供了多种参数让我可以调整导航网格的生成规则。于是乎，调了差不多一整天的参数，终于发现是自己太天真了，结果一点都没变。只有当添加的障碍物的尺寸非常小时，角色的避障功能才能成功生效。当障碍物的体积稍大时，角色会直接穿过建筑物到达终点。当时我的想法是：好吧，既然调参没用，那我就去RecastJS的源码看看它是如何生成导航网格的，是什么原因导致生成导航网格异常。所以，我切换到github。不搜不知道，一搜就惊呆了，发现这个RecastJS原来是用C语言开发的库，后来不知道是谁转成Javascript版本贴出来的在npm上，也就是说看不到Recast的JavascriptVersion源码。好吧好吧，babylon.js自带的避障功能的使用方式完全被屏蔽了。自建导航网格和搜索算法既然内置功能没用，而且babylon.js社区生态中也没有更好的解决方案，那么只能靠自己打造一套适合当前场景的导航网格和搜索算法。先来看看整体思路和流程：获取地图数据，生成合适的导航网格，获取角色行走的起点和终点，利用搜索算法寻找起点到终点的最短路径点导航网格，操作角色根据最短路径行动选择合适的搜索算法先说搜索算法。说到寻路的搜索算法，首先想到的应该是大名鼎鼎的广度优先搜索算法。广度优先搜索广度优先搜索算法是一种非常常用的寻路算法，广泛应用于各种计算机场景，比如Windows画板涂鸦功能，就是使用广度优先算法实现的。我们可以简单地将整个地图分割成N个1X1的正方形网格。广度优先算法的基本原理很简单，从起始格开始，每次上下左右移动。下图中绿色标记点为起点，红色标记点为终点。每轮探索结束后，会将本轮探索过的方格标记为边界，也就是下图中的绿色方格。然后算法会从这些边界方块开始，一个一个地继续下一轮探索，直到在探索过程中找到结束方块，算法就会停止探索。每次探索的时候，我们都需要记录路径的方向，也就是形成一个类似于链表的结构。到达终点后，我们可以根据方向的记录找到对应的最短路径。另外，每一轮探索过的路径格子必须在下一轮探索开始之前被标记，这样算法就知道这个格子已经被遍历过了，如果在后续的探索过程中遇到有标记的格子，就会跳过直接不会被纳入后续的探索轮次。下图中的灰色格子是标记为不再探索的格子。其实广度优先算法实现起来很简单，应用场景也很广泛，但是它也有明显的缺点，就是笨。在最坏的情况下，它需要遍历整个地图才能找到目标点，因此移动太多容易移动。经常导致性能问题。为了解决广度优先算法的性能问题，A-Star算法引入了启发式搜索A-Star算法。与广度优先算法不同的是，我们不会探索所有，而是会选择当前代价（cost）最低的方向去探索，所以它具有一定的方向性，它的前进方向取决于当前边界块中成本最低的块。成本分为两部分，一部分是当前距离成本，或者称为当前成本（f-cost），表示到目前为止你走过的路径数。例如当前格子需要三步才能到达，当前代价为3。代价的另一部分是估计代价（g-cost），表示从当前块到结束块需要多少步.由于它被称为“估计”成本，因此它不是一个准确的值。这个估计值主要用于指示算法优先搜索更有希望的路径。下面介绍两种常用的估算代价：欧拉距离（EulerDistance）：当前格子到终点的直线距离，用数学公式表示为Math.sqrt((x1-x2)^2+(y1-y2)^2)曼哈顿距离（ManhattanDistance）：指当前格子与终点在垂直和水平方向上的垂直和水平距离之和，用数学公式表示为|x1-x2|+|y1-y2|，曼哈顿距离计算不需要平方根，速度快，性能高。当我们知道某个边界块的当前成本和估计成本时，我们可以通过将这两个值相加得到它的总成本，即：总成本=当前成本+估计成本在每一轮寻路中，我们搜索具有探索当前边界内总代价最低的路径，并记录其方向并标记自己，类似于广度优先算法，直到探索结束，我们将通过A-Star算法得到对应的最短路径。与广度优先算法相比，A-Star算法具有一定的方向性，所以总体来说比广度优先算法少了很多无用的探索，遍历地图格子的数量也少了很多，所以综合性能总体上会优于广度优先算法。至此，我们有了合适的搜索算法，下一步就是看如何生成我们的导航地图了。自建导航网格在说如何构建导航网格之前，我们必须了解一个概念，即3D场景中的模型是由一个个三角形的面组成的，所以在构建导航网格的时候，我们也遵循这个原则来设计。Recast中导航网格的生成原理那么我们可以简单了解一下上面提到的Recast中导航网格的构建需要哪些步骤呢？简单来说，总共有六个步骤。场景模型体素化（Voxelization），或“光栅化”（Rasterization）。简单来说，就是将三角面数据转化为像素信息（也称体素信息），可以理解为从一个三角面转化为一个点阵信息。过滤掉可行走表面（WalkableSuface），即通过第一步得到的体素信息，计算体素顶部的可行走表面的数据。生成一个Region，在得到一个可行走的表面后，我们用一些算法把这个表面切割成尽可能大的、连续的、不重复的、中间没有空洞的区域，这些区域就成为Region。生成简化轮廓（SimplifiedContours），通过上一步得到的Region信息计算每个Region的边缘信息，再通过一些简化算法对边缘轮廓进行简化。我们称这种简化轮廓（SimplifiedContours）。为了生成PolyMesh，我们通过划分简化轮廓，将每个简化轮廓分成多个凸多边形。每个凸多边形可以称为一个Poly，它是寻路算法中的基本单位。GenerateDetailedMesh，最后我们对每个Poly进行三角剖分，分成多个三角形，生成我们最终的搜索算法需要用到的导航网格。这里值得一提的是，场景模型在第三步生成Region之后，实际上已经将三维场景简化为类似二维的存在，方便后续的一些计算和操作。但同时，这一步也导致模型在移动时无法完全垂直于地面，只能保持垂直于xOz坐标平面。在我们这次的沙盒游戏中，地图和建筑都非常简单。地图可以简单的看成一个64*64的正方形平面，建筑物也可以简化。变成一个简单的立方体。参考上面生成Recast网格导航的步骤，最终生成了一个不重叠的网格数据。由于我们的沙箱地图不是特别大，所以生成我们的导航网格的方式其实很简单。一句话：直接用一个64*64的正方形平面的顶点数据作为原始导航网格数据，然后剔除建筑物在地面上正方形投影接触的顶点数据，形成的网格剩下的顶点数据就是我们需要的导航网格。在后续的文章中，我们会更详细的讲一下生成方法。在这里，读者只需要有一个基本的概念。A-Star搜索算法与导航网格的结合至此，我们基本了解了A-Star搜索算法的原理和导航网格的生成方法，是时候将它们组装组合起来了。首先，我们在讲A-Star搜索算法的时候，假设地图是由1X1的正方形网格组成，但实际上，由于3D场景中的物体都是由三角形组成的，所以我们的导航网络的网格是同样由三角形组成，所以我们的A-Star算法中的一些计算应该相应地调整。在计算总成本的价值时，我们将总成本分为当前成本和上面提到的估计成本。在当前成本方面，我们还是按照目前已经走过的路径数来计算。使用欧拉距离计算估计成本。这里的计算将从计算正方形格子之间的距离转换为计算三角形之间的距离。因此，我们需要计算每个三角形的中心点，以及格子之间的距离。将使用中心点之间的距离代替，欧拉距离的值是从边界三角形的中点到结束三角形的中点的距离。接下来我们需要对地图顶点数据进行处理，过滤掉顶点数据中与建筑物投影相交的顶点，然后找到过滤后的顶点数据形成的每个三角形的中心点，以及与这个三角形相邻的三角形A列表（邻居）及其邻居数据（门户）。最后我们传入起点和终点数据，A-Star算法会根据起点数据和终点数据找到这个点所在对应的三角面数据，然后从起点三角开始，并根据其相邻三角形对应的cost值进行寻路，直到找到终点三角形，返回路径数据(paths)。最后，我们可以让角色沿着返回的路径数据进行相应的移动，从而达到相应的避障效果。实际应用下的优化其实到这里就结束了。我们已经基本实现了沙盒游戏的寻路算法。但是在测试过程中，我们发现由于获取的路径经过了过多的三角形节点，导致角色在行走时无法移动。拐点太多，有些三角形之间的路径明明可以用直线表示，但实际上需要经过很多三角形的中点。因此，我们引入了拉绳算法来解决路径中拐点过多的问题。这里不介绍拉绳算法。有兴趣的可以通过拉绳算法的漏斗算法进一步了解。加入拉绳算法后，人物的行走路径也进行了优化，最终的实际效果与理想效果基本一致。我们在后续项目优化之前的寻路算法其实并不是我心目中的最优解。因为在这次生成导航网格的过程中，因为我们把整个地图抽象成网格的形式，所以图中的节点太多了，当地图很大的时候遍历会很低效。因此，我们需要将栅格地图简化为节点较少的路标（Waypoints）形式，删除合并导航栅格中一些不需要的点和面。此外，我们还可以加入八叉树的概念，利用三维空间中的x、y、z轴将空间划分为8份，优化搜索效率。鉴于文章篇幅，这里就不对这些内容做过多的展开。希望读者保持好学的态度，读后继续深入研究。参考链接NavigationMesh（NavMesh）原理详解游戏寻路导航1：NavigationMesh最短路径搜索：A*寻路算法详解A*寻路算法#A星#HeuristicSearch
