Multiplayer Game Programming Object Serialization Chapter 4.ppt

Multiplayer Game Programming

1. Multiplayer Game Programming
Chapter 4
Object Serialization

2. Chapter 4
Objectives
Serialization
–Why can’t we just mempy everything between hosts?
–Streams, Endianness and Bits
Referenced Data
–What happens when data points to other data?
Compression
–How to serialize efficiently
Maintainability
–Bug resistant serialization
–Data driven serialization

3. The Need For Streams
Consider the RoboCat
How can we send an instance to a remote host?
class RoboCat : public GameObject
{
public:
RoboCat() : mHealth( 10 ),
mMeowCount( 3 ) {}
private:
int32_t mHealth;
int32_t mMeowCount;
};

4. Naïve Approach to Replication
void NaivelySendRoboCat(
int inSocket, const RoboCat* inRoboCat )
{
send( nSocket,
reinterpret_cast< const char* >( inRoboCat ),
sizeof( RoboCat ), 0 );
}
 
void NaivelyReceiveRoboCat(
int inSocket, RoboCat* outRoboCat )
{
recv( inSocket,
reinterpret_cast< char* >( outRoboCat ),
sizeof( RoboCat ), 0 );
}
•Will this work?

5. What about this RoboCat?
class RoboCat : public GameObject
{
public:
RoboCat() : mHealth( 10 ), mMeowCount( 3 ),
mHomeBase( 0 )
{
mName[ 0 ] = '\0';
}
virtual void Update();

private:
int32_t mHealth;
int32_t mMeowCount;
GameObject* mHomeBase;
char mName[ 128 ];
std::vector< int32_t > mMiceIndices;
Vector3 mLocation;
Quaternion mRotation;
};

6. Problems for memcpy
mHomeBase is a pointer
–Copying the value of a pointer doesn’t copy the data
mMiceIndices is a complex data type
–Calling memcpy on the insides might not copy the data
–The vector on the remote host must be initialized to the proper
size
The virtual Update() requires a virtual function table pointer
–Copying the value of the function table pointer is pointless
mName is 128 bytes, unlikely all are used
–memcpy will copy all 128 bytes regardless

7. Solution
Replicate each member variable individually
–Replicating pointers, replicate the data they point to
–Replicating vectors, replicate their size and data
–Replicating objects with virtual methods, replicate
identifiers to hook up proper virtual function tables
–Replicating large arrays, omit unused elements
But packets should be as big as possible!
–Replicated variables usually < 1300 bytes
–Coalesce member variables before sending
them by serializing into a buffer

8. Serialization
Converting an object ( or graph of objects ) to a linear
form that can be record “serially” into a file or sent
“serially” across a network.
Reverse sometimes referred to as deserialization

9. Output Memory Streams
class OutputMemoryStream
{
public:
OutputMemoryStream() :
mBuffer( nullptr ), mHead( 0 ), mCapacity( 0 )
{ ReallocBuffer( 32 ); }
~OutputMemoryStream() { std::free( mBuffer ); }

//get a pointer to the data in the stream
const char* GetBufferPtr() const { return mBuffer; }
uint32_t GetLength() const { return mHead; }

void Write( const void* inData, size_t inByteCount );
private:
void ReallocBuffer( uint32_t inNewLength );
char* mBuffer;
uint32_t mHead;
uint32_t mCapacity;
};

10. Output Memory Streams Cont ’d
void OutputMemoryStream::Write( const void* inData,
size_t inByteCount )
{
//make sure we have space...
uint32_t resultHead =
mHead + static_cast< uint32_t >( inByteCount );
if( resultHead > mCapacity )
{
ReallocBuffer( std::max(mCapacity * 2, resultHead));
}

//copy into buffer at head
std::memcpy( mBuffer + mHead, inData, inByteCount );

//increment head for next write
mHead = resultHead;
}
Serializing into the stream provides easy way to
coalesce all data into a single buffer
Reduce packet count while handle each member
variable individually

11. Serializing By Type
template< typename T > void Write( T inData )
{
static_assert( std::is_arithmetic< T >::value ||
std::is_enum< T >::value,
"Generic Write only supports
primitive data types" );
Write( &inData, sizeof( inData ) );
}
void Write( uint32_t inData )
{
Write( &inData, sizeof( inData ) );
}
void Write( int32_t inData )
{
Write( &inData, sizeof( inData ) );
}
 

12. Input Memory Stream
class InputMemoryStream
{
public:
InputMemoryStream( char* inBuffer, uint32_t inByteCount ) :
mCapacity( inByteCount ), mHead( 0 ),
{}
~InputMemoryStream() { std::free( mBuffer ); }
uint32_t GetRemainingDataSize() const
{ return mCapacity - mHead; }

void Read( void* outData, uint32_t inByteCount );
 
private:
char* mBuffer;
uint32_t mHead;
uint32_t mCapacity;
};

13. Custom Read and Write
void RoboCat::Write( OutputMemoryStream& inStream ) const {
inStream.Write( mHealth );
inStream.Write( mMeowCount );
//no solution for mHomeBase yet
inStream.Write( mName , sizeof( mName ) );
//no solution for mMiceIndices
inStream.Write( mLocation , sizeof( mLocation ) );
inStream.Write( mRotation , sizeof( mRotation ) );
}
void RoboCat::Read( InputMemoryStream& inStream ) {
inStream.Read( mHealth );
inStream.Read( mMeowCount );
//no solution for mHomeBase yet
inStream.Read( mName, sizeof( mName ) );
//no solution for mMiceIndices
inStream.Read( mLocation , sizeof( mLocation ) );
inStream.Read( mRotation , sizeof( mRotation ) );
}

14. Putting It All Together
void SendRoboCat( int inSocket, const RoboCat* inRoboCat )
{
OutputMemoryStream stream;
inRoboCat->Write( stream );
send( inSocket, stream.GetBufferPtr(),
stream.GetLength(), 0 );
}
void ReceiveRoboCat( int inSocket, RoboCat* outRoboCat )
{
char* temporaryBuffer =
static_cast< char* >( std::malloc( kMaxPacketSize ) );
size_t receivedByteCount =
recv( inSocket, temporaryBuffer, kMaxPacketSize, 0 );

if( receivedByteCount > 0 ) {
InputMemoryStream stream( temporaryBuffer,
static_cast< uint32_t > ( receivedByteCount ) );
outRoboCat->Read( stream );
} else {
std::free( temporaryBuffer );
}
}

15. Endian Compatibility
Different CPUs store multibyte numbers in different
formats
little-endian
–Least significant bytes first in memory
–Intel x86, iOS Hardware, Xbox One, PS4
big-endian
–Most significant bytes first in memory
–PowerPC, XBox360, PS3

16. Endian Examples: 0x12345678
Little Endian
Big Endian
???INSERT FIGURE 4.1 PLEASE
???INSERT FIGURE 4.2 PLEASE

17. Byte Swapping
For compatibility between hosts of different endiannes
–Decide on consistent endianness of stream
–If host endiannes does not match stream endianness
•Swap order of bytes in each multibyte number
before writing
•Swap order of bytes in each multibyte number
before writing
REMEMBER: ONLY SWAP MULTIBYTE, ATOMIC UNITS
( e.g. don’t swap an array of single byte characters )

18. Byte Swapping Con’t
inline uint16_t ByteSwap2( uint16_t inData )
{
return ( inData >> 8 ) | ( inData << 8 );
}
 
inline uint32_t ByteSwap4( uint32_t inData )
{
return ( ( inData >> 24 ) & 0x000000ff ) |
( ( inData >> 8 ) & 0x0000ff00 ) |
( ( inData << 8 ) & 0x00ff0000 ) |
( ( inData << 24 ) & 0xff000000 );
}
 
inline uint64_t ByteSwap8( uint64_t inData )
{
return ( ( inData >> 56 ) & 0x00000000000000ff ) |
( ( inData >> 40 ) & 0x000000000000ff00 ) |
( ( inData >> 24 ) & 0x0000000000ff0000 ) |
( ( inData >> 8 ) & 0x00000000ff000000 ) |
( ( inData << 8 ) & 0x000000ff00000000 ) |
( ( inData << 24 ) & 0x0000ff0000000000 ) |
( ( inData << 40 ) & 0x00ff000000000000 ) |
( ( inData << 56 ) & 0xff00000000000000 );
}

19. Type Aliaser
template < typename tFrom, typename tTo >
class TypeAliaser
{
public:
TypeAliaser( tFrom inFromValue ) :
mAsFromType( inFromValue ) {}
tTo& Get() { return mAsToType; }

union
{
tFrom mAsFromType;
tTo mAsToType;
};
};
Need a tool to treat data of one type as another so we
can genericize byte swapping

20. Templated Byte Swapping Class
template <typename T, size_t tSize > class ByteSwapper;
 
//specialize for 2...
template <typename T>
class ByteSwapper< T, 2 >
{
public:
T Swap( T inData ) const {
uint16_t result =
ByteSwap2( TypeAliaser<T,uint16_t>(inData).Get());
return TypeAliaser< uint16_t, T >( result ).Get();
}
};
//specialize for 4...
template <typename T>
class ByteSwapper< T, 4 >
{
public:
T Swap( T inData ) const {
uint32_t result =
ByteSwap4( TypeAliaser<T, uint32_t>(inData).Get());
return TypeAliaser< uint32_t, T >( result ).Get();
}
};
//specialize for 8...

21. Templated Byte Swapping
Function
template < typename T >
T ByteSwap( T inData )
{
return ByteSwapper< T, sizeof( T ) >().Swap( inData );
}
Single ByteSwap library entrypoint
Uses sizeof to access the proper ByteSwapper class depending on argument size

22. Bit Streams
Not all data requires a multiple of 8 bits
–E.g. a boolean value can be stored in a single bit!
Bandwidth is dear: use as few bits as possible!
Current streams support only byte-level precision
Extend stream library with bit-level precision

23. Bit-Level Streams at work
Each time we write a value into a stream, we should be
able to specify bit count
Consider writing 13 as a 5-bit number and then 52 as a
6-bit number
???INSERT FIGURE 4.3 PLEASE
???INSERT FIGURE 4.4 PLEASE

24. Output Memory Bit Stream
class OutputMemoryBitStream
{
public:
 
OutputMemoryBitStream () { ReallocBuffer( 256 ); }
~ OutputMemoryBitStream () { std::free( mBuffer ); }
 
void WriteBits( uint8_t inData, size_t inBitCount );
void WriteBits( const void* inData, size_t inBitCount );
 
const char* GetBufferPtr() const {return mBuffer;}
uint32_t GetBitLength() const {return mBitHead;}
uint32_t GetByteLength() const {return (mBitHead+7)>>3;}
 
void WriteBytes( const void* inData, size_t inByteCount
{ WriteBits( inData, inByteCount << 3 ); }

private:
void ReallocBuffer( uint32_t inNewBitCapacity );
char* mBuffer;
uint32_t mBitHead;
uint32_t mBitCapacity;
};

25. WriteBits Part 1
void OutputMemoryBitStream ::WriteBits( uint8_t inData,
size_t inBitCount ) {
uint32_t nextBitHead =
mBitHead + static_cast< uint32_t >( inBitCount );

if( nextBitHead > mBitCapacity ) {
ReallocBuffer(std::max(mBitCapacity*2, nextBitHead));
}
//byteOffset = head / 8 , bitOffset = the last 3 bits
uint32_t byteOffset = mBitHead >> 3;
uint32_t bitOffset = mBitHead & 0x7;
 
//calculate which bits of the current byte to preserve
uint8_t currentMask = ~( 0xff << bitOffset );
mBuffer[ byteOffset ] = ( mBuffer[byteOffset] & currentMask )
| ( inData << bitOffset );
  //how many bits not yet used in target byte in the buffer
uint32_t bitsFreeThisByte = 8 - bitOffset;
 
//if we needed more than that, carry to the next byte
if( bitsFreeThisByte < inBitCount ) {
mBuffer[ byteOffset + 1 ] = inData >> bitsFreeThisByte;
}
 

mBitHead = nextBitHead;
}

26. WriteBits Part 2
void OutputMemoryBitStream ::WriteBits(
const void* inData, size_t inBitCount )
{
const char* srcByte = static_cast< const char* >( inData );

//write all the bytes
while( inBitCount > 8 )
{
WriteBits( *srcByte, 8 );
++srcByte;
inBitCount -= 8;
}
//write anything left
if( inBitCount > 0 )
{
WriteBits( *srcByte, inBitCount );
}
}

27. Templated WriteBits
Need single Write method that can take any safe data type, and write it with any number of bits
Defaults to maximum number of bits for given type
Special case default for bool
template< typename T >
void Write( T inData, size_t inBitCount = sizeof(T) * 8 )
{
static_assert( std::is_arithmetic< T >::value ||
std::is_enum< T >::value,
"Generic Write only supports primitive data types" );
WriteBits( &inData, inBitCount );
}
void Write( bool inData )
{ WriteBits( &inData, 1 ); }

28. Input Memory Bit Stream
Analog to OutputMemoryBitStream
Must read values using the same number of bits as
when the values were written
These implementations are for little-endian streams.
–On big-endian platform, byte swap before and after
reading

29. Referenced Data
Pointer member variables reference other data
Container member variables, like vector, also
reference other data
Data can be referenced by only one object, or by
multiple objects
–Remember RoboCat:
•If multiple RoboCats have the same HomeBase,
that HomeBase is referenced by multiple objects
•Each RoboCats has a unique vector of mice
indices it is tracking- each vector is referenced /
owned by only a single RoboCats

30. Inlining / Embedding
Serializing pointer or container values is nonsensical
–They will point to garbage on the remote host
If object completely owns referenced data, serialization can embed the referenced data inline.
Write size of container first for deserialization…
void OutputMemoryStream ::Write(
const std::vector< int32_t >& inIntVector )
{
size_t elementCount = inIntVector.size();
Write( elementCount );
Write( inIntVector.data(),
elementCount * sizeof( int32_t ) );
}

31. Inlining / Embedding Templating
template< typename T >
void Write( const std::vector< T >& inVector )
{
size_t elementCount = inVector.size();
Write( elementCount );
for( const T& element : inVector )
{
Write( element );
}
}
template< typename T >
void Read( std::vector< T >& outVector )
{
size_t elementCount;
Read( elementCount );
outVector.resize( elementCount );
for( const T& element : outVector )
{
Read( element );
}
}

32. Linking
Data referenced by multiple objects cannot be
embedded
–Results in multiple copies of the object when
deserialized
Use Linking
–Assign object needs a unique id
–Serialize pointers to objects by writing the object’s id
•Serialize referenced objects separately / earlier
–When deserializing on remote host, replace an
object id with pointer to deserialized object

33. Linking Context
class LinkingContext
{
public:
uint32_t GetNetworkId( GameObject* inGameObject )
{
auto it = mGameObjectToNetworkIdMap.find(inGameObject);
return ( it != mGameObjectToNetworkIdMap.end() ) ?
it->second :
0;
}
GameObject* GetGameObject( uint32_t inNetworkId )
{
auto it = mNetworkIdToGameObjectMap.find( inNetworkId );

return ( it != mNetworkIdToGameObjectMap.end() ) ?
it->second :
nullptr;
}
private:
std::unordered_map< uint32_t, GameObject*>
mNetworkIdToGameObjectMap;
std::unordered_map< GameObject*, uint32_t >
mGameObjectToNetworkIdMap;
};

34. Compression
Bandwidth is limited
Our job: make the best use of it possible
Can use lossless compression
–Sparse Array Compression
–Entropy Encoding
And lossy compression
–Fixed Point Notation
–Geometry Compression

35. Sparse Array Compression
Writing mName for RoboCat:
Most of mName is probably empty
–don’t need 128 bytes
Prefix with length vs. postfix with null termination
–Worst case still128 bytes, best case very small
inStream.Write( mName , sizeof( mName ));
uint8_t nameLength =
static_cast< uint8_t >( strlen( mName ) );
inStream.Write( nameLength );
inStream.Write( mName, nameLength );

36. Serializing std::string
Storing strings in std::string can yield an automatic
benefit over storing in arrays
void OutputMemoryStream ::Write( const std::string& inString)
{
size_t elementCount = inString();
Write( elementCount );
Write( inString(), elementCount * sizeof( char ) );
}

37. Entropy Encoding
Compress data based on its entropy.
–How unexpected the values are
When values are expected, they contain less
information and should require fewer bits
Example RoboCat::mLocation
–Cat is usually on the ground at a height of 0
–So mLocation.mY is usually 0
•Use fewer bits to serialize Y when it is 0

38. Entropy Encoding Position
void OutputMemoryBitStream ::WritePos( const Vector3& inVector )
{
Write( inVector.mX );
Write( inVector.mZ );

if( inVector.mY == 0 )
{
Write( true );
}
else
{
Write( false );
Write( inVector.mY );
}
}
Single prefix bit indicates if mY is serialized or can be assumed to be 0

39. Entropy Encoding Expected Gain
Worst case, uses 33 bits for height. > 32!
Average case is what matters
–Need empirical data for frequency of 0 height
( assume 90% )
–Then expected value =
0.9 * 1 + 0.1 * 33 = 4.2
Net Improvement in average case!
 .2 bits much better than 32.

40. Entropy Encoding Cont’d
Can support even more common values by using more
prefix bits
–Remember to calculate expected bit count based on
empirical data
Extreme: build complete lookup table of all values based
on likelihood
–Huffman Coding!
Other entropy encoding worth exploring:
–arithmetic coding
–geometric encoding
–run length encoding

41. Fixed Point
Games use floating point numbers for most math
Floating point numbers are 32 bits
Values often don’t require 32 bits of precision
–Leave as floats for fast calculation at run time
–Convert to smaller precision fixed point numbers
during serialization
Fixed point numbers are integers with an implicit
constant division

42. Fixed Point Example
RobotCat:mLocation
–World extends from -2000 games units to 2000 game
units
–Empirical testing shows mX and mZ position values
only need to be accurate to within 0.1 game units
–How many possible relevant values are there for mX?
( MaxValue – MinValue ) / Precision + 1
( 2000 - -2000 ) / 0.1 + 1 = 40001
There are only 40001 possible values for mX
All values representable with only 16 bits

43. Fixed Point Example Cont’d
inline uint32_t ConvertToFixed(
float inNumber, float inMin, float inPrecision )
{
return static_cast< uint32_t > (
( inNumber - inMin ) / inPrecision );
}
inline float ConvertFromFixed(
uint32_t inNumber, float inMin, float inPrecision )
{
return static_cast< float >( inNumber ) *
inPrecision + inMin;
}
void OutputMemoryBitStream ::WritePosF(const Vector3& inPos)
{
Write( ConvertToFixed( inPos. mX, -2000.f, 0.1f ), 16 );
Write( ConvertToFixed( inPos. mZ, -2000.f, 0.1f ), 16 );
... //write y component here...
}

44. Geometry Compression
Some geometric data types have certain constraints
–E.g. Normalized Quaternion
•Squares of components sum to 1
–So can calculate magnitude of final
component from other three components
•Each component >= -1 and <= 1 and rotations
usually require less than 65535 values per
component
–So can use 16 bit fixed point instead of floats

45. Quaternion Compression
Single bit necessary to indicate sign of W
Uses 49 bits instead of 128
–If rotation is usually identity, use entropy encoding
for even greater savings!
void OutputMemoryBitStream ::Write( const Quaternion& inQuat )
{
float precision = ( 2.f / 65535.f );
Write( ConvertToFixed( inQuat. mX, -1.f, precision ), 16 );
Write( ConvertToFixed( inQuat. mY, -1.f, precision ), 16 );
Write( ConvertToFixed( inQuat. mZ, -1.f, precision ), 16 );
Write( inQuat.mW < 0 );
}

46. Quaternion Expansion
void InputMemoryBitStream ::Read( Quaternion& outQuat )
{
float precision = ( 2.f / 65535.f );
uint32_t f = 0;
Read( f, 16 );
outQuat.mX = ConvertFromFixed( f, -1.f, precision );
Read( f, 16 );
outQuat.mY = ConvertFromFixed( f, -1.f, precision );
Read( f, 16 );
outQuat.mZ = ConvertFromFixed( f, -1.f, precision );
outQuat.mW = sqrtf( 1.f -
outQuat.mX * outQuat.mX +
outQuat.mY * outQuat.mY +
outQuat.mZ * outQuat.mZ );
bool isNegative;
Read( isNegative );
outQuat.mW *= ( isNegative ? -1 : 1 );
}

47. Maintainability
Read and Write for data type must remain in sync with
each other
–Changing the order or compression in one method
requires changing the other
–Opportunity for bugs
Read and Write must remain in sync with data type!
–Adding or removing member variable
–Changing data type of member variable
•Including changing precision required!
–All opportunities for bugs!
Tradeoff: Improving maintainability can mean decreasing
performance

48. Abstracting Direction
How to keep Read and Write in sync?
–Replace with a single Serialize function
–Take a parameter to indicate serialization direction
–Or take a stream with abstracted serialization
direction
class MemoryStream
{
virtual void Serialize( void* ioData,
uint32_t inByteCount ) = 0;
virtual bool IsInput() const = 0;
};

49. Abstracting Direction Cont’d
class InputMemoryStream : public MemoryStream
{
...//other methods above here
virtual void Serialize( void* ioData, uint32_t inByteCount )
{
Read( ioData, inByteCount );
}
virtual bool IsInput() const { return true; }
};
class OutputMemoryStream : public MemoryStream
{
...//other methods above here
virtual void Serialize( void* ioData, uint32_t inByteCount )
{
Write( ioData, inByteCount );
}
virtual bool IsInput() const { return false; }
}

50. Serialize Implementation
template< typename T > void Serialize( T& ioData ) {
static_assert( std::is_arithmetic< T >::value ||
std::is_enum< T >::value,
"Generic Serialize only supports primitive data types" );

if( STREAM_ENDIANNESS == PLATFORM_ENDIANNESS )
{
Serialize( &ioData, sizeof( ioData ) );
} else {
if( IsInput() )
{
T data;
Serialize( &data, sizeof( T ) );
ioData = ByteSwap( data );
} else {
T swappedData = ByteSwap( ioData );
Serialize( &swappedData, sizeof( swappedData ) );
}
}
}

51. Data Driven Serializatin
Can use reflection data to serialize objects
–With data about member variables in each object,
procedurally serialize based on that data
–Data can be autogenerated by tool
–Changing data types automatically changes
serialization
–No more out of sync errors

52. Data Driven Serialization Cont’d
void Serialize( MemoryStream* inMemoryStream,
const DataType* inDataType, uint8_t* inData ) {
for( auto& mv : inDataType->GetMemberVariables() )
{
void* mvData = inData + mv.GetOffset();
switch( mv.GetPrimitiveType() )
{
EPT_Int:
inMemoryStream->Serialize(*( int* ) mvData );
break;
EPT_String:
inMemoryStream->Serialize(*( std::string*)mvData);
break;
EPT_Float:
inMemoryStream->Serialize(*( float* ) mvData );
break;
}
}
}