home *** CD-ROM | disk | FTP | other *** search
/ Chip 2003 August / Chip_2003-08_cd1.bin / oddech / maelstrom / maelstrom.exe / Maelstrom / Docs / Technical_Notes-v2.0 < prev   
Text File  |  1999-12-07  |  7KB  |  159 lines
  1.  
  2. ---
  3. Note:
  4. A great deal of technical development between the Technical_Notes-v1.1
  5. and v2.0 is not documented.  This document starts at the beginning of
  6. the addition of networking to Maelstrom, and finishes with the final
  7. networking algorithm used.
  8. (See Networking.Paper for a more organized description)
  9. ---
  10.  
  11. The hardest thing about this networking project is synchronization.
  12.  
  13. My initial feeling was to go with TCP for sending synchronization packets,
  14. but running a real-time game at 30 frames per second, I can't have the
  15. slow-start algorithm after a packet loss and the other overhead of TCP
  16. would be wasteful.
  17.  
  18. My thought was to take advantage of the guaranteed delivery that TCP
  19. offers, since on a 640x480 screen, even one missed frame could have
  20. significant reprocussions in terms of game state.
  21.  
  22. I also need the speed of UDP.  Ideally, this game would be able to run
  23. over 14,400 bps modem speeds.  Using PPP, this averages between 600
  24. and 900 cps, so including IP headers, we would want no more than 600
  25. bytes of traffic every second.  Using 1 byte synchronization packets,
  26. 30 frames per second would require in (1+U+20)*30 bytes throughput
  27. every second. (Where U = #bytes in a UDP header)  That's at least
  28. 630 bytes per second, just going one way.  Guaranteed delivery of
  29. synchronization packets requires at least an ack, nearly doubling
  30. the necessary throughput.
  31.  
  32. The only reason we want such tight synchronization is so that
  33. keypresses arrive on the frame that they need to, and that frame
  34. is the same on every machine in the game.  Since key-presses
  35. average about 10 per second, we can probably get away with only
  36. 10 sync packets every second (1 every 3 frames).  We still want
  37. a granularity of a keyboard poll every frame, but we can now do
  38. lazy acks and do guaranteed delivery on 1 sync per second and
  39. each keystroke.
  40.  
  41. Well, the problem is not if a keystroke is sent to a machine
  42. that is slow, but if a keystroke is sent to a machine that is
  43. fast.  If a fast machine zips through the frames, then a keystroke
  44. at a particular frame will get missed or late, both of which resulting
  45. in corrupt games.  Imagine pressing the turn key on your machine,
  46. pivoting round, and pressing the fire key.  On your machine you
  47. hit the asteroid next to you, and on another fast machine, you
  48. crashed before you were able to hit the fire key.  Instability:
  49. You are dead on one machine, and live on another. :-)
  50.  
  51. We need synchronization on each frame (actually on each key poll,)
  52. to prevent keystrokes coming in a frame or two too late.
  53.  
  54. Keystrokes can ride piggyback on sync frames, so there is little
  55. overhead for that...
  56.  
  57. The alternative is to poll the keyboard every other frame, and only
  58. send sync signals every other frame as well.
  59. ... That doesn't work very well... you need the every frame key poll
  60. to respond quickly while firing.
  61.  
  62.  
  63. Stop and wait?   -- not exactly. :)
  64.  
  65. The conclusion?  Networked Maelstrom won't run over the modem (200 ms
  66. ping times are too slow) and we will use UDP with stop-go protocol
  67. for real-time speed.
  68.  
  69. The next phase is designing a good handshake protocol.
  70. The plan:
  71.     When a new game starts... The checksum server (player 1)
  72.     will send a checksum to all other players.  Each other player
  73.     will, when it receives it, send back the same message.
  74.     How do we guarantee delivery?  We don't, but if the reply
  75.     doesn't make it, the first player will keep sending the NEW_GAME
  76.     packet to that player, and that player will respond, even though
  77.     it's waiting for the first frame packet.
  78.  
  79.  
  80. Another possible dropped packet condition is as follows:
  81.  
  82.     Player 1 sends a frame packet to itself and Player 2.
  83.     Player 2 sends a frame packet to itself and Player 1.
  84.     Player 2 receives the frame packet from Player 1, and itself.
  85.     Player 1 only receives the packet from itself.
  86.     Player 2 continues to the next frame
  87.     Player 1 retransmits the packet from its current frame.
  88.  
  89. Player 2 is now deadlocked waiting for the packet for frame +1
  90. while Player 1 is still asking for the packet for frame +0.
  91. The solution is for each player to keep the it's last frame
  92. packet cached, so that if it receives a request for the last
  93. frame, it can resend the previous frame's packet, and the game
  94. can continue.
  95.  
  96. The players can only be one frame off, because each player does
  97. not continue to the next frame until all players have sent the
  98. frame packet for the current frame.  If one player is one frame
  99. behind, all other players will wait for it.
  100.  
  101. If packets arrive out of order, then an older retransmission can
  102. arrive after a frame has been successfully negotiated.  In this
  103. case, the receiver will send a response if the packet is from
  104. the previous frame, and it will be ignored by the sender, who is
  105. a frame ahead.  Thus consistency is preserved without initiating
  106. packet storms of retransmissions and acks.
  107.  
  108. Note that this configuration really is peer-to-peer, and the only
  109. time one player is a "server" is when the first player sends the
  110. initial level, number of lives, and random seed to all other players.
  111.  
  112. I had a great problem with lock-stepping using the above method.
  113. Imagine both players furiously sending frame packets at each other,
  114. and advancing to the next frame.  Then:
  115.  
  116.     Player 1  (frame 10)        Player 2  (frame 10)
  117.         10 -->                <-- 10
  118.         dropped packet
  119.     Player 1  (frame 10)        Player 2  (frame 11)
  120.         wait                <-- 11
  121.         get 11, timeout
  122.     Player 1  (frame 10)        Player 2  (frame 11)
  123.         10 -->                <-- 10 (cached)
  124.     Player 1  (frame 11)        Player 2 (frame 11)
  125.         11 -->                wait
  126.     Player 1  (frame 11)        Player 2 (frame 12)
  127.         wait                <-- 12
  128.         get 12, timeout
  129.  
  130. This goes on, repeating, as the two players advance frames in lock-step,
  131. one frame per timeout.
  132.  
  133. The solution is for Player 1 to immediately resend the sync packet for
  134. it's frame if it receives a packet for the next frame.  That way it doesn't
  135. have to time out.  If it caches the packet for the next frame, the next
  136. time around, it just sends the packet for the next frame, and advances
  137. immediately.  The two players are now back in sync.
  138. This assumes that few packets will be dropped or otherwise lost.
  139. This seems to be a valid assumption.  Even over a 32.6K link to 
  140. Australia, very few packets were lost and though the game was unplayably
  141. slow, dropped, lost, and timed out packets were few and far between.
  142.  
  143. The new senario:
  144.  
  145.     Player 1  (frame 10)        Player 2  (frame 10)
  146.         10 -->                <-- 10
  147.         dropped packet
  148.     Player 1  (frame 10)        Player 2  (frame 11)
  149.         get 11, cache, 10 -->        <-- 11
  150.     Player 1  (frame 10)        Player 2  (frame 11)
  151.         get 10                <-- 10 (cached)
  152.     Player 1  (frame 11)        Player 2  (frame 11)
  153.         11 -->                get 11
  154.     Player 1  (frame 12)        Player 2 (frame 12)
  155.         12 -->                <-- 12
  156.  
  157. The players are now synchronized again.
  158.  
  159.