<story><title>Michael Abrash on Quake: &quot;Finish the product and you’ll be a hero.&quot;</title><url>http://www.bluesnews.com/abrash/chap70.shtml</url></story><parent_chain><item><author>imurray</author><text>I liked the discussion of transmitting game state for network play. Quick summary: Doom sent differences of state, which &lt;i&gt;had&lt;/i&gt; to be received and therefore acknowledged. Quake sent the whole game state each time, but compressed, so it wouldn&apos;t matter if a transmission was lost.&lt;p&gt;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&apos;t need feedback. The Quake approach sends the game state redundantly, but across time simply repeats information, and repetition codes aren&apos;t optimal.&lt;p&gt;It could turn out that in this application the Quake approach &lt;i&gt;is&lt;/i&gt; best, because for latency reasons it might not be possible to send long enough blocks for Shannon&apos;s theory to apply. The Quake approach is also nice and simple. However, here&apos;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&apos;ll have to wait for another packet or two before we can infer the deltas, but we don&apos;t need to bother telling the receiver that we lost a packet.&lt;p&gt;[1] &lt;a href=&quot;http://en.wikipedia.org/wiki/Fountain_code&quot; rel=&quot;nofollow&quot;&gt;http://en.wikipedia.org/wiki/Fountain_code&lt;/a&gt; — but a much better resource is chapter 50 of &lt;a href=&quot;http://www.inference.phy.cam.ac.uk/mackay/itila/book.html&quot; rel=&quot;nofollow&quot;&gt;http://www.inference.phy.cam.ac.uk/mackay/itila/book.html&lt;/a&gt;&lt;p&gt;EDIT: In response to replies by VMG and JoachimSchipper: I didn&apos;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&apos;s an interesting puzzle to think about.</text></item></parent_chain><comment><author>shadowmatter</author><text>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 &lt;a href=&quot;http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.8894&amp;#38;rep=rep1&amp;#38;type=pdf&quot; rel=&quot;nofollow&quot;&gt;http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12....&lt;/a&gt;)&lt;p&gt;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.</text></comment>
<story><title>Michael Abrash on Quake: &quot;Finish the product and you’ll be a hero.&quot;</title><url>http://www.bluesnews.com/abrash/chap70.shtml</url></story><parent_chain><item><author>imurray</author><text>I liked the discussion of transmitting game state for network play. Quick summary: Doom sent differences of state, which &lt;i&gt;had&lt;/i&gt; to be received and therefore acknowledged. Quake sent the whole game state each time, but compressed, so it wouldn&apos;t matter if a transmission was lost.&lt;p&gt;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&apos;t need feedback. The Quake approach sends the game state redundantly, but across time simply repeats information, and repetition codes aren&apos;t optimal.&lt;p&gt;It could turn out that in this application the Quake approach &lt;i&gt;is&lt;/i&gt; best, because for latency reasons it might not be possible to send long enough blocks for Shannon&apos;s theory to apply. The Quake approach is also nice and simple. However, here&apos;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&apos;ll have to wait for another packet or two before we can infer the deltas, but we don&apos;t need to bother telling the receiver that we lost a packet.&lt;p&gt;[1] &lt;a href=&quot;http://en.wikipedia.org/wiki/Fountain_code&quot; rel=&quot;nofollow&quot;&gt;http://en.wikipedia.org/wiki/Fountain_code&lt;/a&gt; — but a much better resource is chapter 50 of &lt;a href=&quot;http://www.inference.phy.cam.ac.uk/mackay/itila/book.html&quot; rel=&quot;nofollow&quot;&gt;http://www.inference.phy.cam.ac.uk/mackay/itila/book.html&lt;/a&gt;&lt;p&gt;EDIT: In response to replies by VMG and JoachimSchipper: I didn&apos;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&apos;s an interesting puzzle to think about.</text></item></parent_chain><comment><author>VMG</author><text>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.</text></comment>