Conceptual: Synchronizing complex objects
A slightly different idea to add to the mix: have you thought about run length encoding the grid and sending entire compressed states?
It won't always offer predictable bandwidth use (but then deltas don't exactly do this either) and could be vulnerable to pathological cases, but it could be worth a try. It depends on the kind of tile patterns you expect.
Cheers,
Will
Quote:This will definately reduce bandwidth requirements. What would happen if a tile group is out of a client's subscription for a long time and then comes into view? I can imagine having to send a large update, and this also could lead to the server keeping track of a lot of past game states so they can know how the client can 'catch up'.
State is state.
If someone is playing a game of chess, and observers A and B join at time 0 and 20,000 respectively, the full state of the board is always 8x8 tiles, and up to 32 pieces. Regardless of when they join.
This is the difference between delta and baseline.
Baseline is full current state of an object. Delta is what has changed since the *last* update, not since beginning.
It's not like undo mechanism or something similar, where you need to keep track of all actions since the beginning.
Yeah, think about using huffman encoding, or other lossless data compression schemes. That works well if your data has lots of repeating information.
For bug-free delta compression, you do need to cache previous states and exchange sequence numbers. This is to overcome packet loss problems and such. What happens if you drop a packet, and delta-compress strictly from the previous known state, and a packet is dropped? I used delta compression from previous state only in a replay system, since you cannot loose packets. unless you use TCP.
There is also another way to do it simply, which is a mix of delta and baseline. Where you send baselines every so often (say, 4 seconds), and send deltas from that baseline. If a packet is lost, you will potentially have discrepancies until the next full state is sent again.
For bug-free delta compression, you do need to cache previous states and exchange sequence numbers. This is to overcome packet loss problems and such. What happens if you drop a packet, and delta-compress strictly from the previous known state, and a packet is dropped? I used delta compression from previous state only in a replay system, since you cannot loose packets. unless you use TCP.
There is also another way to do it simply, which is a mix of delta and baseline. Where you send baselines every so often (say, 4 seconds), and send deltas from that baseline. If a packet is lost, you will potentially have discrepancies until the next full state is sent again.
oliii,
The delta compression system they are discussing (the "Quake model") is where the server saves the last X updates, together with their sequence numbers. The client will acknowledge each received update, so the server knows one sequence number that the client has seen. The server will send deltas based on that sequence number, until a new acknowledgment is received. Btw: The delta frame needs to also include which sequence number it's based off of, so the client knows how to reconstruct it, and the client needs to keep some amount of backlog, too.
The delta compression system they are discussing (the "Quake model") is where the server saves the last X updates, together with their sequence numbers. The client will acknowledge each received update, so the server knows one sequence number that the client has seen. The server will send deltas based on that sequence number, until a new acknowledgment is received. Btw: The delta frame needs to also include which sequence number it's based off of, so the client knows how to reconstruct it, and the client needs to keep some amount of backlog, too.
Author
Thanks for the replies, everyone. I've been thinking about the suggestions and think I've come up with a good method:
During normal operation, the server will send all delta events, time-tagged with the server time, to all clients. The clients will process delta events in order, and, if they miss any, will send a request to the server. Developing a system for delta states isn't worth the work, as I see it. Sending delta events with requests should be a low bandwidth, latency tolerant system (and basically accomplishes what delta states do, just smaller granularity).
When a player joins, the server will send an absolute state of the game. Moreover, if a client is deemed too far out of synch with the server, an absolute state will be sent. These states will (ideally) be few and far between (less than one absolute state per client per minute).
Compression has been considered and will likely be implemented. RLE and Huffman encoding techniques are options, and it will involve assumptions made about a "normal" tile group state.
This is, of course, an ideal situation. We'll see what happens!
-dirtyminuth
During normal operation, the server will send all delta events, time-tagged with the server time, to all clients. The clients will process delta events in order, and, if they miss any, will send a request to the server. Developing a system for delta states isn't worth the work, as I see it. Sending delta events with requests should be a low bandwidth, latency tolerant system (and basically accomplishes what delta states do, just smaller granularity).
When a player joins, the server will send an absolute state of the game. Moreover, if a client is deemed too far out of synch with the server, an absolute state will be sent. These states will (ideally) be few and far between (less than one absolute state per client per minute).
Compression has been considered and will likely be implemented. RLE and Huffman encoding techniques are options, and it will involve assumptions made about a "normal" tile group state.
This is, of course, an ideal situation. We'll see what happens!
-dirtyminuth
Quote:Original post by oliii
Quake-style delta-compression is awesome for on any fast-paced, data-driven networked games.
What does the quake server store as far as previous states? Does it remember the last N states for compression purposes?
Quote:Original post by hplus0603
oliii,
The delta compression system they are discussing (the "Quake model") is where the server saves the last X updates, together with their sequence numbers. The client will acknowledge each received update, so the server knows one sequence number that the client has seen. The server will send deltas based on that sequence number, until a new acknowledgment is received. Btw: The delta frame needs to also include which sequence number it's based off of, so the client knows how to reconstruct it, and the client needs to keep some amount of backlog, too.
Yes, I know that. Quake 3 goes further I think and caches the 'viewable' states for each clients. That increase the memory requirements.
Quote:Original post by Ozymandias43Quote:Original post by oliii
Quake-style delta-compression is awesome for on any fast-paced, data-driven networked games.
What does the quake server store as far as previous states? Does it remember the last N states for compression purposes?
Yes, so it can diff with the last aknowledged state for each clients.
Quote:Original post by oliiiQuote:Original post by Ozymandias43
What does the quake server store as far as previous states? Does it remember the last N states for compression purposes?
Yes, so it can diff with the last aknowledged state for each clients.
Hrm....not to hijack the thread, but now that I think about it, what's the preferred data type for a large game state? Game states can be kind of large and, worse, their size can change. If you need to keep the last N states in memory, I suppose you'd want to store the game states as a circular buffer of some sort.
Let's say the only two dynamic values are players, missiles, and buffs. A player can have an unlimited number of buffs, and there are an unlimited number of missiles in the air at any one time.
What I'm thinking right now is that I'd create a circular buffer of N elements. Each element would be big enough to store a good amount of missiles and buffs and players. Every time a new missile or buff or player showed up, I'd check to see if the size of a gamestate needed to be increased.
There's gotta be a better way, though, I hope?
There should be no "unlimited" anythings in your design, or you will see problems with resource consumption (maybe even exploits).
If you want to support the worst case, you have to set aside memory for the worst case. There is no other way!
If you want to support the worst case, you have to set aside memory for the worst case. There is no other way!
One thing I recently did for the server end was actually store only the binary delta data that was generated when it had to send delta information to the client. That way you're saving a lot of memory. (my game state is over 50k, but the delta data in the packets was only about 1k max)
Store these binary strings in a linked list. When you get a sequence ack from the client, you know which delta info in memory you can apply to the known client game state. As stated above you could also store a history of what the client knows, but that might be overkill.
Also, use a function that both the client and the server can use for applying the delta information. Mine looks something like:
UncompressDelta(snapshot_t *targetData, delta_t *d)
So, again whether data is coming in packets on the client side or the server is simply updating the known client state, you can use one function for this.
Store these binary strings in a linked list. When you get a sequence ack from the client, you know which delta info in memory you can apply to the known client game state. As stated above you could also store a history of what the client knows, but that might be overkill.
Also, use a function that both the client and the server can use for applying the delta information. Mine looks something like:
UncompressDelta(snapshot_t *targetData, delta_t *d)
So, again whether data is coming in packets on the client side or the server is simply updating the known client state, you can use one function for this.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
