Sync one thousand vector3 across network with minimal bytes?

Question

I am making a game with Unity, and am having problems attempting network synchronisation. Deterministic simulation is impossible because Unity's internal logic is float based. I am trying to make a solution which works on an authoritative client-server model, in which the position of every soldier is corrected by the server 5-10 times a second. This is achieved by sending UDP datagrams, and measures will be implemented to ensure delivery. Between corrections the client simulates the game as best it can.

Soldiers do not often move in straight lines. They engage in flocking and will encounter many obstacles which they have to navigate. Soldiers exist as individuals and do not exist as part of a squad object.

There are things which can be done to reduce bandwidth consumption which are not the focus here, because they are at best temporary improvements. Like only sending the positions of soldiers who are moving and/or observed, and compressing the data before transmission.

The problem is simple. If I have ten soldiers running about that's fine, but if I have one thousand then bandwidth use becomes unreasonable. At the very least we need to send a soldier id (ushort) and position (float, float, float) per soldier. Right now that's 2 + 4 + 4 + 4 = 14 bytes. More data maybe required, for instance the direction of facing (soldiers never look up or down).

14 * 10 * 1000 = 140kb/s ... way too much!

The question is this:

How can we reduce the number of bytes sent per soldier to an absolute minimum and still have a synchronised result?

POSSIBLE SOLUTIONS:

1. One idea I had was that since a soldier's max speed will not change, this allows us to correct the position of any soldier by an absolute value relative to the last known position. But that may suffer from desync too.

Instead of sending a float for the XYZ axis of the position, we send a sbyte. Since this is -128 to 127, we can read/write it to say that the new position is a percent of the soldier's max speed from the last position. If it worked that'd reduce the data sent from 14 bytes to 5. But even 36% is still 50kb/s for 1000 soldiers.

Potentially that could be reduced to 4 bytes some of the time, as soldiers do not always move up or down (Y axis). But that is, like ignoring soldiers who are not moving, not the issue.

2. Another idea I had was to reduce the XYZ axis to 12 bits (1.5 bytes). Each axis has 4 bits, 3 of which are used to find a distance value. 3 bits allows us to count from 0 to 8. There are six values between either end of zero or maximum speed. We have a range of values which can be used as they are "close enough". The other bit determines whether this is positive or negative. The server then forces a correction upon soldiers before it sends their positions to the client, forcing their distance from the last position to conform to one of the "close enough" values.

Additionally, if there won't be more than a thousand soldiers alive at any one time, we can assign soldiers to a living ID, and so shorten the network ID from 16 bits to 10, allowing us to count to 1024.

In total this would reduce the data sent per soldier from 14 bytes to 22 bits (2.75 bytes). I suspect this would be even less likely than the first idea to maintain synchronisation. The result may simply be too jittery. If it did work it'd be 20% of the original bandwidth at 28kb/s.

...

Any ideas are welcome at this point. I've been focusing on making smaller and smaller vector3's, but there may be a much better way of doing this which does something completely different.

Answer 1

Standard compression algorithms are pretty efficient even at the fastest setting. As a quick test I filled a text file with 34k bytes. Compressing with 7-zip on fastest setting gave me a file of 1k. That is ~3% of the original size. Granted my numbers was stored as ascii but it goes to show that similar values can be reduced to a small fraction.

Using standard algorithms can probably be outdone by special techniques discussed in other answers but standard compression techniques should be much faster to implement and less error prone to use well-tested algorithms but if the result is "good enough ®" you can choose if you want to use the gained time to go to market faster or make a sweeter game in areas the user can actually feel.

Answer 2

It seems to me that if you have 1000 guys on the screen and they are flocking, the exact position of each wont be so important as when you have 10?

Could you have the soldiers group up as the total number increases? so, when i have 10 each moving thing is a single solider. When I have 100 they are in squads of ten, with a single position sent and a formation. When I have 1000 they are in 100 unit formations?

This will allow you to scale infinitely, although you will obvs loose the detail

Answer 3

Many of the ideas you posted are good. At some point you will hit saturation point, so there are some trade-offs you are going to need to make. Some of those trade-offs depend on how large your grid is and how fast your units are moving. I'll attempt to add a couple more options you can look at:

• Compression (make sure it actually saves bytes)
• Send XYZ, bearing and velocity so you can send updates less often
• Interleave updates (i.e. update 1/5 of the units with each message)

You can probably pack bearing and velocity into one byte. First 4 bits would be direction (16 directions should be good enough on small screens) and the second 4 bits for velocity (16 gradations from max velocity) to represent slowdowns due to obstacles.

This takes the data from 14 to 6, but you are only sending data for 200 soldiers at a time. It means the device gets 2 updates per second for each soldier, but it has enough data to accurately interpolate the difference. That makes the datagram go from your 5 * 10 * 1000 (50,000 bytes) to 6 * 10 * 200 (12,000) bytes. Still not pretty, but better. Add fast LZ4 compression and you might get it within that 1300 byte sweet spot where routers will tend to leave your packet alone. That really depends on how regular the data looks.

You can save a couple bytes for the ID if you always send the data in the same order. You can use 2 bytes for the first ID for the group, and then we have a known order for the troop ID after that. That takes us down to 3 * 10 * 1000 + 2 (30,002 bytes) or 4 * 10 * 200 + 2 (8,002 bytes).

Answer 4

One of the purposes of flocking is to create emergent behaviors that are hard to model, so your need to model them in a small number of bytes is tricky.

One approach you could take is to anchor the flock to a "virtual" flock which is more deterministic in behavior. Update the flocking algorithm in a way which permits "eventual consistency" between the real flock and the virtual flock. In other words, adjust the algorithm such that the real flock will always eventually line up with the virtual flock in the long run.

Once you have that, then you can start looking at making the virtual flock more predictable, using whatever approaches make sense (perhaps integer math instead of float), and the real flock just hovers around it. If you do this, 90% of the communication will be small unimportant errors in locations. Eventually you will get a soldier that moves way out of line, because the real flock drug him far away from the virtual flock. Then you can handle him as a special case, which is far more efficient than handling every soldier that way.

Answer 5

When 1,000 soldiers are coming at you, does it matter if the one that's 100 meters away at 50° from your forward position is exactly placed when there there are 30 that are 10 meters away directly in front of you?

You could send only the positions of those soldiers that are actually within range of the player's ability to attack or be attacked. The rest could be generated on the client and the player probably wouldn't be able to tell the difference. As real soldiers enter the radius where they matter, send their real positions to the client.

You could choose not to send the positions of any soldiers that are behind the player (or better yet, not in their field of view), as they won't be drawn. Since the server is the ground truth, it can still decide if a soldier behind the player attacked and hit the player, but you don't need to send the soldier's position until the player turns their character around to face that soldier.

Answer 6

XOR the value of each field in your data structure with the previous structure value, then use a variable byte encoding or variable bit compression to send the results across. I would collect the data for all soldiers into one stream and use a fast compression algorithm (after the above xor process) to compress it before sending as a chunk. I recommend lz4 as the algorithm.

Answer 7

Another proposal that tries to avoid sending data instead of sending it efficiently...

You correctly note that you can't use exact client side replication of behaviour owing to dodgy float goodness, but you can do inexact client replication, and then steadily interpolate back to the exact values as updates come in from the server. This is a jolly complicated way of doing things, but it can also provide nice benefits like latency compensation (indeed, from the game code I have looked at, this seems to be how some servers do latency compensation on client inputs: assume they go in a straight line, and smoothly reposition them according to what they did in the past that the server wasn't aware of at the time).

Basically, set the agents off, and then update them regularly (but staggered so that you don't try to send all 1k vectors within one frame) or when they make a server-side 'decision' (i.e. non-predicatble behaviour). If the 'basic' control behaviour are simple enough then 1second or so of client 'guessing' (which will entail integration of floating point inconsistencies) followed by a smooth interpolation back to the actual location may be forgivable.

You suggested that the 'desyning' is noticeable after about 5 seconds: this method will allow you to tune/change the update rate so that the clients don't have to make dramatic updates to agent positions and so that the network isn't swamped by unnecessary updates. Indeed, the rate can vary in real time to respond to the state of the game: if there are too many units to handle then it can start failing gracefully instead of dropping frames/whatever.

I'm not a game programmer, but this sounds perfectly workable, if a tad complicated. When you do get an update from the server you can make the smooth 'fixing' as complicated as you like, and for initial testing you can just have it 'jump' which removes this element of misery at the start and provides a good indicator of whether the idea is going to work or not.