2D Game:为另一个实体找到x个最近实体的快速(Est)方法-大量实体，高度动态
我正在开发一款拥有大量动态实体的2D游戏。为了好玩，我们称他们为士兵，假设他们有50000人(我只是随机想到的，可能多得多，也可能少得多：)。
所有这些士兵都在按照规则移动每一帧--想想机器人/群集/转向行为。对于每个士兵，为了更新它的移动，我需要离我正在处理的X士兵最近的X士兵。
什么是存储它们的最佳空间层次结构，以便在没有太多开销的情况下简化这样的计算？(所有实体每帧都会更新/移动，因此它必须很好地处理动态实体)
回答 3
Stack Overflow用户
发布于 2009-08-13 12:49:30
最简单的方法是使用网格。它有几个优点：
- simple
- fast
- easy用于添加和删除对象
- 如果您仍在执行过多的距离检查
，则可以轻松地将网格更改为更精细的细节
此外，请确保您不会在每次距离检查时都执行squareroot。因为你只比较距离，所以你也可以比较距离的平方。
Stack Overflow用户
发布于 2009-08-13 12:50:19
对于宽相位碰撞检测，可以使用四叉树之类的spatial index (因为它是2D的)或网格。我以前链接过Metanet Software's tutorial；它概述了一个基于网格的方案。当然，您的游戏甚至不需要如此广泛地使用网格。只需将每个参与者存储在隐藏网格中，并将其与相同和相邻单元中的对象碰撞即可。
Stack Overflow用户
发布于 2009-08-13 13:50:04
选择一个好的空间层次结构的全部要点是能够快速选择需要测试的对象。(一旦你发现了这个小的子集，平方根可能就不会再有那么大的影响了)
我还感兴趣的是，对于高度动态对象的2d空间索引，最好/最优的方法是什么。
四叉树/ kd-tree看起来不错，但它们不太适合动态插入。KD树可能会变得不平衡。
这只是一个随机的想法，如果您的实体是点，那么双重插入排序结构(按X和Y排序)与二进制搜索相结合可能是值得尝试的。
https://stackoverflow.com/questions/1271734
复制相似问题
腾讯云开发者
