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:
- He just goes straight and passes between the two portals. No problem.
- 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:
- represent space and time as a mathematical graph,
- add portals as simple edges between distant nodes on the graph,
- 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:
- 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).
- 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.