Waaaay back in 2010 I gave a talk at the GDC detailing exactly how rewind was implemented in Braid, including e.g. how does it reproduce all the particles perfectly without using tons of data. As far as I know in 14 years nobody has implemented an equivalent system in a game. There have definitely been more games that have rewind, but the implemented systems are usually pretty weak, technically speaking. Makes me wonder about the usefulness of giving these kinds of speeches!
Apropos, here is one of the last-to-be-recorded commentaries I am drafting out right now for Braid, Anniversary Edition (I have not even proofread it yet; you have been warned!): Braid's visuals are very, *very* dependent on particles. We use lots and lots and lots of particles. But all these particles need to rewind perfectly -- that was one of the basic principles I adopted early on. The naive way to rewind particles would just be to store in the rewind buffer the position, speed, current color, and so forth, of every single particle, for every single frame, just like we do for any other gameplay object; and then we'd just restore those properties when you go backward in time. But this would use a *huge* amount of memory; typically there are only a handful of gameplay objects on a level, but even in the original game there were thousands or tens of thousands of particles; storing all that data would eat almost all the memory available for rewind, which would affect gameplay very heavily; maybe you'd only be able to rewind for a few seconds, instead of the 15 to 45 minutes you could rewind in the original game. To get around this, particles in Braid work differently than they do in any other game I'm aware of. In pretty much every video game, particles are implemented as follows: you have some function creates particles each frame, picking random properties like size, color, speed, and so on; then you have another function that simulates all currently-existing particles forward for a short period of time: applying gravity, drag from the air, changing the color over time, deciding whether the particle has completed its lifespan and should disappear. This function then gets called every frame, and each time it computes the new state of the particle, this just overwrites the old state -- once you've rendered the frame, there is no reason to remember that old state any more. But under this scheme, particles can't go backward, because this simulator function isn't bidirectional -- basic rules of physics like air friction destroy information (once you've reached terminal velocity, it is not possible to deduce what speed you were going one step in the past) and once a particle has disappeared, you wouldn't know how to recreate it in its final state because all that information is just gone. *But*, the classic particle implementation provides some hints for what we can do to fix this problem. Classically, when the particle is created, we get its random size, color and so forth from a random number generator, and we were careful to seed that generator with a good value to ensure the output is fairly random-looking. When you seed a deterministic random number generator, this *determines* the sequence of numbers that you will get after ... that's what deterministic means! So if we were to seed the generator for *each particle*, based on some numeric identity of that particle, we could get reproducible results out of that spawner function, no matter when and how often we call it. Seeding for each particle introduces more demands on the random number generator -- low-quality generators can easily look less random if you seed them too often -- and I had this problem initially. Even higher-quality generators can produce artifacted results if you seed with low integers, for example, but there are some simple strategies to just mix the numbers up a little to generate a higher seed value that is still deterministic. In order to make this per-particle seeding work, we need an easy way to compute each particle's ID. Since, each frame, one thing we *do* know is what time it is, we build the system so that the time allows us to uniquely identify a particle. For this to work, each particle emitter holds a fixed number of particles only. For example, if an emitter emits one particle per second, and holds 10 particles, then each particle has a lifespan of 10 seconds. If the current game time is 35 seconds, then the 10 particles in the buffer will be particles number 26, 27, 28, and so on up to 35. These indices correspond to the spawn time of each particle, and thus thye uniquely identify each particle; if we render a frame at *36* seconds, we will have particle 27, 28, 29, and so on up to 36, and these will all be the same ones as the previous list, except we dropped 27 off the front and added 36 to the back. In reality all particles have fixed lifetimes, but if we want to give them the appearance of varible lifetimes, we just fade them out faster or slower, and just don't draw particles that have faded out all the way (but these particles still functionally exist!) So we can use these particle indices to seed the random number generator, and thereby reproduce the spawn state of any particle belonging to the emitter, consistently, at any time. But that's just the spawn state. How do we make particles evolve over time? In *principle* we could start by reconstructing the spawn state of each particle each frame, but then doing the classical particle thing and just running small simulation timesteps for each particle until we get them to the current time. But our particle buffer holds particles of a range of ages, and some of them might be very old, so each frame, we might be simulating waaaay too many timesteps, and our game could run very slow. You might start thinking, "Hey, when you are going forward in time normally, you just save the data from the previous frame and you only need to run one timestep. You only need to do complicated slow computation when going backward in time." Lots of computer science papers encourage this kind of strategy, but it is a bad way to think for interactive programs if you have any alternative. Because we want rewinding to be natural, as natural as walking (in fact walking *is* rewinding in world 4!) Either we can maintain a solid frame rate when rewinding, or we can't. If we can, then whatever we are doing for rewinding works for going forward too. If we can't maintain that solid frame rate when rewinding, well, that seriously damages the integrity of the game and we should work hard to change this. So I did not want to keep thinking about some incremental system that has these kinds of problems. I wanted a flat system that would run at the same frame rate always. You might think about combining many simulation timesteps into one, either by just simulating for a larger amount of time, or dropping down to a simplified function when the timestep is big. The problem here is, these would not result in perfect reproduction, which in places like World 4 could even result in large objectionable discontinuities (since you can walk left, from a frame that you just simulated a moment ago, to a frame where you were 5 minutes ago... these must line up seamlessly!) In general, video game physics gives you different results when you simulate things for bigger or smaller timesteps, and games that are carefully-crafted might employ a variety of techniques to deal with this problem. So if your particles are doing normal physics, you can't cut corners, you just have to do a lot of computation. However, the particles in Braid don't affect gameplay in any way; they're just cosmetic. So we really have a lot of freedom about what the particle simulation function is. Rather than implementing problematic physics terms (like air resistance) we can do simpler things that can be expressed in closed form (for example, a parameter like "this particle slows down by 1 meter per second every second" -- this has disadvantages since if you let the particle live long enough, it will slow down, stop and reverse direction, which is probably what you want; but, just don't put in those parameters!) Closed form means we can express the entire evolution of the particle in one short mathematical function, regardless of the amount of time we are simulating it for, and we always get the exact answer. Combined with the deterministically-seeded spawning, this gives us the ability to reproduce the state of any particle, at any time, without storing any per-particle data at all. This is how *most* of the particles work in Braid. Each particle is recreated from scratch and simulated to the current time, every frame, whether we are going forward or backward. The particles don't really exist at all between frames, as we don't keep their data at all.
@Jonathan_Blow I seem to remember it was cut quite short due to the GDC timeslot limitations as well, which suggests that the format also harmed the content.
@Jonathan_Blow Is there a recording of this talk? Sounds fascinating
@Jonathan_Blow Maybe it’s time for a different kind of game developer conference. Long technical sessions, one hall, one game at a time?
@Jonathan_Blow I’m so psyched for the commentary in Braid: Anniversary Edition.
@Jonathan_Blow Your talk committed the cardinal sin of not being surface level with easy to implement ideas.
Actually just saw it for the first time this week. It's the kind of lesson you apply to unrelated problems: If there's an approach that makes all the rest of your work easier, give it a real hard look before resorting to something easier, even if it seems intractable at first.