2dの距離に基づいてJavaのハッシュマップから取得

Question

私はたくさんのユニットでアンドロイドで戦略ゲームを作っています。私は1つおきのオブジェクトの位置をチェックして、彼らは戦い始​​めなければならないほど十分に近いです。今2つのユニットは十分に接近している場合、私は判断することができる唯一の方法は、この方法である：

public boolean inProximity(float x2, float y2) { 
     return Math.sqrt((x2 - x) * (x2 - x) + (y2 - y) * (y2 - y)) <= proximityRadius; 
    } 

私はすべてのユニットを通じて倍のn乗量を反復することにしたくありません。私は位置を格納するためにTreeMapを見ていましたが、ユニットからの距離に基づいてキーを取得するにはどうしたらいいですか？

Answer 1

：

は見てみましょう。基本的には、2D空間を分割し、あなたのユースケースと思われる衝突検出を行うことができます。

http://en.wikipedia.org/wiki/Quadtree

ただ、Javaの四分木でGoogleを行うには、実装上のいくつかのヒットを生成します。私はそれらのいずれかを使用していないので、私は本当にそれらを保証することはできませんが、それはあなたに何かを与える必要があります。

Answer 2

1）まず第一に、平方根をとる必要はありません。数が増えるにつれて正方形と平方根の両方が増加するため、最適化が1つになります。

2）これは「一番近いペア」の問題として知られており、これを解決するための分割統治アルゴリズムがあります。あなたがここにデータ構造を再考し、四分木を見てみたいことがありますhttp://en.wikipedia.org/wiki/Closest_pair_of_points_problem