Python, Pygame, and collision detection efficiency

Question

I'm making a top-down side-scrolling tile game with a custom sprite class (not pygame.Sprite).

The sprite collide() function is causing the frame rate to drop (I used cProfile).

Please help me identify the problem.

The function operates in this general manner:

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. Finding the distance vector between sprites and all the wall tiles is time consuming
2. I thought running rect.colliderect() for only tiles within 250 pixels would be faster; but clearly it's not.
3. I'm not including the source code because I'm looking for more of a conceptual answer to my problem of collision detection inefficiency.

One possible solution would be to create separate lists for different groups of tiles (i.e. wallList, groundList), however, I really believe that there is a fundamental problem with how I'm searching through the list of tile objects.

I'm new to StackOverflow, so, sorry if my question structure/lack of source code offends you.

Answer 1

Instead of checking every tile in the map for collision detection, I created a function that identifies the sprite's current tile, and then returns its eight neighboring tiles. Tile Scan Method:

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]

Finally, after returning the adjacent-tile list, a collide function checks each tile for collision with pygame.Rect.colliderects(). Collision Detection Method:

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'

This new method has proved much more efficient and has solved my problem for now.