Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

What's an elegant way to handle packet loss in a lockstep simulation peer-to-peer RTS where only player input data is sent over the network?

For example, let's say it's tick 1000 and player 1 sends a message saying that he is going to start attacking player 2 at tick 1002. All the other players receive the message except player 2 who is being attacked. Player 2 receives the message very late, at tick 1020. The other players have been running their simulation according to the fact that at tick 1002 player 1 started attacking player 2. And by tick 1010, player 2 is dead. Not only that, but by 1020 his entire dying animation sequence, according to the accurate game state, is already finished. He is completely dead.

Because the network protocol has a reliability layer which resends unacknowledged packets, player 2 eventually receives the message. He can replay the simulation from tick 1002 and arrive at the same game state: that he is dead at tick 1010 and his animation is already finished at 1020. The simulation must correct itself, moving player 2 back where he should be and setting the appropriate animation frame.

From a gameplay standpoint, what's the elegant solution here? Does player 2 immediately just jerk into a fully dead animation? Or does a little dying animation happen anyway (which would mean the game state might not truly be in sync)?

share|improve this question
1  
Not entirely relevant, but this is a good read on lockstep gamasutra.com/view/news/35929 there are also articles around about the networking architecture of Age of Empires and those of Supreme Commander 2 I think that go really in depth :). –  Roy T. Apr 21 '12 at 14:55
    
Yeah, good articles. I've read the Age of Empires article and the one you linked to (which is also available from the author's blog). Is there a different one about Supreme Commander 2? –  Nat Weiss Apr 21 '12 at 17:19
    
Here's the follow-up article: gamasutra.com/view/news/125983/… –  Nat Weiss Apr 21 '12 at 17:33

2 Answers 2

up vote 5 down vote accepted

For example, let's say it's tick 1000 and player 1 sends a message saying that he is going to start attacking player 2 at tick 1002.

That's not how it works. What is sent is what player 1's controls do. Click on location, drag to here, pressed key X, whatever. You don't send specific game state like "is attacking".

The idea being that, as long as everything is synched up, everyone will be getting the same data. So if a user clicks on location X at 1002, and there's an enemy unit there, then both sides will issue an attack order.

That's how P2P works.

Also, the message doesn't say how long it should take to complete; that should be implicitly understood on both sides. You pick a latency; if it starts not being fulfilled, both sides will know it and both sides will up the latency using a common algorithm.

Player 2 receives the message very late, at tick 1020.

If the latency of your game is 2 ticks, then Player 2 should never have advanced past tick 1002. It should have halted the game until it could synchronize with the other player. And Player 1 can't advance beyond tick 1002 until Player 2 tells him that he got Player 1's controller data.

P2P requires lockstep synchronization: each side only progresses to the next tick when it has gotten controller data for that tick from the other side. If it hasn't, then it can't get it. So each side not only needs to know what the next controller data is, but also how far the other side has advanced.

Unless you're in a LAN situation, or have really good netcode, you'll need to up your latency a bit to make this all work. Say, 75-100ms or so.

In general, the idea is this: controller data is tiny. Mouse positions on the map, clicks, buttons, etc. All very small. So you can afford to shove several "ticks" worth of data into a single packet. So each side's packet consists of:

  • How far that player has progressed in terms of "ticks".
  • The controller data for future actions.

Each side will continue to send the same controller data until the other side tells them that they've reached that "tick".

Let's say Player 1 is on tick 1000, and sends controller data for tick 1004. And this packet is lost. Next frame, on tick 1001, Player 1 will send the controller data for tick 1004 and 1005. That packet may gets through. Player 1 gets to 1002, but hasn't gotten an acknowledgement from the other guy about tick 1004. So he sends the controller data for ticks 1004, 1005, and 1006. Player 1 gets to 1003, and he receives acknowledgement that Player 2 got ticks 1004 and 1005. So this frame, Player 1 sends only the controller data for ticks 1006 and 1007. And Player 1 is cleared to advance through 1005.

This uses a 4-tick latency.

share|improve this answer
    
So if player 1 gets to tick 1004 without acknowledgement of his 1004 controller data (I'm thinking of a click or tap at a certain location), what then? Is the data discarded? Rolled over to the next 4 ticks? Or is this where the peers must pause to re-stablish the connection? –  Nat Weiss Apr 21 '12 at 9:33
1  
@NatWeiss: You stop. Until you get the go-ahead from the other player, you have to wait. So you sit there, possibly throwing up a dialog, and you wait. Lockstep P2P requires constant, frequent communication; if you lose touch, then you need to wait to reestablish. That's why most genres (FPS, MMOs, etc) don't use it. For RTS's, it offers the smallest possible round-trip latency (in optimal situations and with good code). And high-end RTS games need that level of networking. Also, they're usually 1v1. DotA and similar games use client/server because they have more people. –  Nicol Bolas Apr 21 '12 at 9:56
    
Also note that this means that your game update loop will only run as fast as your highest latency x2, so 15 updates per second is not uncommon. This would look weird so you separate your drawing/animations etc from the game update loop so they can run at a higher speeds (e.g. 60fps) –  Roy T. Apr 21 '12 at 14:52
    
@RoyT.: "Also note that this means that your game update loop will only run as fast as your highest latency x2" Nonsense. You can run your game update loop as much or as little as you want. It's all about the latency: if you have a 150ms latency, then you could have have 4 33ms ticks between the time the user issues a command and the time that command is carried out. Or you could have 3 50ms ticks. It's up to you (though I would suggest a latency counted in whole numbers of game frame time). –  Nicol Bolas Apr 21 '12 at 16:29
1  
@RoyT.: This is P2P, not client/server. It doesn't work that way. Latency in P2P exists for the network, but it also exists to ensure that each peer has a short buffer of commands to work with. Therefore, if there's a hiccup in the network, if a packet is lost or something, the game doesn't freeze up until the packet is received. In this way, the server can run faster than the latency, so long as every packet sent has multiple commands in it. So again no. –  Nicol Bolas Apr 21 '12 at 16:46

I have the same concern, and I have been thinking about it long time... I'm going to expose my thoughs though maybe not a good approach...

  1. Fixed Point Math: I think is a must to keep sync the simulation for every player.
  2. When there is an input at tick 1000, you should estimate the effective tick for that action... if you consider a ping of 200 ms and your tick duration is 30ms, the tick could be (2 + (200ms x 2) / 30) = 15.
  3. You send a message to every player proposing that input for the estimated tick at 1015
  4. Every player has to validate that action sending an acknoledgement message back.
  5. When the 1015 tick is reached, if any of the players has not been validated... stop the simulation... you have two options: try to validate again or Kick him.

if you don't want to stop simulation at first waiting for every ack, you have to be able to rewind and sync simulation to an older tick.

This can be acomplished in several ways, but I think the easier can be keep a copy of each object state for each tick in the last 2 seconds.

struct ObjectState {
    int Life;
    fint Pos;
    ...
}

class GameObject {
    const ObjectStateCount = 2000 / 30;  // 2 seconds / 30 ms tick
    ObjectState[] State = new ObjectState[ ObjectStateCount ];

    void Update(int PrevTick, int NextTick)
    {
       // Generate right states from PrevTick to NextTick, 
       // Usually one tick of difference
       int BaseTick = PrevTick;
       int Tick = -1;
       while (Tick!=NextTick) {
          Tick = (BaseTick+1) % ObjectStateCount;
          UpdateOneStep(BaseTick, Tick);
          BaseTick = Tick;
       }
    }

     void UpdateOneStep(int PrevTick, int NextTick) {
         State[NextTick].Pos = State[PrevTick].Pos + Velocity...
         ....
     }
}

This way you can easily revert the simulation to an old state where everyplayer were sync.

Every player that is sync with simulation will see the right animations, but player that is lossing packets will realize that is lagging because the inconsistencies in the animation. I think there is no matter with that.

share|improve this answer
    
Question about #4: why does every player have to validate the action? Can't the action just be checked for sanity and then accepted or rejected deterministically by all peers? –  Nat Weiss Apr 21 '12 at 9:21
    
if you validate the input action for every player sending an ack... you are sure that until that tick all is going right. –  Blau Apr 21 '12 at 9:25
    
Couldn't you validate that with occasional hashes of the game state? –  Nat Weiss Apr 21 '12 at 9:35
    
@NatWeiss you can't recover in that case. –  Roy T. Apr 21 '12 at 16:44
    
I think that a RTS should be deterministic, if you does not work with fixed math and you don't execute the input actions (click or keypress orders) at the same tick for every player, your game won't be deterministic, you have to realize that. –  Blau Apr 21 '12 at 17:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.