Tuesday, September 23, 2008

Game Engine Topologies: Peer-to-peer

This is part two of a two-part post on game engine topologies (first part). The first-half is not required reading to grok the second half.

As I mentioned in the first part of this article, a client-server topology generally makes sense when you have relatively few objects that change, as each object update requires messages to be sent to the server and then to all the clients.

In a peer-to-peer topology, the server is only sent stimulus, and that stimulus is rebroadcast to all clients. Synchronization is maintained by having all machines take the same actions at the same time. Not exactly in the wall-clock sense, but in the simulation sense (close to wall-clocks, though).

A concrete example might clear up the differences here. P2P topologies are typically used in RTSes. Imagine that while playing, you select a group of units, then order them to move to a location, then follow-up with an order for them to attack a specific unit. Afterwards, you select another group of units and order them to defend a position.

In a client-server topology, you would send updates about all of those objects as their state changed, and you would periodically have to deal with discrepancies (for example, on one client a unit is out of range but on another client the unit was killed, etc).

In a P2P topology, the messages look something like this:


While this seems like a lot of messages, it's actually quite sparse, particularly considering each message fits in 12 bytes or less. This means the total byte cost for all above messages is around 112 bytes. By comparison, 7 positional updates from a client-server topology would cost about the same. This could be less than one frame of movement!

So these messages are sent, and 'at some point in the future', they are executed. Even on the local machine, commands are not executed immediately! You generally (okay, always) get some sort of client feedback, the unit acknowledges via sound, or a client-only effect is played (for example, a UI element flashes), and then nothing happens for a bit. This is because of the architecture under the covers. The message has to be sent to the server, the server figures out how much time to allow for the latency of all clients, and says 'at this point in the future, everyone execute this command'.

P2P topologies have one other packet that they send 'every so often', a synchronization packet. In order to ensure that the clients are all still in sync--that is, they all still agree on the state of the universe--they need to send a packet that indicates what the state of their universe is. Although there are many ways to accomplish such a task, in practice I've only seen one implementation: CRC the entire simulation, then send the results to the server. If a client goes out of sync, you have only two choices: abort or try to regain syncronization. Although regaining syncronization is possible, I've yet to see a production title attempt it. The reason is simple: a synchronization error is often a sign that one player is trying to cheat.

Peer-to-peer topologies are effectively the 'inductive proof' of game engine topologies. We all start in the same state, and we all issue every command on the same tick. We better all be in the same state on the next tick.

No comments: