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…

[youtube=http://www.youtube.com/watch?v=vaVhcnBiob0]

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!

7 thoughts on “Simple game architecture – part 2: playing with yourself

  1. Anonymous

    Are you planning on making a multiplayer-enabled debugger game? Or is this for something different?

    This was very informative for me…I haven’t messed with multiplayer in my game because it’s not a feature that would make sense, but it’s good to have some extra knowledge floating around.

    Reply
    1. Wilbefast

      Yeah, it’s the same game: right now I’m not experienced enough to do something too far off the beaten track, so the plan is to make a fairly standard top-down shooter (along the lines of Alien Shooter or Cyber Dogs) with a fairly bizarre setting (you play as a debugger).

      Thanks for the feedback TechRogue :-)

      Reply
  2. Anonymous

    Hey, nice overview over network problems, haven’t thought about that problem area that much, yet. Therefore I can’t nitpick anything on network, but I have some remarks on your data structure problems. I would agree that it could be worth it to look into maps, instead of vector or list. Could solve some of your ordering problems. std::map by the way is not a hash table, it’s an ordered map, mostly implemented as red-black-tree or something similar. So you don’t have constant look up time, but only o(log-n) look up guaranteed. In practice it probably won’t make a difference for you though, binary search for small n is pretty much bounded to a few steps. With ordered maps you also have the advantage of fast and deterministic iteration, but if you really need that extra look up speed you should look at std::unordered_map for a real hash table implementation( it’s not (yet) in every implementation of the STL, though). You should maybe also look into std::deque( if that’s not what you are using already), which I heard performs on par or better than std::vector for some purposes.
    On another note, I wouldn’t worry that much about memory usage of vector. I don’t know how big the objects you store in the containers are or how many there are, but as long as you don’t save raw images or other raw data in there, reserving more memory than you need up front shouldn’t lead to problems, shoudn’t be more than a few kilobytes. The platforms you are targeting should have enough memory and if you really get into problems you can optimize afterwards.

    Reply
    1. Wilbefast

      Either way it’s more “kosher” to uses indexes as handles than to use addresses. Something about covering up the low-level stuff with abstractions (and making it private). Okay, so I’m the only one working on this code, but it’s still a good reflex to have, and it pays off when you’re doing network stuff.

      The container for the instances needs if not to be accessible in O(1), be able to iterate through it in order at O(1), like a List. Not only does each Instance get updated, in order, 60 times per second, but this update often involves a collision check, which means running through the list again! That means up to 60*number_of_instances complete iterations per second.
      Actually, what’s really heavy is ray-casting: I’m replacing my “Block” object with a 2 dimensional array so I can perform collision checks in O(1).

      Thanks for the reply – very informative information about the maps :-) Just for you here is a sneak preview of some of the stuff I’ve been working on (with the aforementioned ray-casting – more on this soon):
      http://www.youtube.com/watch?v=ehG0TMo4h-c

      PS – The reason I’ve been using more vectors and arrays than lists or maps is because I’m not all that comfortable with iterators and templates – I’ve never studied them at uni so all I know I’ve learnt off the internet :-S

      Reply
      1. Anonymous

        Well I think, you can iterate through any of the standard containers in linear time using an iterator (and sometimes an index). The constant factors will be different though, but that may depend on compiler, target platform and use case(e.g. vector may outperform the others because it is contiguous in memory, etc).

        Seeing your remark about iterators and templates, maybe you should try to learn a little more basics like iterators, templates and RAII (smart pointers and automagical resource management, really powerful stuff) by reading a book. This site (http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) has a pretty comprehensive list of good books and also links to free web versions. I can also recommend to browse the other questions there from time to time, I learned a lot just by doing that when I need a break at work :)

        Interesting problem you have there with the raycasting. Seems you already have an idea how to solve it and I don’t really know all requirements you have so maybe you don’t need my ideas. Anyways, I would try to rule out as many objects as I can before iterating them all. Meaning trying to distinguish between objects that need to be checked and those that don’t and store them in separate lists( lists only for the raycasting), maybe by movable/immovable or all objects inside and outside a bounding box around the raycasting object. Well, good luck with that problem.

        Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>