Deep Space Exploitation：#9 - 寻路（Pathfinding）

Pathfinding

Source | HN Comments

文章介绍了为游戏开发 NPC 寻路功能的实现。作者采用了 A* 寻路算法，并结合空间划分树优化查询效率。为了适应动态环境，算法使用缓存来处理移动的物体，并定期使缓存失效。此外，为了让路径更自然，算法加入了物体接近度等级，使路径倾向于远离物体。最后，文章还讨论了环绕路径的处理以及效率优化，通过分帧处理来避免性能问题。

Deep Space Exploitation

#9 - Pathfinding

Deep Space Exploitation » Devlog Like2 5 hours ago by JuhrJuhr (@JuhrJuhr) Share this post: Share on Bluesky Share on Twitter Share on Facebook

大家好！ 我最近一直在为游戏中的 NPC 开发寻路功能，这件事情我期待已久，因为它是一个很不错的、需要解决的大问题。我打算写一篇博文，介绍我是如何完成这项工作的。

由于我的游戏玩法，我对寻路有一些额外的要求：

必须处理动态的物理环境（物体可以自由移动并且可以被破坏）
寻路路径最好与物体保持一定距离，但在需要时仍然可以靠近
允许在游戏区域的边界处进行环绕（类似 Asteroids 风格）

总体方法

我的第一个想法是，我希望寻路路径足够详细，以便可以轻松地穿过混乱的物体排列。这意味着更长的搜索时间，因此搜索算法的简单选择是 A*。并且由于我需要查询每个节点的世界以查看它是否被阻塞，因此我认为我会使用空间划分与查询来减少每个路径所需的数量。

我最终坚持了这个计划，并在过程中弄清楚了更详细的东西。

空间划分查询

我构建了一个空间划分树，其中每个节点覆盖游戏的特定区域，然后该节点的每个子节点覆盖其父节点区域的特定区域（树的根覆盖整个游戏区域）。我将其执行到深度为 6，然后叶节点有效地构成寻路导航网格。

现在，当我检查一个节点是否被阻塞时，它首先会检查其父节点。如果其父节点未被阻塞，则其所有子节点都不会被阻塞。如果父节点被阻塞，则子节点需要运行自己的查询，以查看其自己的区域是否被阻塞。这使我们能够通过很少的查询知道游戏的大部分区域是否未被阻塞，这很有用，因为这些查询非常昂贵。

A* 搜索

实际的搜索是一个非常标准的 A* 搜索。每个节点有 8 个邻居，边缘上的节点具有环绕的邻居，这些邻居与它们的遍历成本一起缓存，以便更快地查找。

实时变化的环境

因为物体可以在游戏世界中移动，甚至会被破坏，所以这个算法需要能够实时更新。刚才没有阻挡路径的小行星可能已经移动了，而刚才阻挡路径的小行星可能已经被炸毁了！

我为此提供的简单解决方案是允许算法缓存它检查的每个节点是否被阻塞，但随后每隔一段时间（目前每 500 毫秒效果很好）使该缓存失效。这允许有时间建立世界的图像，并让一个寻路请求使用来自先前请求的信息，但也迫使算法跟上世界的当前状态。

理想情况下，我们不会使整个缓存失效，因为游戏世界的某些部分没有任何变化，但实际上，这是一个足够简单且有效的策略。话虽如此，如果需要，我确实有一个关于如何做到这一点的计划。

在这里你可以看到它实时扩展和更新。每个蓝色方块代表一个未被阻塞的节点，节点中像素的颜色代表与最近物体的距离。

自然的路径

最短路径通常看起来不自然，或者说不安全，所以我希望算法更倾向于远离物体的路径，但在必要时仍然可以靠近（例如，穿过一个小间隙）。

因此，对于每个寻路请求，都会提供一个与物体的首选距离，然后使用该距离为每个节点提供一个接近度等级。此接近度等级在确定到节点的遍历成本时使用，因此在运行搜索时，更靠近物体的节点会更昂贵。

目前，接近度等级具有指数效应，因此路径确实试图避免非常靠近物体，但如果必须靠近一点，它并不介意。

在这里你可以看到路径保持与物体的距离，直到它被迫靠近并在它们之间穿行。你也可以更好地看到空间划分，更大的蓝色方块代表只需要一次查询的区域。

环绕的路径

因为游戏区域允许类似 Asteroids 的环绕，所以我也希望寻路能够考虑到这一点。 NPC 不像玩家那样具有相同的移动性有点刺耳，而且它也使这个问题更有趣。 :)

环绕的路径意味着每个导航节点实际上具有相同数量的邻居，这是一个有趣且可能不常见的属性（3D 地球上的寻路可能具有相同的属性）。

生成环绕的路径实际上并不是困难的部分，很简单就可以给边界节点在网格另一侧的邻居。困难的部分是如何让 NPC 实际跟随该路径，因为在没有任何特殊处理的情况下，它只会到达一个边界处的节点，然后转身并直接朝另一个边界处的节点移动，而根本没有环绕。

为了解决这个问题，每当在路径上发生环绕时，都会在屏幕外添加一个额外的节点，NPC 尝试跟随该节点，然后最终环绕。还有一个问题是，当 NPC 开始环绕时，你使用哪个 NPC 位置来跟随路径（一个物体在环绕时有多个位置），但是一个简单的解决方案是只使用最接近路径中下一步的 NPC 位置。

边界有它们自己的接近度成本，以使路径稍微远离它们，并且使环绕成为一种最后的手段。

在这里你可以看到路径展开并发现，绕过该顺序的最短路径是绕过该顺序，而不是绕过小行星。你还可以看到角落里的经过时间，这是每次更新处理路径所花费的时间，而不是总更新时间。

效率

此算法正在执行大量工作，对于更复杂的路径（无论如何，在我的机器上）最终可能需要几毫秒。我正在努力使游戏尽可能地保持高性能，因此对我来说，这不会减慢任何速度非常重要。

我的方法是首先尽可能地对事物进行基准测试和优化，然后将单个寻路请求的处理分成多个游戏节拍。为了在多个节拍中进行拆分，我在每次 A* 搜索迭代后检查访问的节点数和世界查询，如果其中任何一个超过了我设置的阈值，则循环退出并在下一个节拍中从中断的地方开始。

这意味着当实体请求路径时以及何时获得结果时，存在一些异步性。由于等待时间始终是个位数毫秒，因此玩家实际上感觉不到，尤其是因为它只是 NPC 发出路径请求而不是玩家。

这种效率问题看起来很适合多线程处理，但是我在这里遇到的主要问题是游戏的所有世界状态都保存在主线程和复杂的结构中，因此将其复制到寻路线程将很困难并且可能很慢。我本可以允许寻路线程向主线程发出查询请求，但是那样我们需要处理更多的同步逻辑。因此，为了减少麻烦，我坚持使用主线程并在节拍之间分配处理。

结论

我从其他示例中查看的唯一部分是核心 A* 搜索，其他所有内容都是我自己尽力解决的。我可以说我想要的解决方案具有在线上的许多示例无法满足的特定要求，但老实说，我什至没有看，因为我想自己尝试一下。我喜欢游戏开发的地方是围绕有趣的问题进行思考并提供（希望）一个好的解决方案。也许我可以通过在网上找到别人的解决方案来更快地获得可行的解决方案，但是我不会像现在这样喜欢这个过程。

在我的解决方案测试中，它表现出色并产生了有意义的路径，也许更重要的是，玩家看起来很不错。我想深入研究某些方面，例如仅使世界发生变化的部分查询缓存无效，但可悲的是，我们最终必须转向其他功能。接下来，我将在为某些 NPC 创建行为时实际使用此路径，因此我们将看看结果如何。

获取 Deep Space Exploitation

立即下载