2008年06月25日
バケット同期(Bucket Synchronization)の日本語訳
翻訳記事もみっつ目になりました。
ずいぶん前のことですが、MiMazeというVRMLの3Dネットワークゲームがリリースされました。他のネットワークゲームと異なっていたのは、それが完全な分散型のアーキテクチャで構成されていたことです。
分散アーキテクチャには中央サーバがありません。そのためスケーラビリティに優れており、単一障害点がないこと、また低遅延であることが利点とされています。
反面、それぞれのクライアントは独自に世界の一貫性を保たなくてはなりません。世界が他のプレイヤーと共有されているにもかかわらずにです。問題は世界が簡単に非同期化されるということです。他のプレイヤーから届くイベントの到着時間や順序は当てになりません。これはネットワークの遅延その他の問題によって引き起こされます。
図A左を見てください。これは遅延がない状況で何が起こるのかを示しています。プレイヤーAとBが同じ距離だけある物体から離れて立っているとしましょ う。時間T1にAが物体を撃ちます。そしてT2にBも同じ物体を撃ちます。どちらの世界でもプレイヤーAは物体を撃ち抜いているでしょう。またAがすでに 物体を壊していますからBはそれを撃ちもらします。
では図A右を見てください。もし「Aが物体を撃った」という事がBに伝わるまでに余計な時間がかかるとしたら、Aが物体を撃つ時間の違いから結果は異なっ て見えます。BがT2のとき物体を撃ったら、Bの世界にはAの発射パケットはまだ届いていませんので命中します。その後Aは撃ちもらすことになります。し かしAの世界ではAが命中させBが撃ちもらしたように見えます。
MiMazeはバケット同期(Bucket Synchronization)と呼ばれる技術を用いて、この問題を避けています。バケット同期はロックステップ(Lockstep)というより単純な ネットワーク技術に由来しています。バケット同期ではイベントをすぐに処理してしまわずに、一定の時間間隔に割り当てられたバケット（キュー）に入れ、ま とめて処理します。
このとき重要なのは追加する先のバケットが遅延同期時間分遅らせたものになることです。ローカルなイベントの場合は、全く人工的にこの時間を加えます。他 のプレイヤーから受け取るイベントの場合は、ネットワークを経由する間にこの時間がいくらか経過しているので、その分を差し引きます。こうすることで全て のクライアントは自分の世界の状態を更新する前に、必要なイベントが揃っていることになります。この遅延同期時間は通常、もっとも遅延の大きなプレイヤー に合わせて、若干のバッファと共に設定されます。例を挙げましょう。
あるゲームで
- 50msのバケット間隔
- 100msの遅延同期
50 100 150 200 250
A-L-B-R-C—-D—-E
75msのときローカルイベントLが発生しました。それは遅延するので d(L) = 作成時間(75ms) + 遅延同期時間(100ms) = 175ms に処理されるべきです。これはCとDの間になります。割り当てるバケットはDです。
また125msのときリモートイベントRが発生しました。これも（主にネットワークを経る間に）遅延するので d(R) = 125ms + 100ms = 225ms に処理されます。割り当てるバケットはEです。
図Bは図A右にバケット同期を適用したものです。灰色の箱がバケットになります。黒い点線はイベントがどのバケットに入るかを、赤い点線は遅延同期時間を表しています。
T2以降を追いかけてみましょう。T2でプレイヤーBはローカルな発射イベントを作ります。それはすぐに処理されずにバケットDに入ります。その後、プレ イヤーBはバケットCへ入るべき、プレイヤーAからのリモートイベントを受け取ります。Cが処理されるとプレイヤーAが物体を撃ったことになります。次に バケットDが処理されますが、Aがすでに物体を撃っていますからBの発射イベントは“はずれ”です。両方のクライアントで一貫した結果が得られています。
複数のイベントをひとつのバケットに登録することもできます。その場合はイベントのタイムスタンプを使って処理順序を決定します。
2,3の疑問が浮かんだかもしれません。「入力がすぐに処理されないなら遅れを感じるのでは？」、「ネットワークの遅延が遅延同期時間よりずっと大きくなったら何が起こるの？」
その通りです。入力の反応を遅らせたら、プレイヤーが遅れを感じるというのは本当です。この技術はハイペースのFPSには適しませんが、よりスローなストラテジや、遅れをちょっとしたアニメーションで誤魔化せるようなターンベースのゲームには適しています。
もしネットワークの遅延が遅延同期時間より大きくなったら、そのイベントは使えないので捨ててください。MiMazeはこれの補償に推測航法を使って、最 新の正しい状態から次の状態を推定していました。もうひとつのやり方は可変バケット同期(Breathing Bucket Synchronization)という、遅延同期時間を受信済みのパケットの遅延時間から動的に計算して解決を試みるものです。
バケット同期は入力のみによって駆動されるネットワークゲームにも役立ちます。Age of Empiresはこれに類似した方法を使用していました。
この概念を示すためにサンプルアプリを作りました。ふたつの世界があります。それぞれの世界にはメインプレイヤー、代理プレイヤー、ゲームオブジェクトが ひとつずつあります。左の世界のメインプレイヤーは赤いプレイヤー、代理プレイヤーは緑のプレイヤーです。右の世界はその逆になります。Fireボタンを 押すと、赤もしくは緑のプレイヤーは白いゲームオブジェクトを撃つためのイベントを作ります。誰が当て誰が外すか見てください。隣には白い点群でバケット が示されています。点ひとつがバケットひとつに相当します。赤いバケットにはローカルイベントが、青いバケットにはリモートイベントが入っています。一番 上のバケットが次に処理されるバケットです。
いつものようにソースコードはここからダウンロードできます。
参考文献
Design and Evaluation of MiMaze, a Multi-player Game on the Internet
Laurent GAUTIER and Christophe DIOT
INRIA Sophia Antipolis (http://www.inria.fr/rodeo/)
On the Design of Multiplayer Online Video Game Systems
Chia-chun Hsu, Jim Ling, Qing Li and C.-C. Jay Kuo
Integrated Media Systems Center and Department of Electrical Engineering
University of Southern California, Los Angeles, CA 90089-2564
1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond
By Paul Bettner and Mark Terrano
Leave a Comment
Trackbacked