I’m sure a lot of you can use this utility, so I open sourced it.
Let’s imagine you are trying to make a “fire spreading script”. The most simple, but also most naive way, is to do something like this:
- Find a part which is on fire
- Loop over all parts in Workspace, check if it’s close, and if so, light it (or any temperature-whatever based operation)
However, this scales really badly with the amount of Instances to check. This algorithm will be very slow.
A logical “fix” for this is to split up the Workspace into areas. If you check within a range of 20, and you have a box with instances which has a size of 40 studs, (and the “range sphere” fits in this box), then you only have to check for Instances within this box.
Also, if the sphere “overlaps” another box, you should check in that box. However, as you see, you also make sure that you “skip” a lot of Instances to check. Range operations like getting magnitudes are intensive operations, so they should be avoided.
Splitting up a group of instances is called a ‘binary search tree’ - (it’s actually a data structure). It’s easy to make. However, we all like to spend time on “fun” things, like playing with these trees. I just created this module - with documentation - and you can download it from github.
The repo includes a test place which simulates fire spreading. This is also the place I used to tweak some settings. A small overview of this place (don’t open it for the visuals!)
-> Spawn ~4096 bricks.
-> Load them into the Archer
-> Run Archer
Watch how the fire spreads (brick sizes indicate tempreature, the awesome visuals include color changing - i disabled fire particles to not fry the GPU for 4096 particle spawn). After that, upgrade Archers box range to a huge value, so the “naive” approach is simulated. Watch how the fire spreads much more slow.
I need to tweak some things though, but it’s useable now.