什么是一个很好的，简单的，二维的矩形，只有碰撞检测算法？ [英] What's a good, simple, 2D rectangles-only collision detection algorithm?

问题描述

我设计的碰撞检测的游戏教程为年轻的成年人，所以我想这是尽可能简单，以使其更容易解释。

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，只有矩形，和简单的

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岁）实施了Python和Pygame的运行的顺序。

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.

推荐答案

在我的经验中，所有broadphase碰撞检测算法是比较微妙，很难理解。鉴于矩形碰撞测试是多么便宜，我会用结构在n ^ 2算法的教训，那么作为的奖金的材料，可能引入空间索引的想法。凭借超过千矩形的少，我敢打赌是喑哑的方式是速度不够快。

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.

一个四叉树就可以了你的目的，但要记住，当你处理不点，你必须把矩形中包含所有相交的象限的一个节点。然后，测试的东西，是在一个较低的节点时，你要测试的该节点和它的所有祖先的所有的rects！

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.

这篇关于什么是一个很好的，简单的，二维的矩形，只有碰撞检测算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！