負荷・帯域を減らす超基本

　MMOでは多くのユーザーが同時に接続するわけで、 なんにも考えずにシステムを作ると、 計算量もネットワーク帯域も、ものすごいことになってしまいます。
　例えば1000人が同時接続していたとすると、1000×1000の処理が発生する可能性がありますが、 コレは全力で避ける必要があります。
　このような処理が必要な部分としては、例えば当たり判定などがありますね。 また、ネットゲームですから、あるキャラの行動を他のキャラに伝える必要があります。
　さらに、例えばMMORPGを考えると、 同時接続数が1000人だとモンスターの数はその数倍必要になるかもしれません。 そうなるとさらにえらいことになります。

　上記のようなN^2の処理を避けるための基本は、 影響する可能性がある部分のみのリストを作って管理するということです。
　例えば広いマップの右上の方にいるキャラがあったとして、 マップの左下の方にいるキャラはクライアントの画面には互いに映りませんし、 影響を与えることもないわけです。(この場合は、影響を与える≒視界内にいる) なので近くにいるキャラのみのリストを作って、 当たり判定などはそのリスト内で行えばよいわけです。
　右図を見てください。キャラＡの視界にはB,C,Dしか入っていません。 なので、キャラＡに「影響するリスト」というのを作ってB,C,Dを格納します。
　当たり判定やら(通常)チャットやら大部分の処理はこのリスト内のみを対象にしてもＯＫでしょう。

　上記の例だと、位置情報を元にしたリストなわけですが、 その他にもギルドなど、リストは色々必要になるかもしれません。

　リストの格納方法は線形リストや二分木、 最大数が決まってるならスタティックに確保、など、 色々考えられますが、更新頻度やリストの長さなどを考慮して決めてください。
　リストの内容は相手へのポインタ等になるでしょう。

　さきほどの図の例だと「視界の中／外」と曖昧に言いましたが、 具体的にはどのようにすれば良いが考えてみます。
　一番基本的なものは、互いの距離で判別するものでしょう。 距離が一定未満かそれ以上か、のような物です。
　「視界」はクライアントの描画上の視界と完全に一致しているとは限りません。 クライアントの視界より大きければ十分ですし、 クライアントが3Dなどで非常に遠くまで視界がある場合には、 あまり大きく視界をとるとパフォーマンスに影響するので、 もっと小さくして、ある程度の距離でポップするようにする必要があるでしょう。

　ここで問題になるのは、視界に入った時に通信等のコストがかかる、ということです。 (出る時にも多少かかったりする)
　視界に入った時点で、互いのクライアントに対して相手の情報を送る必要がでてきます。 MMORPGなんかだと、名前とか装備などの見た目とか、そーいう情報ですね。
　視界の境界付近でどちらも同じ方向に進んだ時などに、 非常に頻繁に視界に出たり入ったりしてしまう可能性がでてきます。
　それはマズイのでなんらかの対策が必要になります。
　一つの対策方法は「視界に入る時と出る時で境界までの長さを変える」という方法です。 例えば、20m以内だと視界に入る、25m以上だと視界から出る、てな具合です。 これで、非常に頻繁に視界に出入りすることを防ぐことができます。 (蛇足ですが、電子回路でいうシュミットトリガと同じですね)

　ところで、上記の例ですと、境界として円形を例にしましたが、 この部分はゲームのシステムによって最適なものを選択します。 矩形が最適な場合もあるでしょう。 3Dなら球体や立方体や円筒形になるかもしれません。
　他の例としてもう一つあげてみます。 これはダンジョンなどのように部屋に分かれている場合に有効かも。
　例として上からみた時に右図のようになってる部屋を考えます。 このとき、Ａの部屋のどこにいたとしてもＢの部屋のどの部分も見えません。 Ｂの部屋からもＡの部屋は見えません。Ａ<->ＣとＢ<->Ｃは見えます。
　なので、もし、キャラがＡの部屋にいたとしたら、 影響範囲はＡとＣに限定されＢにいるキャラは視界の外となります。 　Ａ・Ｂ・Ｃの各部屋ごとに、「その部屋にいるキャラのリスト」を保持するようにします。
また、各部屋からどの部屋が見えるか、という情報は計算が少々複雑ですが、 ゲーム中に変化することはありませんので、前もって計算しておけばよいでしょう。
　 　ちなみにmmo!では円形の距離ベースの視界と、 部屋のようなブロック単位の視界の制限、 両方使用していました。

　以上N^2の処理を避ける方法を話したわけですが、 察しのいい方は、「それじゃあリストの作成・更新はどうするの？N^2になるんじゃないの？」 と思うかもしれません。その通りなのです。
　視界から出て行くキャラのチェックについては、リスト内のみチェックをすればよいのですが、 入ってくるキャラについては、視界の外のキャラ、つまり大多数のキャラになってしまいます。

　対策その１は、非常に単純な方法です。
　視界に入るタイミングはそんなに正確でなくても良いのです。 一応20mに境界を設定してたとしても、18mくらいでポップしても、ゲーム的には問題が発生しません。 問題が発生するなら、ちょっと境界を遠くに設定すればいいだけのことです。
　なので、毎フレームごとに確実にチェックする必要はないです。 数秒程度かけてゆっくりチェックするなら負荷はあんまりないと思います。
　また、移動しているキャラのみチェックすれば良い、というのもあります。 相手の方から近寄ってくることもありますが、その時は相手が自分を見つけてくれます。
　移動速度から、サボれる時間を計算する方法もあります。 例えば、ある時に視界の外をチェックして、一番近いキャラが境界からさらに20m先だったとします。 キャラの最大移動速度が1m/secだったとすると、出会うのは最短でも10秒後になります。 なので、この場合だと10秒間はチェックしなくてもよい、とわかります。

　対策その２はもうちょっとまとも(？)に高速化を考えます。
　まず、マップを大まかに分割します。 そして、その大まかなブロックごとに、どのキャラが入っているかを保持しておきます。 で、右図において、赤丸のトコに自分がいるとすると、 境界の中に入るキャラは必ず、周囲のブロックに属しているハズです。 なので、全てのキャラについてチエックしないで、周囲のブロックにいるキャラのみ調べればＯＫです。
　また、前述の部屋によって分ける方法は、結果的にこの方法の応用みたいな感じなので、 全探索する必要は無いです。