2008年02月21日
推測航法(Dead Reckoning)
こんにちは。
今回はネットワークゲームで帯域消費を減らす定番のアルゴリズムのひとつ、推測航法(Dead Reckoning)の話です。
定番といってもネットワークゲームのために考えられたわけではなく、大航海時代から使われてきた航法の応用になります。
具体的には船の元の位置が分かっているときに、時間と船速、進行方向から現在の位置を推定し、目的地を目指す航法です。天測と推測航法についてはこの記事なんか面白いですね。
今は地球上であればGPSを使って簡単に絶対位置を知ることができるようになりましたが、こうした技術こそ航海の全てだった時代もあったわけです。もちろん、廃れてしまったわけではなく自律走行するロボットの制御などでは盛んに使われているようです。他にもヘルメットに取り付けたモーションセンサー（推測航法用）とGPSを組み合わせて屋内・屋外問わず高精度で、人（たぶん軍・警察・消防関係）を追跡しようと試みている研究もあったり……
ネットワークゲームに話を戻すと、キャラクタが移動したときにはその位置は全プレイヤーに伝えられなければなりませんが（そうでないとキャラクタは動きません！）、できるだけ回数を減らしたい。そこで位置を推定してしまえということになります。
で、シミュレータを作ってみました。Jouni/Harri(2007)に書かれていることをそのまま実装…したつもりです。
(左 収束なし, 右 線形補間による収束)
カーソルキーで送信者（緑） を操作できます。受信者は赤で表されています。推定している方が赤ですよ。
送信者と受信者のやり取りはこのように行われています。
送信者側
- 状態（位置と速度と時刻）を受信者に送る。
- 好きに移動する。
- 定期的に今いる位置と、前回送信した状態から推定した今いるはずの位置を比べる。ずれが大きくなっているようであれば再び状態を受信者に送る。
受信側
- 送信者から送られた状態を元に現在位置を推定し表示する。
- 送信者から新しい状態が送られてきてもすぐには表示に反映しない。ほぼ間違いなく表示位置と異なっているはずなので、徐々に新しい状態に基づいた推定位置に移動させる。
これで送信頻度はおよそ秒間１回になっています。ただ人物のように割合ランダムに動くキャラクターに適用するには改良が必要です。収束もスプライン曲線のほうが…ま、こんなこと言わなくてもみんなそのまま実用には使わないから大丈夫だよね。それではまた次回。
参考文献
- Jouni Smed / Harri Hakonen, 2007, コンピュータゲームのアルゴリズム＆ネットワーキング, ボーンデジタル
- Jouni Smed / Harri Hakonen, 2006, Algorithms and Networking for Computer Games Additional material
- Singhal 1996, Effective remote modeling in large scale distributed
- Jesse Aronson, Dead Reckoning: Latency Hiding for Networked Games, Gamasutra
- hplus0603, Entity Position Interpolation Code
Leave a Comment
Trackbacked