R-trees!.......!


R-tree with MAX_ENTRIES=5, MIN_ENTRIES=2


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!

11 Likes

Glad to see this is being proven wrong.

2 Likes

I guess we could say that that comment
became
History
puts on sunglasses

4 Likes

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.

2 Likes

I would hardly say it’s proven wrong… we haven’t seen a practical use for this r tree where a linear search just wouldn’t do.

However, it doesn’t take into account that, sometimes, algorithms are just fun. We can appreciate this r tree as a fun programming project. :slight_smile:

when i clicked i was honestly expecting trees in the shape of the roblox logo but once again im greeted with nerd stuff i cant understand

4 Likes