多人数リアルタイム通信ゲームの移動処理について考察する

# はじめに

VRM使ったリアルタイム通信でなんか面白いこと出来ないか考えている[yoship1639](https://twitter.com/yoship1639)です。

リアルタイム通信は以前は低レイヤのAPIを使いやすいように自分でラップしたり、フラグメント化回避のために四苦八苦したり、サーバ～クライアント間の統一したインターフェースをどうやって実装するか悩んだり、シリアライズどうするか絶望したりしていましたが、最近はgRPCがでたり、それを.Netで使いやすいようにラップしたMagicOnionが登場したりで上記の悩みを全部吹き飛ばしてくれる規格やフレームワークが出てきていい時代になったな～と実感しています。

リアルタイム通信は上記の悩みが最初のボトルネックなので、クリアしたら今度はそれを如何に活用できるかが重要になります。例えばチャットアプリは何も考えずにクライアント->サーバ->全クライアントという様にメッセージを流せばいいですが、これが3Dリアルタイム通信ゲームだと話が変わります。

3Dリアルタイム通信ゲームでよくあるのはキャラクタの移動ですが、これをクライアント全てのキャラクタの移動をリアルタイムで同期するにはどうすればいいでしょうか。

今回は、Unityでリアルタイム通信を使った3Dキャラクタの移動処理を実装してみたら意外といい線行ったので、リアルタイム通信特有の問題をどのような考えを元に乗り越え、どの様な実装をしたのかをまとめられればと思います。

# 多人数リアルタイム通信

多人数のリアルタイム通信の移動処理は簡単にまとめると以下の形が基本形となります

【クライアント】

* 自キャラ（自クライアントのキャラクタ）を移動させる
* 一定間隔で自キャラの位置、回転をサーバに送信する
* 他キャラ（他クライアントのキャラクタ）の位置、回転情報をサーバから受け取り、他キャラのモデルに適用させる

【サーバ】

* クライアントからキャラクタの位置、回転を受け取る
* 一定間隔でクライアントに全キャラクタの位置、回転をブロードキャストする

通信処理を記述するなら当たり前のことを綴っているだけですが、実は上記の説明ではリアルタイム通信が抱える問題を密かに解決しています。それは扇問題（正確な名称かは不明）です。扇問題は本記事とは直接的には関係ないので、記事の最後に記載するので解決の詳細を知りたい方は[番外編：扇問題の解決](#番外編扇問題の解決)を見てください。

さて、他キャラをリアルタイムに同期するときに起こる問題はどの様なことでしょうか。

## 特有の問題

### キャラクタがワープしながら移動する

何も考えずにサーバから受け取った位置、回転の情報を他キャラに反映させると、他キャラはワープしながら移動します。これはサーバから受け取る他キャラ情報がPCのリフレッシュレートよりも遅い時、または一定間隔で受け取れない時に発生します。これは安直にコーディングしたら起こる至極当然の現象なので理解できるかと思います。

分かりやすく仮にコーディングすると以下のようになります。

```csharp
class CharacterInfo
{
    public Vector3 pos; // キャラクタの位置
    public Quaternion rot; // キャラクタの回転
}

// サーバからキャラクタ情報を受け取る度に呼ばれる
public void OnReceive(CharacterInfo info)
{
    transform.position = info.pos;
    transform.rotation = info.rot;
}

void FixedUpdate()
{
    // 特に何もしない
}
```

### キャラクタが一定のスピードで移動しない①

次に、キャラクタの移動に補間処理を付け加えてみます。他キャラがワープするのを避けたい場合、前回受け取った他キャラ情報からキャラクタの位置、回転を予測しその位置に他キャラを配置する処理を施します。

```csharp
class CharacterInfo
{
    public Vector3 pos;
    public Quaternion rot;
}

private CharacterInfo prevInfo; // 前回の位置情報
private CharacterInfo nowInfo; // 位置情報
private float time; // 受け取った時点の時間

public void OnReceive(CharacterInfo info)
{
    prevInfo = nowInfo;
    nowInfo = info;
    time = Time.time;
}

void FixedUpdate()
{
    // timeを元にtransformを補間
    var delta = Time.time - time;
    var rate = delta / Time.fixedDeltaTime;
    transform.position = Vector3.Lerp(prevInfo.pos, nowInfo.pos, rate);
    transform.rotation = Quaternion.Slerp(prevInfo.rot, nowInfo.rot, rate);
}
```

補間処理が記述できているので問題なさそうです。
さて、これがどの様な挙動をするかというと、他キャラは一定速度で移動せず、微妙にブツ切りにワープします。

なぜそのようなことが起こるかというと、サーバから一定間隔で他キャラ情報を受け取っていないからです。この移動処理は一定間隔でサーバから他キャラ情報を受け取ることを前提にしていますが、それは回線やその他の問題で事実上不可能です。なので、一定間隔でサーバから情報を受け取れない事を前提に移動処理を記述しなければなりません。

### キャラクタが一定のスピードで移動しない②

先の対応ではキャラクタが一定のスピードで移動してくれない事が分かりました。なので、線形補間を使った滑らかな移動を試してみます。キャラクタの現在位置から目的の位置までを毎フレーム差分時間を使って移動させるやり方です。移動処理だけでなくいろんな場面で滑らかな表現を可能にする手法なので行けそうな気がします。

```csharp
class CharacterInfo
{
    public Vector3 pos;
    public Quaternion rot;
}

[SerializeField] private float damp = 4.0f; //減衰

private CharacterInfo targetInfo; // 目的の位置情報

public void OnReceive(CharacterInfo info)
{
    targetInfo = info;
}

void FixedUpdate()
{
    transform.position = Vector3.Lerp(transform.position, targetInfo.pos, Time.fixedDeltaTime * damp);
    transform.rotation = Quaternion.Slerp(transform.rotation, targetInfo.rot, Time.fixedDeltaTime * damp);
}
```

この手法でキャラクタの動きがどの様に見えるかというと、一定速度で動かずガクガクした動きになります。damp(移動減衰値)を下げれば滑らかな動きに多少なりますが、キャラクタの本来の位置と現在位置がかなりずれるため、リアルタイム性が求められるゲームには全く向いていません。

<img src="https://camo.qiitausercontent.com/8b3423f120ab8c3a8bcf9f70bd2d9cf6be5167cf/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e61702d6e6f727468656173742d312e616d617a6f6e6177732e636f6d2f302f3131333539352f35353330613465312d393931322d643834662d306334302d6535383834653862663837342e706e67">
↑ガクガクした動きの例(apngなのでブラウザによってはうまく表示されないかもしれません)


色んな補間のやり方がありますが上記の手法ではどれもうまくいきませんでした。サーバからデータが送られてくる間隔が一定でない場合に他キャラをほとんど遅延なく滑らかに動かすにはどうすれば良いでしょうか。

## 考えた解決手法

上記の問題を解決するために考えた解決手法は、他キャラが位置情報を送信する時点の時間を同時に送り、サーバから受け取った他キャラ情報をリストに保持し自クライアントの時間と他キャラ情報の時間を比べて位置を補間するというやり方です。分かりやすく解説していきます。

① 他クライアントは送信時に位置情報だけでなく時間も同時に送る

他クライアントは通常位置情報をサーバに送信するだけですが、そこに送信時の時間も載せます。こうする事で、クライアントがサーバから受け取った他キャラ情報がサーバから受け取った時間ではなく他キャラの送信時点の時間になるので、一定時間で受け取らなくても問題にならなくなります。(MagicOnionのhubを使っていますが、ここでは詳細を割愛いたします)

```csharp
class CharacterInfo
{
    public Vector3 pos;
    public Quaternion rot;
    public float time;
}

IEnumerator UpdateCoroutine()
{
	while(true)
	{
		// サーバにキャラクタの位置、回転、送信時のクライアント時間を送る
		var info = new CharacterInfo()
		{
			pos = player.transform.position,
			rot = player.transform.rotation,
			time = Time.time
		};
		hub.UpdateAsync(info);
		// 0.04秒ごとにサーバに送信する想定
		yield return new WaitForSeconds(0.04f);
	}
}
```

② サーバから受け取った他キャラ情報をリストに保持する

次に、自クライアントは他キャラ情報をリストに保持していきます。これは、ある一定期間の他キャラ情報が無いと補間が出来なくなるためです。

```csharp
class CharacterInfo
{
    public Vector3 pos;
    public Quaternion rot;
    public float time;
}

private List<CharacterInfo> infoList = new List<CharacterInfo>();

public void OnReceive(CharacterInfo info)
{
    infoList.Add(info);
}
```

③ 自クライアントと他クライアントの時間差を考慮する

このままでは、自クライアントの時間と他クライアントの時間に差が出来てしまいうまく位置の補間が出来なくなります。なので、時間差を埋める処理を入れます。

```csharp
class CharacterInfo
{
    public Vector3 pos;
    public Quaternion rot;
    public float time;
}

private List<CharacterInfo> infoList = new List<CharacterInfo>();
private float fixedTime = 0.0f; // 他キャラ情報の補正時間
private float startTime = 0.0f; // 自クライアントの補正時間
private Vector3 targetPos; // 他キャラの目的の位置

void Start()
{
    // 自クライアントの時間補正も考慮する
    startTime = Time.fixedTime;
}

public void OnReceive(CharacterInfo info)
{
    // 最初に送られてきた他キャラ情報の時間を起点にする
    // こうする事で、送られてきた時点から経過時間を考える事が出来る
    if (fixedTime == 0.0f) fixedTime = info.time;
    info.time -= fixeTime;
    infoList.Add(info);
}
```

④ 時間から他キャラの位置を補完する

補正時間を考慮した記述で他キャラの位置を割り出します。

```csharp
class CharacterInfo
{
    public Vector3 pos;
    public Quaternion rot;
    public float time;
}

[SerializeField] private float moveDamp = 12.0f; // 移動減衰

private List<CharacterInfo> infoList = new List<CharacterInfo>();
private float fixedTime = 0.0f; // 他キャラ情報の補正時間
private float startTime = 0.0f; // 自クライアントの補正時間
private int infoListIdx = 0; // 参照するinfoListのindex

void Start()
{
    // 自クライアントの時間補正も考慮する
    startTime = Time.fixedTime;
}

public void OnReceive(CharacterInfo info)
{
    // 最初に送られてきた他キャラ情報の時間を起点にする
    // こうする事で、送られてきた時点から経過時間を考える事が出来る
    if (fixedTime == 0.0f) fixedTime = info.time;
    info.time -= fixeTime;
    infoList.Add(info);
}

void FixedUpdate()
{
    var t = Time.fixedTime - startTime; // 現在の時間
    var i = infoListIdx;
    while (i < infoList.Count - 2)
    {
        // 一定期間内に他キャラがいる
        if (t >= infoList[i].time && t < infoList[i+1].time)
        {
            // 補間時間を割り出す
            var rate = Mathf.InverseLerp(infoList[i].time, infoList[i+1].time, t);
            // 目的位置を割り出す
            targetPos = Vector3.Lerp(infoList[i].pos, infoList[i+1].pos, rate);
            // 回転はここで指定
            transform.rotation = Quaternion.Slerp(infoList[i].rot, infoList[i+1].rot, rate);
            // インデックス指定
            infoListIdx = Mathf.Max(i - 1, 0);
            // 不要な他キャラ情報は削除
            if (infoListIdx > 0) infoList.RemoveAt(0);
            break;
        }
        i++;
    }

    // 滑らかに移動するために固めの線形補間を使う
    transform.position = Vector3.Lerp(transform.position, targetPos, Time.fixedDeltaTime * moveDamp);
}
```

⑤ レイテンシを考慮する

しかしこのままでは、他クライアント->サーバ->自クライアントに情報が来るまでの遅延を考慮していないので、正しい動作にならない可能性があります。そこで、他クライアントから送られてくる情報の遅延の大きさに関わらずに位置を補正できる様に可変レイテンシを組み込みます。

可変レイテンシを組み込んで細かい調整をした最終的な形はこうなります。

```csharp
class CharacterInfo
{
    public Vector3 pos;
    public Quaternion rot;
    public float time;
}

[SerializeField] private float moveDamp = 12.0f; // 移動減衰
[SerializeField] private int interval = 2; // infoList参照の広さ

private List<CharacterInfo> infoList = new List<CharacterInfo>();
private float fixedTime = 0.0f; // 他キャラ情報の補正時間
private float startTime = 0.0f; // 自クライアントの補正時間
private int infoListIdx = 0; // 参照するinfoListのindex
private float latency = 0.0f; // 最初は遅延なしで考える

void Start()
{
    // 自クライアントの時間補正も考慮する
    startTime = Time.fixedTime;
}

public void OnReceive(CharacterInfo info)
{
    // 最初に送られてきた他キャラ情報の時間を起点にする
    // こうする事で、送られてきた時点から経過時間を考える事が出来る
    if (fixedTime == 0.0f) fixedTime = info.time;
    info.time -= fixeTime;
    infoList.Add(info);
}

void FixedUpdate()
{
    var t = Time.fixedTime - startTime - latency; // 現在の時間
    var i = infoListIdx;
    while (i < infoList.Count - interval)
    {
        // 一定期間内に他キャラがいる
        var fromInfo = infoList[i];
        var toInfo = infoList[i + interval - 1];
        if (t >= fromInfo.time && t < toInfo.time)
        {
            // 補間時間を割り出す
            var rate = Mathf.InverseLerp(fromInfo.time, toInfo.time, t);
            // 目的位置を割り出す
            targetPos = Vector3.Lerp(fromInfo.pos, toInfo.pos, rate);
            // 回転はここで指定
            transform.rotation = Quaternion.Slerp(fromInfo.rot, toInfo.rot, rate);
            // インデックス指定
            infoListIdx = Mathf.Max(i - 1, 0);
            // 不要な他キャラ情報は削除
            if (infoListIdx > 0)
            {
                infoList.RemoveAt(0);
                // 遅延なく参照できた場合は遅延を少し少なくする
                latency = Mathf.Max(latency - Time.fixedDeltaTime, 0.0f);
            }

            break;
        }
        i++;
    }
    // 上手く参照できなかった場合は遅延を大きくする
    if (i >= infoList.Count - interval) latency += Time.fixedDeltaTime;

    // 滑らかに移動するために固めの線形補間を使う
    transform.position = Vector3.Lerp(transform.position, targetPos, Time.fixedDeltaTime * moveDamp);
}
```

移動処理だけを重点的に記述しただけなのでこのままでは当然動きませんが、これをベースに動くようにしたら下図の様に他キャラが動くようになります。

<img src="https://camo.qiitausercontent.com/0a7165d2a3ea3356f91dc5704cb946a24fad33bf/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e61702d6e6f727468656173742d312e616d617a6f6e6177732e636f6d2f302f3131333539352f34613566383033632d376639632d363562652d346336332d3162316566373965383735312e706e67">

いかがでしょう、自分でキャラを動かしている様に見えるくらいには滑らかに動かせているのではないでしょうか。
様々な手法を試して一番良い動きをしたのがこの手法でした。

今回の手法ではキャラクタの動きを予測して移動させる(加速度や入力方向をサーバから受け取って処理する)という事はしていません、予測した動きをするとキャラクタがいきなり早くなったりワープせざる負えない可能性があるからです。もちろん予測した動きを記述したほうが遅延が無いように見せることできますが、そのコードを記述するのには少し時間がかかりそうなので、一先ず今回の手法を提案した次第です。


## 番外編：扇問題の解決

扇問題とは、クライアントサーバモデルでN個のクライアントの情報をリアルタイムに他のクライアントに反映させたい場合、安直にコーディングすると通信回数が$N * (N-1)$になるという問題です。つまり、クライアント数が増えれば増えるほど、通信回数が爆発的に増えるという事です。

詳しくは以下の記事を参照いただければ分かるかと思います

* [多人数リアルタイム通信ボトルネック問題、扇問題について](https://qiita.com/kyadet/items/1b45e4cb33adb38dc04b)

この問題、安直なコーディングをすると必ず発生してしまうのですが、意外と簡単に回避できます。
それは、サーバからクライアントにデータを送るタイミングを、クライアントからデータを受け取った時ではなく、サーバ主導で一定間隔で送るようにすればいいだけです。クライアントからデータを受け取る度にサーバが処理していたら処理負荷がクライアントの数に引っ張られてしまうので、それを回避するというのが重要となります。

詳しく説明する前にまず、サーバがクライアントからデータを受け取ったタイミングで全クライアントにデータをブロードキャストする場合の通信回数の例を見てみます①。

クライアント数を$N = 100$、クライアントは秒間$T = 20$回データを送信すると仮定すると、1秒間にサーバからクライアントに向けて発生する通信回数は以下の通りとなります。

$N * (N - 1) * T = 100 * 99 * 20 = 198,000$

これでは、通信回数があまりにも多くて負荷が大きすぎるのは目に見えています。

次に、サーバ主導でクライアントにデータをブロードキャストするとどうなるか見てみます②。

先ほどと同じく、$N = 100$、クライアントは秒間$T = 20$回データを送信すると仮定します。そして、サーバは**秒間20回全クライアントのデータをまとめて送信する**様にします。すると、通信回数は以下の通りになります。

$N * T = 100 * 20 = 2,000$

198,000が2,000まで減りました。約1/100です。少し工夫するだけでこれだけ通信回数が変わりました。
気になるのは通信量です。実は①と②は通信量自体はほぼ変わりません。

クライアントが送信するデータを$D = 28$byte(位置(float x 3) + 回転(float x 4))と仮定すると、①の1秒間の通信量は
99人に28byte送信する処理が100人分あり、それを20回行うので

$(N * (N - 1) * D) * T = 100 * 99 * 28 * 20 = 5,544,000$

で約5.54MBです。

②の1秒間の通信量は
100人に100人分の28byte送信を20回行うので

$N * (N * D) * T = 100 * 100 * 28 * 20 = 5,600,000$

でこちらは約5.6MBとなります。

通信量が変わらないとあまり意味がないと思うかもしれませんが、1 x 10000 と 100 x 100をプログラムが捌くのは明らかに後者の方が速いですし、更に今回はMagicOnionを使っている前提の話なので、内部のデータフォーマッタであるMessagePackによる送信データの圧縮が効きます。それを考えると、②の方が断然効率が良くなります。

キャラクタの位置回転等、秒間20回など高頻度で送信しなければならない場合は②の方が良いですが、例えばキャラクタがアイテムを拾うという処理データを通信するとなると、逆にこちらは①の方が良いです。なぜなら、送信頻度が高くなく連続で送らなくてもいいデータだからです。処理によって住み分けをしっかり行うことが大切になります。

# まとめ

3Dリアルタイム通信の移動処理について、うまくいかなかったパターンと解決出来たパターンを紹介いたしました。
勿論、今回考察した移動処理の捌き方が正解というわけではありませんし、問題なく処理できるという保証もありません（実際サーバをクラウドにデプロイして確認したわけではないので…）。なので、１つのやり方としてこんな移動処理の捌き方があるんだという認識をしていただければと幸いです。

この手の記事がほとんど見受けられなかったので、率先して記事にさせていただきました。今回の手法よりもより現実的で実用的な手法があったら是非参考にしたいのでご教授いただければと思います。

# 権利表記

以下のモデルをお借りして動作確認を行っています。
初音ミク(6)
https://3d.nicovideo.jp/works/td66256
著作: 如月z 様
https://3d.nicovideo.jp/users/56980238