python - 如何提高游戏物理的嵌套 for 循环的速度

Question

我正在用 python 制作一个游戏(特别是使用 pygame 来渲染)，在我的物理引擎中我遇到了 O(n^2) 问题。 在我的引擎对象中:

def step():

    for obj1 in self.objects:
        for obj2 in self.objects:
            if obj1.XY != obj2.XY: # You can't have the object bounce itself
                obj1,obj2 = Collision(obj1,obj2)

每次游戏循环运行时都会发生这些循环 当有 100 多个对象(总共 10000 次迭代)时，嵌套的 for 循环确实会降低 fps。 我想知道是否有一种更快的方法来迭代所有可能的组合并将函数应用于该对

Answer 1

解决这个问题的方法是使用更智能的数据结构，这样你的算法就不再是二次的。

一般情况下研究空间划分，特别是四叉树 ( https://en.wikipedia.org/wiki/Quadtree )(如果您正在执行 2D - 3D 等效项是八叉树: https://en.wikipedia.org/wiki/Octree )。