I liked the discussion of transmitting game state for network play. Quick summary: Doom sent differences of state, which had to be received and therefore acknowledged. Quake sent the whole game state each time, but compressed, so it wouldn't matter if a transmission was lost.
Neither approach seems optimal from an information theory point of view. The Doom approach needs feedback, but communicating at the optimal rate of noisy channel doesn't need feedback. The Quake approach sends the game state redundantly, but across time simply repeats information, and repetition codes aren't optimal.
It could turn out that in this application the Quake approach is best, because for latency reasons it might not be possible to send long enough blocks for Shannon's theory to apply. The Quake approach is also nice and simple. However, here's the approach I have in mind: send the stream of deltas protected by a code that can cope with some of them being erased, such as a Digital Fountain Code [1]. Each message would contain deltas stored slightly redundantly and XORed with previous deltas. If we have all previous deltas then we are set, otherwise we'll have to wait for another packet or two before we can infer the deltas, but we don't need to bother telling the receiver that we lost a packet.
EDIT: In response to replies by VMG and JoachimSchipper: I didn't mean to suggest they should have done anything differently. It worked well enough, and they got it out the door; agreed! I just think it's an interesting puzzle to think about.
Note that fountain codes are very, very patent-protected by Luby et al. Five years ago I came across literature on rateless codes, which are digital fountain codes that allow practically infinite encoding, or a practically infinite stream of data from which the original could be reconstructed. One really promising type of rateless code was online codes, which required O(1) time to generate a single block and O(n) time to decode a message of length n, which was much better than the LT rateless codes that came before it. (The paper can be found at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12....)
I wrote up a Java implementation in my free time, and it worked well and was quite fast. I pinged the authors of the paper, asking if I could open-source it, because I came across a web site with their names on it that seemed like they were going to commercialize the idea. They replied that they had abandoned the idea of online codes because, even though their approach was faster than all other coding schemes, it still violated patents held by Luby and his company Digital Fountain, which has since been acquired by Qualcomm. That was a bummer, because I thought the online codes paper was very elegant, and the implementation was quite simple.
Their arguments suggest UDP with no acknowledgements. If they had needed to send more data they might have needed slightly more sophisticated error correcting codes than repetition codes. Doing that and keeping the latency low could be a challenge however.
You probably can get lost in choosing and implementing the optimal algorithm in every aspect of the game. Sometimes you just have to go with the sub-optimal to get it out of the door.
I agree Luby's codes came after Quake. Although other codes for the erasure channel did exist, and the important ideas for the class of scheme I'm talking about were known. That wasn't meant to be my point though. I was just thinking about the puzzle, rather than what "should" have been done.
I don't follow the final parenthetical comment: the point of the coding is precisely so that the server can recover all information regardless of packet loss so that it can keep going. If a client disappears then the server acts as if it disappeared at the last successfully decoded delta (it has to have a means to deal with clients disappearing regardless).
Regarding my parenthetical comment: the server can ignore input that was not received in time, block while waiting for input, or try to "rewind" the world. The first is lossy, the second leads to the same hiccups as reliable transmission protocols (although the effect may be smaller), and the third leads to "paradox" (and lots of complexity). There are no really good solutions here.
I agree that such codes are interesting, though - I really should know more coding theory...
Thanks for the pointer to fountain codes. Though, since I'm working on a networked game that works over websockets, this is basically something I wouldn't bother with since websockets are TCP, not UDP, and as such they are guaranteed delivery and correct order of arrival. I realize TCP vs UDP is something of a debate in game networking, but it's a simple solution here. Let the protocol do the work and just send (compressed) deltas. I suppose this is equivalent to the Doom way.
A comparison of transport protocols to consider if anyone reading this ever decides to try their hand at implementing such a quasi-reliable UDP-based protocol:
eru makes a really good point, and I suddenly feel much less confident. My intention was to sketch the idea for a protocol that was reliable (with very high probability, just like anything in the real world). So, to repeat the argument: if there's some information we need reliably, whatever cunning thing we layer on top of UDP, we're just reimplementing what TCP does. It seems unlikely we can do better than TCP unless we're doing something very problem specific.
I guess the argument is that a scheme based on UDP can have very low latency a lot of the time, only occassionally stalling while waiting for more data. Whereas TCP, which needs acknowledgements and to keep packets in order, has a uniformly high latency. For this particular type of application, the tradeoffs are different from typical internet use?
TCP is kind of the full feature kid on the block. You might do better making up a protocol that has what you want and skip on the rest. There are real latency costs for parts of TCP that a game will never use i.e. Nagle's algorithm(sure you can turn that one off but every thing has its cost and you can't turn off everything you don't need in TCP).
I am surprised how infrequently RTP comes up in these conversations. Something close to RTP seems like it would be ideal for games.
> For this particular type of application, the tradeoffs are different from typical internet use?
Absolutely. The value of any one packet is fairly low, you can interpolate the player's path, hell, maybe no one else was looking at him at the time. But with TCP, you basically stop the world for a couple roundtrips to make sure you have that packet, so all the packets you received after the original drop and before the retransmission are no longer useful, and you have to drop them too.
It's also worth noting that TCP does /not/ have a uniformly high latency, it does the sawtooth thing. In other words, if Level3 decides they're going to shovel a bunch of your ISP's traffic into the bitbucket for a second, your packets have been dropped, the server is going to wait until it has a complete set of packets, and your TCP implementation has decided to throttle the number of packets you can send to catch up.
> So, to repeat the argument: if there's some information we need reliably, whatever cunning thing we layer on top of UDP, we're just reimplementing what TCP does. It seems unlikely we can do better than TCP unless we're doing something very problem specific.
We can do much better than TCP. We just have to weaken the reliability requirement. And like you say, in the real world, that can go quite a long way, without actually being much weaker than TCP.
Apart from the timelines, my impression is that implementing fountain codes has some IP issues. Also, there is some code complexity in getting them implemented correctly (as hard to get right as paxos). Anyone know a game that used these? Any body have first hand experience?
If considering using fountain codes, I would definitely want to check out the IP issues; there are certainly some patents in that space. For the application being discussed, fountain codes wouldn't be an exact fit anyway. I pointed to them because the ideas used in fountain codes are fantastic, and it might be possible to do something with that flavor.
(I too would love to hear first-hand experience of anyone who's used this type of code.)
Quake really wasn't playable over the internet until the QuakeWorld "extension" came along.
It used prediction and delta codes, and actually ran the server and client (and still runs) at 72 fps, no other online multiplayer game that I know of has done it ever since. This means if you have ping 14 milliseconds, you really have ping 14 milliseconds.
If you've played Quakeworld with solid 72 fps (this only really became possible many many years after its release) and a good mouse, monitor and decent internet connection, all other games after that feel like clunky puppet shows where you can only vaguely affect the end result. That's the reason why it's still being played. It really feels like you're on the server.
The game also enables amazing moves that can be pulled off by sufficiently skilled players - there is no roof for domination abilities, There can be tens of levels of players that can crush anyone below them easily. This also means that it can be pretty newbie hostile at the same time. But it's pure bliss when dueling with someone your own level.
The game companies assumed (probably correctly) that the average consumer never pays attention to good control or stratospheric skill potential, and rather pays for the resolution, level of detail and nice colors as well as newbie entry easiness.
So, Quakeworld was and probably will always be a one off with no peers, a raw formula one in the world of soft SUV:s.
The gameplay is brutal. You have to put things in context. At the time Quake was designed rocket jumping was an unknown concept. Using the mouse was a controversial and new idea (you had to enable +mlook!). As such the game doesn't fit the mold of a refined and balanced FPS. Everything is raw and frenetic. You have to master rockets and lightning gun, you have to exercise strong map control, you have to aim and fire faster than any other FPS before or since. There's no weapon balance to allow for specialists, or forgiving maps to let you stage a comeback. They'll never make another game like it.
Fully agreed. I was hooked on expert mod ctf (with the offhand grappling hook) for quite a while. I've never found another game that approaches that pace of gameplay.
Valve's Source engine (and GoldSrc, HL1), which itself is heavily based on the Quake 3 engine, uses delta compression and prediction as well. This is part of what made Counter-Strike such a popular game, and still is today. Especially in the competitive gaming world.
Valve licensed Quake code from id, and GoldSrc/Source are descended from that. There is no Quake2 or Quake3 code, the improvements over Quake are pure Valve.
QW is the Starcraft of first-person shooters. It's so much fun to duel (or 2on2 or 4on4) that pro players for other games still enjoy coming back to qw, where many of them started. I would say it's a beautiful game.
It also has a ton of fanatical players/mappers/coders hacking on weekends, making their own custom additions to the game.
That's still a client-server model, only one of the clients happens to be the server as well. Quake 1 worked that way, too. The Halo games use a client-server model but support transparent host migration if the original host quits mid-game. That's really tricky to get working even halfway decently!
The Call of Duty games all ultimately descend from the Quake 3 code base, so I wouldn't be too surprised if MW2 and BLOPS were still using a recognizable variation of the networking model described in the article by Brian Hook in my link.
Neither approach seems optimal from an information theory point of view. The Doom approach needs feedback, but communicating at the optimal rate of noisy channel doesn't need feedback. The Quake approach sends the game state redundantly, but across time simply repeats information, and repetition codes aren't optimal.
It could turn out that in this application the Quake approach is best, because for latency reasons it might not be possible to send long enough blocks for Shannon's theory to apply. The Quake approach is also nice and simple. However, here's the approach I have in mind: send the stream of deltas protected by a code that can cope with some of them being erased, such as a Digital Fountain Code [1]. Each message would contain deltas stored slightly redundantly and XORed with previous deltas. If we have all previous deltas then we are set, otherwise we'll have to wait for another packet or two before we can infer the deltas, but we don't need to bother telling the receiver that we lost a packet.
[1] http://en.wikipedia.org/wiki/Fountain_code — but a much better resource is chapter 50 of http://www.inference.phy.cam.ac.uk/mackay/itila/book.html
EDIT: In response to replies by VMG and JoachimSchipper: I didn't mean to suggest they should have done anything differently. It worked well enough, and they got it out the door; agreed! I just think it's an interesting puzzle to think about.