列车寻路算法

Question

我正试图找到一种解决方案,用于在火车游戏中进行寻路,其中存在不同类型的分叉.我希望火车从一个铁路到另一个铁路,除路径寻找外,一切都已实施.

我需要得到一个铁路列表,以便火车可以跟随.现在,问题是我如何获得列表.

• 我已经尝试了A*,因为它停止搜索节点(轨道)是否已经访问过,所以没有用.这是一个问题,因为可能达到某一点的方法是通过最长的路线.
• 尝试了洪水填充,这一次使它不停止搜索是否已经访问过,问题是我如何重建路径以及如何选择它不能再次倒退.

问题在于,有些情况下列车必须多次通过铁路才能到达目的地.

有任何想法吗？

起点是A,结束B.正如您所看到的那样,绿色路径应该是它应该行进的方式.黑色圆圈是火车将不止一次步进的轨道,在这种情况下是2次.

显然,你需要来自2黑色才能达到3红色.你不能只是去1black-> 2red-> 1red-> 3red.

Answer 1

看着这张照片

看起来您的问题可以通过有向图表示.给每个站点和每个交叉点两个节点,每个节点对应列车的每个方向. Dijkstra的算法在有向图上非常有效,所以一旦你遇到问题,其余的就很容易了.

例如,在上图中,从A我们开始,我们移动到junction 1.从那里,只有一个地方可以搬到junction 2,所以有一个箭头来自A- > junction 1和箭头来自junction 1- > junction 2.无论你做出哪种选择,你最终都会junction 1向另一个方向移动,所以我们从那里创建一个单独的节点.从那里,你可以选择去A或B.

请注意,我删除了其中一个J1,因为它是多余的(只有一个地方可去).

如果火车可以在停靠点停下来转弯A,我们可以通过两个方向的边连接这两个节点,或者只是将它们组合成一个节点.

您可以指定边距权重以指定距离.