I'm trying to implement Quake-style delta encoding that works as follows:

1) Each client reports to the host the last tick tlast that it has received from the host.

2) Host generates a snapshot for simulation tick tcurrent and places it in a buffer.

3) For each client, the host compares the snapshot generated at tcurrent to the one generated at tlast and sends that client only the changed values.

4) Client receives the delta snapshot and recreates the full snapshot by filling in the gaps from the one it received at tlast.

Now, this algorithm seems to assume that the host is always sending the client an update on every object in the world, even if that object is irrelevant to that client. What I'm wondering is, what if I have more objects than I can reasonably encode in a single packet? I can send snapshots to clients that only contain updates on some objects (determined by priority, area of interest, etc.), but then I run into a problem. If I'm sending sparse snapshots, when a client tells me it's received data up to tlast, that no longer guarantees that every object has updated to tlast on the client's side.

The naive way I can think of solving this is to keep track individually for every object when it was last updated by the client. This seems to require keeping a jitter buffer for each individual object, though, which adds a lot of complexity. It also requires the client->host packet to contain a long list of every object and its last received tick. Is there a smarter way to handle this?

Thanks!

So, how does this look?

---

Server Process:

Precondition: For each client, the server maintains a ring buffer of the snapshots it has sent.

• Each tick, the server generates a master snapshot for the world state.
• For each client:
  • Select n entities from the new master snapshot to send to that client (by distance, visibility, etc.).
  • Fetch the last snapshot that the client acknowledged from the outgoing ring buffer.
  • For each selected entity:
    • If the entity was present in the prior snapshot and not marked as frozen, send a delta encoding.
    • Otherwise send a full encoding.
  • For each entity that was not selected:
    • Mark the entity as frozen in the snapshot when it goes into the outgoing ring buffer.
    • Do not send any data regarding that entity.
  • Store the generated snapshot in the outgoing ring buffer.

Client Process:

Precondition: The client maintains a ring buffer of received snapshots.

• When it's time to process a snapshot (i.e. it's next in the dejitter buffer).
• For each entity in the world:
  • If the entity is in the snapshot:
    • Update the entity either from the full state or by recomposing its state from a prior received snapshot.
  • Otherwise, mark the entity as frozen locally. Extrapolate it for a short period of time and then hide it.

First: A UDP packet maxes out at 64 kilobytes. That's a LOT of objects!

One thing to keep in mind in this regard is that the larger your UDP datagram is, the more (usually 1.5K-or-so-in-size) fragments it will be split into. And as loss of any fragment leads to effective loss of the whole datagram, this will lead to increasing the datagram loss rate (compared to packet loss rate), IIRC, more or less linearly as your datagram size grows. I'd certainly try to keep away from 64K-sized datagrams (for many reasons, the above one included, but certainly not the only one).

It's probably more efficient to just have a snapshot of all objects for the last N time steps globally, and point into that from each client connection instance. Assuming you have more clients than you have steps of memory, at least.
100 clients, saving the last 10 steps of state, would be quite a win.
If you also need the old states for backwards-checking (Valve/Source/Counter-Strike networking model style) then you can re-use this!

Yep, that's a good idea. I'll just need to maintain a ring buffer of "views" on each client containing which entities it send unfrozen updates for in each outgoing snapshot.

The whole freezing/unfreezing approach is a little more bandwidth-hungry (in terms of server upload) in bad cases than the individually-updated entities approach I proposed in my original post. If an object dances in and out of scope for a period of time I'll potentially be sending a lot of unnecessary full-updates that could have otherwise been delta-encoded. It also enforces a hard limit on my scope size. If everyone in the entire match decides to concentrate on one point and be on screen at once, I'll have pop in/out problems and will consume a lot of extra bandwidth.

However, I think I can do a hybrid of my original post idea (keep track of when each individual entity was updated for a client) without duplicating the snapshots so much based on what you've suggested with this sort of "view" structure per-client while retaining a global master snapshot buffer.

One thing to keep in mind in this regard is that the larger your UDP datagram is, the more (usually 1.5K-or-so-in-size) fragments it will be split into. And as loss of any fragment leads to effective loss of the whole datagram, this will lead to increasing the datagram loss rate (compared to packet loss rate), IIRC, more or less linearly as your datagram size grows. I'd certainly try to keep away from 64K-sized datagrams (for many reasons, the above one included, but certainly not the only one).

I'm trying to stick with Quake-style 1400B packet payloads (with an extra few bytes of protocol overhead). Hence the need for aggressive scoping.

Thanks for the help!

That's true in theory, but the cost of keeping old states of objects around forever for each client is rather punishing.

And if an object has been invisible for a long time, the "delta update" packet to bring it up to date should be the same size as the "reincarnate" packet to bring it up to date, assuming that you're only sending data that is actually likely to change over time. (If you send static data, you probably want to pre-install that and just send a reference to it once.)

I think I can do it with one snapshot buffer as you said. In this approach, the server keeps one outgoing master snapshot buffer and for each client it retains a "view table". A "view table" is a lookup table that contains a mapping of each object id to the latest tick number the client has for that object. So it would look like this:

Every send (on server):

• The server produces a master snapshot and stores it in the history buffer.
• The server creates a scoped/prioritized list of entities to update for a given client
• For each entity
  • Find its last acked frame from the client for that entity from the view table
  • If it's too old, send a full encode from the newly-minted master snapshot
  • If it isn't, retrieve the snapshot from that frame from the master snapshot history buffer and delta-encode

Every receive (on client):

• For each state in the snapshot
  • Add the received state to a per-entity jitter buffer
  • Update the client's view table for that entity to the frame of the received snapshot

Now, there are two downsides to this:

1) The client has to report a view table to the server instead of a single frame ack in each send, which makes the C2S packet bigger. However, a view table is only going to be about 4B per entry, and download on the server is cheaper than upload.

2) The client has to keep one dejitter buffer per entity instead of a single snapshot-level dejitter buffer. This is more expensive, but the client isn't doing this at scale, it only has to maintain one view and one simulation. It also actually kinda simplifies some code I think if I want to do something like spline-based interpolation later on.

Whereas, the big advantage is that we don't necessarily need to update every entity every frame. We could de-prioritize smaller or less game-relevant entities so they only go out in every other snapshot, for instance (like in the "I Shot You First" HALO: Reach networking model). If there are more objects in scope than we can fit in the packet (i.e. everyone decides to meet in the center of the zone), we can transparently round-robin the updates and still delta-encode them rather than having to freeze/unfreeze things intermittently.

This is a top-down game, so I'm interested in situations where the number of visible entities exceed the possible scope. I don't want the scope limit to be a hard number for this reason. I think I can avoid hysteresis and hard bounds entirely if I allow for the "round-robin" update approach I describe above. Ultimately it's always going to be a worst-case.