上周，我们在博客中谈到了允许敌人（咬人）不相遇的变化，但这不是与咬人有关的唯一更新。 巧合的是，本周的更新包括了我们过去几周的工作-更新了敌人的搜索系统。
寻找方法
当单位要移动到某个地方时，首先需要了解如何到达那里。 在最简单的情况下，您可以直接移动到目标，但有时会在途中出现障碍物-岩石，树木，敌巢（生成器），玩家单位。 为了铺平道路，我们需要告知探路者功能当前和最终位置，探路者将返回到我们的
路径 （也许经过多次测量），该
路径只是该单元必须移动才能到达的一组路点。目的地
为了完成其工作，探路者使用了称为A *（发音为“ A star”）的算法。 视频中显示了一个使用A *查找路径的简单示例：biter想要在岩石周围找到路径。 寻路功能开始探索咬人周围的地图（研究以白点表示）。 起初，她试图直奔目标，但是一旦到达悬崖，她就会向两个方向“溢出”，试图找到一个可以再次从其移至目标的位置。
该视频中的算法速度变慢，因此您可以更好地了解其工作原理。动画中的每个点都代表一个
节点 。 每个节点都会记住从搜索开始起的距离以及该节点到目标的距离的估算值（此估算值是通过
启发式函数计算得出的）。 这要归功于A *的启发式功能-它将算法导向正确的方向。
在最简单的情况下，此函数只是简单地计算从节点到目标位置的直线距离-这是我们从开发之初就在Factorio中使用的方法，由于这个原因，算法使算法最初沿直线移动。 但是，这不是唯一的选择-如果启发式函数知道某些障碍，它可以指导算法围绕它，这将加快搜索速度，因为它不必检查额外的节点。 显然，启发式方法越聪明，实施起来就越困难。
一个简单的启发式直线距离估计功能非常适合查找相对较短距离的路径。 它适合我们在Factorio的早期版本中使用-几乎总是让苦涩者长途跋涉，只是因为他们对污染感到愤怒，而且这种情况很少发生。 但是，我们现在有炮兵。 大炮可以轻易在一个大湖的另一侧向大量的苦味射击（并“凝结”），然后试图在湖周围铺平道路。 下面的视频显示了我们之前使用的简单A *算法如何绕过湖面。
该视频显示了实际算法的速度； 他没有放慢脚步。减少区块
寻找路径是一项历史悠久的任务，有许多技术可以改善它。 其中一些技术属于
分层路径搜索的类别：在这种情况下，首先简化地图，然后将路径定位在此简化地图上，然后将其用于查找真实路径。 我再说一遍，这种技术有几种特定的实现，但是所有这些都需要简化搜索空间。
如何简化Factorio的世界？ 我们的地图是随机生成并不断变化的：放置和删除实体（例如，收藏家，墙壁或炮塔）-这可能是整个游戏的最基本机制。 我们不想在每次添加或删除实体时都重新计算整个简化地图。 同时，如果每次需要找到方法时都重新简化地图，那么我们很容易失去性能方面的所有收益。
可以访问游戏源代码的人（Allaizn）提出了一个主意。 结果我实现了。 现在这个想法似乎很明显。
该游戏是基于32x32区块的块。 简化过程将每个块替换为一个或多个
抽象节点 。 由于我们的目标是改善对湖泊周围路径的搜索，因此我们可以忽略所有实体，只考虑瓷砖：您不能在水上，土地上移动。 我们将每个块分成单独的
组件 。 组件是一个图块区域，单位可以在其中从一个组件内部的一个图块到达同一组件的任何其他图块。 在下图中，该块分为两个独立的部分，红色和绿色。 这些组件中的每一个都将成为一个抽象节点-实际上，整个块被简化为两个“点”。
Allaizn最重要的想法是我们不需要为每个地图图块存储一个组件-只需记住每个块周边的图块组件，因为我们只对每个组件（相邻块中）连接的其他组件感兴趣，因此仅取决于块边界上的图块。
分层路径搜索
因此，我们想出了如何简化地图，但是如何使用它来查找路径？ 就像我说的，有很多分层路径搜索技术。 最简单的想法是从头到尾使用抽象节点查找路径，即，该路径将是您需要访问的块组件的列表。 然后，我们使用一系列好的旧搜索A *专门找出如何从块的一个组件移动到另一个组件。
这里的问题是我们过于简化了地图：如果不可能从一个块移动到另一个块怎么办，因为某些实体（例如岩石）会阻塞路径？ 减少块时，我们将忽略所有实体，因此，我们仅知道块之间的图块以某种方式连接在一起，但是对于是否可以从一个移动到另一个，我们一无所知。
解决方案是将简化简单地用作实际搜索的“建议”。 特别是，我们将使用它来创建启发式搜索功能的智能版本。
结果，我们得到了以下方案：我们有两个探路者：
基本探路者 （用于查找实际路径）和
抽象探路者 （用于向基本探路者提供启发式功能）。 每次基本路径查找器创建一个新的基本节点时，它都会调用一个抽象路径查找器以获取到目标的距离的估计值。 抽象路径查找器以相反的顺序进行操作-从搜索目标开始，为从块的一个组成部分到另一个组成部分的开始铺平了道路。 当抽象搜索找到要在其中创建新基础节点的块和组件时，它将使用距抽象搜索开始的距离（正如我所说，这是整个搜索的目标位置）来计算从新基础节点到一般目标的距离的估算值。
但是，即使抽象探路者从一个块移动到另一个块，为每个单独的节点执行整个探路器也将很快。 因此，相反，我们使用一种称为“反向可恢复A *”的方案。 正如我上面所说，“反向”意味着它是从目标到开始的。 “可更新”意味着在找到基本路径查找器感兴趣的块之后，我们将其所有节点保存在内存中。 下次基本探路者创建新节点并需要距离估计时，我们只需查看从先前搜索中保存的抽象节点即可。 同时，很有可能所需的抽象节点仍将保留在内存中（最后，一个抽象节点覆盖了大部分块，通常覆盖了整个块）。
即使基本路径查找器在一个块中创建的节点都未被任何抽象节点覆盖，我们也无需再次执行整个抽象搜索。 A *算法的一个便利功能是，即使“完成工作”并找到路径后，它仍会继续执行，并在已研究的节点周围探索节点。 如果我们需要对尚未被抽象搜索覆盖的块中的基本节点进行距离估计，这就是我们要做的事情：我们从存储在内存中的节点恢复抽象搜索，直到其扩展到所需的节点为止。
以下视频显示了一个正在使用的新寻路系统。 蓝色圆圈是抽象节点； 白点-基本搜索。 视频中的探路者要比游戏慢得多才能显示其工作原理。 以正常的速度，整个搜索仅需花费几个时间。 请注意，基本搜索仍然使用我们一直使用的旧算法，只是神奇地“知道”了如何在湖中移动。
由于抽象探路者仅用于获得距离的启发式估计，因此基本搜索可以很容易地偏离抽象搜索提出的路径。 这意味着，即使块缩减方案忽略了所有实体，基本探路者也几乎可以绕过它们而不会出现问题。 由于在简化地图的过程中忽略了实体，因此我们不需要在每次添加或删除实体时都重复重复此步骤，仅覆盖已更改的那些图块（例如，使用垃圾填埋场的情况）就足够了，这种情况比放置实体要少得多。
另外，这意味着我们实际上使用了多年以来使用的相同路径查找器，只更新了启发式功能。 也就是说，此更改不会影响许多其他系统，而只会影响搜索速度。