サーバーがゲームクライアントに近くの他の目に見えるプレーヤーを効率的な方法で知らせる方法は？

Question

マルチプレイヤーフラッシュゲームに取り組んでいます。サーバーは、他のプレーヤーがプレーヤーの近くにいることを各クライアントに通知します。これを行うには、サーバーはどのクライアントが互いに近くにあるかを継続的に確認する必要があります。現時点では、一時的な解決策として次のものを使用しています。

private function checkVisibilities()
{
    foreach ($this->socketClients as $socketClient1)
    { //loop every socket client
        if (($socketClient1->loggedIn()) && ($socketClient1->inWorld()))
        { //if this client is logged in and in the world
            foreach ($this->socketClients as $cid2 => $socketClient2)
            { //loop every client for this client to see if they are near
                if ($socketClient1 != $socketClient2)
                { //if it is not the same client
                    if (($socketClient2->loggedIn()) && ($socketClient2->inWorld())
                    { //if this client is also logged in and also in the world
                        if ((abs($socketClient1->getCharX() - $socketClient2->getCharX()) + abs($socketClient1->getCharY() - $socketClient2->getCharY())) < Settings::$visibilities_range)
                        { //the clients are near each other
                            if (!$socketClient1->isVisible($cid2))
             { //not yet visible -> add
                                 $socketClient1->addVisible($cid2);
                            }
                        }
                        else
                        { //the clients are not near each other
                            if ($socketClient1->isVisible($cid2))
                            { //still visible -> remove
                                $socketClient1->removeVisible($cid2);
                            }
                        }
                    }
                    else
                    { //the client is not logged in
                        if ($socketClient1->isVisible($cid2))
                        { //still visible -> remove
                            $socketClient1->removeVisible($cid2);
                        }
                    }       
               }
         }
     }
}

正常に動作します。しかし、これまでのところ、私は一度に2人のプレイヤーとしかプレイしていません。この関数は、すべてのクライアントに対してすべてのクライアントをループしています。したがって、100人のプレーヤーでは、関数が実行されるたびに100 * 100 = 10.000ループになります。これはそれを行うための最良または最も効率的な方法ではないようです。

今、私の現在の設定について皆さんがどう思うか、これらの可視性を処理するより良い方法について何か提案がありますか。

更新：世界は無限であることを忘れていました。それは実際には「宇宙」です。マップはありません。また、2次元（2D）ゲームです。

事前に感謝します。

Answer 1

最も簡単な解決策は、次のように世界を均一なグリッドに分割することです：

_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |
_|____|____|____|_
 |    |    |    |

次に、交差するグリッドタイルにオブジェクトを挿入します。

_|____|____|____|_
 | @  |    |    |
_|____|____|____|_
 |    |d d |    |
_|____|____|____|_
 |    | d  |  d |
_|____|____|____|_
 |    |    |    |

近くのオブジェクトのクエリを実行するには、近くのセルだけを見る必要があります。たとえば、プレーヤーから1タイル内の誰（ @ ）を確認するには、マップ全体ではなく9タイルのみをチェックインする必要があります：

/|////|////|____|_
/|/@//|////|    |
/|////|////|____|_
/|////|d/d/|    |
/|////|////|____|_
 |    | d  |  d |
_|____|____|____|_
 |    |    |    |

ただし、世界によっては、この手法は非常に無駄が多い場合があります。空のセルがたくさんある可能性があります。これが問題になる場合は、より複雑な空間インデックスを実装できます。

>

Answer 2

最初に言いたいのは、コードが裏返しに見えることです。どのクライアントがログインしているのか、世界中にいるのかを確認するという面倒な作業を行わなければならない高レベルのゲームロジック機能があるのはなぜですか？そのネットワーク関連のものはすべて、ゲームロジックから削除する必要があります。これにより、より高いレベルで行われ、ゲーム内のロジックは、現在プレイ中のプレイヤーと世界のプレイヤーのみを処理する必要があります。これにより、単純な質問が残ります。これら2人のプレーヤーは互いに十分に近いのでしょうか。すでにお持ちのように、ここでは簡単な距離チェックで十分です。

次は、ループの量を減らすことです。距離は一般に可換プロパティであるため、AとBの間、BとAの間の距離を確認する必要はありません。これを行うには、最初のループがすべてのクライアントを通過するのに対して、2番目のループは反復するだけです。最初のクライアントの後に来るすべてのクライアント。これにより、必要な反復回数が半分になります。

あなたが述べているように、これを継続的に行う必要もありません。ゲームをスムーズに実行するのに十分な頻度で実行する必要があります。移動速度がそれほど速くない場合は、数秒ごとにこれを行うだけで十分に速くなります。

これでもまだ十分でない場合は、ianhが説明するような空間ハッシュシステムを使用すると、実行するクエリの数を減らすことができます。グリッドは最も簡単ですが、何らかのツリー構造（理想的には自己バランス）が別のオプションです。

Answer 3

クアッドツリーを使用して、プレーヤーの位置を表します。
このwiki記事はこちらです。
必要なだけスペース（プレーン）を分割するツリー内のスペース（ユーザー）にオブジェクトを保持します。 無限の問題に関しては-プログラミングでは何も実際には無限ではないので、ユーザーが渡せない境界線を定義します（非常に大きな数の座標であっても、ユーザーが到達するのに100年程度かかるものを使用します） 。