2
\$\begingroup\$

Setting

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\$.

Questions

  • 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).

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Kick-ass. Good job. :) \$\endgroup\$ – Almo Jan 18 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 at 3:43
  • 2
    \$\begingroup\$ @jay with N Log(N) \$\endgroup\$ – Bram Jan 19 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 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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