Hacker News Reader

Comment by mbbutler | Hacker News Reader

How does UDP work if you're also using delta compression? I would naively expect that the accumulation of lost diff packets over time would cause game state drift among the clients.

View on HN

The simplest way I've done it: say client and server start on tick 1, and that's also the last acknowledgement from the client that the server knows about. So it sends a diff from 1 to 2, 1 to 3, 1 to 4, until server gets an ack for tick 3, for example. Then server sends diffs from 3 to 5, 3 to 6, etc. The idea is that the diffs are idempotent and will take the client to the latest state, as long as we can trust the last ack value. So if it's a diff from 3 to 6, the client could apply that diff in tick 3, 4, 5 or 6, and the final result would be the same.

This is done for state that should be reliably transmitted and consistent. For stuff that doesn't matter as much if they get lost (explosion effects, or what not), then they're usually included in that packet but not retransmitted or accounted for once it goes out.

This is different (and a lot more efficient) than sending the last N updates in each packet.

That is a fascinating use of idempotence, bravo!

> The idea is that the diffs are idempotent and will take the client to the latest state, as long as we can trust the last ack value. So if it's a diff from 3 to 6, the client could apply that diff in tick 3, 4, 5 or 6, and the final result would be the same.

Can you elaborate or give an example of how this works?

Imagine the following changes each tick:

    1: x = 1
    2: x = 2
    3: x = 3, y = 5
    4: x = 4
    5: x = 5
    6: x = 6
    7: x = 7, y = 1

Diff from 2 to 4 would be "x = 4, y = 5".

Diff from 3 to 6 is "x = 6", which will always be correct to apply as long as client is already on ticks 3~6. But if you apply at tick 2, you lose that "y = 5" part. This can't happen in a bug-free code because the server will only send diffs from the latest ticks it knows for sure the client has (because the client sends acks)

Cool thanks, that makes sense! In my head I was thinking the diff from 2 to 4 would be something like "x += 2, y += 5", and 3 to 6 would be "x += 3, y += 0"... which of course wouldn't be idempotent and wouldn't allow you to apply the update to different client states.

You can extend it to practical use by imagining these terms as:

    entity[123].active = true
    entity[123].x = 4
    entity[123].y = 8

Then later...

    entity[123].active = false

And with special rules such that if `active = false`, no other properties of the entity needs to be encoded. And if `active = true` is decoded, it sets all properties to their default value. Then you get a fairly simple way to transmit an entity system. Of course you'd want to encode these properties in a much smarter way for efficiency. But the basic idea is there

If you get your data small enough to fit multiple updates into a single packet, you can send the last N updates in each packet.

If your updates are bigger; you probably will end up with seqs, acks and retransmitting of some sort, but you may be able to do better than sending a duplicate of the missed packet.

Exactly, you assign a sequence number to each update, have the client send acks to convey which packets it has received, and the server holds onto and sends each unacked update in the packet to clients (this is an improvement over blindly sending N updates each time, you don't want to send updates that you know the client has already received).

If the client misses too many frames the server can send it a snapshot (that way the server can hold a bounded number of old updates in memory).

You just described TCP

It's close but TCP will retransmit frames rather than packing multiple updates in a single frame.

It's common for people to build this kind of retransmission logic on top of UDP (especially for networked games), it's sometimes referred to as "reliable UDP".

TCP forces sequencing across all packets, SCTP is a bit closer.

It’s not TCP, it’s TCP without head-of-line blocking, which makes it much more suitable for real time games.

You don’t delta compress everything, only a significant part of the payload. Each diff is referential to a previous packet with a unique id. If you don’t have the previous packet, you just ignore the update.

Every 30 frames or so, you send a key frame packet that is uncompressed so that all clients have a consistent perspective of world state if they fell behind.

Using sentTime lets clients ignore old data and interpolate to catch up if behind as well.

It does work, I wrote one from scratch to create a multiplayer space rpg and the bandwidth savings were incredible.

Reply on news.ycombinator.com