RealTime Data compression.

#1 The trick here is to think in bits not bytes, shorts etc. And there is no one who can make better assumptions about the data to be compressed like the object who is writing that data to your packet stream.

The V12 employs a 'bit stream' and hides the packet sending from the game code. All network objects write into this bit stream and the system determines when a packet is full and how frequently to send them.

It doesn't take that much work to set up a bit stream class that can read/write vectors, quaternions, matrices, floats, text strings, etc with variable accuracy and bit length.

Here is an example of a few of the bit stream read/write functions the V12 supports.

void writeInt(S32 value, S32 bitCount);
S32 readInt(S32 bitCount);

void writeSignedInt(S32 value, S32 bitCount);
S32 readSignedInt(S32 bitCount);

void writeRangedU32(U32 value, U32 rangeStart, U32 rangeEnd);
U32 readRangedU32(U32 rangeStart, U32 rangeEnd);

// read and write floats... floats are 0 to 1 inclusive, signed floats are -1 to 1 inclusive
F32 readFloat(S32 bitCount);
F32 readSignedFloat(S32 bitCount);

void writeFloat(F32 f, S32 bitCount);
void writeSignedFloat(F32 f, S32 bitCount);

// writes a normalized vector
void writeNormalVector(const Point3F& vec, S32 bitCount);
void readNormalVector(Point3F *vec, S32 bitCount);

...many more.

There are also a few compression articles here in the GarageGames resource database. Here are a couple that might be of use.
higher accuracy quantized normals
The Data Compression Library

--Rick Overman

#2 Hey Thomas!

Does the V12 engine employ any form of packet compression, like Huffman or arithmetic compression? I was thinking about writting one for our network engine. I read an article on gamasutra about the network engine in Half-life it uses retroactive events, does the V12 engine use these?

Data tuncation can reduce the packet size by 1/2 - 1/4 with the approirate trade off in accuracy ofcourse. However I've noticed after that point you will need to use some algorithimic compression schemes to get any further improvements by reducing the redundancy from the packets. A problem I've faced with really small packets is that the compression headers are larger than the packets themselves, or using an adpative compression, the packets are not large enough to allow for the adapative scheme to work, the packets range from 10 - 100 bytes in these cases.

Another way to reduce bandwidth is to use an event based system for server - client synchronization. That is instead of sending absoulte state data, you send events. For instance if the player presses forward and this causes the vehicle to turn clockwise until they are facing forward. You could send the absoulte rotational information about the vehicle every update tick, or you could just send the event (forward). Every once and a while you can send the absolute state information just to be safe.

In additon to those methods you can also cull out unimportant objects outside of the users viewable area and not send data about them, unless ofcoruse its absoultely nessecary, such as death events etc..

Keep in mind the cost of bandwdith used by the protocol itself. It seems udp packets uses about 48 bytes for the header, while tcp packets use 8! I got these numbers from the paper :

http://www.bolt-action.com/

look under papers for the networking paper.

So if your sending 20 udp packets /sec = 960 bytes eaten up just for the protocol overhead! Well for a cable connection this is nothing, but for a modem thats 1/4 of their capacity.

Well good luck

-ddn

#3 I dont know about 8 bytes for TCP overhead. Perhaps with modem header compression stuff (UDP can be header compressed as well for modem transmission).

I seem to recall an overhead of about 20bytes per packet for TCP transfers.

I am willing to be corrected though, thats just what I recall.

Phil.

#4 hey hey gigantic person. :)

I'm using a mix of events/absoulte data as you mentioned. I dug out my protocol standards book and looked it up. And the uncompressed TCP header 48 bytes as well, in addition to protocol overhead. Header compression for modems helps , but once it leaves the ISP, it's full sized, so it's still needs to be transmitted regardless. :( I got to work on it and i was able to get my general object update down to about 9 bytes, for positional plus various status info so it's looking okay for now, i'll come back to it at alater date i guess. It use to send about 40 bytes or so. :)

Thomas

#5 Just in case anyone is interested here is the link to UDP rfc768 specification.

The V12 does use Huffman compression for strings using a fixed table but does not otherwise compress the packets. We have not had any bandwidth problems so we have not pursued crunching the packets down any further than our bit packing. I do recall doing some tests a long time ago and we did not get any significant additional compression by Huffman encoding the packets.

A packet of game data does not and should not equal a packet of UDP data. Because of the packet overhead you will want to squeeze as many system and object updates per frame/time slice into each UDP packet as possible.

--Rick

#6 After profiling a TCP only server and a UDP / TCP mix server, i didn't find any difference in terms of bandwidth on the server side. However there was a significant difference on the modem client side. A drop of 800 bytes/sec to 200 bytes/sec, of which only 80 bytes/sec of that is game data. I'm pretty sure its due to the TCP compress header. It's true that the packets are uncompressed when they travel through the interent, but the majority of the latency from server->client I've noticed is caused in the last hop from the isp servers to the client. This is esp true for low bandwidth connections like modems. I've noticed an improvement in modem play from swithcing to TCP only.

TCP only, can be made to work in an aciton game however it does require some additonal work. Such as extrapalation of old packet data, reduction of overall bandwidth, and a good timmer synchronization scheme. The tradeoff it seems is more senstivity to the internet conditions and about 20% more latency.

How easy would it be to add a compression layer which automaitcally handles compression of the packet stream in the V12 engine? I'm intrested in perhaps porting over the compression layer from my engine to V12.

Also what timmer synchrnonization algorithims does the V12 engine use?

Well Good Luck!

-ddn