随时间移动的可能轨迹

Question

我试着在时间旅行的情况下计算一个轨迹。

在下面的图片中，有一个角色以一条直线向右行进(就像台球)。如果这个角色遇到了另一个角色，他总是会向右转(通常是这样)。还有一个时间门户在底部，它将你传送到出口门户，在过去的2步。

在这个场景中，字符有两个可能的轨迹：

1. 他一直往前走，穿过两个入口。没问题。
2. 在模拟开始时，退出门户中出现了另一个角色:来自未来的您！两人一步一步地走，在中间相遇。然后，按照碰撞规则，两者都向右转。初始字符在第2步进入门户，从而关闭循环。第二个字符继续向左。

其他一些细节：

• 空间是一个离散的网格
• 时间也是离散的
• 只有允许的方向是上、下、右、左
• 没有玩家的输入或自由意志:角色只是笔直地向前走，然后在碰撞中右转。

我最初的想法是：

1. 用数学图来表示空间和时间，
2. 将门户添加为图中远处节点之间的简单边，
3. 在图上找出可能的轨迹。

时空块表示为三维格图，并根据其方向标记为"X“、"Y”和"Z“类型的边缘。时间用"Z“边表示。使用这种表示方式，时间门户只是不相邻节点之间的附加边缘.该算法将生成一个边列表(顺序可能无关紧要)。

算法规则：

1. 字符是直线的:如果您使用"X“边沿输入节点(resp )。"Y“边)，需要使用另一个"X”边(resp )退出。"Y“边)。
2. 碰撞:如果两个字符从两个不同的边缘进入一个节点，它们将向右转。也就是说，它们改变了边缘类型。

是否有更好的算法自动找到第二个解？如果您的算法不将门户“退出”视为特殊的东西，而是将其视为穿越时空的正常路径，则额外积分。

Answer 1

我坚持这个具体的例子(没有用户输入，除了字符之间的冲突，固定的方向移动，一个门户，正好是两个转到过去)，使算法更具体一点，更易于解析。

为了进一步概括这一点，这个想法是一样的，但是用语言来实现和解释就更复杂了。

• 模拟每个步骤，每次一个步骤(T=1，T=2，.)。在处理多个模拟时( S1，S2，.)，确保在进入下一个模拟之前生成所有模拟的步骤(即T=2 for S1和S2) (即S1和S2的T=3 )。
• 对于每一个新的回合(即T += 1)，对于列表中的每一个模拟，生成两个可能的结果：
  • 有人从传送门出来
  • 有人没有从传送门出来
  • 注意，如果字符可以在任意方向从门户中出来，则生成5个模拟:每个方向一个，没有字符出现的一个。

• 每次有人从传送门出来时，都要设置一个“死亡时钟”。在两次转弯中，必须有人进入入口。
• 为所有已知的模拟继续模拟每一个回合。确保在进入下一个模拟之前生成所有模拟的步骤(即T=2表示S1和S2) (即用于S1和S2的T=3 )。
• 当“死亡时钟”模拟无法满足要求时(例如，在T=3，有人从门户中出来，但在T=5，没有人进入)，将模拟从列表中删除。
• 当您停止模拟时，剩下的所有模拟都是有效的，或者至少还没有被证明是无效的。

您需要多长时间才能运行此模拟，即最大T值是多少？这是非常主观的。你的例子现在很简单，很容易看到，过去几个回合，游戏重复在无穷大。但是，如果你把角色放在一个有能力从墙壁上弹跳的有界的房间里，这个限制可能就不再存在了。

如果您假设一个无界平面，并且您的“地图”符合一个整洁的矩形形状，那么您可以决定结束模拟，一旦所有字符都在“地图”之外进入空白的宇宙，因为这意味着他们将永远继续不相互作用。

除此之外，还需要运行很长一段时间的模拟，直到遇到以前所见过的状态(所有字符的位置和方向)，此时您知道您已经碰到了循环循环(因为重复的状态会产生相同的事件重复。

Answer 2

一种可行的算法是：

1. 将游戏状态分为N次，其中N是用户可能输入的所有输入和退出门户中出现的字符的组合。
2. 对于每个分支，确定游戏状态，假设导致该分支的事件为真。
3. 重复步骤1和步骤2 m+1次数，其中m是门户传输您的时间的距离。
4. 对于假设在下一时间步骤中出现字符的每个分支，请验证该字符是否在m+1时进入门户。如果没有，请删除该分支。
5. 对于假设某个字符不在下一时间步骤中出现的每个分支，请验证该字符没有在m+1时进入门户。如果出现，请删除该分支。
6. 提前时间并删除与未发生的用户操作相对应的所有分支。
7. 重复

由于通过门户传递的字符可以与板上的其他字符交互，即使删除了上面提到的所有分支，您可能在任何时间点(即多重宇宙)出现多个可信的游戏状态。