复杂的路径规划算法

Question

我正在编写一个3D游戏系统，允许摄像机在节点网络之间移动。在我的项目中，我编写了一个代表节点的类。与二叉节点类不同的是，每个节点只能有一个父节点，但可以有任意数量的子节点。使用我的"真正惊人的"绘画技能，我开发了一张图像来表示这些节点的网络。在这个例子中，“根节点”是红色的，黄色路径是最短的，蓝色路径是最长的。重要的是要注意实际的子节点数量并不重要，而是它们之间路径的长度。因此，在计算最短路径时不需要使用启发式算法，因为最短路径将具有最小的组合长度。那么，如何编写递归函数遍历这棵树，并返回最短路径呢？

更新：尽管我的绘画技能很惊人，但我觉得它并没有完全说明我的问题，可能需要更详细的解释。首先，这是用于三维世界空间中的相机系统。世界将充满大量这些节点，并且相机将放置在其中一个节点上。玩家可以向任何方向查看，但不能移动，除非点击鼠标指定方向。一旦出现单击事件，就会沿着他面对的方向发射一条射线，检索出他和X距离之间的节点列表。这里的目标是找到与他连接的最远的节点，然后找到到达那里的最短路径。因此，第一个问题实际上是检查最远的“命中”节点是否比下一个最接近的“命中”节点更快地到达。最远的节点可能包含一条实际上比它前面的节点更长的路径，因此我还需要一些检查的方法。因此，虽然节点只能有一个父节点（如上所述），但应该可以从网络中的任何节点以任何方向遍历这个“树”，将玩家当前所处的节点视为“根”节点。

- RectangleEquals

---

一个构建图形的Dijkstra算法可以为您解决这个问题。只需要查找一下就行了。我之前做过这个，效果非常好。它可以找到任意两个节点之间的最短路径，并告诉您应该遵循哪些节点/路径。不过我错过了绘画技能。 - Khalil Khalaf

也许你想看一下维基百科上的Dijkstra算法页面。那里还有一个很好的动画。唯一的区别是，终止条件不是到达目标节点，而是到达任何叶子节点。 - alcedine

我不明白你想要什么。你是想计算到所有子节点的路径吗？那么使用哪种算法都无所谓，随便选一个（深度优先搜索、广度优先搜索）。如果你想找到两个给定节点之间的最短路径，那么“最短”这个概念就没有意义了：因为任何一个节点只能有一个父节点（它是一棵树），所以只有一条或零条路径。我有误解什么吗？附言：你的绘画技能非常棒 :) - FreeNickname

@freeNick 每个连接上都有权重。因此，每条路径的值都不同：连接权重之和。 - Khalil Khalaf

@FirstStep，是的，我明白了，但如果只有一条路径，那为什么这很重要呢？只有一个或零。这不是任意图形，而是一棵树。 - FreeNickname

Answer 1

一个Dijkstra算法可以解决这个问题。您需要向系统提供图形信息：有多少节点，每个节点的邻居是谁，每个连接的权重等等。只需查找一下即可。我在一段时间前做过这个，它像魔法一样奏效。它能够找到任意两个节点之间的最短路径，并且如果您稍微调整一下（我当时不得不调整我在网上找到的内容），它会告诉您要遵循哪些节点/路径。然而，我错过了绘画技巧。

一些实现版本在这里。

- Khalil Khalaf

---

这真的只是迪科斯彻算法吗？看起来相当相似...除了在我发布的示例中，没有预定义的“目标”需要达到。无论已经遍历了多少子节点，目标只是从根节点开始的最短结束路径。 - RectangleEquals

@reck 它提供了任意两个节点之间的最短路径，这是额外的好处。在您的情况下，如果我理解正确，源将是根节点，目标将是所有叶子节点（循环），然后选择最小值。 - Khalil Khalaf

如果您允许Dijkstra算法解析整个图（即其唯一的终止条件是开放集为空），那么它将为每个节点分配从根节点开始的距离值。然后，您只需迭代每个节点以查找最低和最高值即可。 - Fibbs

@rec，你能不能用你真正惊人的绘画技巧画出玩家所看到的准确图形以及节点之间的连接方式，而不是现在你脑海中的样子？因为我没有看到任何不同的地方，也没有看到任何 Dijkstra 无法解决的问题。 - Khalil Khalaf

也许不需要使用 Dijkstra 算法解决这个问题，直接放弃父节点和子节点的概念，改用按距离排序的 connectedNodes 数组会更好？ - RectangleEquals

Answer 2

我猜你想用可访问的空间点图来表示你的3D世界。忘掉树，它们只是图的特例。然后看看Dijkstra算法。如果你需要让它更有效率，那就看看A*算法，它是对Dijkstra算法的改进。

- Sergei