如何呈现一个检测不同物体之间碰撞的算法？

Question

在一个只是为了好玩的项目中，我遇到了一些问题。

有一个由圆球、尖三角形和细线（还有其他野生动物）组成的二维世界。它们都是WorldCreatures的子类，可以在这个世界中移动。当它们相遇时，就会发生碰撞。

我想要做的事情是找到一种检测它们之间碰撞的方法。现在我的思路如下：

- 对于Ball-Ball，我只需计算它们位置之间的距离，并将其与它们“大小”的总和进行比较。 - Ball与世界边缘之间的碰撞也很简单，我只需检查它们之间的距离，在笛卡尔坐标系中很容易实现。 - 更一般的问题是如何检测线（从某些点开始和结束）或其他可能存在的对象之间的碰撞？线和点之间的距离也可以轻松计算，但我想要的是一种通用的方式来判断对象A是否与对象B发生碰撞。目前的代码看起来有些像这样：

class WorldCreature:
    def detectCollision(self, otherObject):
        # do something 
        if collision:
            self.onCollision(otherObject)
            otherObject.onCollision(self)
class Ball(WorldCreature):
    # someing here
class Line(WorldCreature):
    # someing here

现在，碰撞检测机制应该取决于哪些对象可以发生碰撞。效果也是如此。

我是否应该仅在内存中保留所有对象的列表，并在每一步中循环遍历它们？或者，有没有更好的方法来提高此任务的性能？

- kender

Answer 1

使用四叉树。它们用于消除你知道在碰撞半径之外的大区域，并且让你快速搜索最近的点。

就实际的碰撞检测而言，由于你只使用凸对象，请查看Metanet Software's tutorial关于分离轴定理的教程。在他们的旗舰游戏中，他们实际上使用网格来查找所有要检测碰撞的对象，但使用四叉树也不应该太难。

（我记得读过一篇关于四叉树的文章，其中使用圆形在网格中说明如何找到半径内的点。但我似乎找不到了。）

- Nikhil Chelliah

---

+1 for 四叉树。另一个问题是，您想检测实际碰撞还是只是交集。实际碰撞将要求您扫描您的形状。 - BigSandwich

Answer 2

Python。对我来说有点奇怪 8)

我有用c++创建游戏的经验，所以我从这个角度来谈论。

首先（如果你的对象数量较少，可以跳过此步骤），你需要广相撞检测。已经提到的四叉树只是一种可能的实现方式。广相撞检测用于查找可能发生碰撞的对象对。

然后进行狭窄相撞检测——检查对象对是否发生碰撞。

我使用了以下方案（请注意——这是针对基本图形的，如果你需要多面体碰撞——只需使用GJK和球体、加上射线、线段）：

所有需要碰撞的物体都有CollisionObject，它处理变换并存储CollisionPrimitive（盒子、球等）

每个CollisionPrimitive都有type_id——当你编写A_B_CheckIntersection时，第一个对象始终具有较低的type_id

对于从广相撞检测中获取的列表中的每个Pair，如果需要，你就交换对象，并索引一个数组，该数组存储特定碰撞函数的指针。当然，为此你应该让它们具有相同的接口（c++），但这很容易 8)

关于具体的碰撞例程：请访问http://realtimerendering.com/intersections.html，这是一个很好的起点。

- Alexey Orlov

Answer 3

这取决于一些因素，例如有多少对象，有多少是移动的与非移动的，它们移动的速度等等。我认为开始的正确位置应该是在忽略优化（如修剪碰撞检查）的情况下，确保核心的碰撞检测和行为代码的正确性。

一旦核心代码正确，您可以开始运行实验，看哪种方式对您的表现最好。我建议使用某种空间细分技术，例如kd树（虽然在2d中，您可能会使用四叉树）。

但从根本上说，除了通过编码游戏并进行实验来确定之外，可能没有单一的正确答案。

- zweiterlinde

Answer 4

我认为 Hough Transform 应该在某种程度上有所帮助。

- david makcenzie