Network problems
From AlephWiki
Aleph One Networking
Return to History
Ian Rickard (Inio)
I'm not a game networking expert by any means - I haven't actually ever sat down and implemented the following algorithm, but I have done a helluvalotta thinking about it, so I might as well tell you all what I've come up with. Please forgive over-explanation in some parts, this is a minor rehashing of a message I almost posted to another forum a while back. This message does however assume some experience playing net-optimized games (such as QuakeWorld or UT). Also note that when referring to "the player" I may use the male pronouns, this is not a sexist statement, it is merely proper grammar (ask any grammarian), so don't flame me about it. Coders can skip down to "The Guts" (bottom of message) for the juicy parts.
If anyone has questions feel free to email me, or you can find me quite often on IRC on #macdev @ irc.openprojects.net (nickname inio).
PRELUDE: (skip this if you have a clue about how the net works) Given two nodes A and B on the internet, there is a reasonably predictable latency (time in transit) in getting a packet (a piece of information) from A to B, and vice versa. There is also the possibility that the packet could get lost along the way, and never make it to point B. When considering the average game player there is also a maximum bandwidth (maximum information transferred per second).
In comparison, a LAN is dramatically different. Where as latency on the Internet can be up to half a second (between two modems on opposite sides of the country), its perfectly reasonable to expect LAN latencies to be under 1/100th of a second. In addition the bandwidth is comprably unlimited - millions of bytes per second instead of thousands.
These limitations make playing LAN-optimized games such as Quake and Unreal (not their net-optimized counterparts) painfully slow over the internet. In an average-case situation it could take over a second to just fire your gun, and don't even think about trying to walk around a level with 1-second lag on everything you do.
REDUCING LAG: A while ago I got to be part of an argument on IRC about how QuakeWorld works. The first person to respond to the question of why there isn't lag said something along the lines of "well, it just does it right then and doesn't wait for the server to tell it to move. Its like the local echo in a Telnet client." In the short term this works ok, but it falls apart when you consider that EVERYONE is doing the same thing, and that the world might change around the player both in response to his, and other player's actions. For example imagine a map with a platform that lifts that player up to a higher level when stepped on. You walk up to the platform and barely beat another player's pawn to it, it lifts you up and drops you off on the top level, and the other player is just standing there seeming to run around like a lunatic below you while you grab up some items on the level the platform put you on. The problem is that on the other players computer it looks the same, because in his computer's version of the game he beat YOU to the platform.
This all happens because what you see as the "world" is actually an echo that took who-knows-how long to make it to your computer. It looks like the other player is behind you because your computer is showing you the world as it was when it left the other player's computer, half a second ago. Likewise his computer is showing him your pawn where it was half a second ago, when your computer sent the packet that his is just now receiving. This temporal discrepancy makes it possible for you to both beat each other to the platform, both be beaten to the platform, both run around collecting the items, and both run around like an idiot on the ground below. What you really need is a single point of authority. Sounds like a job for a central server, eh?
Indeed it is. Why not have one player's computer (hereby referred to as the server) say "this is the world", and all the other player's computers (the clients) just use that. This way the platform would only move when the server said it did, and you couldn't have the problem mentioned above. Well, there's the lag again, and this raises another issue - the server is going to need more bandwidth since it has to talk to all the clients at once. So let's require the server be on a T1 or some similar high-bandwidth/low-latancy line. This gets us closer to LAN-quality gameplay - it almost halves the lag for the clients, but its still quite noticeable (quarter second or so on an average modem). It also gives whoever is the server a gigantic advantage over everyone else, they have no lag in their actions. I'll cover solutions to this later.
So let's go back to the local echo solution again, only this time it waits for confirmation from the server before it changes anything about the world, and just to be sure lets have the server send a regular checkup of where the player's pawn is back to the client. This actually makes gameplay pretty reasonable, except that shooting at people is downright impossible, by the time your fire command gets to the server the player you're aiming at has already walked at least a couple more feet, changing your perfectly aimed missile barrage into a complete failure.
What would be best is to somehow be able to see into the future and know where everyone is (or at least thinks they are) right this instant. Not when their data gets to the server. Not when the server echoes it back to you. Now damnit! NOW!
Well, I see two solutions to this. The first involves investing several billion dollars in temporal wormhole research so I'll consider that one outside the scope of this project and only talk about the second - prediction. You may not know it, but I assure you you're doing this inside your head already, except to compensate for latency intentionally included in the game - the time it takes a rocket to get to its target for example. What we need to have the computer do is just figure out where everybody and every thing is going to be now, based on where they were when you last heard about them
THE ANSWER: Let's call the authoritative game universe on the server the "present". In this time context the simulation on the clients is actually run into the "future". They try to stay at a point in time such that actions by the user reach the server shortly before the server gets to the frame that the client was on when the user preformed the action. To make sure the action doesn't happen too early, the client sends an action to the server and includes the game frame "on or after" which the action should be preformed. Every once in a while (once per second or so) the server will send back the average, min, and max offset between what frame the client asked for something to happen on, and what frame the server received the message on, back to the client so it can tweak how far in the future it is to present the most accurate world to the user.
All that stuff, as a wise man once said, is easier said than done. One of the most difficult components is the future prediction, which is complicated by several issues. Predicting the future isn't really that hard, if someones running forward just keep them running forward, fly projectiles through the air like they should, do stuff like it should, really not that hard. The hard part is that this has to be recalculated, for the whole lag period, every single time the server sends an update on the slightest part of the picture. You can ease this burden in one of two ways - either have the server calculate it (assume the server is a frick'n fast box) and send appropriate versions to clients as per their request based on lag, or reduce the complexity of the simulation in the client, by either reducing the simulation frame rate (1/4 of game framerate should be able to produce a decent simulation) or only calculating the parts of the world the player can see.
IDEAS FOR IMPROVEMENT: If bandwidth usage becomes an issue, have server only tell client about objects it can see (I know for a fact that QW did this). Also if you're sending commands from the client as plain text, consider establishing a binary dictionary at connect time, possibly using a modified Huffman coding to reduce common commands to just a few bits. To increase player position simulation accuracy, have clients share outgoing commands with each other. This way the other clients will reieve that information a little before they would if they just got the echo from the server. To avoid cheating only share with reliable, consistent clients who are sharing with you (check commands with actual data recieved from server).
CONCERNS: Is this patented by someone? ID? Cheating becomes easy if you have the client sending too much authoritative info to the server (such as absolute position).
