问题
我想写一个简单的 1D RTS 游戏 并且遇到以下寻路问题: 有很多一维线，到处都是传送器，可以用来在线之间穿行，也可以在当前线内穿行。传送器是在线路之间移动的唯一方式。可以使用什么算法或伪代码来确定行 li1 上的位置 po1 到 li2 上的 po2 之间的最短路径？我们有一组传送器 T(每个传送器都有一个 po 和 li)，它们以零成本相互连接。
为什么不是 A* 或 Dijkstra 算法
这是因为我认为这些在 1D 中是一种矫枉过正。
澄清
- 这听起来可能有点二维，但事实并非如此，因为您只能在一条线上向左或向右移动。
- 前往传送器需要花费成本，但从一个传送器传送到另一个传送器是免费的。 请参阅此 ascii 艺术:
...0....s..0
......0.x...
这里，从起点s到目标x的最短路径是
- 去正确的传送点
- 向下传送一行(仅在此图中；实际上平面是无序的)
- 然后直接前往目标(最终成本 = 5)
最佳答案
你可以从任何其他传送器离开吗？在这种情况下，只有两种可能的方式:从您的起始位置向右和向左。到达传送器后，前往离目的地最近的传送器。完毕。好的，如果您不知道哪个传送器离目的地最近，您可以在同一平面上尝试它们，但仍然如此。
关于algorithm - 使用 'teleporters' 进行一维寻路，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3621282/