Ever since I began working on CodeCraft, I wanted to implement a multiplayer mode which would allow players anywhere in the world to pit their AIs against each other. With most other parts of CodeCraft taking shape, I now spent some time working on that aspect of the game. In this post I want to talk about some of the design challenges and outline my plans for multiplayer.
The core problem one needs to solve to implement multiplayer is to devise a protocol that synchronizes the game state across different machines. My initial approach to this was to distribute the initial world state to all clients at the start of the game and then, on each turn, sync the commands executed by each player. All clients can then individually compute the game state resulting from the commands, just as if they were running a single player game. The appealing property of this protocol is that only a small number of commands have to be send across the network. This minimizes bandwidth requirements and gives conceptual simplicity. For these reasons, this is the protocol of choice for most RTS games.
To make this work, the simulation of the game mechanics must be completely deterministic. If at any point there is as much as a difference in the least significant bit of one of the unit positions, the simulations might diverge over time. Until now I had been assuming I could achieve this level of determinism. After some research, I have come to the conclusion that this is actually a hard problem when you target different platforms. The issue is that the IEEE 754 floating point standard allows some freedom in the precision that intermediary results are stored in. It is also necessary to have full control over the values of various flags that affect floating point behaviour. In C/C++ it is possible (with some effort) to produce binaries that will be deterministic across different machines and in Java, the strictfp keyword seems to allow this as well. However, as far as I can tell there is no way to do this in JavaScript (and, by extension, Scala.js). So that would make multiplayer (or even just viewing replays) impossible in the JavaScript version. This is not a limitation that I want to impose, which is why I have been thinking about alternative ways to implement multiplayer.
(If you want to find out more about floating point determinism, these are some sources I have found particularly useful: What Every Computer Scientist Should Know About Floating-Point , Random ASCII on floating-point determinism, Floating-point determinism in JavaScript)
Option 1
Why go through all the effort of synchronizing state between machines at all? In JavaScript you could just download someone’s source code and run it locally on your machines. Of course this means only one person can actually view the match, it only works for JavaScript, and there are some security concerns. On the other hand, the players don’t need to be online at the same time and it is actually fairly easy to implement. I expect to roll out this feature as early as next week.
Option 2
Instead of transferring commands, sync the entire world state after every simulation step. For most RTS games, this would be infeasible due to bandwidth constraints. Fortunately, CodeCraft operates under slightly different conditions: First, the number of objects in CodeCraft is reasonably small. Second, there is no need to let the AI logic run on every simulation step. I suspect even something on the order of 2 times per second would still be quite acceptable. The clients can still simulate the ticks in between to keep the graphics running smoothly, but now divergence won’t matter since everything gets synced before any new commands are run. If it was a human playing the game, the resulting lag would be annoying, but your AI won’t care.
Implementing this will be a bit more difficult than my initial plan, since I now need to identify and sync a lot of different sources of state rather than rely on a small and well defined set of commands. So it will take longer than I had hoped, but I will still get there eventually.