2D游戏:快速(est)方式为另一个实体找到x最接近的实体 - 大量实体,高度动态

Question

我正在开发一款拥有大量动态实体的2D游戏.为了好玩,让我们称他们为士兵,让我们说有50000个(我只是随机想起来,它可能会更多或更少:)).

所有这些士兵都按照规则移动每一帧 - 想想boids/flocking/steering行为.对于每个士兵来说,为了更新它的运动,我需要最接近我正在处理的X士兵.

什么是最好的空间层次结构来存储它们以方便这样的计算而不需要太多的开销？(每帧都更新/移动所有实体,因此它必须非常好地处理动态实体)

Answer 1

最简单的方法是使用网格.它有几个优点:

• 简单
• 快速
• 易于添加和删除对象
• 如果您仍在进行太多距离检查,则可以轻松将网格更改为更精细的细节

此外,请确保您没有为每个距离检查做一个squareroot.由于您只是比较距离,因此您还可以比较距离的平方.

Answer 2

对于宽相位碰撞检测,像四叉树(因为它是2D)或网格的空间索引都可以.我之前已经链接到Metanet Software的教程 ; 它概述了基于网格的方案.当然,你的游戏甚至不需要如此广泛地使用网格.只需将每个actor存储在隐藏的网格中,并将其与相同和相邻单元格中的对象进行碰撞.