I am designing a 2d game in which a \$1/r^2\$ force acts between moving charged particles, and the number \$n\$ of particles is very large. To calculate the force between all pairs of particles is about \$n^2/2^2\$.


  • How well does this scale in practice when there are hundreds or thousands or particles? (And considering that graphical output is simple, so that we want to compute the positions of all particles ~60 times per second.)

  • If scaling is bad, how can I simplify the game design such that – in practice – it's not an issue any more? (For example, I have thought of constraining all particles to a lattice of discrete sites, but then I don't know how movement in arbitrary directions would work).


1 Answer 1


This is what I do in my N-Body simulation: particles far away can be aggregated in combined cells on a grid. (Multi-resolution Grid.)

enter image description here

I use gravity calculations, but I am sure that charged attraction/repulsion works similarly over distance: it has the same 1/(r*r) scale.

So particles in the same cell, or neighbour cell, you need to fully compute the influence. Particles that are far away, are aggregated. Just pretend there is a virtual particle with aggregate properties in that cell. So you only do one computation for that aggregated region.

In the video in the linked article, I describe it in more detail.

I find that 60K particles at still doable at interactive frame rate. Depending on the clumping, it can still be done at 60Hz.

  • \$\begingroup\$ Kick-ass. Good job. :) \$\endgroup\$
    – Almo
    Jan 18, 2019 at 20:35
  • \$\begingroup\$ Nice! It would be interesting to see how well this scales, in terms of processing time / number of bodies. \$\endgroup\$
    – Jay
    Jan 19, 2019 at 3:43
  • 2
    \$\begingroup\$ @jay with N Log(N) \$\endgroup\$
    – Bram
    Jan 19, 2019 at 15:39
  • \$\begingroup\$ Thanks already. Although I was more looking for simplifications in the game design itself; that is, in the set-up of the rules of the game physics. \$\endgroup\$
    – Deniz
    Jan 19, 2019 at 15:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .