Best way to optimize a networked array?
by Stephen Zepp · in Torque Game Engine · 03/11/2005 (4:13 pm) · 8 replies
I'm looking for the best way to keep a small array of integers networked across a server-client (dedicated) setup, anywhere from 4x4 to 15x15 or so in size. The solution needs to be network bandwidth optimized (yes, I know that's only a small total amount of data in the big scheme of things, but this needs to be as absolutely low bandwidth as possible), and the client's version of the array needs to stay as tightly synched as possible.
One solution I'm playing around with is based on the concept of a sparse array--in this case, our array stays fixed size, but at any one tick, only a few (3-5) values within the array are going to change. The idea here would be to send a tri of the point's x, y, and value, and decode that to update the client's array.
One problem I see with that is if a packet is dropped, AFAIK the standard pack/unpack isn't going to catch the packet drop, and therefore the client will be out of synch until the next tri is sent for those two indices.
Specific Question: How do you actually set (or can you set) the "guaranteed delivery" aspect of a specific bit of information in the normal ghosted object strategy? If I do go with this implementation, I need to ensure that each data point sent is received (they can be out of order, but they must be received), since the frequency of changes to a particular datapoint is going to be relatively low.
If you cannot set a particular element of an object as guaranteed delivered in this way, does anyone have any alternative solutions to accomplish the requirement that is extremely bandwidth efficient?
One solution I'm playing around with is based on the concept of a sparse array--in this case, our array stays fixed size, but at any one tick, only a few (3-5) values within the array are going to change. The idea here would be to send a tri of the point's x, y, and value, and decode that to update the client's array.
One problem I see with that is if a packet is dropped, AFAIK the standard pack/unpack isn't going to catch the packet drop, and therefore the client will be out of synch until the next tri is sent for those two indices.
Specific Question: How do you actually set (or can you set) the "guaranteed delivery" aspect of a specific bit of information in the normal ghosted object strategy? If I do go with this implementation, I need to ensure that each data point sent is received (they can be out of order, but they must be received), since the frequency of changes to a particular datapoint is going to be relatively low.
If you cannot set a particular element of an object as guaranteed delivered in this way, does anyone have any alternative solutions to accomplish the requirement that is extremely bandwidth efficient?
#2
All ghost updates are guaranteed. But, they only send most recent info. It's not a stateful transaction in the same sense that a NetEvent is. But it will notice if a packet is dropped and resend. Read the TNL docs? They go into this in some detail.
If you're trying to deal with arbitrary changes to the imagemap, you might want to go with a wavelet delta strategy, where you keep track of changes from the original heightmap using a wavelet compression scheme, then stream the wavelets to the clients. A quadtree compression of deltas might also be good.
Ghosting does not use NetEvents; NetEvents are for message passing while ghosting is for most recent info.
For the wavelet transmission, you'll probably want to key it off the terrain ghost id and have a seperate update manager (or have it as part of the TerrainBlock) that deals with making sure clients have the right deformation data - maybe also allowing client prediction so that local perturbations are instantaneous.
03/14/2005 (1:21 am)
Hey guys,All ghost updates are guaranteed. But, they only send most recent info. It's not a stateful transaction in the same sense that a NetEvent is. But it will notice if a packet is dropped and resend. Read the TNL docs? They go into this in some detail.
If you're trying to deal with arbitrary changes to the imagemap, you might want to go with a wavelet delta strategy, where you keep track of changes from the original heightmap using a wavelet compression scheme, then stream the wavelets to the clients. A quadtree compression of deltas might also be good.
Ghosting does not use NetEvents; NetEvents are for message passing while ghosting is for most recent info.
For the wavelet transmission, you'll probably want to key it off the terrain ghost id and have a seperate update manager (or have it as part of the TerrainBlock) that deals with making sure clients have the right deformation data - maybe also allowing client prediction so that local perturbations are instantaneous.
#3
The one thing that still has me wondering however is what actually is the best way to pack/unpack the 2-D array? Currently I'm traversing the entire array and packing up each value, and that's obviously not optimized at all. I've been playing around with keeping a secondary "changed" table, and then only sending data point tuples (x, y, value), but this seems just as clunky, just in a different way. Normally we use a mask to indicate that a specific area of data has changed, but I'm still playing around with the best way to keep track of what has changed in the total array.
03/14/2005 (6:45 am)
Thanks! I was aware of the more strict control you had over NetEvents, but wasn't sure if you had this control over ghosted object updates as well, or if they were the "latest update" like Ben mentioned. After getting the prototype transmission working, I think that I can relax the "update must arrive" requirement, so I should be good to go with normal ghosting.The one thing that still has me wondering however is what actually is the best way to pack/unpack the 2-D array? Currently I'm traversing the entire array and packing up each value, and that's obviously not optimized at all. I've been playing around with keeping a secondary "changed" table, and then only sending data point tuples (x, y, value), but this seems just as clunky, just in a different way. Normally we use a mask to indicate that a specific area of data has changed, but I'm still playing around with the best way to keep track of what has changed in the total array.
#4
My game uses an "ownership" concept... land that is OK to build on for each individual player. I didn't want to paint this area for each player, so I used terrain information to make "walls." If the terrain is steeper than a certain point, it is marked as impassable. Then the spawnpoint for each player (with an additional owner tag) is used as a starting point, and the array is flood filled from this point, with the boundaries being steep terrain.
Eventually I'll make a MD5 hash of the array and transmit that every now and then to check if they're in-sync. The only way this should happen is if the player is cheating. But of course I'm probably wrong and it will happen at random moments.
The point is, if you can think of ways to compute things on the client side with minimal network transfer, compression is almost unnecessary. Rethink your approach. My technique most likely will not apply directly to your game, but I'll bet you can think of something.
03/14/2005 (8:39 am)
The game I'm working on requires a 32-bit 258x258 array to be kept in sync, although updates only need to be done every 1 second or so. I thought about many different compression schemes, until I figured out that I didn't really need to send the whole array ever. It starts out clear, so that's simple enough. Whenever a wall is built, that's a networked event, so it reads that info and plots a wall in the array. All of the scanning functions (that use the array) simply use the local client array. My game uses an "ownership" concept... land that is OK to build on for each individual player. I didn't want to paint this area for each player, so I used terrain information to make "walls." If the terrain is steeper than a certain point, it is marked as impassable. Then the spawnpoint for each player (with an additional owner tag) is used as a starting point, and the array is flood filled from this point, with the boundaries being steep terrain.
Eventually I'll make a MD5 hash of the array and transmit that every now and then to check if they're in-sync. The only way this should happen is if the player is cheating. But of course I'm probably wrong and it will happen at random moments.
The point is, if you can think of ways to compute things on the client side with minimal network transfer, compression is almost unnecessary. Rethink your approach. My technique most likely will not apply directly to your game, but I'll bet you can think of something.
#5
How much of the total bandwidth are you spending on this transfer? Sure, you don't want to write clunky code, nobody does. But it's probably not worth optimizing a tiny table too much.
What has changed since last time? The array is tiny, so just keep an old copy. At pack time, compare the two arrays. That way you don't have to any special change logging.
Compression? Your tuples are actually pretty efficient when you only have 3-5 per update. Even if you pass indices as full 8 bit values, 5 tuples costs you only 10 bytes of index data plus what, 5x4 bytes of value data? 30 bytes in total.... With some bit packing on the indices, you can drop that to 25 bytes. If the values can be only 2 bytes each, the total drops to 15 bytes. Maybe you could get a little smaller than that, but it probably isn't worth the extra effort. I think the tuples are a fine way to go.
When you get as small as 15 bytes, the NetEvent or ghosting overhead has got to start being significant anyway.
03/14/2005 (12:20 pm)
Wavelet compression for a 4x4 to 15x15 grid seems like overkill to me, but if you can find a free implementation that is ready to go, hey, why not? That might cover you if you expand to bigger arrays.How much of the total bandwidth are you spending on this transfer? Sure, you don't want to write clunky code, nobody does. But it's probably not worth optimizing a tiny table too much.
What has changed since last time? The array is tiny, so just keep an old copy. At pack time, compare the two arrays. That way you don't have to any special change logging.
Compression? Your tuples are actually pretty efficient when you only have 3-5 per update. Even if you pass indices as full 8 bit values, 5 tuples costs you only 10 bytes of index data plus what, 5x4 bytes of value data? 30 bytes in total.... With some bit packing on the indices, you can drop that to 25 bytes. If the values can be only 2 bytes each, the total drops to 15 bytes. Maybe you could get a little smaller than that, but it probably isn't worth the extra effort. I think the tuples are a fine way to go.
When you get as small as 15 bytes, the NetEvent or ghosting overhead has got to start being significant anyway.
#6
It's actually working quite nicely by sending the entire array every time anything in the array changes, except for the bandwidth issue. I'm hoping now to stick with this overall design, but only transmit the grid tuples that actually change.
03/14/2005 (12:21 pm)
Actually what is ironic is that we originally were doing everything as procedurally generated as possible, but keeping the terrain blocks in sync was a nightmare. Additionally, it became extremely difficult to track multi-grid point changes of an arbitrary number, so the design was refactored to include this type of concept.It's actually working quite nicely by sending the entire array every time anything in the array changes, except for the bandwidth issue. I'm hoping now to stick with this overall design, but only transmit the grid tuples that actually change.
#7
03/14/2005 (12:24 pm)
Alan's hash notion is great, btw, especially if you are relaxing the "update must arrive" requirement.
#8
From what I can see right now, this is exactly what I want to do to figure out which tuples to pack, and then just deliver those. All of your comments about total bandwidth and exactly what you are optimizing from and down to is absolutely right as well--no need to get incredibly anal about it with the tiny size already, but I don't want to be so sloppy as sending 248 values out of a 256 size array when only 8 values have changed.
Thanks for all of the input guys, I think this is going to work out well!
03/14/2005 (12:48 pm)
Quote:What has changed since last time? The array is tiny, so just keep an old copy. At pack time, compare the two arrays. That way you don't have to any special change logging.
From what I can see right now, this is exactly what I want to do to figure out which tuples to pack, and then just deliver those. All of your comments about total bandwidth and exactly what you are optimizing from and down to is absolutely right as well--no need to get incredibly anal about it with the tiny size already, but I don't want to be so sloppy as sending 248 values out of a 256 size array when only 8 values have changed.
Thanks for all of the input guys, I think this is going to work out well!
Torque Owner Andrew Haydn Grant
Part the NetEvent class comments describe three kinds of network events: Unguaranteed, Guaranteed, GuaranteedOrdered. Worst case, you could implement your own NetEvent for array updates, and if everything works as advertised, you should be able to specify the delivery style you prefer.
I suspect that you *do* need updates to be ordered for this system to work flawlessly, by the way. Two updates might both modify the same element, in which case, order is essential.
(Before writing this, I thought that ghosting probably used the NetEvents class, but I peeked at netGhost.cc and now I don't think so.)