The Implementation of Rewind in Braid

okay we'll start whatever so this talk is implementation of rewinding braid it is a technical talk in case you're thinking some kind of design implementation or something that's not it when I submitted this talk I was like oh sure it's pretty simple I'll be able to talk about everything in 25 minutes doesn't seem to be how it is there's a lot of little details I won't be able to get into may go a little bit over time whatever feel free to ask me by email or something anyway who how many people in the room have not played the game all right that's enough okay cool so I'll show you really quickly what it's like that's pretty simple in some ways it's a little 2d platformer shipped on the Xbox 360 ps3 and pc and mac you run around you know you can jump as you always can you can go into these little worlds where things happen [Music] and yo a world this sort of a scrolling area with parallax and all that it can be from one screen to you know eight or ten screens large there's all these objects that move you know you can get cue and you can rewind like this and the rewind is unlimited right it's not a resource and so oh hello all right and that was the first of the design goals that I had was I wanted to find out what happens when you design a game where rewind is not a resource and there's not a traditional sort of death challenge you know gating the game I knew that I wanted to be able to run on consoles because I wanted to maybe sell some copies I knew that I was going to be the only programmer on the game that ended up not quite being true I got a little help at the very end but I really wanted to limit the amount of programming work that I would do because I was also the designer and and you know biz guy and all that stuff so you know if you spend all your time programming you won't have a game because those other elements are missing right now this is a platformer and I knew it was going to involve puzzles okay so when you start talking about rewind and puzzles you start thinking you know I don't want my puzzles to be exploitable right like a typical kind of puzzle might be you can't get between point a and point B in less than a certain amount of time unless you do something special right but like maybe if you're we rewind doesn't put you back exactly where you were you could like rewind you could go forward two frames and rewind one frame and stuff and get little extra centimeters and eventually exploit the puzzle or you could like somehow jump over a hurdle that you wouldn't have been able to jump over normally if you can mess with your momentum so I wanted to ensure that whatever time manipulation is in the game it's not exploitable and I wanted the game to run at 60 frames per second which we usually think of as a CPU kind of issue but when you start talking about remembering things as you need to do for rewind or recording videos or something as you raise your frame rate the amount of data that you have to deal with goes up right but I felt that this was important for a fluid solid platforming experience right so now if you're a programmer has been around for a while I hope these don't get cut off too bad we'll see anyway there are some ways that you might think of implement rewind and they're generally grounded in optimization style thinking like what's the best way to implement rewind right one thing that we often do in game engines in order to repro and fix bugs that can be used for this kind of system is to record all the user input you know you kind of hook the input function in the engine and you record all the button presses that happen and then you can run it again in playback mode and as long as you're all your functions in your game are deterministic then you'll get exactly the same result as you playback the events I've done that a few times I hate it it's a pain in my ass all the time because things break you know they're not robust across revisions like a recording that you make once is not going to work on a different revision you get revisions confused but even worse it places constraints on other parts of the code that live for the duration of the thing so I didn't really explore this option until later in development but it's lucky that I didn't because if I had gone this way it would have ended up designing a very different game because the gameplay depends on having functionality that this would not been able and I'll go into that later another wacky idea you might think of is like reversible simulation right we usually have an engine with entities that have a tick function and it's hit function knows how to bring them forward in time what if that could also bring them backward in time inside that function right well is the question of exactly how to do that you know we're used to just having discontinuous state changes in objects you know if you have differentiable functions that's easy to reverse you know people who do physics know that but if things if you have discontinuities you have to start recording weird data and how do you do that and and you know gameplay code is pretty complicated and it's a big source of bugs already and then if you make it twice as complicated it seems like a bad idea and then if you can only simulate in Reverse how do you get random access to your time stream right if you want to go back to 10,000 frames ago how do you do that without simulating 10,000 frames backwards right so it's not necessarily seeming like a good idea to do it that way okay well what started seeming like the the best option to me was just to record the full state of the world because you know that's robust you know you can reproduce that and that's going to be a lot of data so maybe you drop frames so maybe you record every hundredth frame and in the frames in between that you interpolate between the points but that's not really a good idea because it's it's not exact right you're interpolated frame has a very little probability of being what the actual frame was that you threw away right so there are quality questions about that and again that question of how to avoid exploits comes up so I had to kind of suppress my my impulse right so us guys wanting to be star programmers you know our impulses man I'm gonna do something that's awesome and fast and as a tiny RAM footprint it's going to be better than anything anyone in history has ever done it's going to just be awesome right but my attitude at the time was different than that it was and it's I'm lucky that I had this attitude because just what allowed me to actually finish and ship the game it's that you know I've been doing all this 3d graphics high-tech stuff for years we kill ourselves to get 10% or 5% performance differences we make massively complicated systems to get that performance boost and it breaks all the time you know like games crash and and they just go slowly when they're supposed to go fast and since I'm going to be have to be designing this game and I actually want to ship this game so that my independent developer career will succeed I'm going to do the most robust thing possible right so my focus was on robust enabled me to build the game right and so what is the most robust thing it's not any of these things I talked about because those were concocted with the mindset of being tricky right and tricky means complicated so usually and so what I came up with is a variant of that third idea but dead simple just record all the world state every frame always don't drop any frames just record everything and then figure out a way to compress it and most people would not approach this problem this way but I believe it was by far the best way to approach it so how do you record game state well you've got a world which has got some objects in it and each object in the world you know has a bunch of properties this is pretty Universal games work this way so this is a shot of the editor and the upper right there's sort of this panel for this entity that I had highlighted and you know it's got a bunch of member variables and there's types to them so some of them are integers some of them are vectors some of them are strings whatever right you have to have this somehow in your game if you're going to save the world file so that you can you know edit it and load it in and play it right now you could think of other ways to store things like I could just take the entities in my world and clone them and have a little side world off to the side and just do that every time I want to record something but you know live entities in a game engine tend to be individually allocated right and if you're playing a lot with memory that way that creates fragmentation right you allocate a bunch of memory you freeze something out of the middle there's a hole that you may or may not be able to use and that's bad especially if you're running on a console right and the second point off the bottom of the slide is that things that are serialized are easily compressible like if you want to do entropy coding on them or something like that it's a stream of bytes right you can feed a stream of bytes into any generic compressor and if you were to think about like some kind of live energy scheme if you were going to compress that you have to eventually turn it into a stream of bytes so yeah you just serialize so the you know here's some list of properties from some very basic object and there's a bunch of these objects in a level you know how many I don't actually remember but there's a bunch and if you look at the size of the levels on disk right there between 25k bytes and 175 k bytes and that's great that's a pretty good size for levels on disk but when you're recording 60 of those per second it adds up to a lot of memory really fast so you start doing the second part of what I said which is figure out a way to compress it and that's basically what the rest of the talk from here on is so the most obvious thing and the first thing people will think of when they have programming experiences most of these entities aren't changing at all they're constant we factor them out we only record the things that change right and of course this is a massive win so in braid there's a couple sets of things that are constant on the left is collision geometry which you don't ever see in the game but it determines where you can go and where you can't go and on the right is you know cosmetic stuff it's layout that usually matches up to collision geometry and just makes the level look nice right those don't change so just keep them in a separate array after you load the level and any time you want to seek through the time line to a particular time then you just copy these there's one copy of these for all the frames right so you just make a copy of those and then you go look into the data that you recorded you extract the changing entities right the only ones that you actually needed to save and then you mix them in and you have your final state now this third screen is particles in braid the look of raid depends very heavily on particles there's a bunch of particles everywhere they fade in and out and provide a very sort of shifting feeling to the graphics and if you actually were to record these in a naive way it's a gigantic amount of data because there's thousands tens of thousands of particles on a level you need to record position color and probably about 17 other properties for each one it's gigantic right so what you do is you make the particle entities constant right and how do you do that well you make a function that is a sort of closed form kind of thing where you feed it in a seed from a random number generator and you feed in a bunch of properties describing how the particles should look like what texture is it and one of the UV coordinates and what color does it start at and what color does it end right all the usual particle system stuff but instead of those properties evolving over time they're fixed and then when it comes time to generate the particles you you kind of you know run the equations of physics and you know interpolate all the colors and all that in closed form and just spit out a particle basically from nothing every frame now when you do this it's slower than the way particles usually happen because usually we're tracing particles through space and just modifying each property a little bit in this case you have to regenerate a bunch of random numbers every single for every particle every frame and that's slower and sort of the caveat to this is that I actually had to optimize the particle inner loop relatively heavily compared to the rest of the game in order to get it to run well on consoles yeah the current constables there's no problem on PCs because of out of order processing anyway um well how I wish I could really see more of the slides but okay the so you've got this scheme where you're taking all the state of the game and or all the changing state right so it was a massive win to factor out the constant objects but it's still way too big right we're talking about massive amounts of data so what do you do next you diff individual fields of an entity so that you don't have to save the whole entity right if you have a continuous gameplay experience then chances are that whatever the objects are in the world at frame n plus-1 they're a lot like where they were at frame n with some minor differences right so Wow what just happened I don't okay oh thanks you're trying to fix it okay um now the sides are gone if we can keep trying to fix it that would be good though so so just diagram down here right it's sort of a diagram of what happens in this scheme when we try to seek to a certain frame in the timeline so we want to find where that red dot is right and so we've got these larger sort of yellowish blocks those are the base frames which behave exactly like I explained before they contain data for all the entities in the world so if you wanted to seek exactly to that time that point in a time line you only decode what's in that block and you're done right for anything in between those are smaller blocks that only contained ifs so if I want to seek to wear that red spot is I have to decode the diffs I have to decode what's in the base frame and then I have to apply the diffs to the base frame right now when I say diffs here I'm not actually doing Delta encoding as people do in compression a lot like in Delta encoding if the value used to be a hundred and now it's 100 point five you store like plus 0.5 and it's usually smaller right but I didn't do that because I didn't want to worry about rounding accumulation of error any of that I want to be very very clean so I just or 100.5 or whatever right and this again is another massive wind you know in grade I put base frames every two seconds I believe in the final builds so that's every 120 frames and so you know this gets rid of about you know probably 95% of the memory usage or something like that but it's not enough or at least Wow okay um how about if I do this there we go okay so is it shift f5 to resume from where you yeah okay cool so what I found after I did this is that even though it was a massive memory savings now these base frames still took over half the memory of of you know I don't know if this math works out but whatever they took about half the memory of the system right and the Delta frames took the other half so one frame out of every 120 was taking half the memory it's obviously right for optimizations so what do you do and you know all sorts of schemes can be thought of like hey we'll dip the base frame from the previous base frame so we'll have like a hierarchical thing and it's like log base 120 or something so you climb up a tree to decode but that's kind of that's too non-local for me so what I did and it worked great is I DIF the base frames again off the default constructed state of an entity right so if you're programming in C++ or something you've got a constructor for your object it fills in especially if it's a live object in a game engine it's going to fill in valid values for all the properties of that object and often you won't change a lot of those properties right so so in the base frames now they're not dipped off any frame anymore but they're dipped off of how is this entity different from if you just constructed it and didn't do anything to it and didn't even add it into the world oh my friend hit shift okay so after this you've done a bunch of high-level optimization you start thinking about low-level optimization like an entropy coding layer you know lzw on this string of bytes or something there isn't any in grade partially because it was not needed partially because I had speed concerns about that and I needed as much speed as I could I forget if I talked about that later and these slides are not I had to cut some but yeah it wasn't needed because for example on the xbox360 where you have 512 Meg's of RAM total I dedicated about 40 megabytes to rewind data which seems like a lot of memory but on a game that's completely based on time manipulation it totally makes sense so devoting 40 megabytes gave the player between 30 and 60 minutes of recording time on most levels which is vastly more than you need usually it turns out some levels actually need that which is why it's good to have now if you're unpacking all these frames all the time that's going to be slow of course so you know for here's a screenshot showing a trail effect behind these little monsters when you rewind and the way that works is it just samples the monsters actual position over you know the last lots of frames couple couple of seconds usually in alpha blinds it right and I wanted to do that instead of some kind of extrapolation because again accuracy issues you get weirdness if you start trying to guess where things were so to do that you have to touch a lot of frames every time you want to render and so it makes sense to have a frame cache which in grade is probably about probably about 24 frames and those are totally live instantiated entities they're just not added to the main universe or just off to the side and yeah it's what you would think so some further implementation details you know I was talking about how let's say we're on frame 130 we want to seek your frame 137 and it's base frame is frame 120 right off to the left not to scale and you know the frame before that you actually constructed a new object so it's in frame 136 it's in frame 137 it's not in frame 120 if you go to apply this diff it's not there right and the simple solution to that is just anytime you constructed a new object and it's not on a base frame you just store the state for that object back in the base frame so every we can find it now you don't want to store it in the same array that the actual live data for the world is because when you rewind at that time you don't want to accidentally think that this object that doesn't exist yet exists so you just throw it into parallel arrays so you know it still only takes two frames to decode regardless of what objects you knew or create or destroy if you destroy an object you just don't really worry about it because the way the way that it works is we start at the at the target frame and so if the object doesn't exist there we won't try to dip it at all if it exists in the base frame we just ignore it okay so if you have limited memory to work with then you have to forget things or else you'll crash now fragmentation like I said is a big issue also so we want to somehow figure out how to forget stuff without fragmenting and I experimented with a bunch of things and the thing I was happiest with actually I think the only thing that actually worked across all platforms what's the group all the frames into a big bucket like just for memory allocation purposes and create a heap for that whole bucket and then destroy the heap when I want to forget all that stuff right and and the reason that I do that is because when you destroy a heap you know that the that the actual pages get be allocated they get returned back to the operating system so you're just not going to have fragmentation there's no way so at the same time though if you're using say you're on Windows and you're using heap out like that's super slow right you can't call heap Alec for every allocation that you want to make so what you do is you put a faster allocator in front of that that allocates chunks out of the heap and then hands little pieces back to the application for this it's super simple it uses a pool which hopefully most of us know but it's just basically an array and you move a pointer along the array and if they say I want 10 bytes you give them 10 bytes and you move the pointer 10 bytes and you know everything's totally packed together there's no way to ever D allocate anything from a but you don't need to because you're just going to destroy the heap when you want to forget all this data the heap size and grade is about twenty four seconds of gameplay so you know after I've recorded thirty minutes or 60 minutes and memories full and I have to start forgetting I forget twenty four second chunks at a time and that's about you know 60 frames per second that's about 1,000 or exactly 1440 frames per heap now there's a constraint on this number right it can't effectively be smaller than the difference between base frames right because if your first frame is in a base frame then you've got frames at the beginning of your data that you don't know how to decode because there's nowhere to go back to when you want to do the diff right so you know it has to be a multiple of two seconds because that's how long I put between base frames and 24 seconds seem pretty good now this is still a lot of heaps you know so if I've got 60 minutes of gameplay recorded right now and let's round it up to 30 seconds for easy math that's 120 heaps live but you know it seems like a lot I've never done that before but it seemed fine on all the target platform I get it again wait ah okay I'm just going to maybe stay okay so that's kind of the basics of the system and now going to talk about some special concerns that came up that are more specific to this game but that might have analogs and other games and how they were dealt with yeah I miss day all right so sound effects whenever people ask me about this I usually assume that I did something really crazy for sound effects when you're rewinding like I try to guess when a sound would have finished and then started up going backwards or so it's not how it works at all sound effects are just invisible entities just like everything else in the world and then there's an audio layer that's a little more asynchronous even than usual right the audio layer is usually to streaming samples out to the audio hardware at its own rate this one has a little layer that once per frame goes and looks at the world state looks at all the entities that are supposed to be creating sound and actually pulls the data right so it's pretty autonomous it'll create or destroy a stream that you know it will create a stream if there's an entity making sound that it hasn't got a stream floor and vice versa and so the app never directly plays a sound and I actually like this a lot more even even not even considering rewind but this sort of sound in the world database approach I found it's actually really nice for everything and I use it in my new game which doesn't even have rewind so now often if you're going to so you're going to call a sound effect like I've got the sound entity in my world and I don't want to keep the memory for it or in this case I don't want to keep storing it and rewind all the time so I want to know when the sounds done so I can delete it you might like check to see when all the samples are streamed out or you might look for an audio notification from your sound hardware that's not a good idea because that is with respect to the software like your app that is kind of non-deterministic right you know you don't exactly know when that's going to happen and if you rewind and do something again and the sound has been deleted this time the audio clock might go a little longer and you know it just doesn't match up so in braids sounds actually have their own timer that is tied to the game clock and not any kind of audio system clock and if it's supposed to be a second long sound I just destroy it after a second plus a safety margin of about 10% to account for the fact that the clock on the audio Hardware is gonna be a little bit different from your your idea of what the real time clock is okay so I talked before about how it was really important that you make particles constant because it's a huge amount of data but there's a whole world in grade where that's not true in this world you can drop this little ring that makes this bubble and time go slowly inside the bubble proceeding faster and faster as you radiate out from it and I felt it was very important for the coherency of the world to to ensure that this effects all moving objects right and through all the other worlds there's all this background particles that are noticeably moving and so here are particles that are noticeably moving should should be you slowed by this as well and what that means is that you can't use that approach I was talking about before where you just generate the particles from a seed because you don't know where the rings been for the past while and so you try to apply that to the see data and like it breaks you get a lot of discontinuities whenever you pick up and drop the ring and stuff so what do you do well you can kind of guess I just record it all but I'm trying to be careful again to make it small so I made a different kind of particle system that is only present in this world where you have time dilation and on those base frames I was talking about before it actually records the positions of all the particles these particles don't have as much animation as the particles in the earlier world so there's not a lot of state to record just a position and then a number that you can get the other properties from right because you don't like that the ring doesn't affect you know the the color of the particle right it just affects the time and so you can reconstruct the color and rotation and all that as long as you can reconstruct the time so on non base frames though I don't want to try to stored if somehow of all these particles that's still a giant amount of data like one different particle so what I do is I just or where the Ring is because that's the only thing that can distort time because the base frames are 120 frames apart that's up to 120 frames of data about where this time dilating object is and what I implemented that because I knew I was going to have to do the next thing I'm about to say but I was like no I'm just going to try it and it was a ton of data because on frame 119 you're storing 119 frames in that one frame and on frame 118 you store 218 it's a yeah it adds up real fast so there's an AR le run-length encoding kind of mechanism in there like that ring that you're carrying around it's allowed to I'm being told to cut off alright I'll take another 1 minute and I'll cut off a question come on up to the mic if you got one nobody alright thank you very much [Applause]

Channel: GDC

Views: 98,297

Rating: 4.8814073 out of 5

Keywords: gdc, talk, panel, game, games, gaming, development, hd, design

Id: 8dinUbg2h70

Length: 26min 56sec (1616 seconds)

Published: Mon Dec 12 2016

Reddit Comments

[u/Maxolo]

Thanks! I was just wondering how to implement this. Will watch later. This great new sub is already delivering!