data-structures - 在 2D 环境中检测动态对象之间的碰撞

Question

假设我们在二维世界中有很多动态对象，例如角色、射弹、能量提升，这些都是您在游戏中常见的东西。他们都在动。我们想检测它们之间的碰撞。有什么好的方法吗？

我看过四叉树，但它似乎检测动态移动对象之间的碰撞，我必须每帧重新创建四叉树（因为对象每帧都会改变它们的位置）。这看起来像一个昂贵的操作。

除了四叉树之外，还有其他方法可以解决这个问题吗？有没有办法改进四叉树方法？也许在每一帧上重新创建树毕竟不是那么昂贵？

Answer 1

通常，您更新四叉树（而不是丢弃旧的四叉树并构建新的四叉树），这并不像您想象的那么昂贵：通常物体在每一帧中只移动一小段距离，因此大多数物体保持不变四叉树的节点，几乎没有变化。即使在最坏的情况下，每个项目都移动到一个主要边界并且必须移除并重新插入，成本也只有 O( n log n )。但是或多或少地，对所有项目的任何循环都会花费这么多，所以再循环一次并不是什么大不了的事。