Networking problems in games

Question

I am looking for networking designs and tricks specific to games. I know about a few problems and I have some partial solutions to some of them but there can be problems I can't see yet. I think there is no definite answer to this but I will accept an answer I really like. I can think of 4 categories of problems.

Bad network

The messages sent by the clients take some time to reach the server. The server can't just process them FCFS because that is unfair against players with higher latency. A partial solution for this would be timestamps on the messages but you need 2 things for that:

• Be able to trust the clients clock. (I think this is impossible.)
• Constant latencies you can measure. What can you do about variable latency?

A lot of games use UDP which means messages can be lost. In that case they try to estimate the game state based on the information they already have. How do you know if the estimated state is correct or not after the connection is working again?

In MMO games the server handles a large amount of clients. What is the best way for distributing the load? Based on location in game? Bind a groups of clients to servers? Can you avoid sending everything through the server?

Players leaving

I have seen 2 different behaviours when this happens. In most FPS games if the player who hosted the game (I guess he is the server) leaves the others can't play. In most RTS games if any player leaves the others can continue playing without him. How is it possible without dedicated server? Does everyone know the full state? Are they transfering the role of the server somehow?

Access to information

The next problem can be solved by a dedicated server but I am curious if it can be done without one. In a lot of games the players should not know the full state of the game. Fog-of-war in RTS and walls in FPS are good examples. However, they need to know if an action is valid or not. (Eg. can you shoot me from there or are you on the other side of the map.) In this case clients need to validate changes to an unknown state. This sounds like something that can be solved with clever use of cryptographic primitives. Any ideas?

Cheating

Some of the above problems are easy in a trusted client environment but that can not be assumed. Are there solutions which work for example in a 80% normal user - 20% cheater environment? Can you really make an anti-cheat software that works (and does not require ridiculous things like kernel modules)?

I did read this questions and some of the answers http://stackoverflow.com/questions/901592/best-game-network-programming-articles-and-books but other answers link to unavailable/restricted content. This is a platform/OS independent question but solutions for specific platforms/OSs are welcome as well.

Answer 1

Thinking cryptography will solve this kind of problem is a very common and very bad mistake: the client itself of course have to be able to decrypt it, so it is completely pointless. You are not adding security, you're just adding obscurity (and that will be cracked).

Cheating is too game specific. There are some kind of games where it can't be totally eliminated (aimbots in FPS), and some where if you didn't screw up will not be possible at all (server-based turn games).

In general network problems like those are deeply related to prediction which is a very complicated subject at best and is very well explained in the famous Valve article about it.

Answer 2

Bad network

Players with high latency should buy a new modem. I don't think its a good idea to add even more latency because one person in the game got a bad connection. Or if you mean minor latency differences, who cares? You will only make things slower and complicated if you refuse to FCFS.

Cheating: aimbots and similar

Can you really make an anti-cheat software that works? No, you can not. You can't know if they are running your program or another program that acts like yours.

Cheating: access to information

If you have a secure connection with a dedicated server you can trust, then cheating, like seeing more state than allowed, should be impossible.

There are a few games where cryptography can prevent cheating. Card games like poker, where every player gets a chance to 'shuffle the deck'. Details on wikipedia : Mental Poker.

With a RTS or FPS you could, in theory, encrypt your part of the game state. Then send it to everyone and only send decryption keys for the parts they are allowed to see or when they are allowed to see it. However, I doubt that in 2010 we can do this in real time.

For example, if I want to verify, that you could indeed be at location B. Then I need to know where you came from and when you were there. But if you've told me that before, I knew something I was not allowed to know. If you tell me afterwards, you can tell me anything you want me to believe. You could have told me before, encrypted, and give me the decryption key when I need to verify it. That would mean, you'll have to encrypt every move you make with a different encryption key. Ouch.

If your not implementing a poker site, cheating won't be your biggest problem anyway.

Answer 3

The server can't just process them FCFS because that is unfair against players with higher latency.

Yes it can. Trying to guess exactly how much latency someone has is no more fair as latency varies.

In that case they try to estimate the game state based on the information they already have. How do you know if the estimated state is correct or not after the connection is working again?

The server doesn't have to guess at all - it knows the state. The client only has to guess while the connection is down - when it's back up, it will be sent the new state.

In MMO games the server handles a large amount of clients. What is the best way for distributing the load? Based on location in game?

There's no "best way". Geographical partitioning works fairly well, however.

Can you avoid sending everything through the server?

Only for untrusted communications, which generally are so low on bandwidth that there's no point.

In most RTS games if any player leaves the others can continue playing without him. How is it possible without dedicated server? Does everyone know the full state?

Many RTS games maintain the full state simultaneously across all machines.

Some of the above problems are easy in a trusted client environment but that can not be assumed.

Most games open to the public need to assume a 100% cheater environment.