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

Question

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

要求非常简单.世界是2D,只包含矩形(任意大小).BSP甚至四叉树似乎都是过度杀戮(同样,重点在于简单性)但是我想要比通过所有n(n-1)/ 2个可能的碰撞强制执行更有效的东西.

2D,仅矩形,简单.

任何人都可以指出我可以查找的算法吗？是我正在寻找的四叉树算法吗？

编辑:此外,矩形永远不会旋转(我保持简单).为了让您了解我正在工作的规模,将在您使用Pygame在Python中实现的典型用户的笔记本电脑/台式机(不到5年)上运行几百个矩形.

Answer 1

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

四叉树可以用于您的目的,但请记住,当您处理非点时,您必须将矩形放在包含它相交的所有象限的节点中.然后,当测试低节点的东西时,你必须测试该节点及其所有祖先中的所有rects!

您可能还会考虑排序和扫描算法,因为您已经获得的是轴对齐的边界框.

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