リアルタイム通信が必要なアプリケーションを触ることが増え、必要な知識を体系的に入れたいなと思って「オンラインゲームを支える技術」を読んだ。
15年前の書籍ながら、リアルタイム通信に必要な知識が体系的にまとまっていて、今でも参考になることが多かった。
特に参考になったのは、ゲームの反応速度（レイテンシ）の許容度に応じて「同期式（25ms以下）」「非同期式（100ms以下）」「ブラウザ式（300ms以下）」という3つの実装方式があると整理した上で、それぞれの方式でどういうアーキテクチャがあるかを具体的に解説してくれている部分。
- 同期式では、フルメッシュ型（全端末がコントローラ入力を送り合い、全員分のデータが揃うまでゲーム進行を待つ）とスター型（サーバに入力を集約して進行結果を返す）の2つの実装方法と、人数が増えると同期が崩れる・ホストが離脱すると全体が止まる・途中参加が難しいといった問題点が説明されている
- 非同期式では、ゲーム世界を「自分・相手・環境」の3要素に分解し、どこをどう妥協するかを検討する指針が示されている。たとえば自分と相手の整合性は損得で上書き方向を決める（損する側の結果を採用、得を与える側の結果を採用）、環境のアイテム排他制御は調停役を置く、といった具体的な実装方針までセットで紹介されている
- ブラウザ式の代表であるMMO型では、ゲームサーバのボトルネック解消方法として空間分割法やインスタンス法といったアーキテクチャが取り上げられている
このように、自分が作りたいシステムの許容レイテンシから実装方式を選び、その方式で取りうるアーキテクチャの選択肢を一通り眺められる構造になっているのが非常に良かった。
かなり勉強になることが多かったので、リアルタイム同期が必要なゲームや、リアルタイム通信処理を実装することになった人は読んでみると良さそう。
読書ノート
- 16ミリ秒はプレイヤーにとってゲームの状態変化を認識できる最も短い時間間隔 11
- C/S型ゲームの実装においては、サーバー側で高い性能を持つプログラムの構築が必要。P2P型ではクライアント側で高い性能が必要 64
- 高性能・高機能サーバーは以下の特性を持つ 64
1. 小帯域: 毎秒数回から20回程度、数百バイトまでの通信を続ける接続を
2. 超多数: 1サーバーあたり数千から数万の接続を維持したまま
3. 低遅延: 数ミリ秒から20ミリ秒以内の遅延で処理を行い結果を返す
4. ステートフル: サーバーは状態を持っていて、敵などの可動物が多数リアルタイムにオンメモリ動作を続けている
- 高性能・高機能クライアントの特性は以下の通り 64
1. 小帯域
2. 少数: 1クライアントあたり数本まで
3. 低遅延
4. ステートフル: クライアントは状態を持っていて、クライアント上でオンメモリ動作。さらに画面描画などの非常に重い処理も同時に行う必要がある
5. 多様性: クライアントのネットワーク状況の多様性に対応できる必要がある
- サーバーに比べると接続数は少ないが、描画という重い処理を行いながら遅延なく通信し、多様性に対応する必要がある。
- オンラインゲームサーバーは複数のユーザーが一つのゲーム状態をリアルタイムに共有する必要があるため、非同期に入出力の多重化をするか、スレッドを使って同期的な処理を並列化するかのどちらかをとる。プロセスフォークは使わない 87
- OSI参照モデルを用いて、ごく小さなデータを大量にコマ切れで送信するとヘッダが占める分が多くなり効率が悪い。逆に1400バイト程度の大きなデータ単位なら理論値通りの通信速度が出る。オンラインゲームではアプリケーションのデータ単位が20バイト程度しかないので、理論値の数分の1の速度しか出ないことが多い。理論値の10分の1を目安 87
- クライアント側がサーバーと通信するときは確実にデータが送られていることを保証したい。ネットワークに出力要求をとりあえずバッファに積み込んで、後で確実に実行するという動きが必要。 110
- ユーザー入力は内部のバッファーに送信用地のデータを積むだけ
- オンラインゲームではバイナリフォーマットで特に複雑な階層構造を持つデータを送ることに対応していない単純なもので十分。例えばProtocol Buffersという形式など 116
- ゲームプレイの基本は認知・判断・操作の繰り返し 193
- オンラインゲームの4つの形式とゲームジャンル 251
| | MO | MMO |
| --- | ---------------------------------------------------- | --------------------- |
| C/S | カジュアル | **MMORPG**<br>仮想世界、大戦 |
| P2P | **ARPG（アクションRPG）**<br>対戦格闘、FPS<br>レース、RTS<br>シューティング | × |
- ネットワーク遅延と実装方法 258
- 同期式とは、参加しているプレイヤー全員の端末で動作するプログラムが同期して動作するモデル。1人でもプログラムの進行が遅い場合は全体が止まる
- 非同期式とは、端末プログラムが非同期動作し、各端末のゲーム進行の状態も非同期になる。ある端末プログラムの動作が止まっても進行できるが、データ不整合が生まれる可能性がある
- ブラウザ式とは、サーバーで全てのゲームが進行し、他のプログラムではそれを閲覧しているだけのモデル。端末プログラムが停止しても進行ができ、不整合は起きない。しかし、サーバー経由するため、レイテンシが増大する。
| 名称 | 遅延 | 同期 / 非同期 | 冗長 | 補足 |
| ----- | -------- | -------- | --- | ---------------------------------------------------------------- |
| 同期式 | 25ミリ秒以下 | 同期 | 非冗長 | 高速なネットワークを前提として同期的な実装方法で良い |
| 非同期式 | 100ミリ秒以下 | 非同期 | 冗長 | 低速なネットワークで高速なプレイを実現するため冗長性が必要 |
| ブラウザ式 | 300ミリ秒以下 | 非同期 | 非冗長 | 遅延の大きさが冗長性によって解決できる限界を超えているので、ゲームデータとゲームクライアント（ゲームブラウザ）を完全に分離させる |
- ゲームプログラミングには特性上オンメモリが必要 276
- 1. 16ミリ秒という短時間にゲームのデータが変化し続ける
- 2. ゲームの面白さのため大量のオブジェクトを表示する必要があることが多い
- 3. プレイヤーの操作はいつ入るかわからないため、前もって計算できない。
- 通信レイテンシの最小化のため、実際に使われるネットワークトポロジはスター、フルメッシュ 307
- P2Pではフルメッシュ（同期式） or スター（ホストがあるタイプ） or バス（リフレクト型）。C/S MMOでは常にスター
- ゲームでは、耐障害性や全体のスループット以上に通信レイテンシを最小にしたいという要求の優先順位が高いから
**いろんなアーキテクチャ**
- 同期式は全員分の情報が揃うまでゲームを進行させない方法 319
- 同期式/フルメッシュ型は、ゲームに参加しているすべての端末がマスターデータを用い、すべてのコントローラー入力情報を互いに送り合い、すべての端末からの入力データが揃うまで待つ
- コントローラの情報を送り合う
- 必要な前提条件。入力による状態変化の結果が確実に同じであること 324
- 初期状態は厳密に同じである
- すべての入力情報パケットがすべての端末に確実に漏れなく届く
- ゲーム進行のデータが乱数で変化しない。シードがある疑似乱数なら問題なし。
- ゲーム進行のデータが揺らぎで変化しない。例えば微妙なタイミングによって異なる結果にならない。
- 以下のようにすれば条件を簡単に満たせる
- 乱数シードをすべての端末で揃える
- すべての端末で完全に同じデータでゲームを初期化
- ループを開始する
- 全員分の入力情報を通信して揃えるまで待つ
- プレイヤーAからZの順番で処理し、ゲーム状態を変更
- 描画
- 次の操作を受け付ける
- 自分の分の入力情報を送る
- 問題点
- 人数が増えると、送受信の完全性が急激に崩れやすくなる
- 最も遅い端末に引っ張られる
- ゲームへの途中参加ができなくなる
- 同期式/スター型は、一つの大元のゲームデータを管理するサーバーを設定し、全ての参加端末はプレイヤーの入力情報を全てサーバーに送信し、サーバーがゲームの進行状況を一歩進めて、その差分を全てのクライアントに送り返す。クライアント側はサーバーから情報が来るまでは、実際に描画をせずただ単に待つ。 319
- 最大の利点はプレイヤー数の増加に対して必要な通信経路の増加が少ないので、ゲーム情報の不整合確率が大幅に下がる 334
- スター型の4つの問題 334
- レスポンスがちょっと悪い
- プレイヤーA（ホスト）が途中で離脱したらゲーム全体が回復不能で強制中止
- プログラム構造がフルメッシュ型より少々複雑
- プレイヤーAの端末の通信負荷が他よりも大幅に高く不公平
- 同期式全体で、途中からプレイヤー追加する場合には、ゲームの状態全体を送る必要があり、通信量によっては途中参加が難しくなるという大きな問題がある 334
- 同期式を用いるとプログラムの内容を単純に保っていてメリットがとても大きいので、様々な工夫をして同期式を使おうとする 337
- 途中参加の必要性自体をなくす：レースゲームや対戦、格闘ゲームのように1回のゲーム進行が数分以内で終わるようにする
- レイテンシを少なくする：プレイヤーマッチングシステムを工夫し、地理的に近くにいるプレイヤーを優先的にマッチングする。
- 非同期式の最大特徴は、それぞれの端末におけるゲーム進行の状態が異なっていることを認めること 337
- ゲーム内容の詳細理解と分析をし、何をどのように妥協すべきかを検討する必要がある。
- ゲーム世界を構成する基本要素を自分、相手、環境の3つに分解する
- 関係も(1)自分と相手、(2)自分と環境、(3)環境と相手という3つがある。この時1と2は極めて重要だが、3は重要ではない。1と2はゲームの内容による。格ゲーなら1が主軸、大量の迫り来る敵を倒し続けるゲームなら2が主軸
- 自分と相手
- 非同期にすると当たってないのにという状況が起こることがあり、納得できないことがある。その場合は、結果に至る原因がわかるデータだけは送る必要がある 346
- 結果の整合性を維持する代表的手法は、発生させた側の結果を使うか、受けた側の結果を使うかのどちらか 348
- 原則：損をするような結果が損を受ける側の結果を採用、得をするような結果が得を与える側の結果を採用 353
- 自分と環境 354
- 環境の要素は排他制御が必要かどうかで大きく二つ
- 爆弾が一つあって拾えるだと排他制御は必要、減らない水などは排他制御は不要
- アイテムの排他制御のための調停役 362
- 調停役は、いずれかのプレイヤーの端末に肩代わりさせるか、サーバーに実装するかどちらか
- 気づき: 調停役はdynamodbっぽいAPIを持ってる。set、get、setIf、changed（値変更を通知）
- 敵NPCがプレイヤーに自動で近づき攻撃する場合、非同期環境でどう表現するか難しい。NPCが自動で動くと、端末ごとに挙動が変わる。対応の選択肢としては 368
- 1. すべてのNPCについて一つの端末で処理。問題点は他プレイヤーにはラグがある、すべてのNPC行動が通信に乗るので通信量が膨大
- 2. 基本的に並行に処理を続けるが、定期的に全ての座標を送り合い、違いが大きいときは強制的にどちらかの座標を採用する。通信量は1より少ないが、たまに敵が急に移動する現象が起こる
- 3. なんらかの条件でNPCの管理権限を決める。たとえば一番近いプレイヤーに管理させる（これは自分の近くのNPCと行動することが多い場合に有効）。もしくはNPCの行動アルゴリズムの値を使って分ける。例えば、自分をヘイトしている敵は自分の管理権にするなど
- 気づき：影響が強い環境のラグを減らすという方向性
- MMO型は、非常に長期にわたるゲーム進行をとても多いプレイヤーで共有 381
- ゲーム進行の管理や保存はすべてサーバー側で担当し、プレイヤー側の端末にはゲーム進行の結果を送信し続ける
- MMOの場合は、永続性、蓄積性、大規模性があるため、ブラウザ式しか利用できない 385
- 同期式は何百のプレイヤーの同期処理が無理。非同期式はクライアント側でのゲームデータの改ざんが可能だとまずい
- C/S MMOシステムのボトルネック発生ポイント 421
- ゲームサーバーのボトルネック解消 425
- 空間分割法：ゲームの世界を地理的な構造に基づいて、別のサーバープロセスに処理を割り当てる。
- 空間コピーの方法もあり（昔のオンラインゲームのサーバー）。明示的に選択、ランダム選択、空いているところを選択、フレンドに近いところを選択など。ただし過疎感を生み出す可能性に注意
- インスタンス法：ダンジョンなど、特に負荷が高くユーザーが集中する部分だけを取り出し、そこに専用のサーバーを割り当てる。
- データ部分の暗号化は、多くの場合には、RSA 方式や Diffie-Hellman などの鍵交換方式を用いて、秘密鍵を共有し、セッションが生きている間は使い続けるという実装をする
