QuadTree二维碰撞检测

Question

我目前正在开发一个2D射击游戏，使用四叉树进行碰撞检测。我编写了可以将演员正确推入树中所属的节点/叶子的四叉树。然而，我还有一些问题。

首先，如何使用我的四叉树选择其他对象以测试碰撞？我不确定该如何实现。

这带来了第二个问题。假设我有一个在节点中的物体，它不是另一个节点的邻居，但该物体足够大，跨越了几个节点，我该如何检测实际的碰撞，因为我猜树可能会认为它与“远离”的节点中的物体不够接近而无法发生碰撞？那些无法完全放入节点的物体应该保留在父节点中吗？

在我的游戏中，大多数物体都是不同大小的并且移动。

我已经阅读了很多关于四叉树的博客/文章，但大多数只是解释如何构建树，这并不是我要找的内容。

欢迎提供任何帮助和信息。

- dotminic

---

如果你正在制作的游戏确实像你链接的视频一样，那么你根本不应该使用空间索引。一个未排序的实体列表在几百个移动对象以下仍然可能更快。 - SingleNegationElimination

取决于碰撞方式，我认为对于基于圆形的碰撞可能是这样，但对于基于像素的碰撞可能不是这样。此外，在低数量的对象中，在实体的一维排序列表中查找邻居通常是最快的，如果我没记错的话。但是，实现一个可行的四叉树对于纯粹的经验来说是值得的。（而且，弹幕射击游戏可以轻松地拥有数百个移动对象 :)) - Kos

Answer 1

您可以制定惯例，即每个元素都包含在完全包含它的最小四叉树节点中。

然后，当您检查节点A的碰撞时，可以按照以下方式进行：

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

请注意，对象越小，它们就会位于四叉树中更深的位置，因此它们将比较不频繁。

- Kos

---

顺便提一下，这种只有叶子节点不包含元素的约定可能不是唯一存在的，只是我想到的第一个。你可能会遇到其他变体，它们采取不同的假设，因此需要不同的方法。 - Kos

那么基本上我需要为游戏中的每个对象重复这4个步骤，以测试它是否存在任何潜在的碰撞？ - dotminic

是的，在一般情况下是这样的。但是你可以同时拥有多棵树——例如，子弹不会与子弹碰撞，因此你甚至可以为子弹和敌人分别建立不同的树，并检查每个子弹与敌人树的碰撞等。检查你的逻辑并思考在这种情况下你实际上需要多少棵树 :) - Kos