1

半径内のオブジェクトを見つけるための軽量な方法を探しています。

これまでのところ、私にとって明らかな答えは、各オブジェクトを調べて、その x および y 位置を半径の中心と比較することです。

例：

Turret- 半径内のターゲットを探しています。

TargetArray- 可能なターゲットの配列。

WithinRangeArray- 該当するターゲットをプッシュする配列

Distance^2 = (TargetArray[n].x - Turret.x)^2  +  (TargetArray[n].y - Turret.y)^2

if( Distance^2 < maxRadius^2 ){
WithinRangeArray.push(TargetArray[n])
}

平方根を回避すると、処理能力がいくらか節約されます。しかし、より良い（より軽量な）他のアルゴリズム/理論/方法があるかもしれないと感じています。

TargetArray の理想的な長さ: 一度に 500 未満のターゲット。

4

3 に答える 3

3

半径距離を計算する前に、まずオブジェクトがタレット位置の中心にあるボックス内にあるかどうかを確認してください。target_x < turret_x-range の場合、範囲外であり、距離をチェックする必要はありません。また、turret_x+range、turret_y-range、turret_y+range もチェックしてください。これには、ターゲットがボックス内にあるかどうかを判断するために、最大 4 つの比較と 4 つの加算/減算操作が必要です。

于 2009-10-14T22:07:04.790 に答える
2

2D では Quadtree を実装でき、3D では Octree を実装できます。これは、オブジェクトをグループ化し、正確な距離を実際に確認する前に、オブジェクトの大きなグループをより効率的に破棄できることを意味します。詳細を知りたい場合は、Google で検索してください。これらは、オブジェクトの世界にとって非常に便利なデータ構造です。

最終的な実装ではスペースをあまり節約できないかもしれませんが、膨大な数のオブジェクトを非常に迅速に破棄できるため、信じられないほど高速になります。

于 2009-10-14T21:54:33.133 に答える
0

可能なターゲットを、それらが占めるグリッド スクエアをキーにしたマルチセットに格納できます。次に、ターゲットになる可能性があるタレットのグリッド スクエアに十分近いグリッド スクエアにあるターゲットを反復処理するだけで済みます。

これを行う価値があるかどうかは、ターゲットの数と範囲内にある可能性が高いターゲットの数によって異なります。私は数十万のターゲットを持つアプリケーションに取り組んでいますが、そのうちの 10 または 20 のみが範囲内にある可能性があります。このような状況では、潜在的なターゲット リストを削除するためにかなりの複雑さに投資する価値があります。あなたの場合、わずか 500 のターゲットでは、あまり価値がないかもしれません。

于 2009-10-14T22:03:57.800 に答える