5 ms·

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 acknow

by imurray 15y ago

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. [1] http://en.wikipedia.org/wiki/Fountain_code 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 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.

ehsanu1 15y ago
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.
- eru 15y ago
  Yes, it's for the protocol to worry about. imurray basically described a protocol to build on top of UDP that has slightly weaker guarantees than TCP. (Or does the construction that immurray described benefit from domain knowledge about the underlying data?)
  - imurray 15y ago
    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?
    - krakensden 15y ago
      > 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.
    - eru 15y ago
      > 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.
JoachimSchipper 15y ago
I'm not an expert, but don't you have the timeline wrong? E.g. Luby's "LT codes" is from 2002, well after Quake's 1996 launch date. Honestly, though, I think the Quake guys were going for - and achieved - "good enough". (Also, coding obviously doesn't work for client -> server communication, since the server has to keep going even if packets are lost.)
- imurray 15y ago
  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).
  - JoachimSchipper 15y ago
    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...
VMG 15y ago
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.
swah 15y ago
Haven't the newer games had advances in this area?
- psykotic 15y ago
  Quake 3 sent the game state update to clients as a delta relative to the last state they had acknowledged receiving: http://trac.bookofhook.com/bookofhook/trac.cgi/wiki/Quake3Networking http://trac.bookofhook.com/bookofhook/trac.cgi/wiki/Quake3Ne... On a different end of the spectrum there is Unreal's replication model, still used today by all UE3-based games: http://udn.epicgames.com/Three/NetworkingOverview.html http://udn.epicgames.com/Three/NetworkingOverview.html
  - swah 15y ago
    I remember that MW2 used a different model where one of the players was the host. That was great for folks away from servers, like me - until the guy decided to disconnect, when a new host had to be chosen.
    - psykotic 15y ago
      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.
- Gravityloss 15y ago
  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.
deleted 15y ago
[deleted]
rubinelli 15y ago
You'll probably like another interesting article about a similar problem, the network code of X-Wing vs. TIE-Fighter and how they handled extremely high latency and packet drop rates: http://www.gamasutra.com/view/feature/3374/the_internet_sucks_or_what_i_.php http://www.gamasutra.com/view/feature/3374/the_internet_suck...
- imurray 15y ago
  I did. Thanks! 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.
  - JabavuAdams 15y ago
    You might like RakNet: http://www.jenkinssoftware.com/ http://www.jenkinssoftware.com/ Whenever I think "I should roll my own semi-reliable protocol..." I look there first.
shadowmatter 15y ago
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.8894&rep=rep1&type=pdf 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.

by imurray 15y ago

ehsanu1 15y ago

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.

eru 15y ago
Yes, it's for the protocol to worry about. imurray basically described a protocol to build on top of UDP that has slightly weaker guarantees than TCP. (Or does the construction that immurray described benefit from domain knowledge about the underlying data?)
- imurray 15y ago
  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?
  - krakensden 15y ago
    > 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.
  - eru 15y ago
    > 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.

JoachimSchipper 15y ago

I'm not an expert, but don't you have the timeline wrong? E.g. Luby's "LT codes" is from 2002, well after Quake's 1996 launch date. Honestly, though, I think the Quake guys were going for - and achieved - "good enough". (Also, coding obviously doesn't work for client -> server communication, since the server has to keep going even if packets are lost.)

imurray 15y ago
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).
- JoachimSchipper 15y ago
  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...

VMG 15y ago

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.

swah 15y ago

Haven't the newer games had advances in this area?

psykotic 15y ago
Quake 3 sent the game state update to clients as a delta relative to the last state they had acknowledged receiving: http://trac.bookofhook.com/bookofhook/trac.cgi/wiki/Quake3Networking http://trac.bookofhook.com/bookofhook/trac.cgi/wiki/Quake3Ne... On a different end of the spectrum there is Unreal's replication model, still used today by all UE3-based games: http://udn.epicgames.com/Three/NetworkingOverview.html http://udn.epicgames.com/Three/NetworkingOverview.html
- swah 15y ago
  I remember that MW2 used a different model where one of the players was the host. That was great for folks away from servers, like me - until the guy decided to disconnect, when a new host had to be chosen.
  - psykotic 15y ago
    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.
Gravityloss 15y ago
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.

deleted 15y ago

[deleted]

rubinelli 15y ago

You'll probably like another interesting article about a similar problem, the network code of X-Wing vs. TIE-Fighter and how they handled extremely high latency and packet drop rates: http://www.gamasutra.com/view/feature/3374/the_internet_sucks_or_what_i_.php http://www.gamasutra.com/view/feature/3374/the_internet_suck...

imurray 15y ago
I did. Thanks! 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.
- JabavuAdams 15y ago
  You might like RakNet: http://www.jenkinssoftware.com/ http://www.jenkinssoftware.com/ Whenever I think "I should roll my own semi-reliable protocol..." I look there first.

shadowmatter 15y ago

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.8894&rep=rep1&type=pdf 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.