This is the official rstar library topic, welcome!
rstar is a Lua implementation of the R*Tree data structure. Briefly the R*Tree is a improved version of the classic R-Tree: a structure born to store rectangles of any dimensions, in a way that makes queries like "nearest-neighbor searching" and "all rectangles in a area" quick and efficient.
To achieve this, rectangles are distributed in groups: each of these groups contains at least m members, and never more than M members. A group is called leaf node, which also holds a rectangle sized in a way that contains all its entries(members). Leaf nodes can be treated as entries, thus they can be distributed in groups with the same rules mentioned before, giving birth to internal nodes (or branches).
The node at highest level, which contains all the structure, is called the root, and is the starting point for any kind of operation on the tree.
The R*Tree variant improves the original in the way it builds the structure: creates nodes trying to minimize overlap between them and using as much space as it can.
Overview and Features
R*Tree is good for game developement because its nature makes it suitable in many situations. It must be said that it's not always the best choice: to grow a optimal structure, insertion and deletion take a lot of effort, meaning that for a dynamic set of objects this is not a convenient technique.
On the other hand for static objects with occasional updating, this is going to be lövely!
These are some examples where this library can be really helpful:
Storing solid objects
A advantage of this structure is that it does not need to know how big is the medium object, like a spatial hash does; thus making it great to store objects with a rich range of sizes.
Representing "infinite" worlds
Another advantage is that, unlike Quadtrees, R*Trees are not constrainted to a rigid boundary as they stretch as needed. Worlds which expand over time, like Minecraft's ones, can be handled easily.
If you want to optimize the drawing of game objects, you can retrieve ones which intersect with the screen rectangle to discard invisible ones. Also finding all objects at a point is a very quick operation: sweet to know what the user is clicking!
To detect if the player is bumping into walls, does not make sense to test on a wall a mile away from them; this is a task where the ability to search quickly for walls around the player is a big deal.
This implementation comes with a method to retrieve all rectangles within a circular range, which could speed up raycasting by excluding objects not in the radius of sight.
Nearest-neighbor search is included, and works both with rectangles inserted in the tree and arbitrary boxes.
That's all for now, thanks for checking this out!
P.S. If you'd like to use this with dynamic objects, wait for version 1.1.
- Code and Documentation https://github.com/rick4stley/rstar
- The R-Tree http://www-db.deis.unibo.it/courses/SI- ... /Gut84.pdf
- The R*Tree https://infolab.usc.edu/csci599/Fall200 ... r-tree.pdf
You can download it from here or GitHub, where you can find also source code as separate files.