Friday, 1 January 2010

Unraveling Braid

I can't stop thinking about Braid; everything about it - gameplay design, art, sound - was executed nearly perfectly. And each of those aspects brought something new and interesting to the game. Nevertheless, being a game programmer, it's the code that I'm interested in here, and I can't help musing about how I would implement some of Braid's unique mechanics.

If you haven't played Braid yet but were kind of thinking about it, then stop reading this and go play it, right now! I don't want to deprive anyone of the smallest part of the wonder at exploring Braid's universe for the first time. If you haven't played Braid and don't intend to, then perhaps I can convince you to try it :)

Let me begin by making it clear that I don't know anything about the actual implementation of Braid; I haven't spoken to the developer and I haven't looked at the level editor. But how it's actually implemented is almost beside the point; this is a collection of more general thoughts inspired by Braid.

One of the first things to impress me about Braid was the consistency of its design. In essence, it's a platonic 2D platformer plus just 5 unusual mechanics:
1. The ability to rewind time for some objects in the world.
2. The idea of binding time to one of the dimensions of 2D space.
3. The idea of branching, but interacting, timelines.
4. The ability to distort time in one local region of 2D space.
5. The idea of making objects in some levels run backwards in time.

The ability to selectively rewind time (for some, but not all objects), and the ability to distort time (for some, but not all regions) provides ways for the player to affect the synchronisation of objects in the world to solve problems.
The idea of binding time to a spatial dimension in some levels, such that horizontal movement advances or rewinds time, ingeniously provides both an obstacle and a tool for overcoming other obstacles.
The idea of branching but interacting "shadow" timelines, such that the player can be in multiple places at once, provides a mind-bending tool for solving impossible puzzles.
The idea of running time backwards in some levels turns everything neatly on its head, makes the player gasp in delight when they realise some of the gameplay implications, and provides the most astoundingly clever ending to a game that I've ever had the pleasure to experience.

The player's immense satisfaction in each level comes from painstakingly learning how each new mechanic works, and then synthesising ideas to solve a problem. This game could only work by strictly adhering to the fundamental design mechanics. This is both impressive and requisite: it is impressive that the game never resorts to any special cases, but then, if it did, it would destroy the player's ability to derive satisfaction from their own cleverness.
And because the design never calls for any special cases, I imagine that the code must have been a joy to craft. That is what I am chiefly interested in here, for the observation that Braid adheres to a limited set of mechanics belies the subtle complexity of those mechanics, and therefore their implementation.

What follows is merely my guesswork.

1. Rewinding time.

At any point the player can rewind time by holding down a button, and release it at the point in time at which they wish to resume control and try again. That means what happened in the past needs to be buffered somehow.

Bad Idea Note: Simply buffering the player's inputs would not work, because although all games are deterministic, they are also convergent: given the complete state of the universe (including inputs), there will be exactly one proceeding state, but there may be multiple possible preceeding states (did the player get to their current position by running or falling?). This property of deterministic convergence is employed to mind-bending effect by mechanic #5.

A naive approach might be to simply record the position and state of each object at each frame. But besides being memory intensive, this would make interactions with other objects - which might be moving through time in a different direction or speed - awkward.
I think it would be better that the state of each object, including the player, be recorded at a slightly more abstract level - say, the start/endpoint and velocity of a jump. Each state would be coded to be able to play either forwards or backwards at a given speed, procedurally. This would allow objects to interact dynamically with others when slowed down or going backwards, and not be rigidly bound to what was recorded. This implementation would come in handy for mechanic #2, binding time to a spatial dimension, and #5, running some levels backwards in time.

The abstracted-procedural-state approach would allow every object in the game to have its own individual "timeline". For most objects their timelines would coincidentally match up - they would progress forwards and be rewound backwards synchronously - until their timeline is affected by another mechanic...

2. Binding time to a spatial dimension.

Using the above implementation, this would be fairly simple - control all affected objects' timelines based on the player's current velocity.

Bad Idea Note: It might be more intuitive to think of this mechanic as the player's horizontal position scrubbing backwards and forwards through time, like the progress bar on a media player. And it might therefore be natural to think of using the player's position, not velocity, to control object states. Unlike a prerecorded movie in a media player, however, the objects will not be in the same state on every occasion a given time is revisited. It's impossible to jump to a given time, you have to advance frame-by-frame, state-by-state, procedurally, so that all the interactions can play out dynamically.
That means using the abstracted-procedural-state approach with individual object timelines controlled by player velocity, even if all of the individual timelines happen to be controlled synchronously.

3. Branching but interacting timelines.

This idea, although the most mind-bending for the player to come to grips with, would actually be one of the easiest to implement. Assuming that we record what happened in the past using the abstracted-procedural-state approach, the implementation of this mechanic would be simple.
Each object has a "shadow" object, which is actually an entirely independent object. Shadow objects only interact with other shadow objects and purple objects, which bind together both their shadow and real selves. When time is rewound and control is resumed, most objects and their shadows resume what they were doing, following the same rules. Because it's a deterministic world, the objects and shadows stay in sync, unless something disrupts them by interacting with one but not the other.
However, the player is not deterministic, and can choose to take different actions when control is resumed. The player's shadow repeats whatever the player just rewound.
The player's shadow would be controlled by the recorded states: while rewinding time, instead of discarding the states that we rewind past, they would be kept to use as a control buffer for the shadow. When the recorded states run out, the shadow just slumps, uncontrolled.

4. Distorting time in localised regions of space.

This idea is nice and simple for both the player and the programmer. If each object has an individual timeline, then the speed of that timeline could be set to be proportional to the distance of the object from the distortion.

5. Run time backwards.

This idea is the most fascinating to play, and possibly the most difficult to implement, of them all - due to the deterministic-but-convergent property of games.

First, let's get the easy stuff out of the way. Using the abstracted-procedural-state approach, we would already have coded all the interactions for objects moving backwards through time - for example, a monster going from dead to alive when the player jumps on its head, rather than the other way around. So the basic interactions with objects are already taken care of.

Bad Idea Note: You might initially think that simply running time backwards at a fixed speed for all objects would be easy, given that we already have solutions for selective rewinding, variable timeline speeds, etc. The important difference is that in those cases, the past is known and it's just a matter of replaying it somehow - time can only be rewound backwards for as long as the player has been playing, to the start of the level. In this case, however, time runs backwards from the beginning of the level, and we haven't had a chance to record where each object was. Or will be. Or something. Arrgh!

From the player's perspective, this mechanic is amazing because, when time runs forwards, we can intuitively reconstruct where an object is likely to have come from by observing its current state in the environment. When time runs backwards, that reconstruction becomes a prediction. In a deterministic universe running forwards, given perfect knowledge, we can make perfect predictions - we know exactly where the monster will go. But in a convergent universe running backwards, even with perfect knowledge, we can't make perfect predictions - we can't know whether the monster will stay on the ground or "fall up" to a higher platform. It's amazing when, as the player, you realise that an object's "past" can be affected by actions in the "future", like blocking off a route which makes it impossible for a monster to have "come" from that route. It's like the weird world of quantum mechanics, in which a particle's past is determined by observations made in the future.

The difficulty is that deterministic-but-convergent property. All of the other mechanics could be implemented in a philosophically plausible manner, but I can't see any good way to do this mechanic except by "cheating".

In the other mechanics, the behaviour/AI of an object running backwards along its individual timeline is trivial - just reconstruct it from the recorded abstracted state information. In this mechanic though, we need some actual decision-making logic while running backwards. Take the example of a monster walking backwards along the ground, just about to go underneath a higher platform. Should it continue walking backwards along the ground, or should it "fall up" to the higher platform. What happened in its "past"?

Bad Idea Note: You might think of taking further inspiration from quantum mechanics and assigning a probability to each past, which is fine from a design point of view, but would be practically impossible from an algorithmic point of view. You would need to identify all the places at which the convergence tree can branch (perhaps this could be marked up in data). Then you would need an algorithm for traversing the convergence tree and pruning off the branches that come from impossible starting conditions. Then you would randomly select between the remaining branches. The problem would be identifying the impossible starting conditions - how far back do you branch before determining that the object is stuck in a loop with no start, and how do you account for the interactions with every possible branch of every other object? Combinatorial explosion!

The more sensible approach might be to have a deterministic "default" behaviour like "always walk", and to "cheat" by having the designer specify when the object should deviate from that default behaviour - for example, trigger a "fall up here" marker when the player blocks the ground route (meaning that the monster could not possibly have taken the ground route).
There are few levels that use this mechanic, and the places where there is ambiguity are even fewer, so this scripted approach would probably be manageable.

From a gameplay perspective this approach might also be desirable - having a deterministic default behaviour for each object results in predictability which is probably reassuring to the player, even though, philosophically, the player has no reason to expect the behaviour to be predictable.

So, that's all the main mechanics seemingly neatly implemented. I'm very impressed by how you would be able to get such varied gameplay from relatively simple, but far from obvious, rules.
Damn, I wish I'd made this game...

No comments: