Multiplayer Game Programming読本

multiplayer game programmingという本を気になる部分だけつまみ食いして読んでいる今日はChapter 4にあった"Compression"をまとめる英語の見出しは本文のタイトルを引用し、日本語の見出しは私がみやすさでつけたもの

Compression

マルチプレイのリアルタイム性のあるゲームであればあるほど、通信するオブジェクトと頻度が増え必要な通信帯域が増加するそのため、可能な限り無駄な情報は削減して通信を行う必要があるこの章では低レベルな圧縮方法の紹介を行っている

Sparse Array Compression

本で扱っているサンプルゲームでは名前を128byteまで許容されている。名前の配列に128byteの配列を利用するのがプログラムとしては妥当だが、128byte使い切らないユーザーも含まれるため不要なスペースができてしまう。そこで、名前長 + 名前というバイト列にする事で余計なスペースを除去するという圧縮方法

Entropy Encoding

以下の章ではオブジェクトの方向と回転を表す7つのfloatの圧縮方法について記載されている参考書ではbyte配列を渡す想定をしているが、理解を助けるために下記のような構造体の形式で書いていく

// 合計 28byte
type XXX struct {
	type Location struct {
		x float
		y float
		z float
	}
	type Quartunion struct {
		qx float 
		qy float
		qz float
		qw float
	}
}

頻出する状態には短いデータを与えましょう。という内容サンプルゲームではキャラがほとんどY=0のポジションにいる特性を利用してY=0ならばtrue, そうでなければfalse+floatの情報を送っている

// 合計 24byte + 1bit
type XXX struct {
	type Location struct {
		x float
		ybit bool
		y float
		z float
	}
	type Quartunion struct {
		qx float 
		qy float
		qz float
		qw float
	}
}

Fixed point

Locationの他の2軸の圧縮をするこの内容はゲームの特性と相談になるが、整数値にすることでサイズを減らそうというもの本では縦横に40000(おそらくpx)が表現できれば良いため、int16でよいという内容だった

// 合計 20byte + 1bit
type XXX struct {
	type Location struct {
		x int16
		ybit bool
		y float
		z float
	}
	type Quartunion struct {
		qx float 
		qy float
		qz float
		qw float
	}
}

Geometry Compress

Quartunionは基本的に4つの要素(float)を相手に送るつまり基本的に4byte * 4 = 16byteの帯域を必要とするこれがオブジェクト数分あるため削減ができるならしたい

Quartunionは標準化すると各要素の乗数の合計が必ず1になる具体的には下記の式が成り立つ

Qx^2 + Qy^2 + Qz^2 + Qw^2 = 1

この性質を利用して要素を一つ減らすことができる

ただし、正負の判断用にbool値1bit分を送る必要があるので31bit削減ができる

// 合計 16byte + 2bit
type XXX struct {
	type Location struct {
		x int16
		ybit bool
		y float
		z float
	}
	type Quartunion struct {
		qx    float
		qy    float
		qz    float
		qwbit bool
	}
}

サンプリング

ここの内容はゲームの特性と相談になる回転、360℃を表現するのに4byteを要するは無駄に思えるそこで2byte(16bit)にしてしまおう 16bitは65535まで表現できるためこれでも十分なゲームは多いと思われる

// 合計 10byte + 2bit
type XXX struct {
	type Location struct {
		x int16
		y int16
	}
	type Quartunion struct {
		qx    int16
		qy    int16
		qz    int16
		qwbit bool
	}
}

これにより28byte -> 10byte+1で36%の削減ができた

所感

Entropy EncodingやFixed Pointに関してはゲーム特性に依存する部分が大きい。まぁ、それこそがゲームエンジニア(特にバックエンド)の楽しいポイントだと思う。 Quartunionは納得できる箇所も多く学びが多いものだった(こちらのサンプリングは利用機会も多そう)

とはいえ、これで36%しか減らずアイテム増加と線形比例するのは変わらないので小手先な手法とも言える (貶めるつもりはなく通信設計をきちんとした上で、これらを進めたほうがコストに対してリターンが大きそうだという意味)

Compression#

Sparse Array Compression#

Entropy Encoding#

Fixed point#

Geometry Compress#

サンプリング#

所感#