How to get better performance with pygame?

Question

I'm not a gamedev, I'm a API/Cloud dev, performance has never been an issue for me since most of the time we are limited by network calls.

I've been playing with that for the past 2 days, I wanted to make particles that follow each others but to my surprise, even with a R9 5950x, I can't simulate more than 60 particles

After that it behaves weirdly, a lot less particles are showed, or the screen just becomes black.

I think the most "cpu hungry" thing is sensing where the closest particle is. For that each "agent" need to iterate over every other agent and check if the position of that agent is in its field of view (a triangle attached to the "head" of the agent)

mains.py :

import pygame
import time
import math
import random

import numpy as np

from drawer import draw_polygon_alpha
from models import Point, Color, DirectionVector2C, Vector2D, Triangle

width, height = 800, 600

class CarLikeAgent:
    """
    Car like : direction is always going forward, so when the rotation is changed the direction vector need to be recomputed
    initialize it with direction vector going to the top of the window (up) then apply initial rotation
    """

    def __init__(self, id, position: Point, rotation: float, velocity: float, mass: float, color: Color):

        self.id = id

        initial_direction_vector: DirectionVector2C = DirectionVector2C(0, -1) # going up
        initial_direction_vector.rotate(rotation)
        self.direction_vector: DirectionVector2C = initial_direction_vector

        self.position: Point = position
        # should I make velocity a vector that has different values for x and y ?
        self.velocity: float = velocity
        self.mass: float = mass
        self.color: Color = color
        self.rotation: float = rotation
        self.remaining_turn_angle: float = 0
        self.max_angle_per_frame: float = 1/self.velocity
        self.max_angle_per_frame: float = 5
        # second point is the summit, or point that is attached to the head
        self.field_of_view_triangle = None
        self._head_location = None
        self._body_radius = 3
        self._head_radius = 3
        self._last_positions = []
        self._display_fov = False

    def draw_yourself(self, screen):
        # drwaing the trail
        current_color = np.array(self.color.get_tuple())
        current_radius = radius=self._body_radius
        for nparray_point in reversed(self._last_positions):
            current_color = current_color / 1.1
            current_radius = current_radius/1.05
            pygame.draw.circle(surface=screen, color=current_color, center=nparray_point, radius=current_radius, width=5)

        # drawing the agent
        pygame.draw.circle(surface=screen, color=self.color.get_tuple(), center=self.position.get_tuple(), radius=self._body_radius, width=5)
        #pygame.draw.circle(surface=screen, color=self.color.get_tuple(), center=self._head_location.get_tuple(), radius=self._head_radius, width=3)
        if self._display_fov:
            draw_polygon_alpha(screen, (0, 0, 255, 80), self.field_of_view_triangle.get_tuple())

    def update_fov(self):
        """
        Make a triangle that groe from the "head" and then follow the direction vector, it "sees" what is inside the triangle
        """

        fov_distance = 300
        fov_wideness = 500

        a = np.array(self._head_location.get_tuple())  # "summit" of the triangle, point attached to the "head"
        b = np.array(self._head_location.get_tuple()) + (-fov_wideness / 2, fov_distance)
        c = np.array(self._head_location.get_tuple()) + (fov_wideness / 2, fov_distance)

        pivot = a
        triangle = (a, b, c)
        angle_degrees = self.rotation + 180 # why 180? i don't know
        angle_radians = math.radians(angle_degrees)
        rotation_matrix = [
            [math.cos(angle_radians), -math.sin(angle_radians)],
            [math.sin(angle_radians), math.cos(angle_radians)]
        ]
        # Translate the triangle so that the pivot point is at the origin
        translated_triangle = [(vertex[0] - pivot[0], vertex[1] - pivot[1]) for vertex in triangle]

        # Rotate the translated triangle using the rotation matrix
        rotated_triangle = [(rotation_matrix[0][0] * vertex[0] + rotation_matrix[0][1] * vertex[1],
                             rotation_matrix[1][0] * vertex[0] + rotation_matrix[1][1] * vertex[1])
                            for vertex in translated_triangle]

        # Translate the rotated triangle back to its original position
        final_triangle = [(vertex[0] + pivot[0], vertex[1] + pivot[1]) for vertex in rotated_triangle]
        self.field_of_view_triangle = Triangle(
            Point(final_triangle[0][0], final_triangle[0][1]),
            Point(final_triangle[1][0], final_triangle[1][1]),
            Point(final_triangle[2][0], final_triangle[2][1]),
        )

    def _add_position_to_last_positions_history(self, current_position: np.ndarray):
        if len(self._last_positions) > 15:
            self._last_positions = self._last_positions[1:]
        self._last_positions.append(current_position)

    def update_position(self, velocity_coefficient):

        def compute_point_on_circle_coords(center, radius, angle_degrees):
            angle_radians = math.radians(angle_degrees)
            x = center.x + radius * math.cos(angle_radians)
            y = center.y + radius * math.sin(angle_radians)
            return Vector2D(x, y)

        new_x = (self.position.x + self.direction_vector.x*(self.velocity * velocity_coefficient))

        if new_x > width:
            new_x = new_x - width
        if new_x < 0:
            new_x = new_x + width

        new_y = (self.position.y + self.direction_vector.y*(self.velocity * velocity_coefficient))

        if new_y > height:
            new_y = new_y - height
        if new_y < 0:
            new_y = new_y + height

        magic = 270
        self._head_location = compute_point_on_circle_coords(self.position, self._body_radius, self.rotation + magic)
        self.position = Point(new_x, new_y)
        self._add_position_to_last_positions_history(np.array([new_x, new_y]))

    def update_rotation(self, wanted_angle_in_degree):
        if wanted_angle_in_degree > 360 or wanted_angle_in_degree < -360:
            raise ValueError("Are you serious?")

        # we turn the amount we couldn't turn last frame due to the mass of the agent
        if wanted_angle_in_degree == 0 and self.remaining_turn_angle is not None:
            wanted_angle_in_degree = self.remaining_turn_angle

        if wanted_angle_in_degree < 0:
            sign = -1
        else:
            sign = 1

        turn_angle = 0
        if abs(wanted_angle_in_degree) > self.max_angle_per_frame:
            turn_angle = self.max_angle_per_frame * sign
            self.remaining_turn_angle = (abs(wanted_angle_in_degree) - self.max_angle_per_frame) * sign
        else:
            turn_angle = wanted_angle_in_degree

        self.direction_vector.rotate(turn_angle)
        self.rotation = self.rotation + turn_angle

        if self.rotation > 360:
            self.rotation = self.rotation - 360
        elif self.rotation < -360:
            self.rotation = self.rotation + 360


    def compute_distance_with_point(self, point: Point):
        point1 = self.position.get_tuple()
        point2 = point.get_tuple()
        return math.sqrt((point2[0] - point1[0]) ** 2 + (point2[1] - point1[1]) ** 2)

    def update_remaining_angle_for_closest_visible_agent(self, agents):
        selected_agent = None
        shortest_distance = 999999999999999
        for other_agent in agents:
            if other_agent == self:
                continue

            if self.field_of_view_triangle.is_point_inside(other_agent.position):
                distance = self.compute_distance_with_point(other_agent.position)
                if distance < shortest_distance:
                    shortest_distance = distance
                    selected_agent = other_agent

        if selected_agent is None:
            return

        dx = self.direction_vector.x
        dy = self.direction_vector.y
        # to compute that wee need to translate the absolute coordinate in coordinate with a new center, the base of the direction vector
        x = selected_agent.position.x - self.position.x
        y = selected_agent.position.y - self.position.y
        angle_deg = math.degrees(math.atan2(y, x) - math.atan2(dy, dx))
        self.remaining_turn_angle = angle_deg


def build_agents(width, height):
    agents = []
    for x in range(60):
        agents.append(
            CarLikeAgent(
                id=str(x).zfill(5),
                position=Point(random.randint(1, width), random.randint(0, height)),
                velocity=3,
                rotation=random.randint(0, 359),
                mass=1.0,
                color=Color(255, 0, 0)
            )
        )
    return agents

def clear_screen(screen):
    screen.fill((0,0,0))

pygame.init()

agents = build_agents(width, height)
framerate = 60
time_in_a_frame = 1/framerate
one_percent_of_time_in_a_frame = time_in_a_frame/100
screen = pygame.display.set_mode((width, height))
clock = pygame.time.Clock()
crashed = False
previous_time = time.time()
while not crashed:
    # limit fps to 60
    clock.tick(framerate)
    print("iteration")

    # compute velocity coefficient to mitigate fps variation
    now = time.time()
    dt = now - previous_time
    velocity_coefficient = (dt/one_percent_of_time_in_a_frame)/100
    previous_time = now

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            crashed = True

    clear_screen(screen)

    for agent in agents:
        agent.update_position(velocity_coefficient)
        agent.update_rotation(0)
        agent.update_fov()
        agent.draw_yourself(screen)

    # second loop because every agent position needs to be updated before doing that
    for agent in agents:
        agent.update_remaining_angle_for_closest_visible_agent(agents)

    pygame.display.flip()

models.py :

from geometry import rotate_2d_vector, is_point_inside_triangle

class Color():
    def __init__(self, r: int, g: int, b: int):
        self.r: int = r
        self.g: int = g
        self.b: int = b

    def get_tuple(self):
        return self.r, self.g, self.b

class Vector2D:

    def __init__(self, x: float, y: float):
        self.x: float = x
        self.y: float = y

    def get_tuple(self):
        return self.x, self.y

    def rotate(self, angle_degrees):
        self.x, self.y = rotate_2d_vector(self.x, self.y, angle_degrees)

class DirectionVector2C(Vector2D):

    def __init__(self, x: int, y: int):
        if x < -1 or x > 1:
            raise ValueError("dirention vector can only be -1, 0 or 1 for any given direction")
        if y < -1 or y > 1:
            raise ValueError("dirention vector can only be -1, 0 or 1 for any given direction")
        super().__init__(x, y)

class Point:

    def __init__(self, x: int, y: int):
        self.x: int = x
        self.y: int = y

    def get_tuple(self):
        return self.x, self.y


class Triangle:

    def __init__(self, a: Point, b: Point, c: Point):
        self.a: Point = a
        self.b: Point = b
        self.c: Point = c

    def get_tuple(self):
        return (self.a.x, self.a.y), (self.b.x, self.b.y), (self.c.x, self.c.y)

    def is_point_inside(self, point: Point):
        return is_point_inside_triangle(self.get_tuple(), point.get_tuple())

geometry.py :

import math

def rotate_2d_vector(x, y, angle_degrees):
        angle_radians = math.radians(angle_degrees)
        new_x = x * math.cos(angle_radians) - y * math.sin(angle_radians)
        new_y = x * math.sin(angle_radians) + y * math.cos(angle_radians)
        return new_x, new_y

def is_point_inside_triangle(triangle_coords, point_coord):
        a, b, c = triangle_coords

        x1, y1 = a[0], a[1]
        x2, y2 = b[0], b[1]
        x3, y3 = c[0], c[1]

        x, y = point_coord

        # Calculate the area of the triangle
        A = 0.5 * (-y2 * x3 + y1 * (-x2 + x3) + x1 * (y2 - y3) + x2 * y3)

        # Calculate the barycentric coordinates of the point
        s = 1 / (2 * A) * (y1 * x3 - x1 * y3 + (y3 - y1) * x + (x1 - x3) * y)
        t = 1 / (2 * A) * (x1 * y2 - y1 * x2 + (y1 - y2) * x + (x2 - x1) * y)

        return s > 0 and t > 0 and 1 - s - t > 0

drawer.py :

import pygame

def draw_rect_alpha(surface, color, rect):
    shape_surf = pygame.Surface(pygame.Rect(rect).size, pygame.SRCALPHA)
    pygame.draw.rect(shape_surf, color, shape_surf.get_rect())
    surface.blit(shape_surf, rect)

def draw_circle_alpha(surface, color, center, radius):
    target_rect = pygame.Rect(center, (0, 0)).inflate((radius * 2, radius * 2))
    shape_surf = pygame.Surface(target_rect.size, pygame.SRCALPHA)
    pygame.draw.circle(shape_surf, color, (radius, radius), radius)
    surface.blit(shape_surf, target_rect)

def draw_polygon_alpha(surface, color, points):
    lx, ly = zip(*points)
    min_x, min_y, max_x, max_y = min(lx), min(ly), max(lx), max(ly)
    target_rect = pygame.Rect(min_x, min_y, max_x - min_x, max_y - min_y)
    shape_surf = pygame.Surface(target_rect.size, pygame.SRCALPHA)
    pygame.draw.polygon(shape_surf, color, [(x - min_x, y - min_y) for x, y in points])
    surface.blit(shape_surf, target_rect)

Would writing it in C++ would solve the problem? or is there some gamedev design pattern that can be used to make it more efficient? at the end of main.py you can see the main logic

I saw the direction_vector/velocity/dt for independant framerate in a basic tutorial video but the rest is all me (except the math, it's for google searches). What I mean is that I coded it as I code API stuff.

Thanks.

Answer 1

I don't know about "black magic", but there are definitely some obvious optimizations available here. Which ones will pay off most in your case depends on what your profiling says is consuming the most time.

Spatial partition: don't check every agent against every other agent. Divide your space into bins, and check agents in nearby bins. This takes you from \$O(n^2)\$ where \$n\$ is the total number of agents to \$O(n \times m)\$ where \$m\$ is the number of agents per bin.

Don't check each pair twice: if you want to find all pairs of nearby agents AB, you don't also need to find pairs BA.

Check each agent only against those that came before it in iteration order. If you're iterating your bins left-to-right, top-to-bottom, then you check for agents in bins above and to the left (knowing bins below and to the right will handle checking this agent later on).

This roughly halves your work, but since it's just a constant factor, it doesn't change the big-O.

Batching: GPUs are great at rendering large sets of similar content all at once. When you send drawing instructions one at a time, inter-mixing different types of content, you force them to use only a tiny fraction of the available silicon.

Instead of asking each agent to draw itself, interleaving its dot trails and triangle field of view, try writing all the dot positions/sizes and all the triangle positions/orientations to a buffer, then drawing those buffers in a single pass each.

Avoid allocations in a hot loop: creating and reversing lists requires memory allocation, which is slow. Instead, consider re-using a scratch buffer where the language constructs allow.

Avoid unnecessary math: trigonometric and square root functions are relatively expensive, and you don't need them in most of this code. Your forward direction vector already contains the cosine and sine of your rotation angle, so you can use its components instead of calling trig functions and building a rotation matrix.

Most games will implement an FoV check as a wedge rather than a triangle, which lets you check whether a point is in view with just a length check and dot product - cheaper than a full point-in-triangle test (and it avoids the weirdness of agents being less sensitive/having shorter vision range dead-ahead than in the periphery).