rstar - an advanced space indexing library

[Rick Astley]

rstar
This is the official rstar library topic, welcome!

Introduction
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.

Filtering objects
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!

Detecting collisions
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.

Raycasting
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.

AI
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.

Links

• 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

Try the demo
You can download it from here or GitHub, where you can find also source code as separate files.

[Gunroar:Cannon()]

This seems neat. Is it really fast? Like how fast?

[Rick Astley]

All search queries share the same base idea. Starting from the root: for each child see if it satisfies the input condition (intersects with rectangle or circle/contains a point); if yes, repeat on its children the same loop and go on until leaf level is reached.
On the average case, that loop is done for one node per tree level. In numbers this means that M x tree height rectangles are cheked. Tree height can be calculated using the formula logMN, where N is the number of rectangles you inserted in the tree.
For example if N=1000 and M=20, height is equal to 3: on average 20x3=60 rectangles are checked instead of a thousand.
In conclusion this is that fast, and if correctly tuned to the desired situation even faster.

[Gunroar:Cannon()]

Wow. Wait... so , like, if I want to get all bullet type entities in a tree that has entities added to it, for example, will it be faster than iterating through a table of all entites and getting which one is a bullet?

[pgimeno]

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.

How slow is that? Like, how many insertions/deletions per frame are possible? Few? Hundreds? Thousands?

[Rick Astley]

If you don't mind I would like to answer both your questions in a single post.

R-Tree seems to be the king in handling rectangles (R stands for Rectangle). It's so popular that there are a lot of variants, which are improvements of the base idea. I chose R* variant because in my opinion it is the one which does a better job in making searches fast.
E.g. Google Maps probably uses a couple of those: one on the server to find routes and places nearby, and one on your phone to render the map on the screen.

However, this seems to be the first public implementation of the R*Tree written in Lua; I didn't find anything on Internet.
As you can see in the paper I linked at the bottom of the main post, authors give detailed benchmark data but:

1. Their implementation is written in a weird language.
2. They did it in the 90s

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.

How slow is that? Like, how many insertions/deletions per frame are possible? Few? Hundreds? Thousands?

That said I can't give you an answer now because I'm missing data, but I think my next step is going to be to perform some tests and post here my results. I can say that if you put static objects(like rocks, trees, walls) in it, which won't move much during gameplay, any physics-related task regarding them is going to be light-speed fast.

Wow. Wait... so , like, if I want to get all bullet type entities in a tree that has entities added to it, for example, will it be faster than iterating through a table of all entites and getting which one is a bullet?

Well this tree organises entities using their position in the world, so is useful for tasks like "find which bullet entities are hitting a wall, and should therefore stop or bounce". For your example a simple table is good; in that kind of tasks this structure isn't very helpful.
Anyway in the example I made I would suggest to keep bullets outside the tree, and ask the tree for each bullet which walls is touching on every frame.

[GVovkiv]

Does rstar stands for Rick Star?

[Gunroar:Cannon()]

Haha. no. I don't think the algorithm was made by him, just this implementation. Stands for rectangle (?)

Really liking the sound of all this . And then does that mean it's really fast in getting, let's say, all objects touching/inside an entity?

[Rick Astley]

Does rstar stands for Rick Star?

I really wish it was like that haha

[Rick Astley]

Haha. no. I don't think the algorithm was made by him, just this implementation. Stands for rectangle (?)

Really liking the sound of all this . And then does that mean it's really fast in getting, let's say, all objects touching/inside an entity?

You're right. I'm going to add a demo project soon with some collision detection. Stay tuned