0

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.

9
  • 1
    Is the movement field a grid or real space? Are movement directions limited or can character go 360degree?
    – Euphoric
    May 4 at 13:43
  • I can tell that you can brute-force it with breadth-first graph search with new states being created by "players" appearing at each exit at every point in time and then those states being deleted when there isn't player at entrance to "pair" it with his appearance. But my gut feeling is that will result in huge state explosion even after few steps.
    – Euphoric
    May 4 at 13:57
  • @Euphoric For the moment it's a discrete grid. Allowed directions are only cardinal: up, down, right, left.
    – cdupont
    May 4 at 14:08
  • @Euphoric yes that is right. Simulating players "exiting" portals can work, however it treats portals "exits" as something special. However, in the spacetime block, time portals are just odd links, linking two distant points in space and in time. Normal traveling uses normal links between two adjacent points, "time traveling" uses those odd links. I was curious to find an algorithm that doesn't treat those odd links as special.
    – cdupont
    May 4 at 14:18
  • 1
    I took this to meta to get some second opinions.
    – Doc Brown
    May 7 at 13:34
4

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.

5
  • Thanks a lot, I think that answers well the question (together with Bart van Ingen answer).
    – cdupont
    May 5 at 8:32
  • I think it could be worth to mention a simple, but probably effective optimization: if a portal is not in reach of any character within two turns, it is not necessary to simulate the cases where someone will come out of that portal.
    – Doc Brown
    May 6 at 11:19
  • @DocBrown: Assuming collisions mean that two characters occupy the same space for a single turn, I agree. But if they don't, i.e. the next turn already accounts for the first post-collision movement, then it's possible to have a long chain of collisions that chains into the portal. T-t-t-trick shot!
    – Flater
    May 6 at 11:29
  • Moreover, If it's possible to get from an exit portal to its entrance portal in fewer time steps than it takes you back, you could also take the "loop" multiple times to go as far back as desired. Unless of course something gets in your way, which is the basis of ~every time travel plot ever written
    – trentcl
    May 10 at 14:19
  • There is the "obvious" optimization of only creating splits which are possible to satisfy. If nobody can reach the entry-portal in 2 steps, nobody can leave the exit-portal now. May 17 at 16:59
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).

1
  • Thanks. I was wondering if there was a non-brute force solution?
    – cdupont
    May 4 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.