2

I'm writing an asteroids clone in Pygame and I've tried a few different ways to detect collisions between 'asteroid' rectangles and 'projectile' rectangles (both of which inherit from Rect). I'd like to know which of them (or what other method of detecting collisions) will lead to the least amount of lag. Moreover, I'd like to know why they have the least lag (I tried looking at the source for the Rect class to see how collidelist, colliderect, and collidepoint worked, but it was compiled in bytecode or something of that nature, which I unfortunately don't know anything about). The asteroids and projectiles are in lists named 'asteroids' and 'projectiles' respectively.

I first tried iterating through my projectiles list and using pygame.rect.collidelist on the asteroids list to find collisions:

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)

Unfortunately, this is very laggy, probably because I'm checking all of the rectangles on the screen.

To minimize unnecessary checks, I tried defining a 10 by 10 grid using my screen WIDTH and HEIGHT, and both the projectile and asteroid classes have a method which sets their gridRect attribute to a tuple with the coordinates of the grid segment they are in. I then detect collisions with a nested for-each-in loop like this:

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)

This worked really well as long as there weren't more than 50 projectiles and asteroids, but if possible I'd like even better performance.

Finally, I tried creating an array, sorting the rects into it, and then detecting collisions:

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)

This was probably more laggy than the first one, but I thought that it should be the least laggy because although it's more complex, it minimizes the amount of calls to check if a Rect should colllide.

I know that the second method is the least laggy, but an explanation of why would be really helpful. Instead of the second method, I considered trying to only check asteroids within a certain distance of each projectile, but I can't see how I could do this in an efficient way, because for each projectile I would still have to check the distance of every asteroid.

I'm sure there must be a better way than these methods, so if you know of one please let me know. Also, if you need to see more of my code, let me know and I can edit it in. I think this is the minimum amount needed to get the idea though.

Nik3141
  • 123
  • 4
  • 1
    Is this run every frame? Making a copy of the projectiles list every frame is probably pretty slow – Iain Shelvington Jun 06 '20 at 00:01
  • @Iain Shelvington Yeah it's run every frame. I just assumed that making a copy wasn't going to be too resource-intensive because the slice notation makes it really easy. I used the copy so I could delete inside the loop; if I don't use it I'll need to make a list of objects to delete once the loop is finished, which in itself will require looping through. If I do that, will it be quicker than using the copy? – Nik3141 Jun 06 '20 at 00:10
  • 1
    I suspect it would perform better to have a list of objects to delete rather than copying, yeah. This list of objects to delete could be “global” that you only empty out when you delete something, that way you also wouldn’t have to initialise an empty list every frame – Iain Shelvington Jun 06 '20 at 00:15
  • Copying a list would be a thousand times more expensive than the collision calculations of a few hundred objects. A modest PC with pygame can can easily handle 1000 sprites without lag at 60FPS. – Kingsley Jun 06 '20 at 21:06

0 Answers0