56kモデム接続で大量の敵を処理したSerious Sam
(staniks.github.io)- Serious Engine 1はシングルプレイ・マルチプレイ・デモ再生を同じ決定論的シミュレーション上に載せ、毎ティックごとの全状態ではなくプレイヤーの行動とゲームストリームブロックを記録・送信する
- デモとマルチプレイは初期ゲーム状態を共有したうえで
CPlayerActionのような入力デルタを適用するため、乱数シードとゲームロジックの決定性が同期の鍵になる - ネットワーク層はUDPの上でシーケンス番号、ACK、再送、帯域制限、接続ごとのバッファを直接処理し、低速回線でもプレイを維持しようとしている
CNetworkMessageはシリアライズ、LZ77/LZRW1圧縮、XORベースのデルタエンコーディングを提供するが、チャットを含むメッセージは暗号化されず圧縮のみが適用されることがある- Serious Samのクライアント・サーバーモデルは各クライアントが独自のシミュレーションを維持して帯域を節約する代わりに、同期検証・予測・再送・CRC確認のような補助機構を必要とする
Serious Engineの共通シミュレーション構造
- Serious Engine 1 ソースコード は2016年にGNU GPL v2で公開されており、この分析は公開コードベースを読んでデバッグした内容に基づいている
- Serious Samは当初からマルチプレイゲームとして設計されており、シングルプレイキャンペーンも内部的にはマルチプレイ構造の特殊ケースのように動作する
- エンジンがサポートするモードは以下のとおり
- オフラインのシングルプレイキャンペーン
- オンライン、LAN、ローカル協力プレイと複数のゲームモード
- 1つのクライアントで複数プレイヤーが参加する分割画面
- デモ録画と再生
デモ録画: 全状態の代わりに行動を記録
- デモを毎ティックの全ゲーム状態で保存するとファイルが大きくなるため、Serious Engineは録画開始時点の完全なゲーム状態を一度だけ保存し、その後は毎ティックゲームストリームブロックを記録する
- ゲームストリームブロックには次のメッセージタイプが入る
MSG_SEQ_ALLACTIONS: プレイヤー行動MSG_SEQ_ADDPLAYER: プレイヤー追加MSG_SEQ_REMPLAYER: プレイヤー削除MSG_SEQ_PAUSE: 一時停止または解除MSG_SEQ_CHARACTERCHANGE: プレイヤーキャラクター属性変更
- 中核は
MSG_SEQ_ALLACTIONSで、エンジンはアクティブな各プレイヤーについてCPlayerActionオブジェクトをデシリアライズし、CPlayerTargetに適用する CPlayerActionはプレイヤー状態を保持する- ワールド空間基準の移動速度
pa_vTranslation - ワールド空間基準のキャラクター回転
pa_aRotation - ワールド空間基準の視点回転
pa_aViewRotation - 現在押されているボタン
pa_ulButtons - TSCベースのミリ秒タイムスタンプ
pa_llCreated
- ワールド空間基準の移動速度
- 再生時には初期ゲーム状態を読み込み、各ティックのプレイヤー行動を実際のプレイのように適用する
決定性が必要な理由
- この構造は、ゲーム内のあらゆるものが完全に予測可能であり、プレイヤー行動だけがゲームを変化させるという前提に立っている
- 乱数もゲーム状態の一部であるシードを使う疑似乱数生成器で処理される
CEntity::IRnd()はCSessionState::Rnd()を使うses_ulRandomSeedはゲーム状態のデシリアライズ過程で初期化される
- 真の乱数生成器や異なるシードを使うと、同じデモを再生しても結果が変わる可能性があり、これは同期ずれにつながる
浮動小数点とティック処理
- PC版Serious SamはもともとWindows専用として発売されたため、同じコンパイラとランタイムを使う前提が浮動小数点同期の問題を減らしていた
- レンダラーはDLLであり、OpenGLやDirectX API呼び出しがFPU精度を変える可能性があるため、Serious Engineは
CSetFPUPrecision FPUPrecision(FPT_24BIT)のような精度ガードを使っている - 丸め制御を明示的に設定している箇所は見つからなかったが、
_controlfpで_RC_NEAR状態を確認するassertは存在する - ゲームロジックはレンダリングフレームレートから分離されている
- レンダリングはハードウェアや設定に応じて変わり、内部的には500 FPSに制限されているようだ
- ゲームロジックは毎秒20ティックで固定されている
- 滑らかな動きは現在のティックと前のティックの間を線形補間して作られ、コンソールで
/net_bLerping=0にすると補間を無効化できる
UDP上に構築された独自パケット層
- Serious Engineのマルチプレイには
StartPeerToPeer_tのような関数名が残っているが、実際のモデルはクライアント・サーバー構造である - サーバーはクライアントメッセージを受け取って処理し、関連情報をすべてのクライアントへ配信する
- 各プレイヤーはデモシステムに近い形で自身のシミュレーションを実行し、他プレイヤーの行動情報を受け取って状態を進める
- ネットワークはUDPを使い、順序入れ替わりや損失を解決するために独自プロトコルを重ねている
CPacketはパケット順序と信頼性を管理するpa_ulSequence: シーケンス番号として順序付けと重複除去を行うpa_ubReliable: 信頼性フラグを持つpa_ubRetryNumber: 再送回数を追跡するpa_tvSendWhen: 送信予定時刻と輻輳制御に使われる
- 信頼性パケットはACKを待ち、ACKがなければ再送される
- 最大再試行回数は
net_iMaxSendRetriesで設定され、デフォルトは10のようだ - 再送間隔は
net_fSendRetryWaitで設定され、デフォルトは0.5fのようだ
- 最大再試行回数は
- 信頼性パケットは複数パケットに分割されたストリームを作れる
- 最初のパケットは
UDP_PACKET_RELIABLE_HEAD - 最後のパケットは
UDP_PACKET_RELIABLE_TAIL - 単一の信頼性パケットは両方のフラグを持つ
- 最初のパケットは
- 非信頼性パケットは損失時にストリームが壊れる可能性があるため、ストリームを構成しない
接続ライフサイクルとパケットルーティング
CCommunicationInterfaceはパケット層通信を担当し、サーバー用・クライアント用・ブロードキャスト用のインターフェース関数を持つ- サーバーとクライアントのインターフェースは接続先が既知である前提で、ブロードキャストインターフェースは任意アドレスとの送受信に使われる
CCommunicationInterfaceは2つのマスターバッファを維持するcci_pbMasterInput: 入ってきたUDPパケットをCPacketにデシリアライズして保存するcci_pbMasterOutput: 送信するCPacketをシリアライズしてソケットAPI経由で送る
- 実際のクライアント別通信抽象化は
CClientInterfaceが担う- サーバーは
cm_aciClients配列で各プレイヤーインターフェースを持つ - クライアントは
cm_ciLocalClientでサーバーと通信する - クライアントとサーバーの双方が接続確立に
cm_ciBroadcastを使う
- サーバーは
CAddressのadr_uwIDはクライアント固有識別子またはブロードキャストパケットの印として使われる- 値が
'//'または0ならブロードキャストパケット - それ以外の値はセッション内クライアントID
- 値が
接続確立と基本的なセキュリティ機構
- クライアントはサーバーへ接続するため、
UDP_PACKET_CONNECT_REQUESTフラグ付きの信頼性ブロードキャストパケットを送る - サーバーは同じアドレスとポートのクライアントがすでに接続済みなら、その要求を無視する
- 新規クライアントであれば、サーバーは空いているクライアントインターフェースを探し、次の処理を行う
- そのクライアントの固有識別子を生成する
UDP_PACKET_CONNECT_RESPONSE信頼性ブロードキャストパケットで識別子をクライアントへ送る
- 識別子は固定インデックスだけでなく、タイマー値の一部とクライアントインデックスを組み合わせて作られる
- 他プレイヤーになりすますには
uwIDを一致させる必要があるため、攻撃面は縮小される - 未接続プレイヤーが非ブロードキャストパケットを送ると、Serious Engineはコンソールに警告を出すことがある
シングルプレイとデモはローカル接続の特殊ケース
- シングルプレイとデモ再生も内部的にはサーバーとクライアントが存在するが、同一プロセス内で動作する
- 同一プロセス間でソケットを使う必要がないため、
Client_OpenLocal()はローカルクライアントインターフェースとサーバー側インターフェースを相互接続する - 接続された2つの
CClientInterfaceはExchangeBuffersにより、一方の出力バッファのパケットを他方の入力バッファへ移す - ローカルプレイはマスター入出力バッファや実際のネットワークソケットを経由しなくてよい
ネットワークメッセージ層
CNetworkMessageはパケット上のメッセージ抽象化で、ストリームのように読み書きできる- メッセージは
Read,Write,ReadBits,WriteBitsと<<,>>演算子でシリアライズ・デシリアライズされる - 下位メッセージも保持でき、必要なデータを書いた後に
Shrinkでバッファサイズをデータサイズに合わせられる CNetworkMessageバッファはAllocMemoryを通じて確保され、内部的にはmallocを呼んでいるようだCLinearAllocatorは存在するが使われている箇所は見つからず、メッセージバッファは頻繁に確保・再確保される
圧縮とデルタエンコーディング
- メッセージは指定した圧縮器、またはメッセージタイプごとのデフォルト圧縮器で圧縮できる
MESSAGETYPEは下位6ビットがタイプで、残り2ビットが圧縮方式を示す- LZ77
CzlibCompressor - LZRW1
CLZCompressor - 非圧縮
- LZ77
- デフォルト圧縮はLZRW1のようで、
net_iCompressionシェル変数で変更できる CPlayerActionはそのまま送らず、現在の行動と前回の行動をXORしたデルタを作って送信する- 受信側は前回の行動にそのデルタを再びXORして元の
CPlayerActionを復元する - デルタはデータ変化が小さいほど圧縮効率が高くなる
- 押下キーは複数フレームにわたって維持されることが多い
- 速度や視点回転も浮動小数点の全範囲を大きく行き来しない
- サーバーが
MSG_SEQ_ALLACTIONSで複数プレイヤーの行動をまとめて送る場合、この方式の効果はさらに大きくなる可能性がある
メッセージ暗号化とチャット
- Serious Engineのメッセージは暗号化されていない
net_iCompression=0で圧縮を無効にすると、ゲーム内チャットメッセージはUDPパケットのペイロードに平文で見える- 実際には圧縮が有効だと、パケット盗聴者はLZ圧縮ストリームを解析して展開する必要があるが、必要なデータはパケット内に含まれている
- 当時のゲームは暗号化を扱わないことも多く、認証や鍵交換のような仕組みを実装すると複雑さが増していた可能性がある
- 当時のWebも大半はHTTPだった
ゲームセッション層
CNetworkLibraryは名前に反して、ゲーム状態CSessionStateを含むゲームセッションを管理するCNetworkLibraryは先述のCMessageDispatcherを継承している- サーバー起動時、エンジンは次の手順を実行する
- CRC収集を初期化し、接続クライアントがサーバーと同じファイルを持つか確認する準備をする
- 新しい
CSessionStateを作成し、シリアライズして基本状態ga_pubDefaultStateに保存する - ローカルワールドインスタンスを読み込む
- グローバル通信インターフェースを初期化する
- ローカルセッション状態を初期化し、クライアント接続時に基本状態とサーバー現在状態の状態デルタを送れるようにする
- CRC収集を終えて
ga_ulCRCに保存する
- CRC確認はチート対策というより同期ずれの早期検出に近い
- クライアント参加手順は次の流れをたどる
- 空のローカルセッション状態と通信インターフェースを初期化する
MSG_REQ_CONNECTREMOTESESSIONSTATEでビルドバージョン、モード名、サーバーパスワード、ローカルプレイヤー数、CSessionSocketParamsを送るMSG_REP_CONNECTREMOTESESSIONSTATEでメッセージ、ワールドファイル名、難易度・ゲームモードフラグ、セッション属性を受け取る- 基準ゲーム状態を初期化する
MSG_REQ_STATEDELTAを送ってサーバー現在状態との差分を要求するMSG_REP_STATEDELTAを受け取った後、逆方向diffでゲーム状態ストリームを再構築するCSessionState::Read_t()でローカルセッション状態を初期化する- CRCチェックを実行し、不一致なら接続を切断する
メインループとゲームストリーム再送
- クライアントとサーバーのメインループは概ね似ているが、サーバーは追加処理も行う
- ループはローカルクライアントインターフェースとブロードキャストインターフェースを更新し、ローカルセッション状態が受信したネットワークメッセージを処理する
- サーバーは対応するクライアントインターフェース間のバッファ交換、サーバー側クライアントインターフェース更新、GameAgent更新、リモート管理シェルコマンド処理も担当する
SessionStateLoop()は非信頼性メッセージと信頼性メッセージを分けて処理する- 非信頼性:
MSG_GAMESTREAMBLOCKS,MSG_KEEPALIVE,MSG_INF_PINGS,MSG_CHAT_OUT - 信頼性:
MSG_INF_DISCONNECTED,MSG_ADMIN_RESPONSE
- 非信頼性:
MSG_GAMESTREAMBLOCKSは非信頼性メッセージだが、欠落すると同期が壊れる可能性がある- Serious Engineはゲームストリーム処理段階で欠落したシーケンスを確認し、再送を要求する
- 次に期待されるシーケンスブロックがあれば処理する
- 次のブロックも、さらに新しいブロックもなければ、そのループでは何もしない
- 次のブロックはないが、より新しいブロックがあるなら欠落の可能性があるためタイムアウトを設定する
- タイムアウト後、
MSG_REQUESTGAMESTREAMRESENDで欠落ブロックのシーケンスと件数を要求する
- サーバーは要求されたゲームストリームブロックを再送する
ゲームストリームブロック処理
MSG_SEQ_ADDPLAYERはプレイヤーがゲームに入るとき送信され、プレイヤーインデックスとCPlayerCharacter記述子を含むMSG_SEQ_REMPLAYERはプレイヤー切断時に送信され、プレイヤーインデックスだけを持つMSG_SEQ_CHARACTERCHANGEはプレイヤー名、チーム、外見変更を伝える- Serious Samでは外見バッファに
CPlayerSettings構造が入る - これにはプレイヤーモデルファイル名、武器自動選択ポリシー、照準タイプ、複数のフラグが含まれる
- Serious Samでは外見バッファに
MSG_SEQ_PAUSEは一時停止または解除を伝え、要求したプレイヤー名をコンソールに表示するMSG_SEQ_ALLACTIONSは現在ティック時刻と全プレイヤー行動を含む- 各
CPlayerTargetにCPlayerActionを適用する - その後、タイマー、イベント、移動エンティティ、物理処理を実行する
- 各
- 同期チェックは
MakeSynchronisationCheck()により行われる- エンティティやプレイヤーターゲットなどの
ChecksumForSync()によってCSyncCheckを作る - クライアントは
MSG_SYNCCHECKをサーバーに送り、サーバー状態と一致しなければ接続が切断される
- エンティティやプレイヤーターゲットなどの
予測による入力遅延の緩和
- 予測は、インターネット遅延によって高速ゲームが鈍く感じられる問題を減らすための仕組みである
- ローカルプレイヤー予測はサーバーへ送った行動を使う
- リモートプレイヤー予測はサーバーから最後に受け取った行動を使う
- クライアントがサーバー応答を待たずに実際のゲーム状態を直接進めると、他プレイヤーの行動を知らないため同期が壊れる可能性がある
- Serious Engineは実状態と予測状態を混ぜないためにpredictorを使う
- predictorは通常エンティティに結び付いた「ゴースト」複製に近い
- temporary predictorは予測中に生成され、実際のゲーム状態に対応するエンティティを持たない
- 予測ティックを処理するときはpredictorエンティティだけが処理される
- クライアントがサーバーからプレイヤー行動を受け取ると、既存predictorを破棄して新しい予測サイクルを開始する
- レンダリング時には予測中の元エンティティを描画せずpredictorを描くことで、実状態を大きく変えずに動きが進んでいるように見せる
- ローカルプレイヤーは
plt_abPredictionに保存されたサーバー送信行動数ぶんだけ予測できる - リモートプレイヤー予測で
cli_bLerpActionsが無効なら、最後に受信した行動を繰り返す cli_bLerpActionsが有効なら最後の2つの行動の間を線形補間するが、デフォルトでは無効になっている
Doom・Quakeとの比較
- Doomのネットワーキングは実際にはピアツーピアだったが、クライアント同士が
CPlayerActionに近い構造を交換し、それぞれ独立シミュレーションを回していた - Doomもデモ録画と再生に似たシステムを使っていた
- Quakeは別の構造を採用し、クライアントが大部分のゲームロジックを直接処理せず、サーバーの状態更新を受け取る方式に近かった
- Quake方式は同期問題をあまり気にせずに済み、サーバーが壁の向こうのエンティティ情報を送らないといった形でチート対策もしやすい可能性がある
- Serious SamではQuakeよりアクティブな敵やオブジェクトがはるかに多いセッションが一般的で、毎ティック大量のオブジェクト状態を送ると帯域負荷が大きかった可能性がある
移植性と構造的な限界
- 一部のネットワークメッセージは構造体を
reinterpret castに近い方法でシリアライズしている - 単一コンパイラ・単一プラットフォーム前提なら成立しても、クロスプラットフォームゲームでは構造体レイアウトやパディングが異なる可能性がある
- 32ビット実行ファイルは4バイト境界、64ビット実行ファイルは8バイト境界でのアラインを試みる可能性がある
- エンディアン問題も存在する
- x86 PCはリトルエンディアン
- PS3はビッグエンディアン
- Serious Engineの構造は、ネットワークやファイルといった伝送媒体の違いをゲームロジックから抽象化している点でエレガントだが、全クライアントがゲーム状態のコピーを持つモデルであるためチートが可能になる
- たとえば改変クライアントがデスマッチで壁の向こうにいる他プレイヤーの輪郭を表示できる
1件のコメント
Hacker News の意見
Serious Sam のネットワークコード実装を担当した開発者の一人だった
Croteam のオフィスの机の下でよく寝ながら Usenet を漁っていて、特に QuakeWorld の予測システムを説明した投稿に触発された
その夜、同僚の Dan が遅延をシミュレートできる古い 486 Unix マシンをルーターとして使ってテストしている間に、単純な最小機能の実装をコーディングした
実際のゲームがその上に作られるずっと前のことだった
いまだにあの音が聞こえる
協力プレイとシューティングゲームが大好きだったが、友人たちはいつも Counter-Strike ばかりやりたがった
Serious Sam のおかげで、たまには自分の好きなゲームを一緒にやろうと説得できた
叔父は自分の人生で本当に大切な人で、彼の好きだったゲームを遊ぶことは、その思い出とつながる良い方法だ
素晴らしいゲーム、素晴らしいマルチプレイ、そしてとても良い思い出として残っている
Serious Sam は常に強力な LAN パーティー向けゲームだった
当時いちばん派手なタイトルだったからでも、誰かが事前に計画したからでもない
ほかのゲームがドライバー問題、発熱問題、アップデート問題などで死んでいく中、Serious Sam を起動するとただ動いたので、LAN パーティーを支配した
続編でもこの点は受け継がれ、誰かの PC が完全におかしくなっても安定して画面分割をサポートし、入力デバイスもきちんと扱えた
ゲームのシステム面は信頼性という点で本当に優れていた
同じように Counter-Strike もグラフィックは良くなかったが、トースターのような PC でもよく動いたので長く人気を保った
業務用 PC で安定してよく動く唯一の一人称シューティングゲームで、本当に面白かった
当時の EA では QA と技術サポートがかなり重なっており、サポート担当者は夏には年末発売に間に合わせるための社内ベータテスターとして働き、クリスマス頃に電話が増える冬には技術サポートをしていた
Vigilante 8 の Game Boy Color 移植版でマルチプレイを実装する際、決定論的なゲームプレイを使った
GBC のリンクケーブルは双方向に同時に 1 バイトをやり取りし、ケーブルを挟んで互いを埋め合う一対のシフトレジスタのように動作した
ゲームは GBC のフレームレートに固定されていて、実質的に V-Blank ごとに画面更新作業が多く必要で、これを逃すと滑らかなスクロールが途切れた
マルチプレイ開始時にはシードを交換し、実行はこんな感じだった。A フレームで入力を読み取り、1 バイトに圧縮して送信バッファに入れる。B フレームをレンダリングしている間に送信が行われる。C フレーム開始時点では、A フレームで送ったローカル入力と B フレームで受け取った相手の入力が手元にある
それらの入力をゲーム状態に適用して C フレームをレンダリングするので、ローカルとリモートの入力はいずれも1フレーム遅延で適用された
ローカルプレイには入力遅延がなかったので、マルチプレイで負けたなら遅延のせいにしていいし、必要なら特別に自分のせいにしてもいい
本当に良いゲームで、マルチプレイ実装についての技術的な説明もとても素晴らしい
Croteam は本当に才能あるゲーム開発チームだ
The Talos Principle の 1 作目と 2 作目を本当に楽しんだし、1 作目では完全カスタムの Vulkan ゲームエンジンを早くから作った先駆者の一つだった
Age of Empires の「28.8K で弓兵 1500 人」と同じようなアイデアなのか気になる
https://www.gamedeveloper.com/programming/1500-archers-on-a-...
非常に多くのゲームが長い間このシステムを使ってきたが、最近はいくつかの理由で以前ほど一般的ではないようだ
資源があるかないかのどちらかでよく、制限のための制限を設ける必要はない
帯域幅が 10 倍あるゲームでも、それほど多くの敵をサポートするのに苦労している
今になって気づいたが、技術資源の増加はコンピュータサイエンスの効率性と創造性にむしろ逆効果をもたらしているようだ
帯域幅、ストレージ、メモリ、計算能力が増えるほど、ソフトウェアは資源単位あたり、より遅く、より肥大化し、より無能になる反応を示す
ベンジャミン・バトン式ソフトウェア設計効果と呼べそうだ
記事に数字があるなら見つけられなかった
現代のゲームにも、マルチプレイでありながら敵数が十分に「大規模」と見なせるものは多いし、重要なのがプレイヤー数なら、大規模なプレイヤー数をサポートするゲームもある
前に進むよりも後ろに動いていた時間のほうが多かったゲームだと思う
Steam にあり、同じ制作会社かは分からないが Serious Sam の世界観に属している
Factorio の構造も似ていて、ほぼ入力イベントだけを送信し、ロックステップ・シミュレーションコアに依存している
例外的に鉄道計画ツールのような目立つ部分はある
満足感があり、テストしやすい設計上の制約に見える
子どもの頃、PC Gamer のデモで Serious Sam を遊んだ記憶がある
その頃すでに、昔の DOOM や Quake の時代に戻ったようなレトロ風ゲームだと見なされていた
今では文字通り 20 年が経ち、それ自体が古典になった
Starsiege: Tribes は 56K 接続でも規模が大きく、ばかばかしいほど楽しかった
https://www.gamedevs.org/uploads/tribes-networking-model.pdf
実は少し前に Tribes 2 をダウンロードして、数か月前にもボット相手にプレイした
古いゲームだが今でも面白く、Unity のようなもので作り直してみたいとよく思った
いつかやるかもしれない
1999 年に手続き的に生成された地形をスキーのように滑り降り、ほかの人たちがその上をスキーのように登っていくのを見て、さらに大きなマップと多くのプレイヤーまであった