查找半径范围内的对象

Question

寻找一个轻量级的方式的半径范围内找到的对象。

到目前为止是显而易见的我的回答是经过每个对象，其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个目标

Answer 1

在你计算径向距离，首先查看如果对象是集中在你的炮塔位置框内。如果target_x

Answer 2

在2D，你可以实现一个四叉树和3D，你可以实现一个八叉树，这意味着你将能够组对象，更有效地对他们的确切距离实际检查之前将它们丢弃的大集团。如果你想知道更多，你应该谷歌为他们。它们是非常有用的数据结构为对象的世界。

在最终实施可能不会节省空间很多，但它会是令人难以置信的快，因为你可以非常迅速地抛弃对象的广大。

Answer 3

您可以存储在键上，他们占据了方格多集的可能目标。然后你只需要遍历这是在足够接近炮塔的方格，他们可能是目标方格的目标。

不管这是值得做的，依赖于目标的数量和其很可能是withing范围目标的数目。我工作的应用程序中使用的几十万的目标，蒙山的只有10或20有可能是withinn范围。在这种情况下，它是值得投资的显著复杂修剪潜在目标名单。在你的情况下，只有500个目标很可能不值得。