Simple game architecture – part 2: playing with yourself

I just used a filty-sounding play on words for a title. I’m so original!

One of my many Gamemaker prototypes never to see the light of day was a multiplayer network-game called “Ninja versus Samurai”. The game never got very far for two important reasons: one, I mostly work alone, and two, I only own one computer.

The good news is that virtual machines solve problem number two: I can effectively emulate a second computer and play network games with myself (do you get the joke now?). I’ve been using VirtualBox to run XP and various Linux distributions for some time, for testing purposes and because I can’t be bothered setting up my system for native cross-compilation. Creating a multiplayer game is a lot more complicated than you might think however. It’s hard enough just getting your head around the damn thing…

To TCP or to UDP?

SFML provides a nice network interface for using either “TCP” or “UDP” for network programming. Cool! But wait, what’s the difference!? At times like this the temptation is to act like the perfect, mindless consumer and pick the one that sounds the most familiar. I mean, didn’t “Diablo II” use TCP/IP for LAN games? But we’re all geeks here so we’re going to look at things a little more carefully before we make the wrong choice. And let me make this clear, in no uncertain terms: TCP/IP is the wrong choice for an online action-game!

“Transmission Control” Internet Protocol (TCP/IP)

Rule number one of network gaming is to send as little information as possible and deduce the rest. For example, a ballistic projectile fired at a given speed in a given direction does not need to be synchronised: the clients can all do their own calculations to work out where the projectile will land. So, in theory, one need only synchronise the input from each user: this is, after all, the only thing that can’t be predicted. If we can manage this the rest should sort itself out. Right?

Trouble is, theory doesn’t get you very far in network programming. The internet is a rough place: packets get thrown around from router to router like row-boats in a hurricane, and often arrive out of order if they arrive at all. This is why TCP/IP was invented. This “Transmission Control Protocol” creates the illusion of a stable pipeline between two computers, by constantly checking if packets have arrived and putting them back into the right order. This means a lot of messages being sent backwards and forwards and a lot of waiting for them to arrive so they can be reassembled. But who cares: your packets are guaranteed to arrive in the same order as they were sent, with the specifics taken care of under the hood.

“User Datagram” Internet Protocol (UDP/IP)

The thing is, my game runs at 60 frames per second, so 60 times per second the player input is being read, the player character is being moved, and the AI monsters are reacting accordingly. This means if I only want to be sharing the user input I’ll need to be sharing 60 packets per second between the users. This is impossible, especially with TCP. Yep, you can’t have your cake and eat it too: like almost everything high-level, TCP sacrifices its speed for stability and ease-of-use, and speed is the one thing you really need for an action game.

This is why most of today’s online games use the “User Datagram Protocol” for synchronising clients. If TCP is the Java of internet protocols, UDP is the C (and IP itself is the Assembler). In other words, it’s low-level as all hell, providing no guarantee whatsoever of receipt or even correct order: you just pray and spray. UDP does have its advantages though, or rather its advantage: compared to TCP, it’s really fast!

For more on the TCP/UDP debate, here are a few sources I’ve used:

The illusion of synchronisation

UDP may be fast, but it’s not magic: it can’t make the network run any faster or carry any more of a load before it starts dropping packets. In other words, it’s just plain impossible share the users’ input 60 times per second. About 10 updates per second is more like it (this is apparently the amount of synchronisation that “Quake 3″ does), but that means 50 frames worth of input isn’t being synchronised. And besides, if we’re using UDP some of these packets are going to get lost or arrive in the wrong order! So much for the theory, looks like only sharing the input isn’t going to work out in the end…

In Quake 3: Arena… what’s “dead-reckoning”?

So how do action games like Quake 3 manage to stay in synch? Well, the simple truth is that they don’t: most online action-games provide only the illusion of synchronisation. Quake 3, for instance, runs at 60fps but only every 6th frame is in synch with the server: in between two updates the client makes an educated guess and the show goes on. For example, it can assume that a player will keep running in the direction they were running last time it heard from the server (this is called “dead-reckoning“). Then when the next update arrives the movement is smoothed out to avoid too much of an unsightly snap.

It’s all smoke and mirrors as usual, but in my view that makes it all the more incredible!

In practice… what to synchronise?

As you’ve probably guessed, we need to be sharing absolute values -such as the player character’s current health and their coordinates- rather than deltas (variations). And since the input generally makes changes relative to the current state of the environment, it pretty much counts as a delta. Hang on a minute though: we can’t be sharing all the absolute values of all the attributes of all our objects. We can’t even synchronise just those variables which have changed since our last update in case something gets lost (in which case the client will keep the incorrect value in memory until it changes again server-side).

Okay, everybody calm down. When you think about it, not everything needs to be synchronised. The walls aren’t ever going to move, and explosions and corpses can just do their thing client-side because they’re not affected by the players. Even ballistic projectiles, except those that home in, shouldn’t need to consult the server. So what are we left with? The player characters, obviously, but also anything controlled by the AI will need to be updated to remain in synch: agents will follow a “dead-reckoned” player character off course otherwise.

In the end doing things this way is actually a lot more efficient: sharing the positions of all the characters and agents might seem like a lot of packets, but remember that we’re only doing so 10 times per second rather than 60. Besides, if some information goes astray the problem will probably be corrected a 10th of a second later, and if things lag sometimes it’s a whole of a lot better than your clients going out of synch!

Annex: we still have a problem…

All this is work-in-progress, and I haven’t solved all the problems I’ve run up against, not even theoretically.

To Vector or to List?

Up till now I’ve stored my Instances (see part 1 of this series) in a “Linked List” (a chain of pointers that can be followed in either direction), because all I’ve ever done is to go through the container and update or draw each one in turn. The List is useful because you can easily add, remove or reorder it with having to shift everything across to fill the gaps or to make new ones. It also doesn’t use any more space than it needs, whereas a “Vector” (basically an array which automatically performs realloc() on itself when it needs more space) tends to reserve a lot more memory than necessary unless you control its size manually. Vectors offer one important advantage, random access, but up till now I haven’t needed it. I’ve directly used the Instances’ addresses as handles, and given them a pointer towards their link in the chain for easy navigation.

Trouble is, the address will not be the same on each machine, and updates are likely to arrive out of order. This means I need to be able to update a specific instance at any given time, and so I need to be able to randomly access elements in my container based on a handle. I’m thinking of using a Vector instead of a List, and using the index as a handle. I can then create a List of indexes to use as the draw order…

A TCP-UDP hybrid?

This way of doing things is problematic because there’s no guarantee of messages arriving in the same order as they were sent. Thus if Instances are added to the back of the container in the order in which they were created, it is entirely possible that two Instances ‘A’ and ‘B’ are stored [A,B] on the host and [B,A] on the client. This kind of quiproquo is be a bad thing for obvious reasons: the server and client would be talking with crossed-purposes, and updates would be applied to the wrong Instance.

Another more insidious problem is the possible lost of packets: if a new Instance is created it is vital for everybody to know about it! Otherwise the server will send updates for an Instance that doesn’t exist: at very best they’ll be applied to an entirely different Instance that happened to be created just afterwards, and at worse they’ll cause a segmentation fault instant crash.

TCP/IP would therefore seem like an attractive option for certain kinds of messages, but I’ve read that using both UDP and TCP at once is a bad idea. I may therefore need to implement some of the functionalities of TCP by hand. In other words, certain types of message will need to demand a reply, and until that reply is received the sender will need to persist in resending the message.

Another solution would be a Hash table of some sort (I’m already using std::Map for storing sf::Image and sf::Sound resources). I need to look back over my notes on data-structures to see what the advantages and disadvantages are.

Anyway, as you can see some things still need a lot of work. If you’re familiar with network programming, especially for games, any advice would be greatly appreciated!