《Game AI Pro》使用迭代波前边扩展构建高层次导航网格
关于《Game AI Pro》 Creating High-Order Navigation Meshes through Iterative Wavefront Edge Expansions 的学习笔记。主要涉及使用迭代波前边扩展我也不知道怎么翻译构建navmesh。
简介
传统上，导航网格是由人工创建的，或者使用某种形式的自动空间分解算法。这些算法检查环境中存在的障碍物，然后将它们之间的区域分解为尽可能少的区域。遗憾的是，为游戏环境创建一个具有最佳（绝对最小）区域数量的分解是NP的。这意味着并没有最好的技术。
三角分解方法
当然，有许多种方法正在被尝试与改进。最经典的方法通常从某种形式的环境三角测量开始，然后试图通过组合这些三角形来最小化环境中存在的区域数量。
这种方法的问题在于，在导航网格中保留的三角形会给角色在许多三角形的公共顶点上的区域的导航带来问题。一个角色难以得知他们在汇合点上站在哪个区域。而这些汇合点在复杂的环境中经常出现，这就导致了各种各样的问题。
基于增长的方法
三角分解方法的替代方法是基于生长的方法，它将有助于最小化角色的localization问题。在作者之前的工作中，他们已经提出了基于生长的二维(PASFV)和三维(VASFV)空间分解定位算法，它的灵感来自于空间填充体积算法。虽然这些方法确实能生成高质量的导航网格，但在大型环境中执行时可能会很慢。这是因为这些算法要执行许多不必要的碰撞测试，因为它们必须验证每个生长区域在每个生长步骤中没有侵入另一个区域或障碍物。绝大多数时候，这种测试会返回一个否定的结果。这种不必要的测试是传统的基于生长的算法中顺序迭代扩展的结果。
波前算法
于是作者开发了迭代波前边扩展单元分解（为简洁起见，简称波前）算法，通过减少碰撞测试和迭代增长来解决之前技术中的问题。该算法的工作原理是扫描放置在世界中的每个区域可见的世界几何体，并确定可能发生碰撞的地方。通过强制区域直接扩展到这些位置，消除了大量的碰撞测试。这改变了基于生长的算法的运行时间度量，使其随着世界的复杂性（障碍物的数量）而增加，而不是随着世界的面积而增加。这种技术不仅比现有的基于生长的技术快，而且产生的导航网格通过提供高阶多边形/多面体几何区域，保留了PASFV和VASFV算法所表现出的高网格质量。接下来来看这一算法的具体实现思路。
实现思路
大致步骤如下
- 将单位大小的潜在区域（种子）放入世界中
- 随机选择其中一个区域，从这个区域的角度分析世界中存在的障碍物
- 所选区域进入加速扩张阶段。扩张的方向是算法第二步中分析发现的障碍物。对每个区域重复算法的第二步和第三步；这将使每个区域扩展到它们的最大可能尺寸。
- 新的种子被放置到与刚刚创建的区域相邻的任何可遍历空间中，算法返回到第二步，让这些新的区域扩张。如果无法放置新的种子，算法就会终止。
以下为步骤的详细介绍
初始播种
传统上，基于增长的算法首先使用基于网格的模式将初始单位大小的区域放入世界中。然后，这些方法迭代地给每个区域提供机会，使其沿着该区域的每个边的法线方向向外生长和扩展。
当在初始播种阶段使用波前算法时，我们会使用播种算法生成一个潜在的种子点列表，将潜在的种子放在每一个障碍物边旁边。与简单的网格播种相比，在放置更少的种子的同时有更好的整体覆盖率。然后，随机选择其中一个种子点作为初始区域。其他潜在的种子点将被保留在以后的播种队列中，但只有当它们仍然在未被某一区域占用的可达空间中时才会被使用。如果在以后的播种阶段，这个列表是空的，我们将尝试通过寻找与放置的区域相邻的无人认领的可达空间来重新填充它。如果在这之后这个列表仍然是空的，那么波前算法将终止。
边分类
在生成种子区域后，进入波前算法的边分类步骤。接下来的这两步是该算法中计算量最大的步骤，我们只希望在知道要扩展的有效区域上执行。因此每次只扩展一个区域，并舍弃被之前扩展所覆盖的空间中的种子。在这一步骤中，我们会遍历存在于世界中的障碍物的每一条边，以及存在于已经放置到环境中的区域中的所有边。然后，舍弃所有法向远离区域目标种子点的障碍物边，因为这些边是背向种子区域的，不能与种子区域交互。然后，根据这些边与目标区域位置相比的相对空间位置（+x、-x、+y、-y、+z、-z）将其分类。跨越多个类别的边被放置在第一个适用的类别中，这取决于算法实现中使用的评估顺序。作者的参考实现使用以下排序+y、-y、+x、-x、+z和-z。当然，任何排序都可以完成算法。
一旦这些障碍物边被排序，我们就会定位所有潜在的事件点。区域中法线与排序分类相匹配的边被称为分类边。通过比较每个障碍物边与适当的分类边的斜率，可以预先确定扩大的区域将如何与障碍物互动。这可以通过思考一个从初始种子点绘制的径向半平面扫描来可视化。这条扫描线将报告它发现的边的方向以及边上最接近初始种子点的点。这些被占用空间的边和刚刚放置的区域边之间的相互作用可以简化为一系列的情况。
其中第一种情况是，障碍物边与分类边平行，如上图所示。在这种情况下，我们希望扩张分类边，使其与目标边平齐。通过考察边上离正在评估的区域的初始种子点最近的点来实现这一操作。我们会将这个点以及从它到区域初始种子点的距离作为一个事件记录下来。同时，由于所有已完成扩张的种子区域和正在扩展的区域都只暴露出轴对齐的边，因此任何涉及已被占用的可达空间的情况都属于这一类。
如上图所示，当分类边将与障碍物的一个角相遇时，就会出现一种稍微复杂的情况。在这种情况下只能平行地扩展区域使这个角的顶点位于分类边上。不能改变分类边的斜率，因为这将可能覆盖到之前已完成的种子区域扩张占用的可达空间，这将违反被某一区域占用的空间必须始终保持被该区域占用这一原则。这种情况同样会存储被评估边上最近的顶点的位置以及该顶点到区域初始种子点的距离。
接下来这种情况更为复杂，它可能会导致在扩大的区域中增加新的边。如上图所示，最近的障碍边中间的某点与扫描线相交。这是一种边分割的情况，为了计算这种分割应该发生在哪里，我们要找到正在被考虑的障碍物边上最接近区域初始种子点的点。然后，这个点和这个点与区域的初始种子点之间的距离一起被存储为事件点。此外，存储被考虑的边的两个端点（假设最近的点不是端点），这样将能为这个区域增加一条与交点到某一端点长度相同的新边。然而，我们将不计算这些端点与初始种子点之间的距离，而是将它们视为一种只比事件点离初始种子点稍远一些的特殊情况。这将防止这些点在过程中干扰其他计算。
上图中可以看到一个更复杂的情况，有多个边分割事件。这样的事件应该根据扩张区域的初始种子点的距离来依次处理，通过考虑这些端点的距离确保区域在处理该点时，尽量将其中间的所有空间完全包含在内。
此时，已经有了一个潜在事件的集合，从而让新区域向着这个空间扩展。但是，在开始扩展之前，需要做两件事。首先，如果世界的边界被定义为一些边界条件，而非不可达的空间，则需要插入事件以允许每个区域向外扩展到世界的边界。同时这个列表需要根据每个事件与区域的初始种子点之间的距离进行排序。从而先处理距离较近、更有可能到达的事件，因为更远的事件往往因为存在更直接的障碍物而无法到达。
边扩展
有了某个区域的完整潜在事件列表，就可以进入波前算法的扩展阶段。首先，选择第一个（最接近的）未处理的扩展事件，并从潜在事件列表中删除。然后计算区域边必须移动的距离，以便它们到达这个扩展事件点。这是通过计算两个（三维中的三个）最接近的边的当前位置和目标扩展位置之间的距离来完成的。这个结果会被分解成几个分量（x, y, z），如果这些值是正数，边将直接扩张到事件点。扩张应该随着每个边迭代地向外移动而发生。所有的边都移动了之后，就可以执行碰撞和无效扩展的检查。之所以会发生这种情况，是因为有一些分割事件，如果只执行一半的事件（即允许一条边而不是两条边扩展），可能会出现各种问题。
区域完成扩展时，必须处理任何与其他区域或障碍物的碰撞。任何与障碍物碰撞的扩展区域的顶点处需要插入一条新的边来将该区域转换为一个高阶多边形/多面体。为了构造这个新边，可以取障碍边的相反法线，并将这个新边约束在障碍边的外延上。由于扩展事件是孤立计算的，并没有考虑其他区域，因此有可能发生碰撞，此时区域将不得不从潜在的膨胀事件中收缩。如果发生这种情况，发生碰撞的边应该停止进一步的扩张尝试；然后，算法将选择另一个扩张事件继续处理。重复这一过程，直到没有更多的事件或其所有边因碰撞而停止尝试扩张。
重新播种
在所有种子完成扩展后，将按照前面的播种过程放置更多的种子。如果算法进入播种阶段，但无法放置任何新的区域，它就会终止。这样就会产生一个区域集合，即为所需的navimesh。
后处理步骤
现有的基于增长的空间分解算法(如PASFV、VASFV和SFV)利用了一个后处理步骤来提高所得导航网格的质量。有时其中两个或更多的区域会成长为一个可以由单个凸区域填充的环境区域。这是同时放置和生长多个种子的自然结果，通常会通过合并区域来纠正。然而，这种组合需要花费时间和精力。波前算法的一个优点是它避免了大部分这种形式的后处理。由于两个区域永远不会同时生长，它们不能同时试图细分同一可达空间的凸形区域，从而产生更好的分解。
运行时间
波前算法最坏情况下的运行时间受其执行的环境复杂度的限制，为O(n*m)。其中，n是世界中预设的障碍物的数量，每个障碍物都必须由算法播种的m个区域来评估。这个运行时间可能看起来比现有的基于生长的空间分解算法更差，但这些算法的运行时间会根据世界的大小而增加（由于必须执行额外的生长步骤以填充世界），而波前算法的运行时间只会随着环境的实际复杂程度而增加。一般来说，波前算法的平均运行时间在毫秒到秒的范围内，而相比之下，基于增长的实现的运行时间在几秒到几分钟的范围内。同时，波前算法的内存占用是线性增长的，因为每个新生成的区域只需要在任何给定的时间点上与现有的区域和障碍物进行交互和了解。
总结
以上即为一个波前算法的运行结果。
总的来说，波前算法通过基于四边形的扩展算法生成快速、高质量的分解。这种分解有较少的小区域和退化区域（一般是三角形），而这些区域会干扰角色的导航。这种算法通过执行较少的扩展步骤改进了以前基于生长的方法，从而减少了必须执行的碰撞测试的数量。它的运行时间随世界的复杂性而扩展，而不是像现有的基于生长的方法那样随世界的大小而扩展。此外，由于该算法每次只生长一个区域，减少了通常由多个区域竞争填充同一凸区域而引起的后处理。本算法产生的分解与现有流行算法（如Hertel-Melhlorn或梯形单元分解两个奇怪的我没听说也搜不到的算法）产生的分解相比，效果较好。