QuadTree用于2D碰撞检测

Question

我目前正在研究2D射击类型的游戏,我正在使用四叉树进行碰撞检测.我写了一个工作四元树,正确地将我的演员推入他们属于树的节点/叶子.但是,我遇到了一些问题.

首先,我如何实际使用我的四叉树来选择一个对象应该测试碰撞的其他对象？我不确定如何做到这一点.

这提出了第二个问题.假设我在节点中有一个不是另一个节点的邻居的对象,但是该对象足够大以至于跨越几个节点,我如何检查实际的冲突,因为我猜测树可能认为它不是足够接近与"远方"节点中的物体碰撞？是否应将完全适合节点的对象保留在父节点中？

在我的游戏中,大多数物体都有不同的尺寸和移动.

我已经阅读了大量关于四叉树的博客/文章,但大多数只是解释如何构建一棵不是我正在寻找的树.

欢迎任何帮助/信息.

Answer 1

您可以建立一个约定,即每个元素都包含在完全包含它的最小四叉树节点中.

然后,当您检查节点A的冲突时,您将按以下步骤操作:

1. 当前节点=根节点
2. 检查A与当前节点中每个元素的冲突
3. 如果A可以完全包含在当前节点的任何子节点中,则将当前节点设置为该子节点并再次转到2
4. 最后,以递归方式检查A与当前节点的子节点中的所有元素的冲突.

请注意,对象越小,它们在四叉树中的位置就越深,因此它们的比较频率会降低.