2D游戏：查找另一个实体最接近的x个实体的最快方法 - 大量实体，高度动态。

Question

9

我正在开发一个有大量动态实体的2D游戏。为了好玩，我们称它们为士兵，并假设有50000个（这只是我随机想出来的数字，可能更多或更少 :))。

所有这些士兵都按照规则每帧移动 - 可以考虑boids /群集/转向行为。为了更新每个士兵的移动，我需要找到距离我正在处理的士兵最近的X个士兵。

为了便于进行此类计算而不会产生太多开销，最好使用什么空间层次结构来存储它们？（所有实体都每帧更新/移动，因此必须很好地处理动态实体）

- Pygmy

这里有一个很好的算法，类似于Reinier的建议。 - Ran Halprin

这篇博客（http://blogs.msdn.com/devdev/）有一个很好的解决方案（以及其他一些好的文章）。 - BCS

请将以下与程序设计有关的内容从英语翻译成中文。仅返回翻译后的文本：不要解释其含义。别忘了通过选择最有用的答案来关闭问题。 - Toad

3个回答

5

对于广义相撞检测，像四叉树（因为它是2D的）或网格这样的空间索引就足够了。我之前链接过Metanet Software的教程，它概述了基于网格的方案。当然，您的游戏甚至不需要如此广泛地使用网格。只需将每个演员存储在隐藏的网格中，并将其与同一单元格及相邻单元格中的对象进行碰撞。

- Nikhil

四叉树可能不是最好的选择，因为对于每个移动对象，您都需要将其从树中删除并重新插入，这可能是一个昂贵的操作。或者您需要在每个帧重新构建整棵树。 - Toad

@reinier：我认为你需要进行一些测试，以确定更新四叉树的频率。您始终可以降低该速率并增加对象的半径以测试碰撞。诚然，快速移动的对象可能会飞出扩大的半径，但这些本来就是问题所在的对象。 - Nikhil

同样的论点适用于网格；^) - Toad

@reinier：那么，对四叉树的抱怨是什么呢？也许你是在说每次都必须删除和插入点，但是网格的删除和插入操作复杂度较低。这样说起来有道理。 - Nikhil

0

选择一个良好的空间层次结构的整个目的是能够快速选择只需进行测试的对象。（一旦你找到了这个小子集，平方根可能就不会再带来太多负担）

我对2D空间索引高动态对象的最佳/最优方法也很感兴趣。

四叉树/ kd树看起来不错，但它们在动态插入方面表现不太好。 KD树有可能失衡。

只是一个随机的想法，如果你的实体是点，那么一个通过X和Y进行双重插入排序的结构，再结合二分查找，可能值得一试..?

- Led

如果不需要，为什么要使用它呢？ - Toad

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Toad · Accepted Answer

最简单的方法是使用网格，它有以下几个优点：

此外，请确保不要在每个距离检查中都进行平方根运算。由于您只需要比较距离，因此也可以比较距离的平方。