Particle interaction slow O(n^2)

VincentGarreau / particles.js

A lightweight JavaScript library for creating particles

https://vincentgarreau.com/particles.js/

MIT License

28.72k stars 4.81k forks source link

Particle interaction slow O(n^2) #223

Open mollerhoj opened 7 years ago

mollerhoj commented 7 years ago

The current implementation of particle distance detection uses a naive O(n^2) algorithm. This makes the library extremely slow for even a relatively small amount of particles. I suggest an implementation that uses kd-trees. @VincentGarreau your thoughts? I might have time to make a PR one of these days, especially if you would accept the usage of external libraries.

coder4life commented 6 years ago

In all honesty updates have been non existent from the original author (nothing against the original author we all get busy). I would love to see some improvements put forward, I hope someone forks the project. There have been proposals by others to move to ES6, ect.

mclark-newvistas commented 5 years ago

I think fixing #206 would be the simplest aid to performance; a k-d tree implementation would probably take a while to build, and #206 might give enough of a performance gain.