- 高速なFPS環境では、遅れて届いた状態情報の価値は低いため、Quake 3 は UDP/IP中心の設計 を採用し、遅延の低減を優先している
- NetChannel は損失のあり得る UDP 上の通信を抽象化し、サーバーはクライアントごとの スナップショット履歴 を使って必要な状態差分だけを再計算する
- サーバーは Master Gamestate、直近32件の gamestate、dummy gamestate を併用し、完全更新とデルタ更新 を同じ手順で作る
- クライアントからの ACK がない場合、サーバーは最後に確認されたスナップショットと現在の状態を比較し、欠落した変更と新しい変更 を1つのメッセージにまとめる
- C に組み込みイントロスペクションがなくても、
netField_t とマクロでフィールド差分を見つけ、NetChannel は 1400バイトの事前分割 でルーターによるフラグメンテーションを避ける
UDP/IP を前提にしたネットワークモデル
- Quake 3 のネットワークモデルはエンジンの中でも最も洗練された部分と評価されており、低レベルでは Quake World で初めて登場した NetChannel モジュールが通信を抽象化している
- 高速なゲームでは、最初の送信で取りこぼした情報はすぐに古い情報になるため、再送するより最新の状態を送るほうが有利である
- このためエンジンには TCP/IP の痕跡がなく、信頼性転送が生む遅延は受け入れがたいと考えられている
- ネットワークスタックには、相互に排他的な2つの層が追加されている
- 事前共有キーを使った 暗号化
- 事前計算された Huffman キーを使った 圧縮
- サーバーは UDP datagram のサイズを抑えつつ、非信頼性を補っている
- スナップショット履歴で デルタパケット を生成する
- メモリイントロスペクション方式で変更されたフィールドだけを見つけて送る
サーバーとクライアントの役割
- クライアント側の流れは単純である
- 毎フレーム、サーバーへコマンドを送る
- サーバーから gamestate 更新を受け取る
- サーバーは各クライアントに Master Gamestate を配信しながら、失われた UDP パケットも考慮しなければならない
- 中核となる仕組みは3つの要素で構成される
- Master Gamestate: 普遍的に正しいゲーム状態であり、クライアントのコマンドは NetChannel を通って入り、
event_t に変換された後、サーバー上でゲーム状態を更新する
- クライアントごとの直近32件の gamestate: ネットワークへ送信した状態をリングバッファに保存し、スナップショットと呼ぶ
- dummy gamestate: すべてのフィールドが 0 の状態で、以前の状態がないときのデルタ生成基準として使われる
- サーバーはこの3要素を使って NetChannel に渡す更新メッセージを作る
- クライアントごとの gamestate を多く保持する必要があるため、メモリ使用量は大きくなる
スナップショットで完全更新と部分更新を作る
- 例では Client1 に更新を送る状況で、Client2 の状態が
pos[X], pos[Y], pos[Z], health の4フィールドで構成される場合を用いる
- 通信は UDP/IP で行われ、インターネット上ではメッセージが頻繁に失われうる
-
最初のサーバーフレーム
- サーバーはすべてのクライアントから受け取った更新を Master Gamestate に反映した後、Client1 に状態を配信する
- ネットワークモジュールは毎回同じ手順に従う
- Master Gamestate をクライアント履歴の次のスロットにコピーする
- コピーしたスナップショットを別のスナップショットと比較する
- 最初の更新では Client1 の履歴に有効なスナップショットがないため、dummy snapshot と比較する
- dummy snapshot の全フィールドは 0 なので、結果は完全更新になる
- 各フィールドの前には変更有無を示すビットマーカーが付く
- 例の完全更新では 132ビット を使う
- 形式は
[1 A_on32bits 1 B_on32bits 1 B_on32bits 1 C_on32bits]
-
2回目のサーバーフレーム
- 次のフレームで Client2 が Y 軸方向へ移動し、
pos[1] の値が E になる
- Client1 は前回の更新受信を ACK したので、Snapshot1 は ACK 状態になる
- サーバーは Master Gamestate を次の履歴スロットへコピーして Snapshot2 を作り、有効な Snapshot1 と比較する
- その結果、変更された
pos[1] = E だけがネットワークへ送られる
- 各フィールドにビットマーカーが付くため、この部分更新は 36ビット を使う
- 形式は
[0 1 32bitsNewValue 0 0]
-
3回目のサーバーフレーム
- 次のフレームで Client2 は体力を失い、
health = H になる
- Client1 は最後の更新を ACK しない
- サーバーの UDP パケットが失われた可能性も、クライアントの ACK が失われた可能性もある
- いずれの場合でも、そのスナップショットは利用できない
- サーバーは Master Gamestate を次のスロットへコピーして Snapshot3 を作り、最後に ACK された Snapshot1 と比較する
- 送信されるメッセージは部分更新であり、以前の変更
pos[1] = E と新しい変更 health = H をまとめて含む
- Snapshot1 が古すぎて使えない場合、エンジンは再び dummy snapshot を基準に完全更新を送る
同じ手順で損失を補う仕組み
- スナップショットシステムの単純さは、同じアルゴリズムが2つの作業を自動的に処理する点にある
- 完全更新または部分更新の生成
- 受信されなかった以前の情報と新しい情報を1つのメッセージで再送すること
- UDP パケット損失を別の複雑なフローで処理するのではなく、最後に ACK されたスナップショットと現在の Master Gamestate の差分を計算して補完する
- 以前の状態がない、または使えない場合は dummy snapshot を基準に完全状態を送って復旧する
C でフィールド差分を見つける方法
- Quake 3 は C 言語にイントロスペクションがないが、各フィールド位置を
netField_t 配列とプリプロセッサ命令であらかじめ構成している
netField_t はフィールド名、offset、ビット数を持つNETF(x) マクロは文字列化演算子と entityState_t に対する offset 計算を使い、フィールド情報を短く書けるようにしている- 例の構造は次のとおり
typedef struct { char *name; int offset; int bits; } netField_t;
// using the stringizing operator to save typing...
#define NETF(x) #x,(int)&((entityState_t*)0)->x
netField_t entityStateFields[] = {
{ NETF(pos.trTime), 32 },
{ NETF(pos.trBase[0]), 0 },
{ NETF(pos.trBase[1]), 0 },
...
}
- 実装全体は MSG_WriteDeltaEntity の一部にある
- Quake 3 は比較対象の意味を解釈せず、
entityStateFields の index、offset、size をたどって差分をネットワークへ送信する
なぜ 1400 バイトで事前分割するのか
- NetChannel モジュールは UDP datagram の最大サイズが 65507 バイトであるにもかかわらず、メッセージを 1400バイト の断片に分割する
- 関連コードは Netchan_Transmit にある
- ほとんどのネットワーク MTU は 1500 バイトであるため、1400 バイト分割はインターネット経路上でルーターがパケットをフラグメント化しないようにするための選択である
- ルーターによるフラグメンテーションを避けるべき理由は2つある
- ネットワークへ入る際、ルーターはパケットを分割している間そのパケットを保持しなければならない
- ネットワークから出る際、datagram の全断片を待ったうえで高コストな再構成を行わなければならない
必ず届けなければならないメッセージ
- スナップショットシステムはネットワーク上で失われた UDP datagram を補完するが、一部のメッセージやコマンドは必ず届ける必要がある
- プレイヤーが終了する場合や、サーバーがクライアントに新しいレベルのロードを要求する場合がこれに当たる
- この保証は NetChannel が抽象化している
関連する読み物
まだコメントはありません。