Propagation of Visual Entity Properties Under Bandwidth Constraints
May 24, 2007 Page 6 of 7
5. Data Compression
Online games based on small geographical zones can use position coordinates local to zones, with low range needs. However, a large seamless environment theoretically deals with wide-range coordinates. On the server side, we have 32-bit integer positions with millimetre precision. An approach would be to alternate absolute positions and “smaller” positions relative to the latest absolute positions. However, this technique has strong sequentially constraints, which cannot be easily adapted to our best-effort (non-reliable) lightweight network protocol.
A more suited approach was based on the assumption that a client will only display the entities in the neighbourhood, within the square kilometer surrounding the viewer (Figure 6). Then, a virtual local basis can be used. Instead of translating positions from absolute basis to a basis relative to the viewer, a more CPU-effective method consists in using the “truncated absolute coordinate” algorithm.
The server transmits short entity coordinates, and, to save more bandwidth, also lowers the precision to 16-millimeter in a 1024 m window by dividing the coordinate by 16 (i.e. shifting down by 4 bits). No reference to the viewer’s position is needed:
uint16 ec_short = (uint16)(ec_full >> 4);
To reconstruct the full position of an entity, the client needs the following inputs:
Full viewer coordinates (uint321 vc_full).
Short entity coordinates (uint16 ec_short).
The client calculates the short viewer coordinates, and the short entity delta coordinates from the transmitted values, to finally deduce the full entity coordinates from the full delta (obtained by sign extension) and the damped viewer coordinates (to avoid entity flickering when the viewer moves):
uint32 vc_full_damped = vc_full & ~0xF;
uint16 vc_short = (uint16)(vc_full >> 4);
sint16 delta_short = (sint16)(ec_short – vc_short);
uint32 ec_full = (uint32)(vc_full_damped + delta_full);
For the example in Figure 6:
Full X Coordinates:
Entity A: 0xE000
Entity B: 0x6000
Entity C: 0x2000
Entity A: 0x2000
Entity B: 0xA000
Entity C: 0x6000
Entity A: 0x00020000
Entity B: 0xFFFA0000
Entity C: 0x00060000
If dealing with ground entities, the z-value (altitude) may be even more compressed, by referring to a layer index, provided the client software can access efficiently the 3D topography structure corresponding to a 2D value.
1 Basic types shown are from the NeL library: uint32 is 32-bit unsigned int, sint16 is 16-bit signed int, etc.
Page 6 of 7