2008年03月11日

takushimaClient Side Prediction (Rewind and Replay)

こんにちは。

今回はFPSで主流の(主流だった?)ネットコード(client side predictionとrewind and replay)を実装してみました。Processingシリーズ第2弾です。

本題の前に応答性と一貫性に言及しておきたいと思います。ふつうネットワークアプリケーションは遅延があることで、先のふたつのバランスをとるという問題に直面します。

AさんとBさんが遅延のあるネットワークを介して撃ち合うFPSを例にとります。

応答性は、キーを押せばキャラクターがすぐに移動を始めるとか、トリガーを引くと弾が発射され命中したかすぐに判明するとか、そうしたキー入力から画面表示までの経過時間と考えてください。

一貫性とはAさんとBさんが常に同じ状態を見ているということです。遅延がとても小さければ、これは簡単に実現できます。では遅延が大きい環境で、Aさん がBさんを撃ち、Bさんはそれを避けようとしている状況を考えてみてください。Aさん側から見るとBさんには弾が命中したはずなのに、Bさん側から見ると Bさんは弾を避けていた、なんてことが起きそうです。これを簡単に防ぐには、AさんもBさんもある時刻における行動をお互いに知った上で、シミュレーショ ンを先に進めればよいのですが、そうすると応答性が極端に低下するというお決まりの結論に至ります。

これから紹介するのはそのバランスをとるためのテクニックということです。

このテクニックはQuakeから発展したQuakeWorldのネットワーク部分で初めて使われました。Tim(1999)ではただclient side predictionと呼んでいますが、2008年のGDC講演者Glenn Fiedlerさんが手法の一部をrewind and replay（巻き戻してやり直し）と呼ばれていたのでこれに習うことにします。Glennさんはclient side predictionについての良質な記事を2004年に書かれています。そう、ちっとも最新の話題ではないのです =)

このテクニックを使うにあたっていくつか前提があります。それは…

  • キャラクターの物理的な状態は、そのキャラクターを操作しているプレイヤーのキー入力によってのみ変更できる
  • 物理シミュレーションは同じ入力を与えれば必ず同じ結果になる (決定的な物理が必要)
  • 完全なクライアント／サーバ型で、サーバがすべての決定権を持ち、クライアントは常にサーバの近似となる (クライアントはサーバにキー入力を送り、サーバは更新された状態をクライアントに送る)
  • UDPのように信頼できなくてもよいが、即時性のあるプロトコルを使っている (必須ではない)

昔のFPSを思い浮かべながら以降、読み進めてください。

client side prediction (クライアント側予測)

さて、サーバがすべての状態を更新するとして、あるプレイヤーが前進キーを押したとします。サーバからの結果を待っていると先の応答性が低下してしまいま す。そこで自分のキャラクターについてはサーバと同じ計算を行いクライアント側で勝手に状態を進めることにしました。これがclient side predictionです。前回の推測航法と予測するという点では同じですが、こちらの予測はより正確な予測になります。なんといってもどんなキーを入力 したかが分かっていますから。

もしプレイヤーが自分だけで、パケットが失われることがなければこの予測結果は、完璧にサーバ側の計算結果と常に一致するはずです。

rewind and replay (巻き戻してやり直し)

プレイヤーが自分だけ、なんてことはあるはずもなく、パケットも当たり前のようにインターネットでは失われます。さて、こうなってくるとサーバの結 果とクライアントの予測結果は一致しなくなります。予測が外れたわけですから、クライアントは何とかして帳尻を合わせなくてはなりません(サーバは常に正しいのです)。ま、何も考えずスナップするなり補間することはできます。

しかしサーバから届いた結果はクライアントでは常に過去の出来事です。クライアント側はすでにそこから数十ミリ秒経過した後かもしれません(クライアント 側予測を使っているので、クライアントはサーバを待っていないことに注意してください)。この数十ミリの間にキー入力もたくさん行われたことでしょう。 きっと。

そこであらかじめ入力履歴をとっておき、サーバの結果が指す時刻から現在時刻まで、クライアント側予測をもう一度やり直すことにします。これがrewind and replayです。

えー…時間軸がふたつあるので混乱しますよね。最初、僕もどの時間を考えているのか、分からなくなっていました。紙に書くなりして、じっくり考えてみてください。

注意して欲しいのはこのどちらのアルゴリズムも、自分が操作するキャラクターに対してのみ適用するということです。他のプレイヤーが操作するキャラクターは、ただサーバの結果に従い表示するほかありません。

サンプル

ざっと説明することができたので、ようやくサンプルを出せます。といってもオリジナルではなくGlennさんのNetworked Physicsを写経:-)したものです。Processingで再実装する際に、今回のテクニックに関係のない部分はバッサリ省略させていただきまし た。もともとは3Dだったのに1Dになっていたり、補間した方がかっこいいところをスナップしていたり……

diag.png

(1) : クライアント側のキャラクターの状態 (あなた)
(2) : キャラクターの過去のキー入力・状態履歴
(3) : サーバ側のキャラクターの状態
(4) : 他のクライアントから見たキャラクターの状態

Processingのアプレット

netphysics-080311a.zip

左右キーで左右に移動できます。Lで遅延時間をPでパケット損失率を変更できます。

プレイヤーが自分だけなのでパケット損失(それもキー送信に関するもの)がなければ、rewind and replayは起こりません。遅延時間と損失率を上げてキーを左右に小刻みに入れれば、その様子が観察できると思います。

このテクニックを使っていて複数キャラクターがいる場合でも、サーバはすべてのクライアントのキー入力を待って状態を進める必要はありません。前提にあるようにキャラクターは互いに影響を及ぼさないので、独立して更新できます。サーバはキャラクターごとに異なる時間軸を扱っていると考えてもよいと思います。

では、また。

参考文献

Leave a Comment

Trackbacked

trackback url for this entry: http://www.pyramid-inc.net/lab/archives/108/trackback