Movement and collision function

Question

I just want this code optimized to the max and I don't mind knowing if the optimization is pretty much at the max already or if I am doing movement and collision wrong. My game is a 2d Minecraft style game so it will have a lot of other_rects. Hopefully my code is easy to read.

Code:

def move(rect, movement, other_rects): # move one axis at a time, returns moved rect and info on collisions
 collisions = [0, 0, 0, 0] # left, right, up, down
 if movement.x:
 rect.x += movement.x
 if movement.x < 0:
 for tile in [tile for tile in other_rects if rect.colliderect(tile)]:
 rect.left = tile.right
 collisions[0] = 1
 else:
 for tile in [tile for tile in other_rects if rect.colliderect(tile)]:
 rect.right = tile.left
 collisions[1] = 1
 if movement.y:
 rect.y += movement.y
 if movement.y < 0:
 for tile in [tile for tile in other_rects if rect.colliderect(tile)]:
 rect.top = tile.bottom
 collisions[2] = 1
 else:
 for tile in [tile for tile in other_rects if rect.colliderect(tile)]:
 rect.bottom = tile.top
 collisions[3] = 1
 return rect, collisions

Code for testing:

import pygame
import pygame.math
pygame.init()
pygame.display.set_caption('Physics')
screen = pygame.display.set_mode((500,500),0,32)
clock = pygame.time.Clock()
player = pygame.Rect(100,100,40,80)
tiles = [pygame.Rect(200,350,50,50),pygame.Rect(260,320,50,50)] # could be made bigger
speed = 5
def move(rect, movement, other_rects):
 ... # put move function here
while 1:
 movement = pygame.math.Vector2(0)
 for e in pygame.event.get():
 if e.type == pygame.QUIT:
 pygame.quit()
 exit()
 keys = pygame.key.get_pressed()
 if keys[pygame.K_a] and not keys[pygame.K_d]:
 movement.x -= speed
 if keys[pygame.K_d] and not keys[pygame.K_a]:
 movement.x += speed
 if keys[pygame.K_w] and not keys[pygame.K_s]:
 movement.y -= speed
 if keys[pygame.K_s] and not keys[pygame.K_w]:
 movement.y += speed
 player = move(player,movement,tiles)[0]
 screen.fill((0,0,0))
 pygame.draw.rect(screen,(255,255,255),player)
 for tile in tiles:
 pygame.draw.rect(screen,(255,0,0),tile)
 pygame.display.update()
 clock.tick(60)

• my_stack_exchange_account: Since you're filtering values based on what's returned when you pass them to a function, you could use filter instead of list comps: for tile in filter(rect.colliderect, other_rects):
• RootTwo: It looks like the branches of the if movement.x < 0: statement are reversed. The way all the for tile... loops are coded, the rect sides are set based on the last colliding tile, rather than the closest tile in that direction.
• coder: @my_stack_exchange_account is that faster? If so thank you!
• coder: I have posted some test code. Thanks for your advice everyone. :)
• Mast: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .

Answer 1

First understand that your collision algorithm isn't correct. This is evident by either making the player travel speed higher or making the object coordinates closer; you can quite easily end up with a situation like this:

overlap

That's because you assign the collided edge unconditionally. There is no one correct algorithm; you could:

• Stop the player along their vector of travel at the first collided object, which would work but would not allow for "glancing blows" redirecting diagonal to horizontal/vertical travel
• Undo the minimum amount of travel in each axis necessary to de-collide all objects; this does allow for "glancing blows" and is what I demonstrate below

A first pass that un-breaks this, and makes better use of collidelistall, looks like:

from typing import Sequence
from pygame import Vector2, Rect
import pygame
SPEED = 5
def manhattan(vector: tuple[int, int]) -> int:
 x, y = vector
 return abs(x) + abs(y)
def move(player: Rect, movement: Vector2, others: Sequence[Rect]) -> Rect:
 if not movement: # truthy means any nonzero dimension
 return player
 player = Rect(
 player.left + movement.x, player.top + movement.y,
 player.width, player.height,
 )
 
 for i in player.collidelistall(others):
 tile = others[i]
 # There are four directions, each with its own distance, to de-collide the player.
 deltas = (
 (min(0, tile.left - player.right), 0),
 (max(0, tile.right - player.left), 0),
 (0, min(0, tile.top - player.bottom)),
 (0, max(0, tile.bottom - player.top)),
 )
 # Choose the direction with the lowest necessary Manhattan norm.
 dx, dy = min(deltas, key=manhattan)
 player.left += dx
 player.top += dy
 return player
def get_movement() -> Vector2:
 keys = pygame.key.get_pressed()
 x = 0
 if keys[pygame.K_a]:
 x -= SPEED
 if keys[pygame.K_d]:
 x += SPEED
 y = 0
 if keys[pygame.K_w]:
 y -= SPEED
 if keys[pygame.K_s]:
 y += SPEED
 return pygame.math.Vector2(x, y)
def main() -> None:
 pygame.init()
 try:
 pygame.display.set_caption('Physics')
 screen = pygame.display.set_mode((500, 500), 0, 32)
 clock = pygame.time.Clock()
 player = Rect(100, 100, 40, 80)
 tiles = (Rect(200, 350, 50, 50), Rect(260, 346, 50, 50)) # could be made bigger
 while not any(e.type == pygame.QUIT for e in pygame.event.get()):
 movement = get_movement()
 player = move(player, movement, tiles)
 screen.fill((0, 0, 0))
 pygame.draw.rect(screen, (255, 255, 255), player)
 for tile in tiles:
 pygame.draw.rect(screen, (255, 0, 0), tile)
 pygame.display.update()
 clock.tick(60)
 finally:
 pygame.quit()
if __name__ == '__main__':
 main()

For small object lists this will be enough. For a huge object collection this will still be inefficient and you need to use a spatial indexing data structure like a quadtree. There is no built-in support for this in pygame, but there are examples floating around on the internet.

• Reinderien: For back-compatibility, replace tuple[int, int] with Tuple[int, int], importing that symbol from typing
• coder: sorry, it doesn't work properly, see here
• Reinderien: I cannot reproduce the behaviour you see, and in the end you own this code, not me. You're going to need to debug it.
• coder: The rects are in this pos tiles = (Rect(200, 350, 50, 50), Rect(280, 330, 50, 50)) then try enter in the top. I am going to post my own answer, sorry. Thanks for all your help, I am going to use some of your tricks like collidelistall, max and min.

Answer 2

Thanks everyone who has helped me (in the end it was mainly @Reinderien). Taking bits and pieces of advice I have put together an optimized (most likely not fully) 'movement and collision function'.

Reveiwed code

import pygame
import pygame.math
pygame.init()
pygame.display.set_caption('Physics')
screen = pygame.display.set_mode((500,500),0,32)
clock = pygame.time.Clock()
player = pygame.Rect(100,100,40,80)
tiles = [pygame.Rect(200,350,50,50),pygame.Rect(260,320,50,50)]
speed = 5
def move(rect, movement, other_rects): # move one axis at a time, returns info on collisions
 collisions = [0, 0, 0, 0] # left, right, up, down
 if movement.x:
 rect.x += movement.x
 collided_with = [other_rects[i] for i in rect.collidelistall(other_rects)]
 if collided_with:
 if movement.x < 0:
 rect.left = max(tile.right for tile in collided_with)
 collisions[0] = 1
 else:
 rect.right = min(tile.left for tile in collided_with)
 collisions[1] = 1
 if movement.y:
 rect.y += movement.y
 collided_with = [other_rects[i] for i in rect.collidelistall(other_rects)]
 if collided_with:
 if movement.y < 0:
 rect.top = max(tile.bottom for tile in collided_with)
 collisions[2] = 1
 else:
 rect.bottom = min(tile.top for tile in collided_with)
 collisions[3] = 1
 return collisions
while 1:
 movement = pygame.math.Vector2(0)
 for e in pygame.event.get():
 if e.type == pygame.QUIT:
 pygame.quit()
 exit()
 keys = pygame.key.get_pressed()
 if keys[pygame.K_a] and not keys[pygame.K_d]:
 movement.x -= speed
 if keys[pygame.K_d] and not keys[pygame.K_a]:
 movement.x += speed
 if keys[pygame.K_w] and not keys[pygame.K_s]:
 movement.y -= speed
 if keys[pygame.K_s] and not keys[pygame.K_w]:
 movement.y += speed
 move(player,movement,tiles)
 screen.fill((0,0,0))
 pygame.draw.rect(screen,(255,255,255),player)
 for tile in tiles:
 pygame.draw.rect(screen,(255,0,0),tile)
 pygame.display.update()
 clock.tick(60)

Optimizations

1 - Used collidelistall instead of colliderect, avoids checking for each individual rect. @Reinderien

2 - Used min and max functions to correctly uncollide, also avoids looping through the list of collisions. @Reinderien

3 - Removed the rect from return rect, collisions as the function is already modifying the rect. @Reinderien