Possible trajectories with time travel

Question

I'm trying to calculate a trajectory in the presence of time travel.

In the following picture, there is a character traveling toward the right in a straight line (like a billiard ball). If the character encounters another character, he will always turn right (as a rule). There is also a time portal at the bottom, that will teleport you to the exit portal, 2 steps back in the past.

In this scenario, there are 2 possible trajectories for the character:

1. He just goes straight and passes between the two portals. No problem.
2. At the start of the simulation, another character appears in the exit portal: it's you from the future! Both goes straight one step, meeting in the middle. Then, as per the rule on collisions, both turn right. The initial character enters the portal at step 2, thus closing the loop. The second character continues toward the left.

Some additional details:

• space is a discrete grid
• time is discrete too
• only directions allowed are up, down, right, left
• there is no player input or free will: characters just go straight and turn right on collisions.

My initial idea was to:

1. represent space and time as a mathematical graph,
2. add portals as simple edges between distant nodes on the graph,
3. find possible trajectories on the graph.

The spacetime block is represented as a 3D lattice graph, with edges labeled as type "X", "Y", and "Z" according to their direction. Time is represented by "Z" edges. Using this representation, time portals are simply additional edges between non-adjacent nodes. The algorithm would produce a list of edges (the order may not matter).

Rules for the algorithm:

1. Characters are going straight: if you enter in a node using an "X" edge (resp. "Y" edge), you need to exit using another "X" edge (resp. "Y" edge).
2. Collisions: If two characters enter a node from two different edges, they will turn right. I.e. they change edge type.

Is there a better algorithm to find automatically the second solution? Bonus point if your algorithm does not treat portal "exits" as something special, but just as a normal path through spacetime.

Answer 1

I'm sticking to the specific example (no user inputs, no collisions other than between characters, fixed direction movement, 1 portal, rewind exactly 2 turns to the past) to make the algorithm a bit more concrete and easier to parse.
To generalize this any further, the idea is the same, but it's just a bit more complex to implement and explain in words.

• Simulate every step, one at a time (T=1, T=2, ...). When dealing with multiple simulations (S1, S2, ...), make sure to generate the steps of all the simulations (i.e. T=2 for S1 and S2) before moving on to the next (i.e. T=3 for S1 and S2)
• For every new turn (i.e. T += 1), for every simulation in your list, generate two possible outcomes:
  • Someone came out of the portal
  • Someone didn't come out of the portal
  • Note If characters can come out of the portal at arbitrary directions, generate 5 simulations: one for each direction, and one where no character appeared.
• For every simulation where someone came out of the portal, set a "death clock". In precisely 2 turns, someone must go into the portal.
• Keep simulating every turn for all known simulations. Make sure to generate the steps of all the simulations (i.e. T=2 for S1 and S2) before moving on to the next (i.e. T=3 for S1 and S2)
• When a "death clocked" simulation fails to meet the requirements (e.g. at T=3 someone came out of the portal, but at T=5 no one went in), remove the simulation from the list.
• When you stop the simulation, all the simulations that are left are the valid ones, or at least have not yet been proven to be invalid.

How long do you need to run this simulation, i.e. what is the max T? That is very subjective. Your example now is very simple and it's easy to see that past a few turns, the game repeats at infinitam. But if you e.g. put the character in a bounded room with the ability to bounce off the walls, that limit possibly ceases to exist.

If you assume an unbounded plane and your "map" fits in a neat rectangle shape, then you can decide to end the simulation once all characters are outside of "the map" into the blank universe, since this means they will forever continue on without interaction with one another.

Other than that, it's a matter of running the simulation for a really long time until you come across a state you have seen before (both position and direction of all characters), at which point you know you've hit a cyclic loop (as the repeating state will generate the same repetition of events.

Answer 2

An algorithm that could work is:

1. Branch your game state N times, where N is the combination of all possible inputs by the user and the character appearing in the exit portal or not.
2. For each branch, determine the game state assuming the events leading to that branch were true
3. Repeat steps 1 and 2 m+1 times, where m is how far back in time the portal transports you
4. For each branch that assumes a character appears in the next time step, verify that the character enters the portal at time m+1. If not, delete that branch.
5. For each branch that assumes a character does not appear in the next time step, verify that the character does not enter the portal at time m+1. If they do, delete that branch.
6. Advance time and delete all branches that correspond to a user action that didn't happen.
7. Repeat

As a character that has traveled through the portal can interact with the other characters on the board, even with all the deleting of branches mentioned above, you will likely end up with multiple plausible game states at any point in time (i.e. a multiverse).