[In this technical piece, Introversion's Knottenbelt discusses the 'discrete event simulation' approach to multiplayer in the upcoming Darwinia+ for Xbox Live Arcade, in which player movements and button presses are sent over the network, instead of actual positions of the thousands of in-game objects ]

Introduction

Not many people know this but Introversion's IGF award-winning title Darwinia was released incomplete: Darwinia was originally conceived as a multiplayer game.

Initially codenamed "Future War", the main game design centered around players who could take control of a massive sprite army, that could then be pitched against another players armies in massive battle-epic style. The trouble is, we ran out of money spectacularly.

As the finances at Introversion dwindled the original multiplayer component for Darwinia was hastily dropped. It wasn't until some months later, reveling in the unexpected kudos of winning those IGF awards that the opportunity for us to revisit the earlier multiplayer idea was revived.

Microsoft wanted to bring Darwinia to XBLA, and with that came the need for a multiplayer component - this would in time develop into an entirely new game called Multiwinia, which IV launched on PC at the end of 2008. Multiwinia, along with Darwinia will be released on Live Arcade as Darwinia+ this summer, a momentous occasion for us as Introversion's first release onto a console.

By the time we started work on Darwinia+, multiplayer networking was not entirely new to us - as mentioned we had dipped our toes into the water when first developing Darwinia, and although unsuccessful we had learnt an important lesson; it was better to integrate multiplayer functionality into the core of the game early on.

Nevertheless, the networking we had started with Darwinia proved useful in our later multiplayer titles, such as Defcon released in 2006, and Multiwinia released last year.

Our approach to multiplayer networking has had its advantages and drawbacks, some of which I will explore in further detail here, along with a greater insight into how we approached this key-programming problem.

Conventional Approach

The most common approach to multiplayer networking in games is to have a game server to which the various players connect.

The game server is then responsible for simulating the game world and broadcasting the positions and velocities of all the objects in the world to the connected players.

To make this system work well, the clients typically predict the future positions and velocities of the objects in the world while waiting for the next update.

In Defcon and Multiwinia, however, there are so many world objects whose positions and velocities are changing that to follow the above approach would require more bandwidth than is typically available over a standard broadband connection in the UK.

Taking Multiwinia as an example, if there are 5000 Darwinians in game, and every one is changing position and velocity, then we can calculate the approximate size of a world update as follows:

5000 Darwinians * SizeOf (
New Position ( Represented as 3 32-bit floating point numbers - X, Y, Z)
New Velocity ( Represented as 3 32-bit floating point numbers - DX, DY, DZ)
New State ( byte )
)

= 5000 * ( 4*3 + 4*3 + 1 ) = 5000 * 25 = 125000 bytes

The players would need to be able to interact with the server as well, so if we aim for 10 updates a second, then we'd need:

125000 bytes * 10/s = 1 250 000 bytes/s

And there could be up to 4 remotely connected players (in Multiwinia), so we're really looking at:

3 * 1 250 000 = 3 750 000 bytes/s of upstream bandwidth.

Of course, you could optimize this a bit with various compression techniques, but the point is that it's quite a large number. Clearly, broadcasting updates of world state in this fashion wouldn't be appropriate for the game world of Multiwinia.

Discrete Event Simulation

The approach that we took is essentially one of discrete-event simulation. The idea here is that if there were absolutely no player input, given the same starting conditions, the Defcon and Multiwinia worlds would evolve in exactly the same way over time.

The trick is to influence the evolution of the worlds in response to the players input so that all the simulations keep in step with each other. In theory, we should be able to get away with sending a representation of the player input (e.g. mouse clicks and key presses) to the server to replicate to all clients.

However, much user input does not actually influence the world (e.g. flying around to have a look at what's going on), so we went with an abstraction -- essentially events that represent actions in the world.

Let's take a look at a simplified game loop:

MainGameLoop()
{
while( !GameOver() )
{
ProcessInput();
ProcessEvents();
Render();
}
}

ProcessInput() is responsible for processing the user input. Instead of directly altering the world state, we create an event to send to the server. The server runs at 10 Hz. This means that every 100 milliseconds, it gathers together all the events that it receives from the players and packages them up into a 'Network Letter'.

The network letters are then sent to all the connected players. The server also assigns each letter a sequence number, so that the clients can evaluate the events in order. So for example, when a client requests that a group of Darwinians move to a particular point, this would be encoded by an event:

MOVE_DARWINIANS
TEAM_ID: unsigned int
GROUP_POS: Vector3
GROUP_RADIUS: unsigned int
DEST_POS: Vector3

TEAM_ID is an identifier of the player's team in the world. Since all connected players process the event, it's important to identify which team we are talking about. GROUP_POS is a position in the world, and GROUP_RADIUS is the size of selection circle (all Darwinians within the circle described by GROUP_POS and GROUP_RADIUS will be selected). DEST_POS is where the Darwinians are going to head.

ProcessEvents() receives network letters from the server (if available) and processes them in the server-assigned sequence number order.

If the server within a particular 100 ms slot receives no events, the server will send out an empty Network Letter, with no enclosed events. This is effectively a 'tick' event, and allows the clients to advance the world (and the game time) even though there was no significant user input.

Advantages

The main advantage of this approach is that the amount of bandwidth necessary for the system to work is greatly reduced. For Defcon and Multiwinia we require about 2KB/s per connected client.

So with a typical UK broadband upstream of about 25KB/s, a server would be able to support up to 12 clients, more than enough for Defcon's 6 player games and Multiwinia's 4 player games. In fact, in Defcon we were able to implement a spectator mode, which allows additional clients to connect and become a spectator of the game (without being able to control it, of course!).

Another advantage of this approach is that it is, in theory, quite straightforward to record the game and play it back again. All that is required is to save the history of events and play them back again on the viewing client.

Extending this idea a little, once the events are recorded it is possible to make very high quality videos by experimenting with different camera positions and camera transitions. The game can then be played back twice, once to record the sound, and once frame-by-frame to record the video in high resolution.

Disadvantages

One of the disadvantages of this approach to multiplayer networking is that if a player joins while the game is in progress, the whole history of events since the game started must be transferred to the joining player who must then evaluate the events in the same way.

If the game has been running for a long time, not only the amount of data to be sent can be considerable, but also the amount of time required to evaluate the events may become significant.

The obvious solution to this problem is for the server to record the most recent full world state and send it together with the following events if that would save bandwidth, something reminiscent of the i-frame system used in video codecs.

The other disadvantage of this approach is that the game itself needs to be written carefully so that the evaluation of the events happens in exactly the same way on all clients. This means that if the evaluation of the events is changed in a later update to the game (for example to fix a bug), then all clients must upgrade to the new version in order to be able to play against each other.

Defcon and Multiwinia both used floating-point calculations in the evaluation of the events, which poses additional challenges since although most systems are IEEE-754 compliant, different compilers can compile an expression in different ways leading to subtly different floating-point results.

This is due to the fact that the accumulation of floating point error depends on the order of the arithmetic operations and each compiler optimizes the expression in their own way. There are also further issues when trying to interoperate between PowerPC and Intel processors.

Conclusion

The networking approach we took in Defcon and Multiwinia has worked out well for us. The letter system proved to be scalable and able to cope with more than one game type.

The overall simulation methodology did prove problematic due to its reliance on predictive outcome and we needed to invest quite some time investigating synchronization issues but the end results more than made up for that.

I think that if we were approaching these games again we would think carefully about how to avoid the dependency on floating point calculations and implement a 'quick catch up' mode to mitigate the long joining times.