Time Travel - Rewinding Hexahedra, Part One

In February the second iteration of Hexahedra's rewind system, which allows players to smoothly move back through time to view the factory in the past, went live to beta testers (the game has since gone into open beta, get it on Steam and try out rewinding for yourself).


The Spray Painter and Heater in action, forwards and backwards.

I've already written about rewinding the particle systems, here I want to cover getting the factory state back into the past. The first version of the rewind system achieved this — players couldn't smoothly rewind through past steps, but could snap to the boundaries between steps and replay from there. Here's an old video from when I'd just reimplemented the timeline in the new UI:


The original, discrete behaviour of the timeline.

For this to work, I needed to be able to rebuild the factory in a past state, and then recreate the activity in the factory to lead it through the steps again.

1. Rebuilding past state

Because the factory runs in steps, there isn't much state to keep track of when you're at a step boundary — with a couple of exceptions, the devices are all at rest, cubes aren't rotating or having panels altered, and so on. The bits of data we need to track to be able to restore a state later are:

  • The state of each cube in the factory (including the ones in the teleport buffer)
  • Which command each workstation is about to execute
  • How many cubes we've shipped and the state of the cube sources.
  • For the late-triggering devices (the Laser and the Coloured Panel), whether they were triggered on the step that's just finished, since they won't be at rest at the end of the step if they were.
  • For Panel Storers, the details of the panels currently stored.

To support this, all the parts of the game that need to support rewinding (e.g. the PuzzleTargets that track how many cubes have been shipped) track their state for the most recent 500 steps. That's a fairly arbitrary limit that may change, I just didn't want the memory usage to be unbounded, and having a huge number of past steps makes it tricky to precisely drag the timeline handle.

Storing cube state isn't as tricky as it might look. Although each workstation has ownership of up to 8 cubes (one in the middle, one moving to an adjacent workstation, five arriving from different directions, and one being downloaded from the teleport buffer), any incoming cube will have been merged into the central cube by the time a step has ended. So, at a step boundary we only have to consider any cube in the middle and any cube travelling to another workstation; a cube takes two steps to move between workstations, at the start of the next step it'll switch to being an incoming cube that's managed by the receiving workstation.

To give you a feel for the system as a whole, here's the saving and retrieving of cube state:


// At the end of a step, only the central cube and an outgoing cube
// could be present. Take copies in case we want to restore them later.
public void PreserveCubeState() {
    HexState cubeState;
    HexState outgoingState;
    // We need to create a HexState to put in the list either way,
    // but the contents may not be terribly interesting.
    if (cube != null) {
        cubeState = new HexState(
            cube.GetUnderlyingHex(),
            cube.cubeId,
            cube.transform.localPosition,
            cube.GetFaceRotations());
    }
    else {
        cubeState = new HexState(null, 0, Vector3.zero, null);
    }
    if (outgoing != null) {
        outgoingState = new HexState(
            outgoing.GetUnderlyingHex(),
            outgoing.cubeId,
            outgoing.transform.localPosition,
            outgoing.GetFaceRotations());
    }
    else {
        outgoingState = new HexState(null, 0, Vector3.zero, null);
    }
    savedCubes.Add(cubeState);
    savedOutgoings.Add(outgoingState);
    savedIds.Add(new List(cubeIds));
    cubeIds.Clear();
    replayCubeIds.Clear();
    if (savedCubes.Count > Timeline.HISTORY_LIMIT) {
        savedCubes.RemoveAt(0);
        savedOutgoings.RemoveAt(0);
        savedIds.RemoveAt(0);
        oldestStateAvailable++;
    }
}

// Restore the saved cube state. This only ever happens on step boundaries,
// so we only have to worry about the central and outgoing cubes.
public void RestoreCubeState(int step) {
    if (step < oldestStateAvailable || step >= savedCubes.Count + oldestStateAvailable) {
        // Out of bounds, don't do anything
        return;
    }
    // Clear out the old versions,
    // including anything incoming (e.g. sourced cubes)
    if (cube != null) {
        Destroy(cube.gameObject);
        cube = null;
    }
    if (outgoing != null) {
        Destroy(outgoing.gameObject);
        outgoing = null;
    }
    for (int i = 0; i < incoming.Length; i++) {
        if (incoming[i] != null) {
            Destroy(incoming[i].gameObject);
            incoming[i] = null;
        }
    }
    if (downloading != null) {
        Destroy(downloading.gameObject);
        downloading = null;
    }
    if (uploading != null) {
        Destroy(uploading.gameObject);
        uploading = null;
    }
    if (failedPayload != null) {
        Destroy(failedPayload);
        failedPayload = null;
    }

    // Restore the saved versions
    HexState savedCube = savedCubes[step - oldestStateAvailable];
    HexState savedOutgoing = savedOutgoings[step - oldestStateAvailable];
    if (savedCube.hex != null) {
        cube = CreateCube(
            savedCube.hex,
            savedCube.localPosition,
            savedCube.faceRotations);
        cube.OverrideId(savedCube.id);
        if (VisualizationTracker.IsVisualizationVisible(savedCube.id)) {
            cube.ResumeVisualization();
        }
    }
    if (savedOutgoing.hex != null) {
        outgoing = CreateCube(
            savedOutgoing.hex,
            savedOutgoing.localPosition,
            savedOutgoing.faceRotations);
        outgoing.OverrideId(savedOutgoing.id);
        if (VisualizationTracker.IsVisualizationVisible(savedOutgoing.id)) {
            outgoing.ResumeVisualization();
        }
    }
    RestoreCubeIds(step);
}

public void RestoreCubeIds(int step) {
    // We need the saved IDs recorded one step later than requested.
    // When we record the state at the end of step N, we use it when
    // we want to replay step N+1.
    // However, when replaying step N+1, we need the IDs generated
    // during N+1 and saved at the end of N+1.
    // If we're replaying the last step, we just won't have saved anything yet.
    List savedIdList;
    if (step - oldestStateAvailable + 1 >= savedIds.Count) {
        savedIdList = new List();
    }
    else {
        savedIdList = savedIds[step - oldestStateAvailable + 1];
    }
    replayCubeIds = new List(savedIdList);
    cubeIds.Clear();
}


As well as storing all the functionally important information about each cube — the material, colour, and decorations of each panel, any damage to the cube, and any payload — we also want to store the orientation of each panel. When restoring a cube's state we want to be able to remember whether, say, the planks on a wooden panel were horizontal or vertical, otherwise the cube might appear to be rotating when restoring to a past state even if it's just sitting there.

Restoring cubes is simply a case of throwing away the old GameObjects and creating new ones with their attached scripts in the correct state. The devices don't get recreated, so we just need to make sure they're in the correct end-of-step state. We already have an EndStep method that gets called when the factory is running and hits the end of a step to make sure everything's in the correct state — making sure that any lerps are complete, VFX has been turned off, etc — and we use that to get each device into its dormant state. There's then a bit of extra work for the Laser and Coloured Panel in case they need to be in their just-triggered state, and for the Panel Storer so it's holding the correct contents.

2. Replaying past activity

Once we've got the factory into a prior state, we then need to be able to replay the activity in the factory from that point. Although I didn't plan it that way, it turns out that Hexahedra's code structure makes this pretty straightforward.

A detailed look at the code architecture.

If you want the full lowdown, the video goes into a fair bit of detail, but briefly, the core simulation part of the game creates a list of events for each step that Unity can use to visually show what's going on. So I don't need to rewind that core section, I can instead just store the event list for each previous step, and feed those to the rest of the code when I'm replaying. If I catch up to the present and need to run new steps, I can then get the core simulation to advance and give me fresh data.

Here's the relevant bit of Update from UPuzzle, which is the top of the code hierarchy on the Unity side, plus the top-level preservation of state.


public void Update() {
    ...
    ...
    if (newFactoryStep) {
        // Finish off the old step
        factory.EndStep();
        hexSourceContainer.EndStep();
        puzzleTargetContainer.EndStep();
        bufferContentsContainer.EndStep();
        // Advance the step pointer.
        // If we don't have any historical data for that step
        // (i.e. we're not mid-replay), get more from HexSim.
        stepPointer++;
        if (stepPointer >= historicEvents.Count + oldestStepAvailable) {
            // Get, and preserve, new data
            finalStep = !puzzle.AdvanceState();
            PreserveState();
        }
        else {
            finalStep = (finalStepPointer == stepPointer);
            factory.RestoreCubeIds(stepPointer);
        }
        // Either way, if we're about to stop, grab the stop event
        if (finalStep) {
            stopEvent = puzzle.stopEvent;
        }
        // If the player is about to fail the level, get the UI to reflect this
        if (AboutToFail()) {
            PrepareForFailure();
            SpeedLimiter.ZeroAccumulatedTime();
        }
        // Update the timeline UI
        timeline.Advance(oldestStepAvailable, historicEvents.Count - 1 + oldestStepAvailable, stepPointer);
        // Start the new step.
        DistributeEvents();
        if (runOneStep && !prerunStep) {
            runOneStep = false;
            speedManager.Pause();
            // Make sure we stop at exactly the step boundary.
            SpeedLimiter.ZeroAccumulatedTime();
        }
        prerunStep = false;
    }
}


private void PreserveState() {
    if (finalStep) {
        finalStepPointer = stepPointer;
    }
    historicEvents.Add(puzzle.latestEvents);
    // If necessary, drop the oldest data.
    if (historicEvents.Count > Timeline.HISTORY_LIMIT) {
        historicEvents.RemoveAt(0);
        oldestStepAvailable++;
    }
    factory.PreserveState();
    bufferContentsContainer.PreserveState();
    puzzleTargetContainer.PreserveState();
    hexSourceContainer.PreserveState();
}


3. UI

The only other thing left to do was to give the user a way to move the factory back and forth through time. In the second video at the top of this post you can see the curved timeline and the draggable handle, with a readout of the step we're looking at and the timeline handle snapping to step boundaries.

In cases where there weren't many steps stored dragging the handle might not seem to do anything until the player had dragged quite a long way, so there was also a semi-transparent "ghost" version of the drag handle that would track the mouse position, with the solid version snapping to the closest boundary. Once there were enough steps stored, however, the handle would move relatively quickly and the ghost wasn't necessary (and just cluttered the view a bit) — this is the behaviour in the video above.

When the player resumes playback from some time in the past, we then need to do a bit of basic trigonometry to work out where the timeline pointer should be as it moves around the curve. With that in place, we're pretty much there bar the debugging.

Drawbacks

This original rewind system did allow the player to go back in time and rewatch the action to find bugs in solutions, but because the rewind itself operated in discrete steps, there were some downsides. While you were dragging the timeline handle around, it was hard to get a feel for things like cube rotations because the cubes would just jump 90 degrees at once. With the more recent smooth rewind players can drag time back and forth within each step, making it much easier to visualize what's going on while maintaining extremely fine-grained control of playback. I launched the initial version in the closed beta in order to get it into players' hands, gather feedback, and see if any bug reports came in, but I was very keen to get to work on the smooth version. I'll write a separate post about that stage of the work.

Update: here it is!

Hexahedra is now live — head to the store page to grab a copy or try the demo.

Tagged in: c#, unity, rewind, hexahedra