UselessGameDev logo UselessGameDev title

Time Travel in Unity

Fri 19 January 2024 #UselessGameDev
This text is a written version of the video above, with future plans to incorporate graphics and figures for illustration.
As I'm working my way through the backlog of videos that were published before this website, I suggest reading the article alongside the video for a comprehensive experience.

A little while ago I got really interested in games that talk about rewinding time. Some use it in their stories, others as a game mechanic, some make clever use of it as a way to save player progression and allow coming back to any point in time rather than fixed checkpoints.

So I thought, what would it take to make a little game that allows the player to rewind time?

Transform Rewind

Creating TransformRecorder

The first thing we'd want to do is to record what happens during gameplay. And the most obvious thing to start with is the position of dynamic objects. So let's start by implementing a TransformRecorder, that would hold the information of Position and Rotation of a single object, for every frame of the game. This way we can stick it on any gameobject and record the transform properties.

public class TransformRecorder : MonoBehaviour
{   
    private List<Vector3> m_recordedPositions = new List<Vector3>();
    private List<Quaternion> m_recordedRotations = new List<Quaternion>();

    private void Update()
    {
        Record();
    }

    private void Record()
    {
        m_recordedRotations.Add(transform.rotation);
        m_recordedPositions.Add(transform.position);
    }

    public void RestoreFrame(int frame)
    {
        Debug.Assert(m_recordedPositions.Count > frame);
        transform.position = m_recordedPositions[frame];
        transform.rotation = m_recordedRotations[frame];
    }
}

I don’t need to record Scale in my case, so let's simply set up two lists, one for positions, one for rotations. Every frame we add the current position and rotation to their respective lists, so that we can come back to them in the future.

If doing this every frame seems like a bit of a waste, keep reading.

Playback Controller

Now to play these records back we need to start working on what we will call the PlaybackController: It will be a class that manages all of those TransformRecorders, and tells them to play a certain frame back.

It has two states: Playback, and recording.

Recording is the default, “free” state where we let the game follow its normal course and where recorders will record properties every frame.

Playback is when we wish to override the values of the transform properties, and force them to be in the same state as they were at an arbitrary frame. In which case, we don’t want to be recording.

public class PlaybackController : Singleton<PlaybackController>
{
    private bool m_isPlayback = false; // State of the playback.
    private int m_playbackFrame = 0; // Current frame being played back
    private int m_playbackSpeed = 0; // In [Game] Frames per [Unity] Frame

    public int Frame => m_playbackFrame;
    public bool IsPlayback => m_isPlayback;


    /// Pause recording
    public void Pause()
    {

    }

    /// Resume recording
    public void Resume()
    {

    }

    /// Asks all recorders to restore the properties of the current playback frame
    private void RestoreFrame()
    {
        foreach (var recorder in m_recorders)
        {
            recorder.RestoreFrame(m_playbackFrame);
        }
    }

    private void Update()
    {
        if (m_isPlayback)
        {
            m_playbackFrame = Mathf.Max(0, m_playbackFrame + m_playbackSpeed);
            RestoreFrame(); // Restore the recorded state at frame [m_playbackFrame]
        }
        else // We're recording, just keep track of time
        {
            m_playbackFrame++;
        }
    }
}

When in Playback state, every Unity frame, the PlaybackController asks all TransformRecorders, to restore the properties of their transform at the current frame being played back. If the player rewinds to a previous point in time, and then switches back to Recording mode, we need to erase all existing records beyond this point, as they will be re-written.

Generic Rewind

Factoring into a generic class

We can record the position of dynamic object, however when we stop the game while a dynamic object is launched into the air, and then resume the game, it looks like physical properties of the object, such as the momentum, aren’t restored. Which makes sense, beccause we need to record what's happening inside Rigidbody components also.

So we're going to make a RigidBodyRecorder to go along our TransformRecorder, but I think it's time to create a more generic way to record any Monobehaviour component, so we're going to make a generic Recorder<T> class to hold the common Recorder code.

public abstract class Recorder<T> : Recorder
{
    // ...

    protected virtual void Update()
    {
        Record();
    }

    protected abstract void Record();

    protected abstract bool DifferFromLast();
}

It doesn't look like much here because I removed all the housekeeping stuff like registering the recorder in the PlaybackController. But now the PlaybackController can store generic recorders and we can make the TransformRecorder inherit from that class as well. Much cleaner.

Rigidbody Recorder

Now we can start working on our RigidbodyRecorder. Similarly to the TransformRecorder, it needs to store two lists, one for velocity and one for angular velocity.

Recording is also fairly simple, And since the Rigidbody is in kinematic mode during playback, we’re only restoring momentum when exiting playback mode.

public class RigidbodyRecorder : Recorder<Rigidbody>
{
    private List<Vector3> m_recordedVelocities = new();
    private List<Vector3> m_recordedAngularVelocities = new();

    protected override void Record()
    {
        m_recordedVelocities.Add(Rigidbody.velocity);
        m_recordedAngularVelocities.Add(Rigidbody.angularVelocity);
    }

    public override void RestoreFrame(int frame)
    {
        // We don't need to restore the rigidbody state during a pause
        // We will set it to the right values once we Resume()
    }

    public override void Pause()
    {
        Rigidbody.isKinematic = true;
    }

    public override void Resume()
    {
        Rigidbody.isKinematic = false;

        Rigidbody.velocity = m_recordedVelocities[PlaybackController.Instance.Frame];
        Rigidbody.angularVelocity = m_recordedAngularVelocities[PlaybackController.Instance.Frame];
    }
}

Optimization

Now you know there's always a part where we talk optimization. I make a first draft that works but runs like garbage, and then we struggle to sort it out. In this case, storing all of this information, every frame, for every object, it comes at a cost.

A compute cost but also a cost in RAM. Each dynamic object saves a Position, Rotation, Velocity, and Angular Velocity. Supposing a Vector3 is worth 3 floats and a Quaternion is worth 4 floats, you then have (3 + 4 + 3 + 4) = 14 floats per object per frame. The size of a float in memory is 4 bytes. That’s 56 bytes per object, per frame, and that’s not even counting whatever room is consumed by the lists we store these in.

At this rate, we’re going towards an OutOfMemoryException fast. The thing is, we’re not even interacting with every object at every frame. And that’s, where we can improve things. Maybe we only need to record stuff that needs recording. If an object that never moves hasn’t changed its properties since the last frame, why bother recording the same values a second time, and a third time, and so on?

Recording only when needed - Structure

We need a new data structure to hold the records. Lists just ain't gonna cut it. So we can start by changing them into a custom records registry structure, which I called FrameRecordContainer<T>.

// Out with the old
private List<Vector3> m_recordedPositions = new ();
private List<Quaternion> m_recordedRotations = new ();

// In with the new
private FrameRecordContainer<Vector3> m_recordedPositions = new ();
private FrameRecordContainer<Quaternion> m_recordedRotations = new ();

It consists of a Dictionary, indexed by an Integer, this way I can store the record corresponding to each frame, with potential gaps between records.

We can then Get a frame Value, Set a frame Value, and purge all values after a certain frame.

Then we need to add a method in each Recorder to tell if the properties of the component being recorded differ from the last record. If they are identical, we can skip the redundant recording.

Recording only when needed - Reading

Now that we have gaps in our records, we have to adapt the Get method of the FrameRecordContainer: when asked to fetch the record for a certain frame, if the frame is missing, I used the naive way of finding, among the available frames, the highest frame that was below the frame we asked for, simply by going through all records backwards.

public T Get(int frame)
{
    if (m_records.ContainsKey(frame))
    {
        return m_records[frame];
    }

    // Awfully unoptimized
    var allKeys = m_records.Keys.ToList();
    for (int i = allKeys.Count - 1; i >= 0; i--)
    {
        if(allKeys[i] <= frame)
        {
            return m_records[allKeys[i]];
        }
    }
}

Tangent on lookup strategies

Let’s go on a little tangent about this lookup strategy: it’s not very effective. At first I figured it was good enough for the scope of the video, but still I decided to write a few test cases to measure the time it would take to fetch, say, 1000 random frames from a list with 10 000 elements, with various sized gaps.

This naive method iterates over every key of the dictionary, starting from the highest. In the worst case scenario, it iterates all the way back to the first record. It thus has an linear (O(n)) complexity.

I then tried to use LinQ’s FindLast() function, and unsurprisingly, it yielded 30% better time performance.

The next step was to convert the list of frames into an array. My thought was that, Arrays being notoriously more performant than Lists, it would work better. But for some reason once turned into an array the naive method became faster than Array.FindLast().

The results were there I was already boasting a 65% improvement in my algorithm and was ready to move on, when I thought about implementing a dichotomic search algorithm, or binary search. I wasn’t really expecting it to be all that different, despite the theoretical logarithmic (O(log(n))) complexity, I always thought it was more of a theoretical thing you learn in school and felt like it’s pretty rare to see them in the wild.

Boy was I wrong. The difference was so drastic, at first I thought my code was broken because it ran nearly instantaneous on my CPU compared to other methods.

"Naive" Method Array.FindLast Dichotomic
ItemsInList = 10 0 0.021 0.01
ItemsInList = 100 0.02 0.05 0.01
ItemsInList = 10 000 1.54 2.88 0.02
ItemsInList = 100 000 15.81 29.21 0.03

Total time for 10 000 lookups in each list, over 100 lists.
Timings in seconds. Lower is better.

It was so incredibly faster than the naive implementation. This last line isn't just theoretical too, over a long gaming session I can totally imagine an object like the player having a hundred thousand frames of position records. Though maybe in this case the game design should limit how far in the past you can rewind or something.

Flabbergasted but content, I figured I could turn the page on optimization: now that the system isn’t recording at all until I interact with objects, I know I have a scalable and efficient recording system, even if the game should still by design limit the total number of values that can be stored, by limiting the amount of dynamic objects on scene.

More Recorders

We now have an efficient way of storing and looking up data, and a generic Recorder template.

That’s great because we can progressively implement recorders for each component we will use in our game (e.g. AnimatorRecorder, MaterialRecorder, LightRecorder, AudioSourceRecorder...). For instance, the Animator component: without an AnimatorRecorder, by default, rewinding puts the character back to idle state, so I whipped up a very basic AnimatorRecorder. It records: - The name of the current state (in a FrameRecordContainer<string>) - and The normalized time inside the current state (in a FrameRecordContainer<float>)

It works well enough for my simple Animator controller in this test project, of course a proper AnimatorRecorder would need to be able to record the state of parameters, and handle complex situations like blend trees and stuff. But I think this is a good enough proof of concept for now.

Conclusion

So every component that has an effect over time should have its Recorder counterpart. Some components will be tedious or even impossible to record, but maybe they can be swapped for components that are easier to write a Recorder for, such as components that animate objects based on a function of Time. Check out the bonus video on the subject for Patreon supporters.

I really enjoy games about time manipulation, and it was interesting to try and make my own Time Rewind feature. Until next time, if you have played interesting games that center around Time and/or Time Travel, please let me know in the comments of the youtube video. Have a good one!

As always, get the full source code for this Unity project on the Patreon page.

Cool games with time travel / mechanics

Credits

Assets

Music