Python、Pygame和碰撞检测效率

Question

我正在制作一个自定义精灵类（而不是pygame.Sprite）的上下左右滚动瓷砖游戏。

精灵碰撞（collide()）函数导致帧速率降低（我使用了cProfile进行测试）。

请帮助我找出问题所在。

该函数一般按以下方式运行：

def collide(self):
        for tile in tiles:
            if tile.type == 'wall':
                if self.getDist(tile.rect.center) < 250:
                    if self.rect.colliderect(tile.rect):
                        return True

1. 在精灵和所有墙砖之间找到距离向量很耗时间。
2. 我认为仅针对250像素内的瓷砖运行rect.colliderect()会更快，但显然不是这样。
3. 我不包括源代码，因为我正在寻求解决碰撞检测效率问题的更多概念性答案。

一个可能的解决方案是创建不同组瓷砖的分离列表（如wallList、groundList），但我真的相信我在搜索瓷砖对象列表方面存在根本性问题。

我是StackOverflow的新手，所以如果我的问题结构/缺乏源代码冒犯了您，请谅解。

- Frumples

---

在代码前添加4个空格以正确格式化。 - Cory Kramer

@Nabla 我看了一下，非常有帮助，谢谢你。 - Frumples

我猜墙砖只有O(1)（或O(n)，这取决于你所说的“墙”砖）, 而不是O(n^2)的普通砖。因此，仅循环遍历墙砖可能更有效率。 - EyalAr

@Frumples，你只需要检查瓦片交叉点，就可以知道精灵中心的瓦片。它只能与该瓦片或其邻居（第二个邻居等，取决于精灵大小）发生碰撞。碰撞检查应该可以在O(1)内完成。 - user3072164

@Nabla 那是个好主意。所以，我只需要检查右侧、左侧、前方和后方的瓦片索引吗？我也会尝试一下。谢谢。 - Frumples

Answer 1

为了避免检查地图中的每个瓦片以进行碰撞检测，我创建了一个函数来识别精灵当前所在的瓦片，并返回其周围的八个瓦片。瓦片扫描方法：

def scanTiles(self):
    m = curMap.map # this is a 2d matrix filled with tile-objects 
    x = int(self.trueX) # trueX & trueY allow me to implement
    y = int(self.trueY) # a 'camera system'
    curTile = m[y // T_SIZE[1]][x // T_SIZE[0]] 
    i = curTile.index # (x, y) coordinate of tile on map

    nw = None # northwest
    n = None # north
    ne = None # northeast
    e = None # east
    se = None # southeast
    s = None # south
    sw = None # southwest
    w = None # west

    # Each if-statement uses map indices
    # to identify adjacent tiles. Ex:
    # NW  N  NE
    # W  CUR  E
    # SW  S  SE

    if i[0] > 0 and i[1] > 0:
        nw = m[i[1]-1][i[0]-1]
    if i[1] > 0:
        n = m[i[1]-1][i[0]]
    if i[0] < len(m[0])-1 and i[1] > 0:
        ne = m[i[1]-1][i[0]+1]
    if i[0] < len(m[0])-1:
        e = m[i[1]][i[0]+1]
    if i[0] < len(m[0])-1 and i[1] < len(m)-1:
        se = m[i[1]+1][i[0]+1]
    if i[1] < len(m)-1:
        s = m[i[1]+1][i[0]]
    if i[1] < len(m)-1 and i[0] > 0:
        sw = m[i[1]+1][i[0]-1]
    if i[0] > 0:
        w = m[i[1]][i[0]-1]
    return [nw, n, ne, e, se, s, sw, w]

最后，在返回相邻图块列表后，碰撞函数会使用pygame.Rect.colliderects()检查每个图块是否与其他图块发生了碰撞。碰撞检测方法：

def collide(self, adjTiles): # adjTiles was returned from scanTiles()
    for tile in adjTiles:
        if tile:             # if a tile actually exists, it continues
            if tile.type == 'wall': # tile type can either be 'ground' or 'wall'
                if self.rect.colliderect(tile.rect1):
                    return True # if there is a collision, it returns 'True'

这种新方法证明更高效，目前已解决我的问题。

- Frumples