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 中，您可以实现四叉树，在 3D 中，您可以实现八叉树，这意味着您可以对对象进行分组并更有效地丢弃大量对象，然后再实际检查它们的确切距离。如果您想了解更多信息，您应该搜索他们。对于对象世界，它们是非常有用的数据结构。

最终的实现可能不会节省太多空间，但它会非常快，因为您可以非常快速地丢弃大量对象。

于 2009-10-14T21:54:33.133 回答
0

您可以将可能的目标存储在它们所占据的方格上的多重集中。然后，您只需要遍历距离炮塔网格正方形足够近的网格正方形中的目标，它们可能是目标。

这是否值得做，取决于目标的数量和可能在射程内的目标的数量。我正在开发一个具有数十万个目标的应用程序，其中只有 10 或 20 个可能在范围内。在这种情况下，值得投资于显着的复杂性来修剪潜在的目标列表。在您的情况下，只有 500 个目标可能不值得。

于 2009-10-14T22:03:57.800 回答