复杂的寻路算法
Complicated pathfinding algorithm
我正在为 3D 游戏编写一个系统，允许相机在节点网络之间移动。
在我的项目中，我写了一个 class 代表一个节点。与二进制节点class不同，每个节点只能有一个父节点，但允许有任意数量的子节点。
使用我的真正惊人的绘画技巧，我开发了一个代表这些节点网络的图像：
本例中，"root node"为红色，黄色路径最短，蓝色路径最长。
这里需要注意的重要一点是，实际的 子节点数量并不重要 ，而是 添加的长度它们之间的路径。因此，在计算最短路径时不需要启发式方法，因为最短路径的组合长度最小。
那么你会如何写一个递归函数来遍历这棵树，并且return最短路径？
更新
虽然我的绘画技术很牛逼，但我觉得它并没有完全说明我的问题，也许需要更详细的解释...
首先，这是针对 3D 世界中的相机系统 space。世界将充满一堆这样的节点，相机将放在其中一个上。允许玩家朝任何方向看，但如果不在给定方向上单击鼠标则不能移动。一旦发生点击事件，就会向他面对的方向射出光线，检索他与他 X 距离之间的节点列表。这里的objective就是要找到最远连接到他的节点，然后最短路径到达那里...
所以第一个问题实际上是检查最远的 "hit" 节点实际上是否比下一个最近的 "hit" 节点更快到达。最远的节点可能包含的路径实际上比它前面的节点长 ，因此我还需要一些方法来检查它。所以心中有一个目标，但是这个目标可以换到稍微靠近一点的节点，让事情变得更加复杂。
是的，虽然节点可能只有一个父节点（如上所述），但这个 "tree" 实际上应该可以从网络中的任何节点向任何方向遍历，处理玩家当前所在的节点作为 "root" 节点。
Dijkstras 算法将为您解决这个问题。您需要为您的系统提供图表：有多少个节点，每个节点的邻居是谁，每个连接的权重......等等。只需查找即可。我刚才做了这个，它就像一个魅力。它会找到任意两个节点之间的最短路径，如果你稍微调整一下（当时我不得不调整我在网上找到的内容），它会告诉你要遵循的 nodes/path 是什么。但是我错过了绘画技巧
一些实现版本HERE
我猜你想要代表你的 3d 世界是 space 中可访问点的图表。忘掉树吧，它们只是图的特例。
然后研究 Dijkstra 算法。如果您需要提高效率，请查看 A*，这是对 Dijkstra 的改进。
我正在为 3D 游戏编写一个系统，允许相机在节点网络之间移动。
在我的项目中，我写了一个 class 代表一个节点。与二进制节点class不同，每个节点只能有一个父节点，但允许有任意数量的子节点。 使用我的真正惊人的绘画技巧，我开发了一个代表这些节点网络的图像：
本例中，"root node"为红色，黄色路径最短，蓝色路径最长。
这里需要注意的重要一点是，实际的 子节点数量并不重要 ，而是 添加的长度它们之间的路径。因此，在计算最短路径时不需要启发式方法，因为最短路径的组合长度最小。
那么你会如何写一个递归函数来遍历这棵树，并且return最短路径？
更新
虽然我的绘画技术很牛逼，但我觉得它并没有完全说明我的问题，也许需要更详细的解释...
首先，这是针对 3D 世界中的相机系统 space。世界将充满一堆这样的节点，相机将放在其中一个上。允许玩家朝任何方向看，但如果不在给定方向上单击鼠标则不能移动。一旦发生点击事件，就会向他面对的方向射出光线，检索他与他 X 距离之间的节点列表。这里的objective就是要找到最远连接到他的节点，然后最短路径到达那里...
所以第一个问题实际上是检查最远的 "hit" 节点实际上是否比下一个最近的 "hit" 节点更快到达。最远的节点可能包含的路径实际上比它前面的节点长 ，因此我还需要一些方法来检查它。所以心中有一个目标，但是这个目标可以换到稍微靠近一点的节点，让事情变得更加复杂。
是的，虽然节点可能只有一个父节点（如上所述），但这个 "tree" 实际上应该可以从网络中的任何节点向任何方向遍历，处理玩家当前所在的节点作为 "root" 节点。
Dijkstras 算法将为您解决这个问题。您需要为您的系统提供图表：有多少个节点，每个节点的邻居是谁，每个连接的权重......等等。只需查找即可。我刚才做了这个，它就像一个魅力。它会找到任意两个节点之间的最短路径，如果你稍微调整一下（当时我不得不调整我在网上找到的内容），它会告诉你要遵循的 nodes/path 是什么。但是我错过了绘画技巧
一些实现版本HERE
我猜你想要代表你的 3d 世界是 space 中可访问点的图表。忘掉树吧，它们只是图的特例。 然后研究 Dijkstra 算法。如果您需要提高效率，请查看 A*，这是对 Dijkstra 的改进。