一个好的、简单的、只能检测2D矩形碰撞的算法是什么？

Question

我正在为年轻成年人设计一款碰撞检测游戏教程，因此我希望这个教程尽可能简单，以便更容易解释。

要求非常简单。世界是2D的，仅包含矩形（任意大小）。BSP甚至四叉树似乎过于复杂（再次强调，重点在于简洁），但我希望找到比暴力查询n(n-1)/2所有可能的碰撞更高效的算法。

2D、仅限矩形，简单明了。

有没有人可以指点一下我可以查阅的算法？四叉树算法是否符合我的要求？

编辑：此外，这些矩形将永远不会旋转（我保持它简单）。为了让您了解我正在处理的范围，将在使用Python和Pygame实现时，有数百个矩形运行在典型用户的笔记本电脑/台式机上（少于5年）。

- Alvin Smith

---

我们可以假设您只考虑与“坐标轴”对齐的矩形，无论它们是什么？ - erickson

是的，您可以假设矩形始终与坐标轴对齐。这些矩形永远不会旋转。 - Alvin Smith

Answer 1

根据我的经验，所有的广相撞检测算法都相对微妙且难以理解。鉴于矩形相撞测试非常便宜，我会使用n²算法来构建这个课程，然后作为额外材料，也许会介绍空间索引的概念。如果不到数百个矩形，我敢打赌愚蠢的方法已经足够快了。

四叉树对你的目的来说应该是可以的，但要记住，当处理非点时，您必须将矩形放在包含其所交叉的所有象限的节点中。然后，在测试低节点中的内容时，必须针对该节点及其所有祖先中的所有矩形进行测试！

您还可以考虑一种排序和扫描算法，因为您已经拥有轴对齐的边界框。

- Jonathan Feinberg

---

对于扩展对象来说， 包围体层次结构比四叉树更好的选择。 - Victor Liu

取决于应用程序。他可能每秒处理数万个矩形；在这一点上，开始考虑优化是有意义的。或者它是一个嵌入式应用程序，使用8位、1 MHz的处理器之类的东西。 - Carl Smotricz

我认为四叉树是最容易理解的。虽然它存在交叉问题，但并不可怕。事实上，你可以让学生自己“看到”这个问题。而且，四叉树非常容易通过图形化方式解释，这使它成为一个很好的教学工具。 - Alex Feinman

Answer 2

在早期尝试制作简单2D游戏时，一种简单的策略是通过维护按较长维度排序的列表来加快检测速度。碰撞阶段大致如下：

for i in 0..n
   j = i+1
   while rect[j].left < rect[i].right
       check for collision in y
       j=j+1
   endwhile 
endfor

- AShelly

Answer 3

这是一个简单的算法，可以在轴对齐矩形上加快速度。选择其中一个轴作为“排序轴”，本文中选择X轴作为排序轴。将每个矩形指定为两个节点，即“进入”节点和“退出”节点，这些节点位于排序轴上。进入节点必须始终在轴上具有低于退出节点的值。创建一个排序的列表，包含所有进入和退出点。遍历排序列表。在遇到每个“进入”节点时，将其添加到“已进入”矩形列表中，并针对“已进入”列表中的所有其他节点执行暴力碰撞检测。在遇到每个“退出”节点时，从“已进入”列表中删除它。然后，您可以通过对Y轴进行排序并在Y轴上设置“进入”和“退出”点来向读者演示练习。

- Kennet Belenky

---

是的，这就是我所说的“排序和扫描”。 - Jonathan Feinberg