Tsparticles: Performance improvement with Spatial Hashmap

[matteobruni]

A Redditor suggested me to use a spatial hash map or a k-d tree to improve general performance. One of these methods should replace at least the main loop, and probably some others if I'm right.

The comment is this:
https://www.reddit.com/r/javascript/comments/fmdn6e/tsparticles_what_particlesjs_could_be_if_it_wasnt/flfrqk2?utm_source=share&utm_medium=web2x

There's some articles and code to check.

[matteobruni]

I checked some particles system with spatial hashing and I've seen some bad performance there too. This require more study.

[matteobruni]

This codepen https://codepen.io/matteobruni/pen/bGdyrmK seems to work fine. This can be a starting point

[TylerBurnett]

Porting the code to typescript. Might need some assistance in its use once it's ready.

[TylerBurnett]

So from the looks of the class itself, everything seems to be ok. I'm not exactly sure where this implementation will fit compared to the rest of the code. Implementation into the Particle class would be huge and unreasonable due to the huge reliance on the Particle Array.

Hence I would suggest a partial implementation. I'm investigating using it purely for just the collision detection of particles.

This is what I've achieved so far.
The class

[matteobruni]

Hi @TylerBurnett, thanks but the two classes I referenced here were already ported, and then deleted.

The main issue is how to use them, there's a lot of configurations that can have different distances and create a map for every distance doesn't seem the right solution.

Probably I'm doing something wrong but I'm focused on other activities that I would release first, like the Vuejs component (https://github.com/matteobruni/particles.vue) and I didn't spent some good time on the map.

If you have some ideas we can discuss them.

[TylerBurnett]

No worries, there wasn't any closure on the ticket so I assumed it was ongoing. To be fair I'm not making much head way either. It seems both methods create huge arrays for the purpose of this. Which isn't productive. I'll leave it for the moment.

[TylerBurnett]

@matteobruni, I reworked it.

Generic method
AVG = 0.012741932990931

Spatial Grid - 20 cell size
AVG = 0.0052941151593319

Optimizing it at the moment to further the improvements. I believe at higher densities there should be larger improvements. This was only tested on particle collision.

[matteobruni]

Good job! About half the time, it's awesome!

[TylerBurnett]

The initial framework for spatial grid mapping has been laid out and implemented in particle overlapping. See: https://github.com/matteobruni/tsparticles/pull/222
Further integration with this system will prove to have more performance improvements.

The next step ideally will be integration with the Interaction manager which definitely has its own design hurdles. All three behaviors contained in the Interaction manager have independent distance checking, meaning that an implementation either needs to do checks independently for all three or one that runs at the furthest of the three distances.

[TylerBurnett]

I've managed to hotwire the linker function to utilize the spatial neighbor checking. It's still very early stages but comparing numbers it looks like I've managed to bring down frame compute time from 22ms to `16ms.