查找半徑範圍內的對象

尋找一種輕量級的方法來查找半徑範圍內的對象。查找半徑範圍內的對象

到目前爲止，這是明顯，我的回答是要經過的每個對象，其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個目標。

來源

2009-10-14 SketchBookGames

在計算徑向距離之前，首先檢查物體是否位於以轉塔位置爲中心的方框內。如果target_x < turret_x範圍那麼它超出範圍並且不需要檢查距離，還要檢查turret_x +範圍，turret_y-range，turret_y +範圍。這需要最多4次比較和4次加/減操作來確定目標是否在框中。

來源

2009-10-14 22:07:04 progrmr

在2D，你可以實現一個四叉樹和3D，你可以實現一個八叉樹，這意味着你將能夠組對象，更有效地對他們的確切距離實際檢查之前將它們丟棄的大集團。如果你想知道更多，你應該爲他們谷歌。它們是世界對象非常有用的數據結構。

最終實施可能不會節省空間很多，但它會是令人難以置信的快，因爲你可以非常迅速地拋棄對象的廣大。

來源

2009-10-14 21:54:33

你可以存儲在鍵上，他們佔據了方格多集的可能目標。然後你只需要遍歷與網格正方形足夠接近的目標就可以成爲目標。

不管這是值得做的，取決於目標的數量和這很可能是withing範圍內目標的數量。我正在研究一個有數十萬個目標的應用程序，只有10或20個目標可能在範圍內。在這種情況下，投入大量的資金來修剪潛在的目標列表是值得的。在你的情況下，只有500個目標，這可能不值得。

來源

2009-10-14 22:03:57 ravenspoint

查找半徑範圍內的對象

回答

相關問題