c++ - QuadTree 用于 2D 碰撞检测

Question

我目前正在开发 2D 射击类型的游戏，并且我正在使用四叉树进行碰撞检测。我编写了一个工作四叉树，可以正确地将我的 Actor 插入它们在树中所属的节点/叶子中。但是，我遇到了一些问题。

首先，我如何实际使用我的四叉树来选择一个对象应该针对哪些其他对象测试碰撞？我不确定这是如何完成的。

这就引出了第二个问题。假设我在节点中有一个对象不是另一个节点的邻居，但是该对象足够大以至于它跨越了几个节点，我如何检查实际的碰撞，因为我猜测树可能认为它不是足够接近以与“远处”节点中的对象发生碰撞？不完全适合节点的对象是否应该保留在父节点中？

在我的游戏中，大多数物体大小不一，并且四处移动。

我已经阅读了大量关于四叉树的博客/文章，但大多数只是解释了如何构建一棵树，而这并不是我真正想要的。

欢迎任何帮助/信息。

Answer 1

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

然后，当您检查节点 A 的冲突时，您会这样进行:

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

请注意，对象越小，它们在四叉树中的位置就越深，因此比较少。