近年インタネットの普及に伴ない、ネットワークを利用したオンラインのコンピュータゲームが流行してきた。特にその中でも注目されているのがMMORPG(Massively Multiplayer Online Role-Playing Game)というジャンルである。 これは、コンピュータが提供する環境上で複数のプレイヤーたちがお互いの存在を認めながらロールプレイングゲーム(多くは、イベントへの参加、モンスター退治、宝探しなど)を行うというゲームである。
従来のMMORPGはクライアント/サーバ型と呼ばれるネットワーク形式で作られており、そのためにゲームの規模がサーバの性能に大きく依存していた。 そこで特定のサーバを必要としないネットワーク形式であるPeer to Peer型のネットワークを用いたP2P型MMORPGについて考察する。
この項ではネットワークや、分散システムに関わる知識の説明をする。
MMORPGにおいてはある程度のリアルタイム性が要求される。一方で、通信の正確さもある程度必要となる。ここで、通信の正確さとは次のようなことである。バイナリファイルの通信中に誤りが生じて、500byteのデータが失われた場合、そのデータは無期限で再送を待つ必要がある。つまり、少しでもデータが失われているうちは通信が完了しない。一方、IP電話の音声の通信中に誤りが生じて、0.5秒間の通信が途絶えた場合、その0.5秒に関しては期限無しで待つようなことはない。 この場合は再送を行わず、失われた通信はそのまま失ったままにする。そして、次の音声が来たらそのまま受信して、即座に音声に変換する。これは、リアルタイム性が要求されることと、人間同士の会話という高レイアな利用においては、信頼性の確保は受信者が送信者に音声などで再送を願うなど、上位レイアで処理する前提になっているからである。
MMORPGの特性を考えた場合、上記のファイルと音声の中間に位置する。つまり、アイテムを取得した、使用した、無くしたなど、異世界で保証しなければならない唯一性に関するような情報については、誤りが生じてはならない。一方で、プレイヤの位置情報など、過去のよりも現在の方が優先度が高いような情報もある。位置情報などはある程度欠損していても過去に遡らず、最新の位置情報に基づいて処理を行う。このようにMMORPGは扱うデータには様々な種類があり、リアルタイム性や正確さなどの要求事項が異なる。そのため、基本的にはリアルタイム性を重視したプロトコルを使用し、重要なデータに関しては、そのプロトコル上で正確さを確保するようなプロトコルを使用することで、要求仕様に対応することとする。
インターネットでリアルタイム性を重視するプロトコルとして、UDPがある。これはIPパケットをそのまま送信するようなものであり、通信相手とネゴシエーションを行ったり、複雑な再送処理などを行ったりはしない。ただし、輻輳処理も行わないため、輻輳が生じるようなネットワークの混雑を引き起こすとネットワーク障害を生じされる原因となるので注意が必要である。
クライアント/サーバ型のMMORPGの形態は図の通りである。図においてクライアントの役目は、ユーザ操作のサーバへの送信と、サーバからの受信データによる画面表示である。この点で、WWWのブラウザと基本的には役割は変わらない。ただし、通信がリアルタイムであったり、画面表示が三次元グラフィックであったりする。現行のMMORPGは全てこの形式で運用されている。
サーバの役割は、異世界のシミュレーションの他、ユーザの管理、クライアントとの通信の管理などが挙げられる。クライアントの役割はプレイヤーの操作を送信し、サーバからの返信をグラフィック化することである。 RPGを進行するための複雑な処理は全てサーバ上でおこなわれる。そのためサーバに負荷が集中するのでゲームの規模がサーバの性能に大きく依存し、サーバの処理量を超えるとゲーム空間に接続できなくなるような問題がある。
P2PとはPeer to Peerのことである。このPeerとは、分散協調するサーバとクライアントが一体化したものである。すべての参加端末が同じPeerというプログラムを動作させると、互いに通信を行いながら、Peer同士の接続情報を交換し、相互通信可能な通信チャネルを確立する。このPeer同士の通信チャネルの集まりをヴァーチャルネットワークなどと呼ぶ。Peer同士はヴァーチャルネットワーク上で相互に情報を交換しあうことで、全体で一台のサーバとしての機能を担うことになる。
P2Pにおけるクライアント側のメリットは、Peerには分散協調サーバが含まれているので、サーバ接続はパソコン内で完結することである。そして、クライアントと交換した情報は分散協調サーバ同士の通信により、相互に同期が取られる。さらに、この他のメリットをとして特定の中央サーバを利用しないため、C/S型よりもスケーラビリティで優位になる可能性がある。また、アクセスが集中する情報ほどその情報の伝達が早くなる性質があるため、アクセス集中による遅延を解消できる可能性がある。
このような性質を持つP2P型のネットワークでMMORPGを考える。MMORPGでは異世界のシミュレーション、ユーザ管理、サーバ間の同期などをP2Pで行う必要がある。
本研究で使用した分散システム上で用いられるようなテクニックを説明する。
合意問題とは分散システム上で全てのノードのある変数xをあるひとつの値に統一するという問題である。
図3.合意問題
例えばP2PでのMMORPG上でプレイヤーがアイテムを取得する場合に複数人の候補が上がった場合を考える。P2Pでは各ノードが各々サーバとしての機能を持っているのでそれぞれのノードは独自にその結果を処理してしまうと、アイテムはひとつしか存在していないのに複数人がアイテムを取得することは現実的におかしい。そこで各ノードの意見をひとつに統一する必要が出てくる。
合意問題は各ノード間でメッセージ交換をして意見の統一を目指す。その代表的な解決方法は多数決である。
図4.合意問題でのメッセージ交換
各Peerは多数決用に他のPeerの変数を記録するための変数yを用意しておき、自分の値を代入しておく。そして、各Peerは自分の変数の値を全てのPeerに送信する。
図5.合意問題での多数決
各Peerはそれぞれ他のPeerから受け取った値を変数に代入し、各Peerでそれぞれ多数決をとる。このとき各Peerが正常に動作しているなら別々に集計しても多数決の値は全てのPeerで同一のものとなる。
図6.合意成功
各Peerはそれぞれ多数決で得た値に統一したい変数xを書き換える。これで各Peerのある変数xをひとつの値に統一することができた。
図7.多数決失敗
しかし多数決の結果、ひとつの値に決定できない場合も存在する。
図8.ランダム化アルゴリズム
そこで決定できない場合にはランダム化アルゴリズムを使う。ランダム化アルゴリズムではランダム値を返す関数を利用できる。それを利用すると値を決定できなかった際にランダム値で多数決を取り直すことで有限時間以内に意見を合意できる。また、過半数の意見が分かればよいので合意をするために全員の意見を待つ必要はない。そのためひとつの意見が過半数を取った時点で意見を決定してしまっても良い。 分散システムでの合意問題ではノードの故障がしばしば重大な問題となる。MMORPGではノードは任意のタイミングで切断が可能である。これは分散システムで停止故障が頻繁に起こるシステムと見なすことができる。多数決合意中に停止するノードが発生すると合意できなくなったり、矛盾が現れる問題がある。そのため合意問題中にノード数の変動が発生場合には合意をやり直す必要がある。
大域イベントとはゲーム全体に影響を与えるようなイベントである。MMORPGでの例を挙げるとアイテムが出現するイベントである。プレイヤーの移動等は各Peer別々に処理しても問題はない。しかし、アイテム出現等の全プレイヤーに平等におこなわなければならないイベントもある。例えばあるPeerでだけアイテムが出現しているという状態は明らかにMMORPGとして破綻している。
図9.大域イベント
図はそれぞれのネットワーク形式でのイベントの発生のメッセージの流れである。C/S型では大域イベントはサーバが発生させ、それぞれのクライアントにメッセージを送る。その役目をP2P型ではノードのどれかひとつがそれを担わなければならない。しかし、イベントを発生させるリーダーのようなノードを決定するとそのノードが切断した場合にリーダー選挙問題が必要になり、一時的にイベントが起こせなくなってしまう。よって全てのノードが均一の確率でイベントを発生させることとする。そうすることでノードの切断、接続に関係なくイベントを発生させることができる。しかし複数ノードが同時にイベントを発生させようとした場合は2.4.1の合意問題として解決する必要がある。
またイベントの発生のタイミングはゲームという性質上不公平が起きてはならない。具体的にはイベントを起こすノードがイベントを発生させてから他のノードにもメッセージを送信するなどということは不公平な大域イベントを生み出す。しかしイベントを発生させるノードがメッセージ送信時間を調整し、他のPeerがメッセージ受信タイミングでイベントを起動させるようなアルゴリズムでは発生ノードに負荷が集中する。そこで各ノードが自らそのタイミングを調整できるようなアルゴリズムが好ましい。そこで各ノードにタイマーを保持させそれを同期させることによってイベントの発生タイミングを同期する。
タイマー同期の仕様を次のようにする。
上記のように設定すると各Peer間でタイマーの同期が取れれば同時刻にイベントが発生できる。
図10.タイマー
以下よりタイマー同期の具体的な方法を説明する。なお、Peer間の通信遅延は一定と仮定して考える。
タイマーの値を同期させるにはお互いが相手のPeerのタイマーの時刻を知る必要がある。まずは、PeerAがPeerBのタイマーの時刻を知る方法を説明する。
PeerAはタイマーを始動させ、PeerBにタイマーの値を要請するメッセージを送る。このときPeerBはタイマーを開始していなくてもよいが、PeerAからのメッセージが届いたならばタイマーを開始する必要がある。
図11.タイマー要請
通信遅延を3[s]とすると3[s]後にPeerBにメッセージが到着する。
図12.メッセージ到着
PeerBはメッセージが到着するとPeerAに対して自分のタイマーの値を返信する。
図13.タイマー返信
通信遅延3[s]後PeerAはPeerBからの5[s]というメッセージを受け取る。
図14.タイマー受信
しかしここで本当に知りたい値はPeerBの現在のタイマーの時刻8[s]である。そこでPeerBがメッセージを送信したあとに到着までにかかった時間を求める必要がある。ここでPeerAのタイマーはこのやりとりでのメッセージの往復にかかった時間になっているのでその半分は片道にかかった時間である。よって
返信された時刻5[s]+片道分の通信遅延6/2[s]=PeerBの現在のタイマー8[s]
と計算できる。
PeerBも同じ方法を使えばPeerAの値を知ることができる。そのため早い方の時間に合わせる、平均をとるなどの方法でタイマーの値をあわせることができる。
しかし、実際は往復での行きと帰りの遅延時間はまったく同じではないし、通信遅延以外の遅延も存在するはずなので完全な1[ms]も誤差のないような同期を生み出せるわけではない。
本研究では実際に単純化したP2P型MMORPGを作成し、次章で述べる検討項目の解決策が実際に動作可能であることも実証する。
PeerとしてJavaで作成したプログラムを考える。ユーザーインターフェースはグラフィック画面とキー入力で行う、またネットワークインターフェースを持ち、UDPの指定したポートを使用して通信を行う。
基本ルールは宝探しである。ゲーム空間にランダムに現れるアイテムをプレイヤーたちは自由に動き回り取得する。
実際の流れは、まずプレイヤーはPeerを起動し他のPeerを起動しているプレイヤーと接続する。接続している全Peerはひとつの共通のゲーム空間を作る。プレイヤーは自分の操作できるキャラクターを矢印キーで操作する。アイテムはランダムに出現しプレイヤーはそれに自分のキャラクターを重ねることで取得することができる。自分の取得したアイテムは画面右に表示され、再接続しても情報は失われない。
また、ゲーム中の予期せぬ切断にもゲーム全体が停止しないことを確認するためにプレイヤーの切断はタイムアウトのみで判定する。
ゲームの起動にはconfig.txtとlist.txtという２つの設定ファイルを用意する必要がある。config.txtには自分の使用する受信用ポートと自分プレイヤーIDを記す。list.txtにはゲーム起動時の接続先のIPとポート番号を記す。具体例は付録に付ける。
図15.作成したゲームのスクリーンショット
本研究でのプログラムの作成にあたり以下の問題点を解決した。
図16.アイテム保持情報
図はC/S型とP2P型のアイテム所持情報の例である。
C/S型は全ての情報をサーバが保持してゲーム空間を作っている。クライアントはそこにアクセスし、サーバ上で他のクライアントとゲーム情報を共有する。
P2P型ではゲーム上の情報管理を複数（あるいは全て）のPeerがおこなう。その結果ゲーム空間は同期をとてはいるが実質Peerの数だけ存在しているようにもみなすことができる。そしてメッセージ到着順や過去の取得情報の消失などによってアイテムの増殖や複数人取得が起きる可能性がある。
特にゲーム上に固定数しか存在しないアイテムを実装する場合にゲーム上にそのアイテムが何個存在しているかを一律管理するサーバがないためアイテムの全体数を制御することが困難である。そのためアイテム数を安全に管理できるようなシステムが必要になる。
そこで一般的にはプレイヤーがアイテムを所持しているという考えを使うが、本研究ではアイテムが自分を所持しているプレイヤーの情報をもっているという考え方にした。感覚的にはアイテムに名札をつけて管理するという考え方である。
図17.名札付け
その結果アイテム所持情報は図のようになる。
図18.アイテム管理情報
このようにするとアイテムは所持者をひとりしか決めれないためアイテムが増殖する可能性をなくし、唯一性を保つことができる。
MMORPGでは複数人が同時にイベントを起こす場合が存在する。例えばアイテムを取得する場合である。MMORPGでのアイテムの取得は一般的に早いもの勝ちのルールで行われるため、アイテムの場所に複数人が押しかけて一斉に取得イベントを起こすことがよく見られる。
図19.イベント発生の流れ
図はアイテム取得のメッセージの流れである。
C/S型ではイベントはサーバが全て管理しているため、メッセージ到着順などで処理が可能である。
P2P型では各Peerが持っているゲーム空間を同期するためにアイテムを取得したPeerは他のPeerにアイテム取得メッセージを送信する必要がある。このとき各Peer間には通信遅延が存在するためPeerAでは他のPeerBとPeerCのプレイヤーの動きは遅延して見える。そのためPeerCがアイテムを取ったという行為がPeerAでは遅延していて、自分の方が先にアイテムを取ったように見えることがある。そのため図のようにPeerAとPeerCでゲーム空間の情報が異なってしまう問題が発生する。
図20.複数人が同時にイベントを起こした場合
そのような問題を解決するためには各Peerのアイテム取得状況を統一する必要がある。しかし現実的に通信遅延を0にすることはできないので二つのPeerが別々の主張をすることをなくすのは難しい。そこで別々の主張をひとつの意見に統一するための合意問題を解き、この問題を解決する。
基本的には2.4.1で説明した多数決による合意を行う。その際一番初めの意見としてアイテム取得を主張しているPeer以外のPeerはアイテム取得を主張しているPeerからのメッセージの内、最も早く届いたメッセージのPeerを自分の主張とする。そして各Peerで主張を交換しあい合意問題を解く。合意問題が正しく解ければアイテムを取得できるPeerはただひとつなり、Peer間でゲーム状況の矛盾は発生しない。
図21.合意問題
ただし、ここで合意問題で矛盾が発生する可能性がひとつある。それは切断、接続によるPeer数が変動があった場合である。このとき、メッセージの遅延等により多数決をとる際の総人数がPeerによって違ってくると、合意にPeerによって違いが出てくる可能性がある。合意問題中にPeer数の増減が起きたならば大抵の場合やり直したほうが確実である。
MMORPGでは複数のプレイヤーに対して同時に起きるようなイベントが存在する。たとえばアイテム出現などで全てのプレイヤーに対して平等に起きる必要がある。
図22.イベントのメッセージの流れ
図はアイテム出現イベントの際のメッセージの流れである。
C/S型ではサーバがゲーム進行を管理しているのでサーバがアイテムを出現させる。
P2P型ではサーバのようなゲームをまとめて管理しているサーバが存在しないのでゲームに参加中のPeerの内、どれかがイベントを開始させる必要がある。このときイベントを起こす権利を持った代表となるようなPeerが一時的に必要になる。このような時、通常の分散システムではリーダー選挙問題と呼ばれるような代表を決めるアルゴリズムをおこなう場合がある。しかしMMORPGでは切断接続という概念があるため、代表となったPeerが切断してしまう可能性がある。なので本研究では全てのPeerがイベントを起こす権利を持ち、それぞれがランダムのタイミングでイベントを発生させることとした。しかしその結果複数のPeerが同時にアイテムを出現させようとする場合がある。
図23.イベントの発生
その場合は4.2の時と同様に同時に起きたイベントととして合意問題解き、イベントをひとつに決定することができる。
起きるイベントがひとつに決定できたのなら次はタイミングをあわせる必要がある。
図24.アイテム出現
例えば図のようにイベントを発生させたPeerがまっさきにアイテムを出現させ、その後他のPeerにメッセージを送信するといった方法はゲーム上に不公平な状態を引き起こす。そこで少なくともアイテム出現時刻を同期させるようなシステムが必要になる。そこで本研究では2.4.2で説明したようなタイマーによる同期を使用した。
その理由は、まず各Peerがそれぞれで出現時刻を調整するのでPeerの切断、接続によってアルゴリズムが止まってしまうことがない。例えばひとつのPeerが全てのPeerの通信遅延などを調べて出現時刻を調整させようとするとそのPeerに負荷がかかるうえ、そのPeerの切断によってイベントが失敗する可能性がある。
次にこのアルゴリズムではタイマーの進む間隔が同一であればどのPeerがいつ同期しようとしても同期させることができる。同時というものを作り出そうとしているアルゴリズム自体を、当然同時に実行させることはできない。なので、どのPeerがどのタイミングで実行しても同期できなければならない。このアルゴリズムではPeerがいつタイマー同期を動作させても同期させることができる。
RPGというジャンルではゲームデータの保存が必要である。特にMMORPGは長期にわたってプレイすることが多く、プレイ時間が直にそのプレイヤーのステータスに結びつくため簡単にデータが消えるようでは話にならない。
図25.進行状況の保存
図はC/S型とP2P型でのゲームデータの保存にあたるノードの時間的推移である。太い線で囲まれたノードが保存を担当し、破線のノードはゲームの一部のデータを持ち、必要に応じて保存を担当しているノードにデータを要求してプレイする。 C/S型ではゲームがプレイできる時は全てサーバが動作している時である。そのためサーバはゲーム上全てのデータを把握することができて矛盾なく保存が可能である。
しかしP2P型では常に動作しているようなPeerは存在しない。どのPeerも等しく切断する可能性があるためデータを保持しているPeerは次々に新しいPeerにデータをコピーしていかなければならない。
図26.データの消失
今回はその可能性をなくすために全てのPeerが等しく全てのデータを保存することにした。
図27.データの保存
全Peerが最新データを持っていれば少なくともひとつのPeerが存在する限り上記のような問題は発生しない。しかし、全Peerが切断した場合は対応できていない。
P2P化するにあたって作成したプロトコルの説明をする。
まず、Peer同士が行う通信のルールについて説明する。
通信は全てUDPで行われる。この理由はTCPと比べて正確性には劣るが通信が早いとされており既存のネットワークゲームではよく使われているプロトコルだからである。特にキャラクターの移動などのリアルタイム性が問われ、過去のデータの重要性が低いものはUDPで通信することが望ましい。
各Peerは以下のときに通信をおこなう。
メッセージは以下のルールによって構成される。
| B | コマンド | ボディ長 | ボティ | E |
|---|
メッセージはひとつのパケット内に複数のコマンドを含めることができる。 具体的なコマントは以下の通りである。
| 番号 | コマンド | ボティ |
|---|---|---|
| 01 | ログイン | ポート番号,自分のID |
| 02 | プレイヤー位置 | 自分のID,X座標,Y座標,ポート番号 |
| 03 | アイテム位置 | アイテム番号,X座標,Y座標,持ち主 |
| 05 | 新参加者出現 | 新参加者のID,ポート番号,IP |
| 10 | アイテム出現 | 自分のID,アイテム番号,X座標,Y座標,人数 |
| 11 | アイテム出現(合意) | 合意投票するプレイヤーID |
| 12 | アイテム出現(失敗) | |
| 13 | アイテム出現(再送) | 合意投票するプレイヤーID,ラウンド |
| 14 | アイテム出現タイマー | 自分のID,アイテム番号,X座標,Y座標 |
| 15 | アイテム出現タイマー返信 | タイマー時間 |
| 17 | 投票失敗 | |
| 18 | アイテム強制出現 | アイテム番号,X座標,Y座標 |
| 20 | アイテム取得 | 自分のID,アイテム番号 |
| 21 | アイテム取得(合意) | 合意投票するプレイヤーID,アイテム番号 |
| 22 | アイテム取得(失敗) | 拒否投票するID,アイテム番号 |
| 23 | アイテム取得(再送) | 合意投票するプレイヤーID,アイテム番号,ラウンド |
| 24 | アイテム強制取得 | アイテムを取得するプレイヤーID,アイテム番号 |
| 30 | タイムアウト | タイムアウトの可能性のあるプレイヤーID |
| 31 | タイムアウト(復帰) | タイムアウトの可能性のあるプレイヤーID |
メッセージ例：
4.2の同時に起こしたイベントの例として実際に作成したプログラムで実装したアイテム取得の際におこなわれる通信に使用されているプロトコルについて説明する。
大まかな流れは以下のとおりである。
以下より実際に使うメッセージを含めた説明をする。
アイテム取得イベントはプレイヤーが移動してアイテムに重なることで発生する。アイテムに重なることでアイテム取得イベントを発生させたPeerは他のPeerにメッセージ20のアイテム取得のメッセージを送信する。図はPeerAがアイテムを取得した例である。四角の中は多数決を取るための各Peerの意見を表してる。
図29.アイテム取得イベント開始
受信したPeerは先着順で自分の意見を決める。
図30.意見の決定
意見を決めたPeerは合意なら合意メッセージ21,既に別のPeerに合意メッセージを送っているなら別のPeerに合意している旨のメッセージ22を全てのPeerに送信する。
図31.意見の交換
受信したメッセージを集計して多数決を取り、意見を決定する。
図32.多数決
合意したならば各Peerでアイテムの所持者情報を書き換えてアイテム取得イベントを終了させる。なお、合意が決定したPeerは他の全てのPeerにむけてメッセージ24のアイテムの取得者を強制的に決定するメッセージを送る。このメッセージは合意で決定した取得者のIDが含まれており、このメッセージを受信したPeerはもしも合意問題が解けていなかったとしても取得者を決定する。
また以下のような合意に失敗した場合を説明する。
図33.合意失敗
この場合まず自分の意見をアイテムの取得候補に挙がっているPeerの内いずれかにランダムで決定する。 そしてその値を他のPeerにメッセージ23を使用して送信する。メッセージ23は自分の意見の他にラウンド数の情報が含まれている。ラウンド数とはその合意が何回やり直したかの回数である。この情報がないと全てのPeerが同期して動いているわけではないため古い合意問題中にランダムでやり直したメッセージが届いても古い合意問題で帰ってきたメッセージだと判断してしまうからである。そのためやり直した回数が増えるほどラウンド数も増やして送られる。
図34.合意のやりなおし
4.2の同時に起きるイベントの例として実際に作成したプログラムで実装したアイテム出現の際におこなわれる通信に使用されているプロトコルについて説明する。
大まかな流れは以下のとおりである。
以下より実際に使うメッセージを含めた説明をする。
アイテム出現イベントは各Peerがランダムな確率で発生させる。その際アイテムの出現位置もそのPeerがランダムで決定する。出現させることになったPeerは他のPeerに対してメッセージ10を送信する。
図35.アイテム出現イベント
受信したPeerはアイテム取得イベントと同様に先着順で意見をきめて、送られてきた値に合意するならばメッセージ11,合意しないならばメッセージ12を送信する。
図36.意見送信
受信したメッセージを集計し合意する値を各Peerごとに多数決で決定して、アイテム出現のタイマーをスタートさせる。なお、多数決が決定できなかった場合にはアイテム取得イベントのときと同様に意見をランダムで決定しなおしてメッセージ13で他のPeerに送信する。
タイマー同期はPeerがタイマーを開始させた時点でタイマーの時刻を要請する旨のメッセージ14を全てのPeerに送信する。
図37.タイマー要請
メッセージ14を受信したPeerは送ってきたPeerに対して自分のタイマーの値をメッセージ15を使って返信する。このとき受信側でタイマーがスタートしてなければスタートし同様にメッセージ14を他のPeerに送信する。
図38.タイマー返信
返信された値を用いて2.4.2で説明したタイマー同期を行なう。ただし、このとき他のPeerとの調整用のものとアイテム出現に実際に使うタイマーを分けておかなければメッセージの順番によって同期が取れなくなることがある。例えば2つの値の平均値で同期を取りたいのに片方だけ先に修正するとあとから実行したほうの平均値が変わってしまう。以上の動作が終了したらタイマーによってアイテムが出現する。また、出現後メッセージ18を送信し、もし出現していないPeerがいれば出現させる。
上記以外の通常の基本的な通信メッセージについて説明する。
本研究で実際にP2P型のMMORPGを作成したところ、サーバなしでゲームをおこなうことができるものになったが実際に運用していくためには解決しなければならない問題が存在した。
合意問題ではPeer数が増加するにあたり、合意問題中に切断するPeerの数も増加する。合意問題中に切断が発生すると合意に矛盾が発生する可能性があるため合意問題を最初からやり直しているので、合意までの時間が長くなってしまう可能性がある。これは切断に対する対策を考えるか、より良い合意問題を解くアルゴリズムで解決することできる可能性がある。本研究でとった対策は切断の判定を全てのPeerの一致が必要として、全てのPeerで総接続Peer数の差を極力なくした。また、本研究では切断を宣言するという動作をPeerに実装させなかった。そのためPeerの切断はタイムアウトのみで扱われる。これは、切断を宣言する動作を実装してもそれをおこなわずに切断してしまうPeerが必ず現れることと、それを利用した不正行為が行われる可能性があるためである。タイムアウトしたかどうかの判定はすべてのPeerの合意が必要なことして、各Peer間に総接続Peer数を同期させた。だが、通信遅延によりわずかながらPeer数の違いのあるタイミングがあるので合意問題での矛盾が起きる可能性を否定できない。また新しいPeerの接続でも同様の問題が起きる可能性がある。
解決策としては合意にかかわるPeer数を少なくすることがあげられる。その方法の一例として分散システムの相互排除問題のアルゴリズムで使われることがあるコータリーというものを提案する。
図39.相互排除問題
相互排除問題とは分散システム上で、あるノードがある変数Xを書き込み、読み込みする際に他のノードに変数Xを書き換えられないようにそのノードに書き込み、読み込みの権限を限定するという問題で権限を限定することを変数をロックするという。ノードはロックしたい変数があるとき他のノードに許可をとるがここで全てのノードに許可をとらなくていい方法としてコータリーを使った相互排除問題が提案されている。ここの許可を取るという行為を合意問題として当てはめると今回のシステムに利用できる。
Uをプレイヤーの集合とするとコータリーとは以下の2条件を満たす空でないUの部分集合(コーラム)Qiの集合である。
以下にコータリーの構成の例をあげる。
ここでは有限射影平面をコータリーの一例として扱う。
図40.有限射影平面
有限射影平面とは以下の3つの条件を満たす直線の集合である。
ある集合UがU=k^2-k+1かつk-1が素数の冪で表される場合には有限射影平面を構成する一般的な手続きが知られている。この方法ではUがによっては条件を満足できないが、条件を満足するUより大きな最小の値によってコータリーを決定し、そのコータリーのUに属さない要素をUに属す要素に置き換えて、置き換えたことによってUに存在する集合のうちの他の集合を含むものを除去することで任意のUに対してコータリーを構成できる。
以下ではこの方法の最小k-1=2であるU=7の有限射影平面を用いてコータリーを構成する。
まずの位数(k-1)^2のアフィン平面を構成する。
アフィン平面とは以下の3つの条件を満たす直線の集合である
図41.アフィン平面
ここで上記の集合に対して同じ傾きの平行な直線の集合にひとつ共通の頂点を与えてやる。
さらにここで追加した頂点をひとつの集合として{E,F,G}を作る。
これにより有限射影平面によるコータリーが作成できた。
コータリーが形成できるとそのグループ内での投票で合意を達成できる。それはグループ内の誰かは他のグループにも属しているので他のグループではその人の合意を得られないからである。グループ内で投票が起きた場合他のグループでおきた投票に対して確実に失敗させるメッセージに送ることでひとつのグループ内で合意を決定できる。
しかしこの方法は同グループ内での通信遅延によっては以下のようなデットロックを起こす可能性がある。
図42.デットロック
この状態では全てのコーラムで、ある一人が別のコーラムで合意してしまっているため、どのコーラムも合意することができない。そこで各コータリーはロックの情報を交換しあいデットロックを検知する必要がある。コータリーは合意時間を早くしてくれるが人数の変動でコータリーが壊れると合意できないという欠点が存在し、再構築には時間が掛かる可能性がある。
コータリーは合意にかかわる人数を同一コーラム内のノードのみに絞れるため、人数変動の影響を最小限にできる可能性がある。
また他の問題として今回使った合意問題での先着順がある。C/S型では中央サーバとの通信遅延を把握すれば先着順に通信遅延を考慮すると”クライアントがメッセージ送信した早さ”での早いもの順で見ることが可能である。しかしP2P型では過半数以上に早く届いたプレイヤーとして動作させると他のPeerとの通信遅延が少ないPeerが有利になってしまう。そのため例えば日本で運用していると通信遅延が大きくなるであろう海外の人は不利な状況になってしまう。ここでは大域時計のようなシステムを作ることで解決できる可能性がある。
そして進行状況の保存では全てのプレイヤーが全てのデータを持つとなるとプレイヤーが増えるにあたって通信量が増加するし、ゲームが続くにつれて通信しなければならない情報も増加する。この点はスケラービリティに悪い影響を与える可能性がある。また、全てのPeerの切断に対してはローカルにデータを保存することである程度の復旧は可能で少なくとも自分の進度のデータは守られるがゲーム全体の進行状況の矛盾が発生する可能性もあり、サーバなしで完全に復帰できるようなシステムを作ることは困難に思える。
しかし現状運用されていてそれなりの人気があるものならばプレイヤー数が０になることはまずないし、０人になるようなゲームはMMORPGとして成り立っていないので問題にならない可能性もある。
本研究ではP2P型のMMORPGについて実際に設計、作成をおこなった。P2P化にあたり、サーバ/クライアント方式でサーバが担っている役目をP2Pで実現するための問題点を解決した。
P2P型では、C/S型でサーバがまとめて管理しているようなゲーム情報が複数のPeerに分散される。そのためアイテムの不正コピーなどが発生する恐れがあったが全Peerのアイテム数を管理し、不正コピーを防止できるように改良することができた。 同時に起きたイベントを処理する問題ではC/S型ではサーバが判断していたイベントの発生順を合意問題という分散システムの従来の方法で解決できた。ここでは特にPeerによってイベント発生のメッセージが到着する順番が違うことが問題になった。なぜなら先着順で単純に処理するとPeerによって意見が分かれてしまうからである。そのため、合意問題という分散システムの各ノードの意見を統一するという問題のアルゴリズムを使用した。
各peerで同時に起きるようなゲーム側が主導になって発生させるようなイベントの問題では、C/S型ではサーバがゲーム空間を管理しているのでサーバがイベントの発生源になればよいがP2Pではその役目を決定することが困難であった。分散システムでいうリーダー選挙問題で扱われるようなアルゴリズムをつかってリーダーとなるPeerを決定してもそのPeerの切断の発生や、負荷の集中する可能性があった。そのため各Peerが平等にイベントを発生できるようなシステムにしてイベントが重複してしまったときは合意問題を解きイベントをひとつに決定することでゲーム側主導にイベントを発生できた。また、その発生タイミングは合意問題を解き終わったPeerから発生するのでは通信遅延の長いPeerが不利になるのでタイマーを使い同期させることにした。 ゲームの進行状況を保存するという問題では、C/S型では常にサーバが起動し、サーバ上でゲームがおこなわれているのでサーバが進行状況を全てを把握し、保存することができる。しかし、P2P型では常に存在しているようなノードがいないことが問題であった。しかし全てのデータを新しく接続してきたPeerに送信し、全てのPeerが常に最新データを持つようなシステムにしたことで再接続の際に進行データが失われないようにすることができた。
以上のようにMMORPGのP2P化での問題を分散システムの既存の手法などを用いて解決することができた。しかし実際に大規模化して運営していく上ではまだ改良の余地があり、今後の研究が求められる。
本実験で作成してプログラムのソースを付録としてつける。クラスごとに簡単に説明する。それぞれのファイル名はクラス名と対応している。また初期接続先リストであるlist.txtと設定ファイルであるconfig.txtの設定例も付ける。
全体の流れはゲームを起動するとGame02クラスのメイン文でConstantクラスがファイルから情報を取得する。その後インスタンス生成やパネルを生成して受信用スレッドと送信用スレッドとアイテム出現用スレッドを開始させる。メッセージを受信できる準備が整ったらコネクトメッセージを送信してゲームが開始される。
以後は受信用スレッドが送られてきたメッセージを他のクラスの関数に送り処理していく。
ソースは以下からダウロードしてください。