Improve code to avoid slow particle collision

Question

I need to divide space into cells. Each cell should be approximately the size of the particle radius so that a particle does not occupy more than 4 cells as in the illustration below:

The r-ray particle can occupy up to 4 cells. Its own cell (where the center (x,y) of the particle is located) and 3 other neighboring cells.

Reason for optimization: With the current code, when I increase the amount of particles, the program becomes very slow and the collisions between them do not occur in a fluid way.

canvas.cpp

#include "canvas.h"
#include <QPainter>

canvas::canvas(QWidget *parent) :
QWidget(parent)
{
m_particulas.resize(50);

int n = m_particulas.size();
for(int i = 0 ; i<n ; ++i)
{
    m_particulas[i].init();
}

startTimer(5);
}

void canvas::paintEvent(QPaintEvent * event)
{
(void) event;

QPainter painter(this);
painter.setWindow(0,0,1000,1000);
painter.setRenderHint(QPainter::Antialiasing, true);
painter.setPen(QPen(Qt::black, 2, Qt::SolidLine, Qt::RoundCap));
painter.setBrush(QBrush(Qt::darkCyan, Qt::SolidPattern));

int n = m_particulas.size();
for(int i = 0 ; i<n ; ++i)
{
    double x = m_particulas[i].x();
    double y = m_particulas[i].y();
    double L = m_particulas[i].r();
    painter.drawEllipse(QPointF(x, y), L, L);
}
}

void canvas::timerEvent(QTimerEvent *event)
{
(void) event;

int n = m_particulas.size();

for(int i = 0 ; i<n ; ++i)
    m_particulas[i].andar();

for(int i = 0 ; i<n ; ++i)
{
    Particula &pi = m_particulas[i];

    for(int j = 0 ; j < n ; ++j)
    {
        if (i == j) continue; //(MODO 2)

        Particula &pj = m_particulas[j];

        if (pi.testa_colisao(pj))
        {
            pi.calcula_colisao(pj);
        }
    }
}
update();
}

particle.cpp

#include "particula.h"
#include <stdlib.h>     /* srand, rand */
#include <cmath>

Particula::Particula()
{

}

void Particula::init()
{
m_r = 20;

m_x = 900.0*rand()/RAND_MAX + 50;
m_y = 900.0*rand()/RAND_MAX + 50;

m_vx = 2.0 * rand()/RAND_MAX - 1;
m_vy = 2.0 * rand()/RAND_MAX - 1;

double norma = sqrt(m_vx*m_vx + m_vy*m_vy);
m_vx /= norma;
m_vy /= norma;
}

void Particula::normaliza(double &vx, double &vy)
{
double norma = sqrt(vx*vx + vy*vy);

if (norma > 0)
{
    vx /= norma;
    vy /= norma;
}
}

bool Particula::testa_colisao (Particula &p)
{
    double dx = x() - p.x();
    double dy = y() - p.y();

    double dist2 = dx*dx + dy*dy;
    double somaRaios = r() + p.r();
    return dist2 <= somaRaios * somaRaios;
}

void Particula::calcula_colisao(Particula &p)
{
    double vx = p.x() - x();
    double vy = p.y() - y();
    normaliza(vx,vy);

    p.m_vx += vx;
    p.m_vy += vy;
    normaliza(p.m_vx,p.m_vy);

    m_vx -= vx;
    m_vy -= vy;
    normaliza(m_vx, m_vy);

   do
    {
        andar();
        p.andar();
    } while (testa_colisao(p));
}

double Particula::x() const
{
return m_x;
}

double Particula::y() const
{
return m_y;
}

double Particula::r() const
{
return m_r;
}

void Particula::andar()
{
m_x += m_vx;
m_y += m_vy;

if(m_x > 1000-m_r) m_vx *= -1; //inferior - multiplicado por -1 para inverter a     direção...
if(m_y > 1000-m_r) m_vy *= -1; //direita
if(m_x < 0+m_r) m_vx *= -1; //esquerda
if(m_y < 0+m_r) m_vy *= -1; //superior
}

Answer 1

For illustration purposes, consider a simple division in which your canvas is broken into 4x4 smaller squares, as in the figure below:

Your code tests the collision within the method canvas::timerEvent, today by checking it between every possible combination of n particles: p₁ x p₂. Therefore, it has a quadratic complexity (O(n²)) and can take long enough for a large number of particles.

Using a simple division like the one illustrated, you can make a single loop to locate the particles in the different squares and so "filter" only those in the same square (or neighboring squares, as you prefer) of a particle of interest.

Filtering is simple to perform using a single loop to traverse all existing particles (the complexity is O(n), and you can use the same loop you already use to make particles walk):

• Divide the canvas dimensions in length (width) and height (height) respectively by the number of squares in a row and in a column (in the illustrated example, this number is 4 for ambox). This will result in the pixel dimensions of a square (i.e., length and height of a square in pixels).
• In the location loop, for the current particle p_i, divide the values of its coordinates into x and y respectively by the length and width of a previously calculated square, and take only the entire part (truncate the result). This will result in the index (started at 0) of the square in which the particle is located on the X and Y axes, which can be used to store and reference the particles in a two-dimensional array representing the squares.

Example:

Consider that the canvas is 100 x 100 pixels and that a particle A is finds at the coordinate (x:80, y:25) and another particle B is at the coordinate (x:48, y:77).

As are 4 squares in a canvas line, the length of one square is 100/4=25 pixels. How are 4 squares in a column of canvas, the height of a square is 100/4=25 pixels. Thus, a square has 25 x 25 pixels; on the X axis of the canvas, the first square goes from pixel 0 to pixel 24, the second of pixel 25 to pixel 49, the third of the pixel 50 to pixel 74, and the last from pixel 75 to pixel 99; as a height is equal to length, the same values apply to the coordinates of squares in the y-axis of the canvas.

For particle A. By dividing its value of x = 80 by the length of the square results in: 80/25 = 3,2. Extracting the whole part, you have value 3. This value indicates the index the square in which the particle is in the X axis, that is, in the fourth and last square on the left to the right (remembering that the index is from 0). When dividing its value of y = 25 per square height results in: 25/25 = 1. Extracting the whole part, one has the value 1 which indicates that the particle is in the second square from top to bottom. That is, using a two-dimensional array to represent the squares, the particle is squared CANVAS[3,1].

For particle B. By dividing its value of x = 48 by the length of the square has: 48/25 = 1,92 with an integer equal to 1. When dividing its value of y = 77 by the square height is: 77/25 = 3,08 with whole part equal to 3. That is, the particle is in the square CANVAS[1,3].

Once you have the particles located on their different squares, the verification of the Colizão can be done only for the particles within each square. You can do this by simply traversing the squares in a two-dimensional array and doing the collision test only for the particles stored within the current square (i.e., within CANVAS[i,j]).

Although within each square the comparison has quadratic complexity, in the overall result the computational cost will be much lower, proportional to its division (imagine that you have 100 particles; to compare all of them you need 100x100 = 10000 comparisons; with only 4 cells, if there are 25 particles in each cell you will need only four local comparisons of 25x25 particles, that is, 4x25x25 = 2500 comparisons - only 25% of what would be needed without division).

You may not need a very large division. Maybe using 16 cells (4x4 division as illustrated) is enough for your purpose. Also, you may not need to recalculate the location of the particles in the same time range as you move them, but this will depend on their speed and fine-tuning that you may need. I advise you to start with the simplest solutions (less squares, relocation at every turn), and apply the changes as you feel the need.

P.S.: Note also that in my suggestion I am not considering the particle dimensions (which was a concern of yours in the question, but which I judged unnecessary). If you have any reason for this (perhaps from the reference where you yourself took an image posted in the comments), I think it’s important that you specify in the question. :)