2
  • 我有一个位置为 (x, y) 的对象集合
  • 这些物体随机移动
  • 可以有数千个

在任何时候，我都会从位置 POS 获得（恒定）半径 RAD 中的对象列表。

编辑 - 上下文：这是一个游戏服务器，它将（自然地）拥有数千名玩家。当玩家移动/[做出动作]时，我想将更新发送给半径内的其他玩家。

简单的方法，每次我需要列表时：

near_objects;
foreach( objects o ) {
    if( o.distance( POS ) < RAD )
        near_objects.add( o )
}

我想有更好/更快的方法，但我不知道要搜索什么。

4

3 回答 3

3

这里有两个建议。

通常您使用 sqrt( (ax-bx)^2 + (ay-by)^2 ) 计算距离，而昂贵的部分是计算 sqrt()，如果您在循环外计算 RAD^2 并将其与内部进行比较sqrt() 可以避免在循环中计算 sqrt()。

如果大部分物体都离得很远，你可以通过使用来消除它们

if( abs(a.x-b.x) > RAD ) continue;
if( abs(a.y-b.y) > RAD ) continue;
于 2013-07-01T12:22:27.793 回答
1

我认为这是针对某种 MMO 的——无法想象在任何其他情况下会有“数千名”玩家。所以你的问题实际上更复杂 - 你需要确定哪些玩家应该收到关于每个玩家的更新，所以它变成了 O(n^2) 问题，我们正在处理数百万个问题。首先要考虑的是你真的想只根据距离发送更新吗？您可以将您的世界划分为区域并为每个区域保留单独的玩家列表并仅检查这些列表，因此对于 m 个区域，我们有 O(m * (n/m)^2) = O(n^2/m ）。显然，您还希望向同一队伍中的玩家发送更新，并让区域过渡点附近的玩家相互了解（但确保该区域保持较小且对玩家没有吸引力，这样他们就不会只是站在那里）。还考虑到巨大的世界和相对较慢的玩家速度，您不必经常更新该信息。还要记住，内存/缓存的使用对性能非常重要，我指的是列表作为一个抽象术语——您应该在数组中以紧密的循环访问数据，但要确保元素不要太大。在这种情况下，考虑为那些密集循环创建一个包含基本玩家数据的简单类，并保留指向包含其他数据的更大类的指针。

总而言之-您的问题似乎很基本，但是您正在尝试构建MMO，这不仅在技术上很复杂，而且还需要大量工作。我相信，追求一个更小、不那么雄心勃勃的项目，你实际上能够完成会更有益。

于 2013-07-01T13:23:19.767 回答
0

您可以将对象放入有序的数据结构中，并按它们与 POS 的距离进行索引。这类似于优先级队列，但您不想一直推送/弹出项目。

每当对象移动到新位置时，您都必须更新对象的键。要迭代给定半径 RAD 内的项目，只要距离（键）小于 RAD，您只需迭代此有序数据结构的项目。

于 2013-07-01T12:16:16.083 回答