マルチプレイヤーネットワーキングのプレイヤー位置同期について Part4～Interpolation2

# リキャップ
[Part3](http://qiita.com/y_li/items/4aebc5a1acd3cc6796b6)でpredictionを紹介することで自分のキャラクターのパフォーマンスを相当改善したと思います。
しかし、他のクライアントがコントロールしているキャラクターはpredictionに必要とされている情報が都合に合うタイミングで入手出来ないため、残念ながら適用出来ません。

では、どうすればいいでしょう？もちろん、interpolationに任せるしかありません。
でも、Part2で演示したようにinterpolationの効果はパーフェクトと言えません。
自分が最近色々改善策を試したところで自分が納得出来る効果を何とか実現したので、このPart4で共有したいと思います。

# Interpolationの問題
まずは記憶をリフレッシュするため、interpolationの問題をもう一度考えましょう。
Part2で見えた問題は主に二つありまして、微妙なグダグダ感と入力から反応までのラグ感この二つです。

ラグ感はインターネット通信している以上回避できない問題なので、諦めましょう。
微妙なグダグダ感について何とか解決策を考えましょう。

# 発想と改善
これから少しずつ改善策を説明します。
サンプルとして表示するコードは一応Part3をベースに改修したものですが、読みやすいため関係のない部分は省略させていただきます。

## スムーズさの改善
スムーズに見せるのが目的のinterpolationは何故か微妙にグダグダになっている原因は同期メッセージがクライアントに届くインターバルの違いによる移動スピード不一致です。
なので、考えられるのはインターバルを無視してスピードを固定させることです。つまり、前後にフレームの間に固定なスピードで補間することです。

コードはこんな感じです。

```csharp
// Client
private float m_Speed = 5.0f;
private IPackerSet m_PackerSet = new BasicPackerSet();
private Vector3 m_TargetVal;

public override int OnReceive(MemoryStream stream)
{
    int read = 0;

    object latest_ack_timestamp;
    object latest_ack_pos;

    read += m_PackerSet.Unpack(stream, out latest_ack_timestamp);
    read += m_PackerSet.Unpack(stream, out latest_ack_pos);

    var pos = ((Vec3f)latest_ack_pos).ToUnityVector3();

    if (CommunicationProxy.IsMine)
    {
        // クライアントが予測した移動結果をサーバの計算結果と比較。。。
    }
    else
    {
        m_TargetVal = pos;
    }

    return read;
}

public override int OnSend(MemoryStream stream)
{
    int write = 0;

    // 入力情報を送信出来るのはこのクライアントがコントロールしているキャラクターだけ
    if (CommunicationProxy.IsMine)
    {
        // ユーザ入力情報をstreamに書きます。。。
    }

    return write;
}

private void LateUpdate()
{
    if (CommunicationProxy.IsMine)
    {
        // 移動予測。。。
    }
    else
    {
        transform.position = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);
    }
}
```
では、早速比較してみましょう。
今回の比較重点は改善前後のリモートクライアントキャラクターのinterpolation効果なので、ローカルは表示しますが、サーバキャラクターは非表示させていただきます。
説明：
1. ”ローカル”は比較対象として用意したサーバと通信せずユーザの操作にすぐ反応するキャラクターです。緑のキューブで表示します。
2. ”Interpolation1”は改善する前のinterpolationを使っているキャラクターです。青いキューブで表示します。
3. ”Interpolation2”は改善したinterpolationを使っているキャラクターです。Interpolation1より明るい青いキューブで表示します。
4. 画面下部の矢印はユーザが押したボタンです。

1.ローカル VS Interpolation1（同期頻度：20 fps）

![local_interpolation1.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/607e49cd-2a1d-ae66-2d16-595f9fe0b15e.gif)

2.ローカル VS Interpolation2（同期頻度：20 fps）

![local_interpolation2.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/13f51558-49c2-7582-f035-4597db1434cf.gif)

3.ローカル VS Interpolation2 VS Interpolation1（同期頻度：20 fps）

![local_interpolation1_interpolation2.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/9bf59982-6bec-312e-da3f-4ffaceb4c778.gif)

4.ローカル VS Interpolation1（同期頻度：5 fps）

![local_interpolation1.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/6e943958-f992-22df-9a02-ccd5afec0568.gif)

5.ローカル VS Interpolation2（同期頻度：5 fps）
 
![local_interpolation2.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/023be2ab-9f43-a493-af4b-81cda6b70767.gif)

6.ローカル VS Interpolation2 VS Interpolation1（同期頻度：5 fps）

![local_interpolation1_interpolation2.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/ef3e9ebc-4ae8-8187-8143-3ab86bdc36bd.gif)

ご覧通りにinterpolation2の移動痕跡がもっとスムーズになっています。特に20fpsバージョンの方が明らかです。原因は5fpsバージョンで同期のインターバルが20fpsより長いため、ある程度インターバル変動の影響・頻度を軽減したからです。

しかし、interpolation2でもたまにジャンプしているように見えますが、それはネットワークの不安定によるパッケージロストかまたは一瞬急激な通信スピードの変動です。

## パッケージロスト対策
では、次は上記パッケージロスト・スピード変更によるパッケージ到達遅延の対策を考えまよう。
方法としてはレンダリングを更に過去に戻すことです！つまり、同期フレームをキャッシュしてパッケージロスト・到達遅延の時アーティフィシャルが出る状況に陥ってしまいまである程度のバッファーを持たせることです。
注意すべきのは、この方法はラグを代償としてスムーズさを求めることです。だから、キャッシュしすぎると人為的にラグを厳しくさせることになります。
これはゲームプレイによって最適な値が違いますが、普通はextrapolationと結合して2フレームぐらいのキャッシュで使います。

コードは以下です。

```csharp
// Client
private int m_BufferSize = 2;
private Queue<Vector3> m_SyncFrameCache = new Queue<Vector3>();
private float m_Speed = 5.0f;
private IPackerSet m_PackerSet = new BasicPackerSet();
private Vector3 m_TargetVal;

public override int OnReceive(MemoryStream stream)
{
    int read = 0;

    object latest_ack_timestamp;
    object latest_ack_pos;

    read += m_PackerSet.Unpack(stream, out latest_ack_timestamp);
    read += m_PackerSet.Unpack(stream, out latest_ack_pos);

    var pos = ((Vec3f)latest_ack_pos).ToUnityVector3();

    if (CommunicationProxy.IsMine)
    {
        // クライアントが予測した移動結果をサーバの計算結果と比較。。。
    }
    else
    {
        if (m_SyncFrameCache.Count >= m_BufferSize)
        {
            m_SyncFrameCache.Dequeue();
        }
        m_SyncFrameCache.Enqueue(pos);
    }

    return read;
}

public override int OnSend(MemoryStream stream)
{
    int write = 0;

    // 入力情報を送信出来るのはこのクライアントがコントロールしているキャラクターだけ
    if (CommunicationProxy.IsMine)
    {
        // ユーザ入力情報をstreamに書きます。。。
    }

    return write;
}

private void LateUpdate()
{
    if (CommunicationProxy.IsMine)
    {
        // 移動予測。。。
    }
    else
    {
        if (m_SyncFrameCache.Count == m_BufferSize)
        {
            // フレームキャッシュは既にいっぱいなので、人為的なラグを抑え、キャッシュの貯めと消費バランスを維持するため、
            // 今補間中のフレームをスキップします
            m_TargetVal = m_SyncFrameCache.Dequeue();
            transform.position = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);
        }
        else
        {
            var new_val = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);

            // MoveTowardsメソッドはTime.deltaTime * m_Speedがtransform.positionとm_TargetValの間の距離より遠い場合
            // m_TargetValを返すので
            // Time.deltaTime内実際移動できる距離を計算するため、次のフレームをターゲットにします。
            // しないと、当アップデートで正確な移動距離を算出出来ません
            if (new_val.Equals(m_TargetVal) && m_SyncFrameCache.Count > 0)
            {
                m_TargetVal = m_SyncFrameCache.Dequeue();
                transform.position = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);
            }
            else
            {
                transform.position = new_val;
            }
        }
    }
}
```

ご覧通り、フレームバッファーには2フレームをキャッシュしていて、例えその内1フレームがロストや到達遅延だとしても計算が止まることにはなりません。
でも、万が一2フレームもロストしてしまいましたらどうしましょう？
普通の状況下は極稀なので、そのまま計算を止めるてもいいですが、でももうちょっと頑張ってみましょう。

## Extrapolation
方法はextrapolationを使うことです。
Interpolationは前後二フレームのデータを元にこの間ある時点のデータを計算する方法と言いますと、extrapolationは前後二フレームのデータを元にこの間以外の時点のデータを計算する方法です。
なので、extrapolationというのは事実上ある程度の予測です。この予測は精確予測に必要の情報が持っていないで行うものなので、Part3で紹介された方法のような完璧な予測は出来ません。Extrapolationを連続に行う時間が長くほど正確度が低くなるため、一回extrapolationで続ける最大時間を抑えましょう。（ここでは0.1秒にします）

コードは以下です。

```csharp
// Client
private int m_BufferSize = 2;
private Queue<Vector3> m_SyncFrameCache = new Queue<Vector3>();
private float m_Speed = 5.0f;
private IPackerSet m_PackerSet = new BasicPackerSet();
private Vector3 m_TargetVal;
private Queue<KeyValuePair<T, T>> m_SyncFrameCache = new Queue<KeyValuePair<T, T>>();
private float m_ExtrapolatedTime = 0.0f;
private float m_ExtrapolatedMax = 0.1f;
private bool m_IsExtrapolating = false;

public override int OnReceive(MemoryStream stream)
{
    int read = 0;

    object latest_ack_timestamp;
    object latest_ack_pos;
    object dir;

    read += m_PackerSet.Unpack(stream, out latest_ack_timestamp);
    read += m_PackerSet.Unpack(stream, out latest_ack_pos);
    read += m_PackerSet.Unpack(stream, out dir);

    var pos = ((Vec3f)latest_ack_pos).ToUnityVector3();

    if (CommunicationProxy.IsMine)
    {
        // クライアントが予測した移動結果をサーバの計算結果と比較。。。
    }
    else
    {
        if (m_SyncFrameCache.Count >= m_BufferSize)
        {
            m_SyncFrameCache.Dequeue();
        }

        // dirはextrapolationで使われる方向です。
        // 前後二フレームを使ってdirを予測するより、サーバから正確な方向をもらう方が計算の精度がより高くなります
        m_SyncFrameCache.Enqueue(new KeyValuePair<Vector3, Vector3>(dir, pos));
    }

    return read;
}

public override int OnSend(MemoryStream stream)
{
    int write = 0;

    // 入力情報を送信出来るのはこのクライアントがコントロールしているキャラクターだけ
    if (CommunicationProxy.IsMine)
    {
        // ユーザ入力情報をstreamに書きます。。。
    }

    return write;
}

private Vector3 Extrapolate(Vector3 start, Vector3 dir, float interval, float speed)
{
    // Extrapolation出来る最大時間限度に届いたらextrapolationをストップします
    if (m_ExtrapolatedTime >= m_ExtrapolatedMax) return start;

    m_ExtrapolatedTime += interval;
    return start + dir * interval * speed;
}

private void LateUpdate()
{
    if (CommunicationProxy.IsMine)
    {
        // 移動予測。。。
    }
    else
    {
        if (m_IsExtrapolating)
        {
            if (m_SyncFrameCache.Count == m_BufferSize ||
                (m_SyncFrameCache.Count > 0 && m_ExtrapolatedTime >= m_ExtrapolatedMax))
            {
                // Extrapolationの途中にフレームバッファーがいっぱいになった
                // またはバッファーにフレームが残っていて、extrapolationする最大時間限度に届いた時
                m_IsExtrapolating = false;
                var frame = m_SyncFrameCache.Dequeue();
                m_Direction = frame.Key;
                m_TargetVal = frame.Value;

                transform.position = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);
            }
            else
            {
                transform.position = Extrapolate(transform.position, m_Direction, Time.deltaTime, m_Speed);
            }
        }
        else
        {
            if (m_SyncFrameCache.Count == m_BufferSize)
            {
                // フレームキャッシュは既にいっぱいなので、人為的なラグを抑え、キャッシュの貯めと消費バランスを維持するため、
                // 今補間中のフレームをスキップします
                var frame = m_SyncFrameCache.Dequeue();
                m_Direction = frame.Key;
                m_TargetVal = frame.Value;
                transform.position = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);
            }
            else
            {
                var new_val = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);

                // MoveTowardsメソッドはTime.deltaTime * m_Speedがtransform.positionとm_TargetValの間の距離より遠い場合
                // m_TargetValを返すので
                // Time.deltaTime内実際移動できる距離を計算するため、次のフレームをターゲットにします。
                // しないと、当アップデートで正確な移動距離を算出出来ません
                if (new_val.Equals(m_TargetVal))
                {
                    // 何かの原因でバッファーに一フレームも持っていない場合でextrpolationを行います
                    if (m_SyncFrameCache.Count == 0)
                    {
                        m_ExtrapolatedTime = 0.0f;
                        m_IsExtrapolating = true;
                        transform.position = Extrapolate(transform.position, m_Direction, Time.deltaTime, m_Speed);
                    }
                    else
                    {
                        var frame = m_SyncFrameCache.Dequeue();
                        m_Direction = frame.Key;
                        m_TargetVal = frame.Value;
                        transform.position = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);
                    }
                }
                else
                {
                    transform.position = new_val;
                }
            }
        }
    }
}
```
では、早速また効果を見ましょう。

1.ローカル VS Interpolation1（同期頻度：20 fps）

![local_interpolation1.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/d09d5bc2-7dda-9e5d-ef23-1e2210efb1e7.gif)

2.ローカル VS Interpolation2（同期頻度：20 fps）

![local_interpolation2.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/01c2a5fd-320e-a825-bc75-ea48e9e19ef1.gif)

3.ローカル VS Interpolation2 VS Interpolation1（同期頻度：20 fps）

![local_interpolation1_interpolation2.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/bbfe75b6-ca33-5aab-5848-4fe5eed35b5c.gif)

4.ローカル VS Interpolation1（同期頻度：5 fps）

![local_interpolation1.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/6fa2466d-f4a2-1b77-c4be-37b8820bf368.gif)

5.ローカル VS Interpolation2（同期頻度：5 fps）
 
![local_interpolation2.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/10531f2c-6b85-c92c-ea4c-49878fa66d65.gif)

6.ローカル VS Interpolation2 VS Interpolation1（同期頻度：5 fps）

![local_interpolation1_interpolation2.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/aa55d09f-7fb1-68e7-6189-7b532bf335bf.gif)

## 再同期
同期効果はどんどん完璧に近づいていますが、でももう一つ懸念が残っています。それはより厳しいパッケージロストや遅延が発生したら、ちゃんと復帰できるかどうかです。
もともとinterpolationの場合、スピードは同期インターバルにより自動的に変動するこら上記の状況が発生してもスピードが一瞬高くなり、心配はいりません。
しかし、ここで説明した改修版interpolationはスムーズに見せるため、スピードと同期インターバルの繋がりを削除してスピードを定数に変わりました。
つまり、その自動復帰能力もなくなってしまいました。上記異常状況が発生してしまいますと、以下のようなラグ激増になります。
![before.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/95d4fbfb-433d-f717-ba11-15500ce770b9.gif)

では、どうすればこの復帰能力を取り戻せるんでしょうか？
答えはPart3のpredictionで一度説明した再同期ロジックと似ているものを入れればいいです！しかもPart3のような複雑な再同期ではなく、もっと簡単なものです。
つまり、一定なラグ（前後二フレーム間の時間差）限界値を超えたら最新の位置に瞬間移動させることです。

実装は以下のような感じです。

```csharp
// Client
private int m_BufferSize = 2;
private Queue<Vector3> m_SyncFrameCache = new Queue<Vector3>();
private float m_Speed = 5.0f;
private IPackerSet m_PackerSet = new BasicPackerSet();
private Vector3 m_TargetVal;
private Queue<KeyValuePair<T, T>> m_SyncFrameCache = new Queue<KeyValuePair<T, T>>();
private float m_ExtrapolatedTime = 0.0f;
private float m_ExtrapolatedMax = 0.1f;
private bool m_IsExtrapolating = false;
private float m_LastSync = 0.0f;

public override int OnReceive(MemoryStream stream)
{
    int read = 0;

    object latest_ack_timestamp;
    object latest_ack_pos;
    object dir;

    read += m_PackerSet.Unpack(stream, out latest_ack_timestamp);
    read += m_PackerSet.Unpack(stream, out latest_ack_pos);
    read += m_PackerSet.Unpack(stream, out dir);

    var pos = ((Vec3f)latest_ack_pos).ToUnityVector3();

    if (CommunicationProxy.IsMine)
    {
        // クライアントが予測した移動結果をサーバの計算結果と比較。。。
    }
    else
    {
        var interval = Time.time - m_LastSync;
        m_LastSync = Time.time;

        if (interval >= m_ResyncThreshold)
        {
            Reset(pos);
            return read;
        }

        if (m_SyncFrameCache.Count >= m_BufferSize)
        {
            m_SyncFrameCache.Dequeue();
        }

        // dirはextrapolationで使われる方向です。
        // 前後二フレームを使ってdirを予測するより、サーバから正確な方向をもらう方が計算の精度がより高くなります
        m_SyncFrameCache.Enqueue(new KeyValuePair<Vector3, Vector3>(dir, pos));
    }

    return read;
}

public override int OnSend(MemoryStream stream)
{
    int write = 0;

    // 入力情報を送信出来るのはこのクライアントがコントロールしているキャラクターだけ
    if (CommunicationProxy.IsMine)
    {
        // ユーザ入力情報をstreamに書きます。。。
    }

    return write;
}

private void Reset(Vector3 initial_val)
{
    m_SyncFrameCache.Clear();
    m_ExtrapolatedTime = 0.0f;
    m_TargetVal = transform.position = initial_val;
    m_IsExtrapolating = false;
}

private Vector3 Extrapolate(Vector3 start, Vector3 dir, float interval, float speed)
{
    // Extrapolation出来る最大時間限度に届いたらextrapolationをストップします
    if (m_ExtrapolatedTime >= m_ExtrapolatedMax) return start;

    m_ExtrapolatedTime += interval;
    return start + dir * interval * speed;
}

private void LateUpdate()
{
    if (CommunicationProxy.IsMine)
    {
        // 移動予測。。。
    }
    else
    {
        if (m_IsExtrapolating)
        {
            if (m_SyncFrameCache.Count == m_BufferSize ||
                (m_SyncFrameCache.Count > 0 && m_ExtrapolatedTime >= m_ExtrapolatedMax))
            {
                // Extrapolationの途中にフレームバッファーがいっぱいになった
                // またはバッファーにフレームが残っていて、extrapolationする最大時間限度に届いた時
                m_IsExtrapolating = false;
                var frame = m_SyncFrameCache.Dequeue();
                m_Direction = frame.Key;
                m_TargetVal = frame.Value;

                transform.position = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);
            }
            else
            {
                transform.position = Extrapolate(transform.position, m_Direction, Time.deltaTime, m_Speed);
            }
        }
        else
        {
            if (m_SyncFrameCache.Count == m_BufferSize)
            {
                // フレームキャッシュは既にいっぱいなので、人為的なラグを抑え、キャッシュの貯めと消費バランスを維持するため、
                // 今補間中のフレームをスキップします
                var frame = m_SyncFrameCache.Dequeue();
                m_Direction = frame.Key;
                m_TargetVal = frame.Value;
                transform.position = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);
            }
            else
            {
                var new_val = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);

                // MoveTowardsメソッドはTime.deltaTime * m_Speedがtransform.positionとm_TargetValの間の距離より遠い場合
                // m_TargetValを返すので
                // Time.deltaTime内実際移動できる距離を計算するため、次のフレームをターゲットにします。
                // しないと、当アップデートで正確な移動距離を算出出来ません
                if (new_val.Equals(m_TargetVal))
                {
                    // 何かの原因でバッファーに一フレームも持っていない場合でextrpolationを行います
                    if (m_SyncFrameCache.Count == 0)
                    {
                        m_ExtrapolatedTime = 0.0f;
                        m_IsExtrapolating = true;
                        transform.position = Extrapolate(transform.position, m_Direction, Time.deltaTime, m_Speed);
                    }
                    else
                    {
                        var frame = m_SyncFrameCache.Dequeue();
                        m_Direction = frame.Key;
                        m_TargetVal = frame.Value;
                        transform.position = Vector3.MoveTowards(transform.position, m_TargetVal, Time.deltaTime * m_Speed);
                    }
                }
                else
                {
                    transform.position = new_val;
                }
            }
        }
    }
}
```
これで復帰能力が戻りました。
![after.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/f3a109b8-ff60-3773-0830-455a3144339e.gif)

# まとめ
本文は最後のPartです。一応これでServer Authoritative Movementは以下自分にとって納得出来る目標を達成しました。
1. 安全性
2. ユーザインプットに対する即時反応（自分がコントロールするキャラクターのみ）
3. キャラクター移動のスムーズさ

# レファレンス
1. https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking
2. http://www.paladinstudios.com/2014/05/08/how-to-create-an-online-multiplayer-game-with-photon-unity-networking/
3. https://gamesnet.yahoo.net/documentation/tutorials/building-flash-multiplayer-games-tutorial/synchronization
4. https://gamesnet.yahoo.net/documentation/tutorials/building-flash-multiplayer-games-tutorial/interpolation
5. http://www.gabrielgambetta.com/fpm1.html