Particles overlapping when colliding in python py-game

Question

]When running the simulation the particles can overlap and freak out a bit. I think because it's a discrete simulation when the collision is detected the particles have already overlapped so the sections which calculates the final velocity doesn't work right.

I solved the same problem for the particles and the screen boundary but I can't figure out how do to it for a particle-particle collision. Any help would be greatly appreciated

import pygame
import random
import math
import numpy as np

width, height = 700, 450
screen = pygame.display.set_mode((width, height))
particles = []
no_particles = 10
tick_speed = 200

class Particle:
    def __init__(self, x, y, r):
        self.r = r
        self.pos = np.array([x, y])
        self.vel = np.array([random.uniform(-0.5, 0.5), random.uniform(-0.5, 0.5)])
        self.acc = np.array([0, 0]) #tick_speed/(tick_speed * 10)

    def display(self):
        pygame.draw.circle(screen, (227, 53, 15), (int(self.pos[0]), int(self.pos[1])), self.r, 1)

    def move(self):
        self.vel = self.vel + self.acc 
        self.pos = self.pos + self.vel
            
    def bounce(self):
        if self.pos[1] > height - self.r:
            self.pos[1] = 2*(height - self.r) - self.pos[1]
            self.vel[1] = -self.vel[1]

        elif self.pos[1] < self.r:
            self.pos[1] = 2*self.r - self.pos[1]
            self.vel[1] = -self.vel[1]

        if self.pos[0] + self.r > width:
            self.pos[0] = 2*(width - self.r) - self.pos[0]            
            self.vel[0] = -self.vel[0]
            
        elif self.pos[0] < self.r:
            self.pos[0] = 2*self.r - self.pos[0]
            self.vel[0] = -self.vel[0]
            
    @classmethod
    def collision(cls, p1, p2):
        dc = math.hypot((p1.pos[0]-p2.pos[0]), (p1.pos[1]-p2.pos[1]))
        if dc <= p1.r + p2.r:
            x1, y1 = p1.pos[0], p1.pos[1]
            x2, y2 = p2.pos[0], p2.pos[1]
            m1, m2 = p1.r**2, p2.r**2
            
            n = np.array([x2-x1, y2-y1])
            un = n / np.linalg.norm(n)
            ut = np.array([-un[1], un[0]])
            
            v1 = p1.vel
            v2 = p2.vel

            v1n = np.dot(un, v1)
            v1t = np.dot(ut, v1)

            v2n = np.dot(un, v2)
            v2t = np.dot(ut, v2)

            v1n_prime_s = (v1n * (m1 - m2) + 2*m2*v2n) / (m1 + m2)
            v2n_prime_s = (v2n * (m2 - m1) + 2*m1*v1n) / (m1 + m2)
             
            v1n_prime = v1n_prime_s * un
            v1t_prime = v1t * ut

            v2n_prime = v2n_prime_s * un
            v2t_prime = v2t * ut
            
            u1 = v1n_prime + v1t_prime 
            u2 = v2n_prime + v2t_prime
            p1.vel = u1
            p2.vel = u2

            
while len(particles) < no_particles:
    r = random.randint(10, 20)
    x = random.randint(r, width-r)
    y = random.randint(r, height-r)
    collide = False
    for particle in particles:
        d = (particle.pos[0] - x)**2 + (particle.pos[1] - y)**2
        if d < (r + particle.r)**2:
            collide = True
            break
        
    if not collide:
        particles.append(Particle(x, y, random.randint(10, 20)))
        
          
running = True
clock = pygame.time.Clock()
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
            
    screen.fill((255, 255, 255))
    for particle in particles:
        particle.move()
        particle.bounce()
        for particle2 in [p for p in particles if p!= particle]:
            particle.collision(particle, particle2)
        particle.display()
        

    pygame.display.flip()
    clock.tick(tick_speed)


pygame.quit()
quit()

The problem is similar to the problem described in [Sometimes the ball doesn't bounce off the paddle in pong game](https://stackoverflow.com/questions/62864205/sometimes-the-ball-doesnt-bounce-off-the-paddle-in-pong-game). It can be solved with ease for 2 particles - see [Pygame how to let balls collide](https://stackoverflow.com/questions/63145493/pygame-how-to-let-balls-collide/63187016#63187016) . However, it is much more difficult to solve for N particles. What happens if a particles is squeezed by 2 other particles? — Rabbid76, Sep 16 '21 at 14:12
Related [Random systematic movement in pygame](https://stackoverflow.com/questions/65468240/random-systematic-movement-in-pygame/65468502#65468502) — Rabbid76, Sep 16 '21 at 14:23

score 1 · Accepted Answer · 2021-09-16T17:42:57.910

The problem is that you are checking and resolving collision multiple times for the same balls in a single iteration.

Since the direction has already once been "reflected" once, these dot products,

v1n = np.dot(un, v1)
v1t = np.dot(ut, v1)

v2n = np.dot(un, v2)
v2t = np.dot(ut, v2)

yield the opposite direction in the next collision resolution, which causes the balls to move towards each other.

"Energy" is being added to the system every time the balls collide, because of these,

p1.r**2, p2.r**2
2*m2*v2n, 2*m1*v1n

which causes the freak out that you mention.

Solution is to simply check and resolve the collisions once:

for i in range(len(particles)):
        particles[i].move()
        particles[i].bounce()
        for j in range(i + 1, len(particles)):
            particles[i].collision(particles[i], particles[j])
        particles[i].display()

As Rabbid76 pointed out, this fails as the number of particles increases. If you statically resolve the collision first, everything will work since the collision will have already been resolved and your dynamic resolution code will set the velocities accordingly.

@classmethod
def resolveStatically(cls, n, dc, p1, p2):
      displacement = (dc - p1.r - p2.r) * 0.5
      p1.pos[0] += displacement * (n[0] / dc)
      p1.pos[1] += displacement * (n[1] / dc)
      p2.pos[0] -= displacement * (n[0] / dc)
      p2.pos[1] -= displacement * (n[1] / dc)

@classmethod
def collision(cls, p1, p2):
    dc = math.hypot((p1.pos[0]-p2.pos[0]), (p1.pos[1]-p2.pos[1]))
    if dc <= p1.r + p2.r:
        #...
        n = np.array([x2-x1, y2-y1])
        cls.resolveStatically(n, dc, p1, p2)

Full code:

import pygame
import random
import math
import numpy as np

width, height = 700, 450
screen = pygame.display.set_mode((width, height))
particles = []
no_particles = 100
tick_speed = 200

class Particle:
    def __init__(self, x, y, r):
        self.r = r
        self.pos = np.array([x, y])
        self.vel = np.array([random.uniform(-0.5, 0.5), random.uniform(-0.5, 0.5)])
        self.acc = np.array([0, 0]) #tick_speed/(tick_speed * 10)

    def display(self):
        pygame.draw.circle(screen, (227, 53, 15), (int(self.pos[0]), int(self.pos[1])), self.r, 1)

    def move(self):
        self.vel = self.vel + self.acc 
        self.pos = self.pos + self.vel
            
    def bounce(self):
        if self.pos[1] > height - self.r:
            self.pos[1] = 2*(height - self.r) - self.pos[1]
            self.vel[1] = -self.vel[1]

        elif self.pos[1] < self.r:
            self.pos[1] = 2*self.r - self.pos[1]
            self.vel[1] = -self.vel[1]

        if self.pos[0] + self.r > width:
            self.pos[0] = 2*(width - self.r) - self.pos[0]            
            self.vel[0] = -self.vel[0]
            
        elif self.pos[0] < self.r:
            self.pos[0] = 2*self.r - self.pos[0]
            self.vel[0] = -self.vel[0]

    @classmethod
    def resolveStatically(cls, n, dc, p1, p2):
          displacement = (dc - p1.r - p2.r) * 0.5
          p1.pos[0] += displacement * (n[0] / dc)
          p1.pos[1] += displacement * (n[1] / dc)
          p2.pos[0] -= displacement * (n[0] / dc)
          p2.pos[1] -= displacement * (n[1] / dc)
            
    @classmethod
    def collision(cls, p1, p2):
        dc = math.hypot((p1.pos[0]-p2.pos[0]), (p1.pos[1]-p2.pos[1]))
        if dc <= p1.r + p2.r:
            x1, y1 = p1.pos[0], p1.pos[1]
            x2, y2 = p2.pos[0], p2.pos[1]
            m1, m2 = p1.r**2, p2.r**2
            
            n = np.array([x2-x1, y2-y1])
            cls.resolveStatically(n, dc, p1, p2)
            
            un = n / np.linalg.norm(n)
            ut = np.array([-un[1], un[0]])
            
            v1 = p1.vel
            v2 = p2.vel

            v1n = np.dot(un, v1)
            v1t = np.dot(ut, v1)

            v2n = np.dot(un, v2)
            v2t = np.dot(ut, v2)

            v1n_prime_s = (v1n * (m1 - m2) + 2*m2*v2n) / (m1 + m2)
            v2n_prime_s = (v2n * (m2 - m1) + 2*m1*v1n) / (m1 + m2)
             
            v1n_prime = v1n_prime_s * un
            v1t_prime = v1t * ut

            v2n_prime = v2n_prime_s * un
            v2t_prime = v2t * ut
            
            u1 = v1n_prime + v1t_prime 
            u2 = v2n_prime + v2t_prime
            p1.vel = u1
            p2.vel = u2

            
while len(particles) < no_particles:
    r = random.randint(10, 20)
    x = random.randint(r, width-r)
    y = random.randint(r, height-r)
    collide = False
    for particle in particles:
        d = (particle.pos[0] - x)**2 + (particle.pos[1] - y)**2
        if d < (r + particle.r)**2:
            collide = True
            break
        
    if not collide:
        particles.append(Particle(x, y, random.randint(10, 20)))
        
          
running = True
clock = pygame.time.Clock()
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
            
    screen.fill((255, 255, 255))

    for i in range(len(particles)):
        particles[i].move()
        particles[i].bounce()
        for j in range(i + 1, len(particles)):
            particles[i].collision(particles[i], particles[j])
        particles[i].display() 
            
    pygame.display.flip()
    clock.tick(tick_speed)

pygame.quit()
quit()

Particles overlapping when colliding in python py-game

1 Answers1