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)

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:

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.

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