2
\$\begingroup\$

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)
\$\endgroup\$
7
  • \$\begingroup\$ 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): \$\endgroup\$ Sep 28, 2022 at 17:54
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – RootTwo
    Sep 28, 2022 at 18:56
  • \$\begingroup\$ @my_stack_exchange_account is that faster? If so thank you! \$\endgroup\$
    – coder
    Sep 28, 2022 at 22:45
  • 1
    \$\begingroup\$ I have posted some test code. Thanks for your advice everyone. :) \$\endgroup\$
    – coder
    Sep 29, 2022 at 0:48
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Mast
    Oct 1, 2022 at 12:05

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ For back-compatibility, replace tuple[int, int] with Tuple[int, int], importing that symbol from typing \$\endgroup\$
    – Reinderien
    Oct 2, 2022 at 21:58
  • \$\begingroup\$ sorry, it doesn't work properly, see here \$\endgroup\$
    – coder
    Oct 3, 2022 at 9:00
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Reinderien
    Oct 3, 2022 at 12:20
  • \$\begingroup\$ 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. \$\endgroup\$
    – coder
    Oct 3, 2022 at 21:15
1
\$\begingroup\$

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

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.