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.

Peer-to-Peer
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:

StartSelection(PlayerID)
AddUnit(1)
AddUnit(2)
AddUnit(3)
StopSelection(PlayerID)
MoveSelectionTo(location)
SelectionAttack(TargetObject)
ClearSelection(PlayerID)
StartSelection(PlayerID)
AddUnit(4)
AddUnit(5)
StopSelection(PlayerID)
SelectionDefend(location)


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.

Game Engine Topologies: Client-Server

In multiplayer games, you have to communicate information between the clients to keep the game in sync. This simple requirement actually has quite a far-reaching impact in your game engine. Although there are many variations on the theme, there are two primary topologies that are used to achieve communication between clients: "Client-Server and Peer-to-peer". These topologies are used all the way from the simplest multiplayer game (think Worms), to the most complicated MMO. In a two-part post, I'll cover the topologies used by games today.

Client-Server (examples: WoW, every multiplayer FPS ever)
In a client-server topology, you have one (or possibly more) servers, and you have many clients. The clients are each responsible for a set of one or more objects, and whenever a change occurs in one of these objects, the client communicates those objects to the server, who takes appropriate action. Likewise, when other game entities change, the server pushes that information to the various clients. The clients can be thought of as basically dumb, they aren't doing much (or possibly any) world simulation and instead are just rendering the state of the world as they were told on any given frame. It's probably obvious--but worth saying anyways--that in a client-server environment, all clients are lagging behind the server by some amount of time, known as their latency. That is, while the server may be processing simulation time 30, clients might all be processing at time 27, 28, 29, or 26, depending on how long it takes for them to receive network traffic as well as render the results of the current state of the simulation.

The values of client-server topologies are that they are generally low-latency. You press a button, and the results are immediately sent to the server. The downside of such a system is that the network requirements scale linearly with the number of objects that exist in the game universe.

In Client-Server topologies, there are two basic modes: Client Authoritative (CA) and Server Authoritative (SA). Valve has also clever spin on this approach, which I'll discuss seperately below.

The primary difference between CA and SA involves the messages that are sent along with who validates that the message is legal. In a CA environment, the client sends messages like "Spawn a rocket here, travelling in this direction with this velocity," or "I hit this entity for XYZ points of damage." The server doesn't perform additional validation of these messages, which leads to an obvious problem: cheating. In fact, even if you have a completely robust and bulletproof client (which is pretty much impossible), these types of architectures are vulnerable to man-in-the-middle (MITM) attacks. It would be trivial, for example, to write a client that sat next to your game, listening for a global hotkey that would insert an automatic 'kill shot', for example. The upside of CA servers, however, are that the game feels virtually lag free for all players, because if it looks like a hit on your machine, it is a hit.

By contrast, SA architectures validate the messages on the server, and the messages are typically more of an "I tried to take this action" message. For example "I pressed fire", or "I moved forward". The server validates that the messages are legal, and then sends the appropriate response (or issues the action). The upside of this sort of architecture is that cheating becomes enormously more difficult, because there typically isn't a "I hit so-and-so for 400 points of damage" message, and even if there is, the server will take steps to validate that the message occurs in a valid and well-formed state. The downside is, of course, latency. This leads to some complex architecture to try and deal with the latency, generally called Client Prediction. I'll cover this topic in another post at some point in the future.

Team Fortress 2, along with other Valve FPS games based on the source engine, perform an interesting spin on client-server engine design. They try to pretend to be client authoritative, but are actually server authoritative. They do this by keeping a window backwards in time of up to a second (this is configurable) of where all the simulation objects have been. As said before, all clients must be running at some time slightly behind the leading edge (where the server is) due to latency (both rendering and network), even though this latency is very small. When a player takes an action (the most obvious of which is firing a weapon), he sends a timestamp to the server along with the "I've fired" message. The server gets the time stamp and essentially rolls the world backwards to that time to determine whether the player got a hit or not, and then sends the appropriate messages to all other clients. As long as the client and server agree on where objects are at a particular time, which is known as being in sync, then the client prediction is effectively completely accurate.

The effect of this logic is great for the person shooting, but can be a bit surprising for the person being shot. Imagine that you're running across the battlefield, duck behind a wall and think "I'm safe," only to find out a half-second later that you've been headshot. It's happen many-a-time to me and my friends, and it's always a little surprising.

The cheapest code is the code that doesn't exist

We have a common idiom in software: the fastest code is the code that doesn't execute. For non-nerds, this basically means that you want to structure your code so that you don't execute unnecessary computations.

As a corollary, I'll propose that every line of code you write (or every line of code you generate through C++ template facilities) is a line that costs you something in maintenance. Thus, the cheapest code is the code that doesn't exist.

It seems obvious, and it should be. The problem (imho) is that programmers are drinking the kool-aid. There's this myth that programming is a really hard, complicated problem. For some classes of programming, it's true. It is hard. Most programming is not hard, though. You think about a problem, you think about how you would sove the problem by hand and you speak another language to solve the problem in a more automatic way.

Unfortunately, it seems that oftentimes programmers overthink problems. They solve problems that don't exist or they try to build scaffolding around an otherwise simple problem. And that results in an unmaintainable blob. This is often done in the name of 'code reuse.' Debunking the notion that code reuse is always a good idea is a subject for another post, though.

Cheers.

Where are the books for experienced programmers?

Recently, I've been reading books on how to develop websites using "Web 2.0" techniques (basically AJAX). What I've noticed about these books--and even other coding books in my library--is that there is a serious lack of books for the experienced, well-disciplined programmer.

I honestly find it a little insulting that every book on C++ feels the need to re-explain to me APIE (Abstraction, Polymorphism, Inheritance, Encapsulation). As does every Java book. As does every Python book. Even books that claim to cater to the experienced or advanced programmer always recover these topics.

Of course, I've heard of projects like Rosetta Code, but that's not really what I'm looking for either. For one thing, there are only 87 examples, not even covering topics I'm really interested in. (An example of a topic I'd like to see is, "How to remove items from a collection based on a predicate?") Yes, it's wiki. Yes, I could go write the article myself. No thanks.

I guess what I really want to find are books that tell you the right way to perform tasks in a certain language, or why you would prefer one method over another. For example, in which situations should I prefer to use a vector instead of a map? (I'll give you a hint, even in key-value situations there are reasons to sometimes prefer a vector to a map).

For example, let's say I'm writing a new piece of C++ code. Should I use the stl? Almost always. Is there a good logging subsystem out there that I could use to avoid rewriting a new one? Are there any libraries I should avoid? Boost.

I don't need to relearn why I should write objects or what should go into an object. Tell me how to define an object, how to use inheritance, how abstraction is implemented. Give me actual, realistic costs of making design tradeoffs. For example, how much will it cost me to call a virtual function? Is there a way I can mitigate this inside of a single class, if I really know what the type of the class is?

I'm sure, one of these days, someone will get it. Till then, I'll just continue to suffer in silence.