in Game tech

Back to The Future (Part 2)

I really enjoy a good cup of tea. On the surface, making tea is really easy: take some tea leaves, pour some hot water over them, and wait a few minutes. In practice, the difference between a bitter, undrinkable brew, and a perfect cup of tea is all in the details; the type and amount of tea, the temperature of the water, and the steeping, time all make a huge difference. A playback system for a game is very much the same. As we saw last month, the basic idea is really simple: Record all game inputs, make the game deterministic, and you get the same playback every time. Unfortunately things aren’t quite that simple in real life. Just as with tea making, the secret to a perfect playback system is all in the details.

Let’s look at some of the common problems that can trip up the playback system and what we can do about them. We’ll warm up by starting with the easiest ones and work our way to the hardest ones.

Game Versions

A playback of a game recorded with a different version is almost guaranteed to end up with different results than the original version. Any minor tweaks to AI parameters, pathfinding algorithms, or just about anything is most likely going to generate a different game state. It doesn’t even have to be a change in code either: adding a new character or moving a trigger volume will also cause different playbacks.

In general, you’re best off avoiding using recorded inputs from previous versions of the game. Inserting the game build version at the beginning of the recorded game state file allows you to detect version mismatches during playback. If a mismatch is detected, you can either print a warning or give up on the state verification altogether. This check will be particularly useful if you’re sharing recorded sessions across the office (perhaps through a bug database) and people are on slightly different versions.

The idea of recording a session in release mode (all optimizations enabled, few debugging checks in place), and playing it back in debug mode is very tempting. Unfortunately, mixing and matching configurations is almost guaranteed not to work. Middleware libraries will often have slightly different behaviors in debug and release, which will throw off playback right away. But most likely so does your own code, and often in ways you might not expect. For example, you might have different floating point rounding modes in debug and release. Or even a more subtle difference: depending on the optimizations you have turned on, in debug mode a float variable might be copied back to memory after each operation (which rounds it back to a float), whereas in release the program might execute several operations in a row on that value before writing it back to main memory and causing the rounding only once. The results are going to be very close, but they’ll often be cumulative and the simulation will quickly diverge.

As a general rule, treat debug and release builds as if they were different versions. Make sure to include which configuration it is along with the build number in the game state file so you can check for that as well.

Memory State

Reading data from uninitialized memory is probably the number one cause of non-determinism in games. Uninitialized memory will contain whatever data was stored there before. That can mean anything from sane-looking values to total garbage. What’s worse, they’re going to change from run to run, so if your game ever uses the values contained in uninitialized memory, playback is not going to be deterministic.

The most common case of using uninitialized memory happens by reading a variable that was declared and not initialized. This mistake is easy to see when we’re dealing with a standalone variable, but when it becomes a member variable hidden inside some class, it becomes a lot less obvious. It’s also important to notice that this will only happen when we declare variables on the stack or we create them dynamically on the heap. For global and static variables, the C runtime takes care of initializing them all to zero for us.

Cranking up the compiler warning level to the maximum will allow it to catch some of the most obvious cases of reading uninitialized variables. For extra checks, I recommend a static code analysis program such as PC Lint. That’s almost guaranteed to catch every use of uninitialized variables (along with ten thousand other things, some of them extremely useful, though most of them you probably won’t care about at all).

Another common mistake is to read past the end of a valid memory area, such as an array. The values read from memory in that case are going to depend on where that array is, and what happened before. In any case, it’s going to become a source of non-determinsim, and it’s a clear bug that should be fixed right away.

If you ever find that your game is deterministic in debug mode but not in release mode, start by suspecting access to uninitialized memory. In debug mode, a lot of platforms will fill the memory heap with specific bit patterns describing the memory status: allocated, freed, etc. Those patterns can be really useful to track down problems with memory allocations, but they also set memory values to a consistent state, which will make debug builds seem deterministic when they really aren’t.

Pointer Values

Unless you’re working on a platform over which you have total control, and you have a very strict memory allocation scheme, you should probably never rely on the actual numerical value of your pointer variables. The pointer values will change from run to run, and will depend on what happened before, including what other programs were running at the time.

If you’re puzzled at the idea of using the pointer values as part of the logic in your program (and you should be), you still need to watch out for this possibility. Some well-known, open source compression libraries rely on this technique by hashing pointer values. This means that two consecutive runs of the same program might end up with two slightly different results.

In general, it’s considered a good practice to avoid using pointer values for anything other than dereferencing them and accessing the data they’re pointing to. Making decisions based on their actual numerical values is asking for trouble, and you can almost always achieve the same result by using offsets between pointer values (as long as you know they’re coming from the same memory block), which has none of those problems.

Asynchronous File I/O

This is where things start to get fun. A lot of games perform background loads while the game is running. Whenever the game detects it will need an asset, it initiates an asynchronous load. When the load is complete, the game is notified and, optionally, does some processing on that asset. There is no guarantee about when exactly the load will complete, which means that each playback has the potential to be slightly different.

If the background load just brings in more mipmaps for a texture, it’s not going to affect the simulation whether it happened a frame earlier or a frame later. On the other hand, if it’s loading a more detailed AI navigation path, it can definitely affect the position and state of AI units. Even if you’re not loading data that affects the simulation, it’s very useful to have asynchronous file IO work deterministically to catch bugs more reliably. For example, the game might crash if a background texture load completes the same frame as a line of dialog sound is requested. As any programmer who’s ever had to debug a problem like this will tell you, being able to reliably reproduce that crash is worth a small fortune.

We can turn asynchronous file loading into a deterministic operation by considering the read completions as inputs to the game. Whenever an asynchronous file load completes, we record it in the game input file at the corresponding frame. During playback, the game will request background loads as usual, but completion events are made available only when they’re read from the input stream.

This can be easily implemented at the game level by buffering all background read completions. During recording and normal game operation, background read completion events are made available as soon as they happen. During playback, however, background read completion events need to be available the exact same frame they happened in the original session. If the read finishes earlier, it is simply buffered for a few frames until the correct time. If the read hasn’t completed by the time it finished in the original session, the game blocks until it’s done and it’s made available right away. That means that playback might be a bit choppy at times, while the game blocks for data to be read, but it will ensure that playback is fully deterministic. Notice that blocking the game while waiting for a read to complete is not going to affect subsequent frames with a larger delta time because we’re also reading the system clock from the input

Network Data

What about online games? Our playback method has been concerned exclusively with local players. Playtesting and Q/A on online games is much more expensive and time consuming than single-player games because of the manpower required and the coordination necessary to set the games up. Wouldn’t it be great to be able to replay a 30-person game that resulted in a crash without having to get 30 players again?

Data received from the network most definitely influences the game itself, so it’s another input to the game. We could treat all network traffic like any of the other inputs. Record it along with the other game input and play it back by inserting the network packets as if they had come from the network card. That would work, but it’s a bit more complicated than it has to be. Fully emulating the network traffic, connection status, and everything else can be a bit tricky to get just right.

A simpler approach consists of translating the data received through the network into higher-level game actions. For example, whenever a player fires a weapon, it results in a network packet, which is translated into a game-level action whenever it’s received. Then, the local simulation applies the action that causes that player to fire locally. You probably already have a system like that in place in your multiplayer game anyway. Recording those actions is a much simpler task than the raw network traffic, and playing back a recorded multiplayer game is just a matter of inserting the game-level actions at the same time they occurred, just like any
other input.

The game input file is going to grow significantly as soon as you start recording all the actions created by the players through the network. Fortunately, most games are extremely careful to minimize network bandwidth, so the input file will remain at a reasonable size even recording all that data.

Threads And Multiprocessors

In today’s games, multithreading is an inevitable reality. Even if your code isn’t explicitly multithreaded, parts of your engine and middleware are probably using multiple threads. The problem with threads is that you never know exactly when one thread stops working and another one resumes. So it is possible that two events in two different threads will happen in different order in two runs of the game. To make things even more fun, most of today’s platforms have multiple cores, making determinism even more complicated. Do we need to give up determinism in a thread-dominated world?

The totally honest answer is that we’ve already picked all the low-hanging fruit. If you really want your game to be 100 percent deterministic while running in multiple threads over multiple cores, get ready to roll up your sleeves and do some serious work. For the rest of us, we can still get most of the benefits of a playback system without total determinism. That means that there is potential for bugs caused by thread interactions that might not be repeatable from run to run. But at least the game simulation will be the same for every playback, so the recording technique should still be very useful.

In the easiest case, the simulation runs on a single thread, with the rest of the threads dedicated to graphics, sound, and other systems. If we apply all the techniques we’ve covered so far, the simulation itself should be deterministic and we shouldn’t have to do anything different than we did in the singlethreaded case.

However, as soon as the simulation is spread across multiple threads, we need to be a lot more careful. Even if we have no control over the thread context switches, we can at least ensure that major events happen in the same order no matter how they were executed. For example, if a worker thread creates a set of actions to be executed, we can sort those actions before processing them. If that’s not an option (because those actions are processed as soon as they are created, for example), we could record the creation order as part of the input recording, although enforcing that order during playback might have far reaching consequences for many systems deep inside the game.

If achieving 100 percent determinism in a threaded environment is important to your project, have a look at Replay Director. It’s a commercial tool and set of libraries that gives you very accurate recordings and playbacks of your game, including thread context switches, with little extra programming on your part.

More Than Just For Debugging

At this point, if you’ve applied all the techniques we’ve discussed so far, you should have a pretty bullet-proof recording and playback system: lightweight, reliable, and accurate. It will be a great help as a debugging tool, but there’s no reason to stop there. You could use the same system to record demo sequences to show off in presentations without the need to make a movie capture and degrade the image quality. You can also truthfully claim that it’s a live demo, running on the game itself, not a canned movie, which always carries extra weight with most audiences.

You can even integrate the playback system as a key feature in your game. Halo 3 already does this by allowing you to replay any play session, examine what happen exactly, and let you take screenshots of the juiciest moments. It can be a great feature for a lot of games for almost no extra effort over what you’ve already implemented. The main problem will be to make sure future updates to the game don’t affect the playback of older gameplay sessions. This is really hard to achieve, since the most insignificant change can end up causing the simulation to diverge in unexpected ways. So if you’re going to rely on it as a game feature, you need a suite of comprehensive tests verifying that nothing changes whenever the game is updated. Last month we saw how to verify that a playback results in the same game state as the original session, so again, there’s very little extra work there.

With all these techniques in your toolbox, you should be able to make your game pretty close to 100 percent deterministic—enough to have a solid playback system and use it to its fullest during production, and maybe even as a game feature.

This article was originally printed in the June 2008 issue of Game Developer.

Comments are closed.