Determinism in Games | |
| January 28th, 2011 | |
 Spencer Nielsen   |
One day while I was hard at work a couple weeks ago I hit a really difficult technical snag. I stood up from my desk, let out a sigh and declared to the other person working in the office that “I’ve lost my determinism!”. He then inquired how I had lost my motivation while visibly wondering if I had used the word correctly. Although I had hit a significant roadblock, my determination to overcome it and make progress on my game was higher then ever. The “determinism” of my game however, had been lost. Now I needed to take it back.
Right now I am in the thick of bringing up the core engine for my upcoming game. I have been working in a whole slew of different areas and technologies like OpenGL, Bullet3D, MySQL, CoreGraphics, Game Kit and Game Center. One aspect that I have been concentrating a lot on (especially in light of the integration of the Bullet3D physics engine) has been to make sure that the game execution is completely 100% deterministic. In computer science when a function is deterministic it means that when you provide it a specific set of inputs you will get the exact same set of outputs every time. This can be very important in games for a number of reasons. One reason is that you don’t want users to get different results when they play the exact same way. Now this might not be a big deal for some games because the variations in output might be so slight that they may not be of notice or consequence. However, if you ever want to make your game networkable or enable replays of past games then determinism is almost always required (unless of course you follow the QuakeWorld networking paradigm). Short of having one computer serialize and transfer its entire game state to all of the other network clients, you need assurance that the exact same set of player inputs executed on all of the networked machines will produce the exact same game state on every one.
Making sure your game is deterministic can sometimes be a challenge (especially when physics simulation and networking are involved). You need to examine things like your use of random number generation, use of pointers as identifiers (hint: don’t ever use a pointer as an identifier) and consider differences in instruction execution on the platforms you are targeting. Care and thought also needs to put into considering things like compiler options and optimization levels. For example, if you release an update to a game with a higher optimization level than the originally released version, you can potentially change the execution of the game and make the newer version incorrectly replay past game replays. It also goes without saying that you should be very careful in changing any sort of gameplay mechanic outright between versions.
A real life example of this hit me the other day when I got out my old copy of Starcraft and started up replays of some epic multiplayer and single player matches played with friends about 5 years ago. Sadly the changes to unit behavior and execution since the replays were made (although ever so slight) caused execution to start to drift after about 10 minutes in one example. By around 12 minutes it was clear that our original gameplay was completely gone and the players just sat there doing nothing because all the player commands that the replay was attempting to execute were not valid in that game state. From what I have heard, Starcraft 2 actually keeps old copies of the game around after you update for the sole purpose of maintaining the integrity of replays.
In the development of my game thus far I have encountered these three challenges with regard to determinism (in order of increasing difficulty):
1. The same simulation inputs will resolve to the exact same state every time
Many of the code examples out there for Bullet3D set things up in such a way as to make it run non-deterministically. It can however be made to run deterministically with these settings:
One thing to note is that even with this setup, the same simulation can still run differently across platforms. Specifically those platforms that differ from each other in floating point math implementations (like x86 Mac OS X and ARM iOS) will probably not run the simulation in the same way.
2. Synchronize exact simulation state between networked devices while maintaining smooth framerate and responsiveness
This is a fairly complicated subject and my solution is very specific to my game’s mechanics. Full explanation of what I did will receive it’s own blog post treatment at a future date. Sufficeth to say that a fair amount of it has do with the psychology of user that plays my game.
3. Maintain simulation determinism across serialization
This basically means that I should have the ability to stop a simulation, write it to disk, read it from disk and keep going without affecting the result of the simulation. Unbeknownst to me before I started this project, this would actually be the hardest to achieve of all three. I have finally found a solution that works really nicely and I am satisfied with it enough that I have decided to go with it. There is still somewhat of an ongoing issue with this though and it has specifics in the Bullet3D physics engine. If you care to dive into this one I started a thread that explains and discusses it here.
Conclusion
If anything, I think the takeaway is that determinism in games can be hard but is almost always worth it. Take the extra time early in the development cycle to make sure that your outcomes are exactly reproducible and engineer infrastructure to audit and report any inconsistencies when they pop up so that you can catch any determinism breaks early.