树皮在球状树上还是在别的地方看？

Question

场景:大量玩家在3d空间中玩实时游戏，必须以一种服务器能够有效更新其他玩家和任何其他玩家的移动和动作的方式来组织。在模拟中，需要根据彼此之间的范围来选择对象之间的“对话”；这是为了保持网络的健全性、程序员的理智，以及允许服务器让处理整个世界游戏空间中的较小块。

但是，如果你有3000名玩家，这就会遇到一个人必须运行3000人的问题！计算找出每件事之间的范围。(谷歌告诉我，这个数字最终超过9000位数，这太疯狂了，不值得在一个近乎实时的环境中考虑。)

黎明游戏似乎已经解决了这个问题，他们的大型在线第一人称射击游戏“星球2”；它允许3000名玩家在一个共享的空间上玩，并具有实时响应能力。他们显然是通过“Sphere”数据结构来实现的。

但是，我不确定这是他们使用的解决方案，我仍然在质疑如何应用"Sphere树“的概念来将剔除范围的计算减少到一个合理的数量。

如果Sphere树不是适合树皮的树，那么我还应该关注什么来解决这个问题呢？

(我主要是一个c#程序员，但我正在寻找一个逻辑的答案，而不是代码的答案)

我发现了关于球状树的参考资料；

http://isg.cs.tcd.ie/spheretree/#algorithms

https://books.google.com/books?id=1-NfBElV97IC&pg=PA385&lpg=PA385#v=onepage&q&f=false

Answer 1

下面是我的一些想法:让n表示玩家的总数。

1. 我想你的估计是3000！是错的。如果您想要计算给定一个固定距离矩阵的所有对距离，则运行3000 Select2操作，按O(n^2*t)的顺序排列，其中t是计算两位玩家之间距离的操作数。如果你用欧几里得距离来构造玩家的下面的图，你可以把它简化为全对最短路径问题，这个问题可以通过O(n^3)中的Floyd算法来完成。
2. 您所描述的内容听起来非常类似于执行范围查询：searching。有很多数据结构可以帮助您，例如范围树和k-d树。

Answer 2

如果对象只需要与距离<= 100米的对象交互，那么您可以将世界划分为100 m×100 m瓷砖(或体素)，并跟踪每个非空瓷砖中的对象。

然后，当一个对象需要“交谈”时，您只需要检查最多9个瓷砖中的对象，以确定它们是否足够接近可以听到。