I just finished working on implementing R-trees in Roblox! An R-tree partitions n-dimensional space into a tree. Nodes in the tree represent ranges of space, and each node contains all the space spanned by its children. This makes searching for things in space really fast!
R-trees are found in a lot of GPS systems. They help with things like finding the closest gas stations to where you are on the map. I’m going to be using them with bounded gravity fields. Given a point in space, I can find all the gravity fields that have influence there in O(log(n)) time where n is the number of gravity fields!
I definitely have had a use for a partitioning system before.
The use-case was for pathfinding nodes(finding the nearest one) of which there were over 500 in a map.
For 40 npc’s, at 30 updates per second, this would’ve been 600,000 distance checks per second.