algorithm - 什么是一个好的、简单的、仅限二维矩形的碰撞检测算法？

Question

我正在为年轻人设计一个碰撞检测游戏教程，所以我希望它尽可能简单，以便于解释。

要求非常简单。世界是二维的，只包含矩形（任意大小）。BSP 甚至四叉树似乎都过大了（再次强调简单性），但我想要比暴力破解所有 n(n-1)/2 可能的冲突更有效的东西。

2D，仅矩形，简单。

谁能指出我可以查找的算法？我正在寻找四叉树算法吗？

编辑：此外，矩形永远不会旋转（我保持简单）。为了让您了解我的工作规模，您的典型用户的笔记本电脑/台式机（不到 5 年）上将运行数百个矩形，这些矩形是用 Python 和 Pygame 实现的。

score 8 · Accepted Answer

根据我的经验，所有宽相碰撞检测算法都相对微妙且难以理解。鉴于矩形碰撞测试是多么便宜，我将使用 n^2 算法来构建课程，然后作为奖励材料，可能会引入空间索引的概念。用不到数百个矩形，我敢打赌愚蠢的方式已经足够快了。

四叉树适合您的目的，但请记住，当您处理非点时，您必须将矩形放在包含它相交的所有象限的节点中。然后，在测试低节点中的某些内容时，您必须针对该节点及其所有祖先中的所有矩形进行测试！

您也可以考虑使用排序和扫描算法，因为您已经得到的是轴对齐的边界框。

score 7 · Accepted Answer

在简单 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

score 3 · Accepted Answer

这是一个简单的算法，可以稍微加快速度并适用于轴对齐的矩形。

选择其中一个轴作为“排序轴”。对于这个描述，我会说 X 轴是排序的。将每个矩形指定为两个节点，一个“进入”节点，一个在排序轴上的“退出”节点。输入节点在轴上的值必须始终低于输出节点。

创建所有进入和退出点的排序列表。

遍历排序列表。当您点击每个“输入”节点时，将其添加到“输入”矩形列表中，然后对“输入”列表中的所有其他节点进行暴力碰撞检测。当您点击每个“退出”节点时，将其从“输入”列表中删除。

然后，您可以引导读者完成一个练习，其中“进入”列表本身在 Y 轴上排序，“进入”和“退出”点在 Y 轴上。

3 回答 3