5

我正在尝试在有不同类型分叉的火车游戏中找到寻路的解决方案。我希望火车从一条铁轨到另一条铁轨，除了寻路之外，一切都已实现。

我需要一份铁轨清单，这样火车才能跟上。现在，问题是如何获取列表。

  • 我试过 A*，没有用，因为如果节点（轨道）已经被访问，它会停止搜索。这是一个问题，因为到达某个点的方法可能是通过最长的路线。
  • 尝试了洪水填充，这次如果已经访问过，它不会停止搜索，问题是我如何重建路径以及它如何选择它不能再次向后退。

问题是在某些情况下，火车必须多次通过铁路才能到达目的地。

有任何想法吗？

起点是 A，终点是 B。正如您所见，绿色路径是它应该行进的方式。黑圈是火车将不止一次踩的铁轨，在这种情况下是 2 次。

A->B

在此处输入图像描述

很明显，你需要从 2 黑色到 3 红色。你不能只选择 1black->2red->1red->3red。

4

2 回答 2

6

看着这张照片

路口

看来您的问题可以用有向图很好地表示。给图中的每个停靠点和每个路口两个节点，一个用于火车的每个方向。 Dijkstra 的算法在有向图上完美运行，所以一旦你遇到了这种形式的问题，剩下的就很容易了。

例如，在上图中，从 开始A，我们移动到junction 1。从那里，只有一个地方可以移动到，，junction 2所以会有一个来自A-->junction 1的箭头和一个来自junction 1-->的箭头junction 2。无论您做出哪种选择，您最终都会到达junction 1，但会朝另一个方向移动，因此我们从那里创建一个单独的节点。从那里，您可以选择前往A或B。

图形

请注意，我删除了其中一个J1，因为它是多余的（只有一个地方可以去）。

如果火车可以在像 那样的停靠点停止和转身A，我们可以通过两个方向的边将这两个节点连接起来，或者将它们组合成一个节点。

您可以给边缘权重以指定距离。

于 2013-10-01T13:36:14.607 回答
0

洪水填充确实应该做的事情（我在类似的情况下使用它） - 但你只需要仔细使用开关和段。

应该允许算法在不同方向上通过同一段，但不能在同一方向上。即每个段真的应该被视为两个独立的。

要重建路径，您应该在淹没它们时为段分配数字，以便每个到达的起点N-1都标记有N- 然后在向后移动时，应该跟踪段，以便数字稳步减少一。

这真的是一种 BFS。

于 2013-10-01T10:12:44.737 回答