使用四叉树时,如何处理在四边形之间移动的对象？

Question

我正在尝试在我正在制作的游戏中使用四叉树进行碰撞检测,但我不确定如何处理可能在不同四边形之间移动的对象？

我能想到的唯一方法是每帧清除整个树,然后在那里添加所有内容,但这似乎可以获得cpu密集而且效率不高.你是否检查每一帧的每一个物体,看它是否已移出它当前四边形的界限,如果是,那么将它移除并读取它？这看起来似乎效率非常低,因为你每帧都要对每个移动物体进行碰撞检查.

此外,关于四边形但与在其中移动的对象无关,如何在同一个四边形中处理多个对象？我读过的关于它们的大多数网站都说你应该在一个四边形中只有一个,也许两个,如果你得到的更多,那么就把它们推到树上.如果你有一个像的情况下这样？你有三个圆圈,它们都在它们下方的水平边缘,所以它们不能再往下走了,但是有三个都在同一级别,人们说你不应该有.

Answer 1

我认为实现您的建议并不是特别低效：检查对象是否已移出其四叉树，如果是，则删除并重新添加它。任何从一帧移动到下一帧的对象都需要对其执行一些碰撞检测，当然吗？并且四叉树操作只有在移动四叉树时才会执行，并且在那里花费的 CPU 时间可能会被执行更精确的“对象 A 是否触摸对象 B？”的 CPU 时间所掩盖。计算。所以我不知道你能做得更好。

关于你的第二个问题：我不知道其他人如何实现四叉树，但我允许对象占据多个四叉树，正是出于你在图表中给出的原因（当对象跨越边界时）。因此，对象具有“当前四边形列表”而不是“当前四边形”。