我正在为年轻人设计一个碰撞检测游戏教程，所以我希望它尽可能简单，以便更容易解释。
要求非常简单。世界是二维的，仅包含矩形（任意大小）。 BSP 甚至四叉树似乎有点矫枉过正（再次强调简单性），但我想要比暴力破解所有 n(n-1)/2 可能的碰撞更有效的方法。
2D，只有矩形，而且很简单。
谁能指出我可以查找的算法吗？我正在寻找四叉树算法吗？
编辑：此外，矩形永远不会旋转（我保持简单）。为了让您了解我正在工作的规模，在您的典型用户的笔记本电脑/台式机（不到 5 年）上将运行大约几百个矩形，这些矩形是通过 Python 和 Pygame 实现的。
根据我的经验，所有宽相碰撞检测算法都相对微妙且难以理解。考虑到矩形碰撞测试的成本有多低，我将使用 n^2 算法来构建课程，然后如下bonus材料，也许引入空间索引的想法。由于矩形数量少于数百个，我敢打赌这种愚蠢的方式足够快。
四叉树适合您的目的，但请记住，当您处理非点时，您必须将矩形放入包含其相交的所有象限的节点中。然后，当测试低节点中的某些内容时，您必须针对该节点及其所有祖先中的所有矩形进行测试！
您还可以考虑排序和扫描算法，因为您已经拥有的是轴对齐的边界框。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
