什么是好的、简单的、仅限 2D 矩形的碰撞检测算法?
我正在为年轻人设计一个碰撞检测游戏教程，所以我希望它尽可能简单以便于解释.
I'm designing a collision detection game tutorial for young adults, so I want this to be as simple as possible to make it easier to explain.
要求很简单.世界是二维的，只包含矩形(任意大小).BSP 甚至四叉树似乎有点矫枉过正(同样，重点是简单)但我想要比暴力破解所有 n(n-1)/2 次可能碰撞更有效的方法.
The requirements are very simple. The world is 2D and contains only rectangles (of arbitrary sizes). BSP and even quadtrees seems like it would be overkill (again, the emphasis is on simplicity) but I would like something more efficient than brute forcing through all n(n-1)/2 possible collisions.
二维，仅限矩形，简单.
2D, rectangles only, and simple.
谁能指出我可以查找的算法?我正在寻找四叉树算法吗?
Can anyone point to an algorithm I can look up? Is a quadtree algorithm what I'm looking for?
此外，矩形永远不会旋转(我保持简单).为了让您了解我的工作规模，在您的典型用户的笔记本电脑/台式机(不到 5 岁)上使用 Pygame 用 Python 实现的大约有几百个矩形.
Also, the rectangles will never be rotated (I'm keeping it simple). And to give you an idea of what scale I'm working at, there will be on the order of a few hundred rectangles running on your typical user's laptop/desktop (less than 5 years old) implemented in Python with Pygame.
根据我的经验，所有宽相碰撞检测算法都相对微妙且难以理解.鉴于矩形碰撞测试的成本有多低，我会使用 n^2 算法来构建课程，然后作为 bonus 材料，也许会介绍空间索引的想法.少于数百个矩形，我敢打赌愚蠢的方式足够快.
In my experience, all broadphase collision-detection algorithms are relatively subtle and hard to understand. Given how cheap rectangle-collision testing is, I'd structure the lesson using the n^2 algorithm, then as bonus material, maybe introduce the idea of spatial indexing. With fewer than hundreds of rectangles, I'll bet the dumb way is fast enough.
四叉树很适合您的目的，但请记住，当您处理非点时，您必须将矩形放在包含它相交的所有象限的节点中.然后，在测试低节点中的某些内容时，您必须针对该节点及其所有祖先中的所有矩形进行测试！
A quadtree would be fine for your purposes, but remember that when you're dealing with non-points, you have to put the rectangle in a node that contains all of the quadrants it intersects. Then, when testing something that's in a low node, you have to test against all the rects in that node and in all of its ancestors!
您也可以考虑排序和扫描算法，因为您已经得到了轴对齐的边界框.
You might also consider a sort and sweep algorithm, since what you've already got are axis-aligned bounding boxes.