0

问题

我想写一个简单的1D RTS 游戏，并且有以下寻路问题：一维线很多，到处都是传送器，可以用来在线之间穿行，也可以在当前线内穿行。传送器是在线路之间旅行的唯一途径。什么算法或伪代码可以用来确定线 li1 上的位置 po1 到 li2 上的 po2 之间的最短路径？我们有一组传送器 T（每个都有一个 po 和 li），它们以零成本相互连接。

为什么不是 A* 或 Dijkstra 算法

这是因为我认为这些在 1D 中将是过度杀伤力。

澄清

  • 这听起来可能有点二维，但不是因为你只能在一条线上向左或向右移动。
  • 前往传送器是有成本的，但从一个传送器传送到另一个是没有成本的。看到这个 ascii 艺术：
    ...0....s..0
    ......0.x......

在这里，从 start s 到 target x 的最短路径是

  • 去正确的传送器
  • 向下传送一条线（仅在此图中；实际上飞机是无序的）
  • 并直接到达目标（最终成本 = 5）
4

3 回答 3

2

You can go from any teleporter from any other? In that case, there are only two possible ways: right and left from your starting position. Once you reach a teleporter, go the teleporter closest to the destination. Done. Ok, if you don't know which teleporter is closest to the destination, you might try them all on the same plane, but still.

于 2010-09-01T19:43:24.043 回答
0

由于向左或向右移动只能击中另一个传送点，因此您基本上可以认为每个传送点都连接到其左右两侧的传送点；所以每个传送点都连接到其他四个传送点。

这只是制作一个图，每个节点最多有四个边。因此，只需在内存中构建该图，然后使用 Dijkstra 算法解决您的问题（这并不过分，因为我们不再“处于”一维状态）。这将比@Jakob 建议的蛮力算法快得多。

于 2012-06-14T17:18:41.370 回答
0

我相信您可以通过将起点搜索与终点搜索相结合来改进 Jakob 的答案。

在您的第一步中，从起点开始并考虑 2 条搜索路径。一条向左走的路和一条向右走的路

每次迭代都会在两条路径上迈出一步，直到其中一条路径......

  1. ...你点击 x （搜索，这是最短路径）
  2. ...你击中了一个传送器

情况 (2) 在尚未击中传送器的路径上标记。

现在从您的终点 x 开始，也开始搜索 2 条路径。因此，左右移动，每次迭代 1 步。现在又有两种可能的结果：

  1. 您击中了标记的位置->最短的路径从标记的方向从起点开始，并在没有传送器的情况下到达终点。
  2. 你击中了一个传送器 -> 你的最短路径从步骤 (2) 中的开始到传送器，然后从步骤 (4) 中的传送器到终点 x。

这将在 2n 步中找到最短路径，其中 n 是该路径的长度。（因为你总是在看两个方向）。

于 2017-03-24T12:56:18.173 回答