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

# リキャップ
[Part2](http://qiita.com/y_li/items/b976cfd5800f0e1ffff7)で紹介されたinterpolation方法はキャラクター移動のスムーズさをかなり向上させたんですが、完璧とは言えません。特にキャラクター反応のラグが気になります。

# Prediction
なので、今回はそれを完璧に解決できるもう一つの方法を紹介したいと思います。この方法はprediction（予測）です。

## Predictionとは
Client Authoritative Movementが自分のキャラクターがスムーズかつラグなしで移動できるのは計算ロジックがクライアント側が持っていて、サーバは単純な転送しかやっていないからです。いわゆる、smart clientとdumb serverです。
Server Authoritative Movementが安全的で、チートを最大限度防止出来るのは計算ロジックがサーバ側が持っていて、クライアントは単純にサーバの計算結果をユーザに見せるのみからです。つまり、dumb clientとsmart serverです。

両方も各自の優劣があり、どちらも完璧に言えません。ではどうすればそれぞれの優勢を発揮し、劣勢を回避できるんでしょう？
自然に考えられるのはもちろんサーバもクライアントもスマートにすることです。つまり、smart clientとsmart serverです。
実現原理を言葉で言うと実は結構シンプルなもので、単純に移動の計算ロジックをサーバとクライアント両方にも持たせれば大丈夫です。

もっと詳しく説明すると、クライアント側がもちろん今までのようにユーザ操作をサーバ側へ送信しますが、しかし、その同時にサーバ側のレスポンスを待たずに自分もキャラクターの位置を計算して予測します。
それからその予測結果をすぐレンダリングしてユーザに見せます。サーバが結果を返したら自分の計算結果とサーバの計算結果を比較して、一緒ならば何もしない、違ったらサーバの結果に合わせます。
つまり、サーバは主にチェックのみです。
だって、クライアントにとってユーザの入力情報が既に持っているから、チートをしない限り同じ時点の計算結果は必ずサーバと一緒になるはずです。何故わざわざサーバから自分も知っている情報を待たなければなりませんか？

これで、自分のキャラクターはもちろんすぐ反応するし（完全にラグゼロ）、移動もスムーズだし（補間しなくても毎フレームの位置が分かる）、しかもチートを阻止できます。（サーバが計算結果の最終決定権を持っているから）

## サーバ側について
サーバ側の計算・チェックは色々実装方法がありまして、ここで二つ紹介したいと思います。

### 最も簡単な方法
一番簡単で、計算も重くない方法はサーバ側で精確な計算を行わず、単純に前後二回同期通信の間経過した時間及びキャラクター移動スピードを元に前回の位置と今回の位置の間の距離を検証することです。
この方法はサーバ側のチェックにそんなに精確性を要求しないゲームには結構いい方法と思います。データ送信量が少なくて実装も楽です。
この方法は簡単しすぎるので、ここでは長く説明しなくても分かると思います。

### 更に有効な方法
上記の方法で検証出来るのはあくまで瞬間移動・スピード改ざんをやったかどうかぐらいで、もしもっと細かくコントロールしたければ、今から説明するちょっと面倒な実装を使った方がいいです。
この方法は言葉で話したら実もシンプルです。サーバ側に本当の計算ロジックを持たせばいいのことです。
でもよく考えると、細かいところはいっぱいあります。

まず、サーバ側でキャラクターがユーザの操作に移動させた線路を再構築するため、クライアントがサーバへ送信するデータは一つのユーザ入力だけではなく、前回送信してから今回までの間にすべてのユーザ入力情報と各入力を行ったタイムスタンプです。
あと、今送信した時点でクライアントにキャラクターがどこにるかを記録しておきます。
サーバの返信を待たずに続きのユーザインプットを処理して新しい位置を計算及び表示します。

それから、サーバ側はそのデータを元に前回計算した最終結果及びタイムスタンプから今最新受け取ったデータのタイムスタンプまでキャラクターの移動を再構築して最新のタイムスタンプにキャラクターがどこにいるかを計算します。
計算した結果をクライアントに送信します。

最後、クライアントが受信したらその計算結果を前に記録した同じタイムスタンプを持っているクライアント計算結果と比較します。
合っていればそのままなにもやらなくて続きます。
合っていないければ、今までの流れをストップしてサーバへ同期し直すのリクエストを投げます。
サーバがそれを受け取ったら同じく今までの流れをストップし、自分が計算した最終ユーザ位置を返します。
クライアントがその正確な位置をもらったら同期流れを再開し、サーバへ再同期終了ということを伝えます。
サーバに再同期終了というメッセージが届いたらサーバ側も同期流れを再開します。

図にすると、こんな感じです。
![Prediction.png](https://qiita-image-store.s3.amazonaws.com/0/48530/ebe1790f-e138-9694-c3ae-3552590e8d36.png)

もちろん、この再同期が必要かどうかの検知はクライアントではなく、サーバ側に任せても大丈夫です。その代わりに、同期通信中クライアント側がサーバ側へ送信する時、自分現時点の位置も送信する必要があります。

こうやって、例えチーターが居て改ざんしたクライアントでゲームを進行して、最悪の場合（わざと変なデータを送信するとか、再同期を行わないとか）でも影響を受けるのはチーターのクライアントだけです。
他のクライアントが見えるのはサーバ側の計算結果だけなので、影響を全く受けません。

## 実装
方法一は簡単なので、ここで見せるのは方法二の実装となります。

まずはクライアント側です。

```csharp
// Client

private float m_SqrErrorTolerance = 0.0001f; // サーバの計算結果とクライアントの計算結果はこの値を超えたら再同期の必要があります
private bool m_NeedResync = false; // 再同期が必要になりますと、このフラッグで通常同期流れを一旦ストップします
private Queue<KeyValuePair<float, Vector3>> m_InputQueue = new Queue<KeyValuePair<float, Vector3>>(); // 収集したユーザ操作
private Vector3 m_LastInput = Vector3.zero;
private Queue<KeyValuePair<float, Vector3>> m_PosWaitForAck = new Queue<KeyValuePair<float, Vector3>>(); // サーバ側の計算結果と比較する必要があるクライアントの計算結果記録
private float m_TimeElapsed = 0.0f; // タイムスタンプ生成用
private float m_Speed = 5.0f;
private Vector3 m_Direction = Vector3.zero;
private IPackerSet m_PackerSet = new BasicPackerSet();

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 (!m_NeedResync)
    {
        // クライアントの計算結果とサーバの計算結果を比較
        if (m_PosWaitForAck.Count > 0)
        {
            if ((float)latest_ack_timestamp >= m_PosWaitForAck.Peek().Key)
            {
                // サーバの計算結果のタイムスタンプより古い履歴をスキップします
                var current_ack_pos = m_PosWaitForAck.Dequeue();
                while (current_ack_pos.Key != (float)latest_ack_timestamp)
                {
                    current_ack_pos = m_PosWaitForAck.Dequeue();
                }

                if ((pos - current_ack_pos.Value).sqrMagnitude >= m_SqrErrorTolerance)
                {
                    m_NeedResync = true;
                    CommunicationProxy.RPC("RequestResync");
                }
            }
        }
    }

    return read;
}

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

    if (!m_NeedResync)
    {
        var t = m_TimeElapsed;
        write += m_PackerSet.Pack(t, stream);
        write += m_PackerSet.Pack(m_InputQueue.Count, stream);

        var current_pos = transform.position;
        m_PosWaitForAck.Enqueue(new KeyValuePair<float, Vector3>(t, current_pos));

        while (m_InputQueue.Count > 0)
        {
            var pair = m_InputQueue.Dequeue();
            write += m_PackerSet.Pack(pair.Key, stream);
            write += m_PackerSet.Pack(pair.Value.ToVec3f(), stream);
        }
    }

    return write;
}

private void Move(Vector3 dir)
{
    m_Direction = dir.magnitude > 0.0f ? dir.normalized : Vector3.zero;
}

private void LateUpdate()
{
    var delta_time = Time.deltaTime;

    Move(new Vector3(Input.GetAxis("Horizontal"), 0.0f, Input.GetAxis("Vertical")));

    // 同じ操作を連続二回記録しないようにすることで、送信量を最適化します
    if (m_LastInput != m_Direction)
    {
        m_LastInput = m_Direction;
        m_InputQueue.Enqueue(new KeyValuePair<float, Vector3>(m_TimeElapsed, m_Direction));
    }

    var new_pos = transform.position + m_Direction * m_Speed * delta_time;
    transform.position = new_pos;

    m_TimeElapsed += delta_time;
}

[RPC]
private void Resync(Vec3f resync_pos)
{
    m_InputQueue.Clear();
    m_LastInput = m_Direction = Vector3.zero;
    transform.position = resync_pos.ToUnityVector3();
    m_PosWaitForAck.Clear();

    CommunicationProxy.RPC("FinishResync", m_TimeElapsed);

    m_NeedResync = false;
}
```
次はサーバです。

```csharp
// Server

private bool m_NeedResync = false; // 再同期が必要になりますと、このフラッグで通常同期流れを一旦ストップします
private KeyValuePair<float, Vector3> m_LastSimulatedPos; // 最新の計算結果
private Vector3 m_Direction = Vector3.zero;

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

    object target_timestamp;
    read += m_PackerSet.Unpack(stream, out target_timestamp);

    object input_count;
    read += m_PackerSet.Unpack(stream, out input_count);

    float last_simulated_timestamp = m_LastSimulatedPos.Key;
    Vector3 pos = m_LastSimulatedPos.Value;
    var direction = m_Direction;

    // キャラクター移動状況を再構築します
    for (int i = 0; i < (int)input_count; ++i)
    {
        object input_timestamp;
        object input;

        read += m_PackerSet.Unpack(stream, out input_timestamp);
        read += m_PackerSet.Unpack(stream, out input);

        float delta_time = (float)input_timestamp - last_simulated_timestamp;
        pos += direction * m_Speed * delta_time;

        last_simulated_timestamp = (float)input_timestamp;
        direction = ((Vec3f)input).ToUnityVector3();
    }

    // 今回の同期通信した時点のタイムスタンプまでキャラクターの最新位置を更新します
    float delta_time_to_target = (float)target_timestamp - last_simulated_timestamp;
    pos += direction * m_Speed * delta_time_to_target;

    if (!m_NeedResync)
    {
        m_LastSimulatedPos = new KeyValuePair<float, Vector3>((float)target_timestamp, pos);
        m_Direction = direction;
    }

    transform.position = m_LastSimulatedPos.Value;

    return read;
}

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

    if (!m_NeedResync)
    {
        write += m_PackerSet.Pack(m_LastSimulatedPos.Key, stream);
        write += m_PackerSet.Pack(m_LastSimulatedPos.Value.ToVec3f(), stream);
    }

    return write;
}

[RPC]
private void RequestResync()
{
    m_NeedResync = true;
    CommunicationProxy.RPC("Resync", m_LastSimulatedPos.Value.ToVec3f());
}

[RPC]
private void FinishResync(float timestamp)
{
    m_LastSimulatedPos = new KeyValuePair<float, Vector3>(timestamp, m_LastSimulatedPos.Value);
    m_Direction = Vector3.zero;
    m_NeedResync = false;
}
```
サーバ側のコードを見たら既に気づいた方がいるかもしれませんが、今回のサーバはPart2のサーバのように50ms経過したら50msをかけてゆっくりとシミュレーションするではなく、一瞬でもらったタイムスタンプの最後までファーストフォワードです。
結果としてはサーバ側のキャラクターを表示すると瞬間移動に見えます。でも、サーバ側のキャラクター移動はそもそもデバッグのためで、ユーザに見えないだし、普通も非表示のままです。
つまり、スムーズに見せる必要はありません。むしろ、常に出来るだけ早く最新の情報がほしいです。

## 効果
では、効果を見ましょう！いつものように20fpsと5fpsバージョンを二つ用意しました。
説明：
 1. ”ローカル”は比較対象として用意したサーバと通信せずユーザの操作にすぐ反応するキャラクターです。緑のキューブで表示します。
 2. ”クライアント”は、まー、クライアントですね。ユーザの入力をサーバへ送信し、サーバの計算結果を表示するキャラクターです。青いキューブで表示します。
 3. ”サーバ”はサーバ側のキャラクター表示です。もちろん、これは単純に比較目的に表示しているだけで、普通は表示しないです。赤いキューブで表示します。
 4. 画面下部の矢印はユーザが押したボタンです。

1.ローカルVSクライアント（同期頻度：20 fps）

![local_client.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/c2f91ac5-8a99-bc74-3533-c58cae74ce3d.gif)

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

![local_server.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/c6b117c0-9b4d-3149-9f24-19db378a2d67.gif)

3.ローカルVSサーバVSクライアント（同期頻度：20 fps）

![local_server_client.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/c83ff0ed-be11-c69d-ef32-28bc15cea427.gif)

4.ローカルVSクライアント（同期頻度：5 fps）

![local_client.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/b201d0b0-8add-83bc-623d-d883ae0bb396.gif)

5.ローカルVSサーバ（同期頻度：5 fps）
 
![local_server.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/59240a08-3f37-8009-24d6-fe9d24f5ee99.gif)

6.ローカルVSサーバVSクライアント（同期頻度：5 fps）

![local_server_client.gif](https://qiita-image-store.s3.amazonaws.com/0/48530/5d7c0354-a7c6-3335-9b16-da42c8e44fe9.gif)

どうでしょう？クライアントの動きはたとえfpsが5しかないでも、スムーズさも反応の速さもローカルに負けないでしょう？
ユーザにとっては自分がシングルプレイヤーゲームのキャラクターを操作するような感じで、全くラグを感じられないはずです。

# 自分以外のクライアントの場合
今まで繰り返して話していたのは自分がコントロールしているキャラクターの動きだけですが、では他のクライアントのキャラクターはどうでしょう？同じくpredictionを応用出来ますか？
残念ながら、predictionの前提は最新のユーザ入力情報をフルで持つことです。この点はリモートクライアントにとっては流石に無理です。
無理やりスピードや移動痕跡などでpredictionをすると、アーティフィシャルが悪化する一方になりえます。
なので、普通の状況下、リモートクライアントのキャラクターを予測することを勧められません。全くしないか、超短い時間内にするかどちらです。
つまり、リモートクライアントはinterpolationをするしかありません。でも、Part2にも見せたように、シンプルなinterpolationでグダグダ感があり、納得出来ない場合もあります。
もちろん、アニメーションでそれを極力隠すことは出来ますが、でも、本当に更にスムーズに見せる方法がないでしょうか？
実はinterpolationの方法をちょっと改修すると、これは出来ない分けでもありません。
具体的な改修方法は、次の[Part4](http://qiita.com/y_li/items/52be823fa4a74592099f)で説明します。