範囲内のものを探す

Question

私は最初のオンラインマルチプレイヤーゲームを構築しており、特定の範囲内のすべてのプレーヤーを見つける最良の方法を見つけようとしています。

私は周りを見回しました。他のすべての解決策は、距離探索機能を組み込んだゲームエンジンAPIに基づいています。

各プレイヤーは生のx,yの座標を持ちます。

私が考えた最初のことは、サーバー上のすべてのユーザーをループし、範囲内のユーザーをフィルタリングすることでした。単にPythagorasの定理を使用していました。しかし、もっと良い方法があるはずです。

私が考えている最も良いことは、約100（10 x 10）のセクションにマップを分割し、それに応じてセクションにユーザーを配置することです。私はその後、ユーザーがいるセクションを取得し、サーバー上のすべてのユーザーをループする代わりに、9つの四角形（3x3、ユーザーセクションおよびそれを囲むすべてのユーザー）のすべてのユーザーをループします。

これは、サーバー全体を1秒に1000回ループするよりも優れていると確信していますが、それを行う標準的な方法がありますか？

クライアント側とサーバー側の両方でliteを維持したいと考えています。

Answer 1

あなたが考えたのは、同じ象限でお互いが近くに集まっていない限り、プレイヤーごとに一定数の操作があるので、漸近的に最適です。配列にたくさんのメモリを割り当てるのを避けるために、x、yをx/distance、y/distanceにマッピングする（ハッシュセット/テーブル/ディクショナリ）とハッシュ関数を使うことができます。問題のプレーヤーの距離内のプレーヤーのエントリをチェックしてください。

This videoほぼ同形的な問題について話しています。ビデオでは、同じ場所にたくさんのサークルを持つことはできません。

より単純な最適化をお探しの場合は、最初に他のプレーヤーのxとyが問題のプレーヤーのxとyの範囲内にあるかどうかを確認してからxの差の二乗yはあなたがチェックしている距離の2乗より小さい。

このため、一部psudocodeは次のようになります。

distance = 100 
sections = {} 

# initial setup 
for player in players: 
    section_x = player.x/distance 
    section_y = player.y/distance 
    index = [section_x, section_y] 
    if !sections.get(index): 
     sections[index] = [] 
    sections[index].push(player) 

def players_near(player): 
    nearby_players = [] 
    section_x = player.x/distance 
    section_y = player.y/distance 
    for section_dx in -1..1: 
     for section_dy in -1..1: 
      index = [section_x + section_dx, section_y + section_dy] 
      players = sections[index] 
      if players: 
       nearby_players.extend(players) 

    result = [] 
    for nearby_player in nearby_players: 
     dx = abs(player.x - nearby_player.x) 
     dy = abs(player.y - nearby_player.y) 
     if dx <= distance and dy <= distance and sqr(dx) + sqr(dy) < sqr(distance): 
      result.push(nearby_player) 

    return result