您将以何种方式提出一种算法来检测不同对象之间的冲突？

Question

在开展一个真正有趣的项目时,我遇到了一些问题.

有一个2D世界,有圆球,尖角三角形和瘦线(也许还有其他野生动物).它们都是WorldCreatures的子类.他们可以进入这个世界.当他们相遇时,会发生碰撞.

我想做的是找到一种检测它们之间碰撞的方法.这就是我现在站在的地方:

• 对我来说Ball-Ball很简单,我只是计算它们与位置的距离,并将它与它们的"尺寸"之和进行比较.
• 球和世界边缘之间的碰撞也很简单 - 我只是检查它的距离,在笛卡尔坐标系中,它很简单.
• 更常见的问题是 - 如何检测Line(在某些点开始和结束)或其他可能存在的对象之间的冲突？线和点之间的距离也可以很容易地计算,但我想要的是

如果Object A与Object发生冲突,可以采用某种通用方式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

现在,碰撞检测机制应该取决于哪些物体可以碰撞.效果也会如此.

我应该只保留内存中所有对象的列表,并在每一步中循环遍历所有对象吗？或者,是否有更好的方法来改善此任务的性能？

Answer 1

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

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

(我记得在四面体上阅读一篇文章,在网格中使用圆圈来说明如何在半径范围内找到点.但我似乎无法找到它.)