我正在开发具有大量动态实体的 2D 游戏。为了好玩，我们称他们为士兵，假设他们有 50000 人（我只是随机想到的，可能或多或少 :)）。
所有这些士兵都在按照规则移动每一帧——想想机器人/植绒/转向行为。对于每个士兵，要更新它的运动，我需要最接近我正在处理的那个士兵的 X 个士兵。
存储它们以促进这样的计算而没有太多开销的最佳空间层次结构是什么？（所有实体每帧都会更新/移动，因此它必须很好地处理动态实体）
Pygmy
问问题
2333 次
3 回答
11
最简单的方法是使用网格。它有几个优点：
- 简单的
- 快速地
- 易于添加和删除对象
- 如果您仍在进行太多距离检查，则可以轻松将网格更改为更精细的细节
另外，请确保您不要为每次距离检查进行平方根。由于您只比较距离，因此您还可以比较距离的平方。
于 2009-08-13T12:49:30.257 回答
5
对于宽相位碰撞检测，像四叉树（因为它是二维的）或网格这样的空间索引就可以了。我之前链接到Metanet Software 的教程；它概述了一个基于网格的方案。当然，您的游戏甚至不需要如此广泛地使用网格。只需将每个actor存储在一个隐藏的网格中，然后将其与同一单元格和相邻单元格中的对象进行碰撞。
于 2009-08-13T12:50:18.903 回答
0
选择一个好的空间层次结构的重点是能够快速地只选择需要测试的对象。（一旦你发现了那个小子集，平方根可能不会再受到太大的伤害了）
我也对高动态对象的二维空间索引的最佳/最佳方法感兴趣。
Quadtree / kd-tree 看起来不错，但它们在动态插入方面不太好。KD树可能变得不平衡。
只是一个随机的想法，如果您的实体是点，那么结合二进制搜索的双插入排序结构（按 X 和 Y）可能会尝试..？
于 2009-08-13T13:50:03.607 回答