pygame中检测矩形列表之间冲突的最有效方法？

Question

我在Pygame中编写了一个小行星克隆，我尝试了几种不同的方法来检测“小行星”矩形和“投射物”矩形之间的碰撞（两者都继承自Rect）。我想知道它们中的哪一种（或其他检测碰撞的方法）将导致最小的延迟。此外，我想知道为什么它们的延迟最小（我试图查看Rect类的源代码，以了解collidelist、colliderect和collidepoint是如何工作的，但它是用字节码或类似性质的代码编译的，不幸的是，我对此一无所知）。小行星和射弹分别位于名为“小行星”和“射弹”的列表中

我首先尝试遍历我的投射物列表，并使用小行星列表上的pygame.rect.collidelist来查找碰撞：

index = 0
for projectile in projectiles[:]: #copy so I can delete from original
    index = projectile.collidelist(asteroids)
    if index != -1:
        del asteroids[index]
        projectiles.remove(projectile)

不幸的是，这是非常滞后的，可能是因为我正在检查屏幕上的所有矩形

为了减少不必要的检查，我尝试使用我的屏幕WIDTH和HEIGHT定义一个10乘10的网格，而抛射体类和小行星类都有一个方法，可以将它们的gridRect属性设置为一个元组，其中包含它们所在网格段的坐标。然后，我使用嵌套的for-each-in循环检测冲突，如下所示：

for projectile in projectiles[::-1]:
    for asteroid in asteroids[::-1]:
    if projectile.gridRect == asteroid.gridRect and projectile.colliderect(asteroid):
        projectiles.remove(projectile)
        asteroids.remove(asteroid)

只要弹丸和小行星不超过50颗，这种方法就非常有效，但如果可能的话，我希望性能更好

最后，我尝试创建一个数组，将矩形排序到其中，然后检测冲突：

gridRects = []
for i in range(GriddedRect.GRIDSIZE):
    gridRects.append([])
    for j in range(GriddedRect.GRIDSIZE):
        gridRects[i].append({"Projectiles": [], "Asteroids": []})

for asteroid in asteroids:
     gridRects[asteroid.gridRect[0]][asteroid.gridRect[1]]["Asteroids"].append(asteroid)
for projectile in projectiles:
     gridRects[projectile.gridRect[0]][projectile.gridRect[1]]["Projectiles"].append(projectile)


for i in range(GriddedRect.GRIDSIZE):
    for j in range(GriddedRect.GRIDSIZE):
        for projectile in gridRects[i][j]["Projectiles"][::-1]:
            index = projectile.collidelist(gridRects[i][j]["Asteroids"])
            if not index == -1:
                asteroids.remove(gridRects[i][j]["Asteroids"][index])
                del gridRects[i][j]["Asteroids"][index]
                projectiles.remove(projectile)
                gridRects[i][j]["Projectiles"].remove(projectile)

这可能比第一个更滞后，但我认为它应该是最不滞后的，因为尽管它更复杂，但它可以最小化检查Rect是否应该合并的调用量

我知道第二种方法的滞后性最小，但解释一下为什么会有帮助。 与第二种方法不同的是，我考虑只检查距离每颗抛射体一定距离内的小行星，但我不知道如何有效地进行检查，因为对于每颗抛射体，我仍然需要检查每颗小行星的距离

我相信一定有比这些方法更好的方法，所以如果你知道的话，请告诉我。另外，如果您需要查看更多我的代码，请告诉我，我可以在中编辑它。我认为这是获得这个想法所需的最低金额