In my opinion, the main source of replay instability comes from the timing model. I just dealt with this yesterday, in fact: I have a puzzle game running the Box2D physics engine, and had to rework some of my architecture to make it run deterministically each time the player restarts, since the gameplay is predicated on testing a configuration, resetting, and adjusting it.
Representing time in a game requires some way of slicing a time delta into discrete slices that you can run processing on it; so in the end every timing model comes down to "use a time delta directly within your simulation code" or "chunk it into frames and store or drop the remainders." The latter option is almost a given if you want your results to be stable and deterministic, it's just a matter of _when_ you apply the frames.
In my case, before the refactor I had each segment of the simulation(AI, spawners, physics, etc.) running independent frame chunks from the same dT. The problem is that in a loop that looks like:
If dT is large enough, then AI will run multiple times before ever hitting physics, causing some bizarre behaviors that may or may not be acceptable(in my case, not).
My solution was to change it to:
while (dT>fixdT)
{
ai.update(fixdT);
phys.update(fixdT);
spawns.update(fixdT);
dT-=fixdT;
}
This way, no one piece of code can race ahead of the others, but the option is still there to let some things run only every n frames(including fractional amounts).
Another thing I had to do for stability was a full reset on everything. Pre-refactor, I let Box2D stay "warm" and just removed all bodies, but this turned out to affect determinism - and proved worse for start times than a cold restart, anyway.
For something so basic, I always find this very tricky to get right. Interference from global state can sneak in all from a lot of different unexpected ways.
One of my games allowed people to save replays and levels to the web. The online infrastructure, creation of the editor and debugging of replays dwarfed the time taken to create the game in the first place, making the game take over 4x as long as it otherwise would have. (Note the levels and replays list is only from the last day, never got around to doing an all time best.)
A good read on this topic: John Carmack's .plan entry from 14 Oct 1998. He writes about replay as a development tool, how it's necessary to record time, and how journaling inputs "turns a realtime application into a batch process".
This method of storing replays frequently leads to brokenness when the game logic updates due to patches. IL2: Sturmovik had replays like this and if you ran an old replay on a newer version, the replay planes would end up running off the runway or similar.
IIRC, the Starcraft 2 beta keeps old versions of the game engine around to let you play back older replays.
A similar technique is occasionally used in non-server-based multiplayer games - here's a Gamasutra post-mortem for _X-Wing vs. TIE Fighter_ where sending inputs across machines is discussed: http://www.gamasutra.com/view/feature/3374/the_internet_suck...
I was big into Supreme Commander in the first 6 months after its release. They had a phenomenal online database of every ranked replay as well as ranking which would point users to great high-level replays.
Early on, Supreme Commander was great at putting out balance changes and hotfixes. Unfortunately, every single patch would completely empty the online database and would also break any replays you stored on your computer! People managed to hack together a version switcher eventually, but I still ended up losing lots of awesome replays.
One of the neatest ways replays are implemented is in MAME (Multiple Arcade Machine Emulator). The replay is recorded by just recording all of the inputs given to the emulator during the course of the game. Since the entire system is deterministic, you can watch a replay by having MAME just play back the game with the inputs stored in the file.
If it's anything like SNES/Genesis/other console emulators, the only entropy source is player input. I can't imagine many arcade machines would have a true persistant clock, and even then you could just store the start time as part of the replay data to ensure you get the same output for rand(time()) each time.
Having worked in both games and the desktop world, implementing replays is a lot like implementing undo/redo, and they're both an immense time-suck. It's easy for developers on the different sub-systems to create something that on the surface seems complete but is doing a bad job of recording and responding to the needed events. Inevitably either the original developer or the poor sucker tasked with implementing undo has to go back in and rewrite the code, which takes longer than everyone expects.
Unless, of course, you already need determinism for multi-player to work. Real time strategy games, first person shooters with complex AI, and other games that are networked in lock-step are already completely deterministic and have to be for it to work at all. You basically get replays for free that way, but it has to be a conscious effort of the entire team to maintain determinism.
Luckily, determinism is something that you can verify with an automated process. After each checkin, run some automated tests on a server farm. Run them twice. During the first run, take a full game world state snapshot periodically. During the second run, verify that the world state is identical since the first run. If it isn't, re-run the test twice. Take snapshots more frequently during the interval where determinism broke. Recurse like a binary search. You can automatically pin-point the exact frame where the simulations diverge.
One you have a replay file and the exact frame, you have the best bug report on the planet. "This replay is build 12345 and crashes on frame 54321". Fire it up in the debugger, run a system command "fast forward to frame 54321" and then just start stepping. Oh, it crashes on that line? Let's drill into that: restart replay, set breakpoint, run to frame 54321, step-in. Freaking beautiful.
Starcraft 2 introduced replay rewinding which I think is even more interesting.
I guess that it loads a replay at the time you're watching it simply by replaying the game with the help of actions and at the same time it stores states of the game and then if you rewind (you can't continuously rewind like a VCR, you pick a state in the past and you go on from there) it loads that state.
It sounds so easy when you write it like this but I'm sure it's a lot harder than it sounds.
I swear SC1 had rewinding in its replays. Or at least jumping to the past. And from what I remember, SC1 replays recorded all user inputs, timing data, as well as w/e the unit AI (pathfinding and auto attack) did. This would cause some problems across patches which would make previous replays glitchy since something about the unit stats would change. For example, if a unit had 45 hp and then upgraded to 50hp in a patch and the replay had a unit kill the 45 hp unit and immediately leave, then in the patched replay, you would just have a 5hp wounded unit left standing there.
There were all sorts of tools for analyzing replays. They did contain ALL user inputs, so you could map a players APM second to second through the entire game, and you could also break out what percentage of their clicking was spam, and what were actual commands.
Representing time in a game requires some way of slicing a time delta into discrete slices that you can run processing on it; so in the end every timing model comes down to "use a time delta directly within your simulation code" or "chunk it into frames and store or drop the remainders." The latter option is almost a given if you want your results to be stable and deterministic, it's just a matter of _when_ you apply the frames.
In my case, before the refactor I had each segment of the simulation(AI, spawners, physics, etc.) running independent frame chunks from the same dT. The problem is that in a loop that looks like:
ai.update(dT); phys.update(dT); spawns.update(dT);
If dT is large enough, then AI will run multiple times before ever hitting physics, causing some bizarre behaviors that may or may not be acceptable(in my case, not).
My solution was to change it to:
while (dT>fixdT) { ai.update(fixdT); phys.update(fixdT); spawns.update(fixdT); dT-=fixdT; }
This way, no one piece of code can race ahead of the others, but the option is still there to let some things run only every n frames(including fractional amounts).
Another thing I had to do for stability was a full reset on everything. Pre-refactor, I let Box2D stay "warm" and just removed all bodies, but this turned out to affect determinism - and proved worse for start times than a cold restart, anyway.