Barnes Hut and magnetic (Coulomb) forces


I’m working working at a particle system where I need to have lots of particles (around 5K or more). I want all particles to be attracted to a couple of attraction points, though they should keep a distance form these points. Each of the particles tries to keep some space from the surrounding particels to get a shape like this:

Here I’ve implement the particles and coulomb force using just 300 particles which works fine. Because I need more I’ve googled to find some info on implementing a system where each particle interacts with surrounding particles. Someone advised me to use the Barnes Hut algorithm… so I did which works fine as far as normal interaction. Though when I added the coulomb forces it works, but only for each quadrant. Therefore I’m wondering if someone knows more about Barnes Hut or another algorithm I could use?

This is the result when using Barnes Hut together with coulomb forces:


hi roxlu,
there is an interesting thread on particle binning here,

not sure if it helps but looks a lot like what ur working on.


i’d suggest particle binning here also.

the slow-down when you add new particles is coming from the part of the code that works out the distance between particles. it scales poorly because, expressed in Big-Oh-notation, it is O(n^2): each particle (n) has to loop through all the other particles (n) to determine distance: n*n = n^2.

particle binning means you can only focus on paricles that matter: you decide that you can ignore all particles more than, say, 10 distance units away, then finding the particles nearer than that is just a case of walking through the relevant bins and only looking at those particles.


Hi Damian and Julapy,

Thanks a lot for your messages I’m reading Kyles code atm and reading up on
that binned particle system. Seems elegant.


Hey roxlu, I just realized a few things after looking at this image again.

1 You mentioned in your email that the MAX_CHILDREN is ~50, while it should be much smaller (maybe ~10).

2 Barnes-hut has a constant that changes the behavior of the approximation: it allows for a trade off between accuracy and speed. You might want to try tweaking that more toward the accuracy side. When it is all the way toward the accuracy side, it should do n^2 calculations and simulate things correctly. If it’s not, there’s something else wrong.

3 Binning could work here, but you already have the quadtree structure so you might as well use it. Though quadtrees work best when the space is sparse, and binning when the space is evenly distributed… so I’m not sure what the space is going to look like in the end, but that will influence which technique is fastest for the local interaction.