rstar - an advanced space indexing library

[togFox]

I'm struggling, out of my own ignorance, to understand how storing rectangles in a tree can be useful. I looked through the original post and don't 'get it'. Perhaps I've yet to uncover a problem that is best solved by R trees.

(I don't mean to devalue your library. All new libraries are good libraries!)

[Rick Astley]

I'm struggling, out of my own ignorance, to understand how storing rectangles in a tree can be useful. I looked through the original post and don't 'get it'. Perhaps I've yet to uncover a problem that is breast solved by R trees.

(I don't mean to devalue your library. All new libraries are good libraries!)

It's ok, I've never released code before so I understand that my descriptions may be confusing.

Rectangle has a meaning that goes beyond four edges sticked togheter in this case. If you are familiar with collision detection techniques, you know that checking if a bird is touching a tree is pretty laborious, and annoying when you find out they do not at all.
Avoiding as much as possibile to jump in that meticulous job could be a key factor in a game. So people figured out that a complex shape could be represented by a rectangle that perfectly contains it (no waste of space); this way you can check if rectangles collide before going on with the precise testing.
Unfortunately in big games that could not be enough! When there are hundreds of rectangles to check, the time taken is still big.

This R*Tree is a optimization solution: your game might have a ton of collision checks to do, and care for fancy particle effects and animations as well on every frame. R*Tree avoids tests between far rectangles (and not only that).

In conclusion, if you have a small game this library is not going to make any difference, but on big projects it could potentially erase some bottlenecks.

[pgimeno]

I'm struggling, out of my own ignorance, to understand how storing rectangles in a tree can be useful. I looked through the original post and don't 'get it'. Perhaps I've yet to uncover a problem that is best solved by R trees.

Collision libraries like bump.lua are already using some kind of rectangle querying optimization, which is what this library does. Without such thing, if your world consists of, say, 1000 rectangles, you have to check each of them in order to verify if you're going to collide with it. Swept collisions are expensive to calculate, so checking 1000 rectangles is prohibitive. If you can check just those rectangles for which there can possible be a collision, the search space is greatly reduced. For example, of these 1000 rectangles it's possible that only 8 or 10 are near the moving entity.

This library is able to answer the question, "what rectangles are near the entity?"

Bump.lua utilizes a technique called a "spatial hash", a structure where the rectangles are stored in bigger containers aligned to a grid, and accessible via the coordinates of this grid. This technique is fairly straightforward; all operations are pretty fast, but it has its pitfalls, e.g. it's not very efficient when your rectangles are much bigger than the grid size, because each such rectangle has to be stored in O(n²) containers, or much smaller, meaning you may have a lot of rectangles in the same container. I imagine the R* technique covers that case better, but I'm concerned about insertion/deletion time.

Check the demo of bump: https://github.com/kikito/bump.lua/tree/demo to see why this is important.

[togFox]

I see now. Thanks both. I've never had to calculate so many collisions but I can see how some might have the need. I'll keep this in mind for future projects.

[Rick Astley]

I imagine the R* technique covers that case better, but I'm concerned about insertion/deletion time.

I've just remebered that I forgot to mention a important thing, my bad.

Before the release of this library, version 1.1 was alredy planned, because I wanted to add another feature in a later release(it's also stated on GitHub).
This feature is bulk loading, which builds the tree in one hit, and overcomes the limits of sequential insertion.
I guess I will include also a tree destruction method (which should be pretty fast and straightforward). And maybe combine them in a elegant update method, who knows.
With these features the tree could be reconstructed on every frame quickly.

In conclusion, with the next version this library will get what it lacks to handle dynamic objects. I hope this will ease your worries and ones of others interested.

[Gunroar:Cannon()]

Nice. Can it be used for something other than collision detection.

[Rick Astley]

Nice. Can it be used for something other than collision detection.

Off course, a example is reducing the number of drawing calls to the strictly nececessary. You can think about your window as a rectangle, which can be used to search in the tree to get only objects that are visible on screen.

[Gunroar:Cannon()]

SO SORRY. Already knew that one. Though still useful(but in a way still collision detection, like bump.lua, not a bad thing). Anything else?

[BrotSagtMist]

Sounds awesome.
Sadly the Demo doesnt run here.
I get: game.lua:290: attempt to call field 'mod' (a nil value)

[Rick Astley]

Sounds awesome.
Sadly the Demo doesnt run here.
I get: game.lua:290: attempt to call field 'mod' (a nil value)

Try replacing that line with

Code: Select all

math.fmod(i-1, 3)

or

Code: Select all

(i-1) % 3

One of these should fix the error, depending on your Lua version.