rstar - an advanced space indexing library

Showcase your libraries, tools and other projects that help your fellow love users.
User avatar
togFox
Party member
Posts: 770
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: rstar is here for you!

Post by 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!)
Last edited by togFox on Tue Aug 03, 2021 9:26 am, edited 1 time in total.
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
Rick Astley
Prole
Posts: 16
Joined: Sat Mar 13, 2021 11:51 am

Re: rstar is here for you!

Post by Rick Astley »

togFox wrote: Tue Aug 03, 2021 2:53 am 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.

Code: Select all

if self.thoughts[1] == 'give you up' then
   table.remove(self.thoughts,1)
end
 
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: rstar is here for you!

Post by pgimeno »

togFox wrote: Tue Aug 03, 2021 2:53 am 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.
User avatar
togFox
Party member
Posts: 770
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: rstar is here for you!

Post by 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.
Current project:
https://togfox.itch.io/backyard-gridiron-manager
American football manager/sim game - build and manage a roster and win season after season
User avatar
Rick Astley
Prole
Posts: 16
Joined: Sat Mar 13, 2021 11:51 am

Re: rstar is here for you!

Post by Rick Astley »

pgimeno wrote: Tue Aug 03, 2021 12:03 pm 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. :death:

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.

Code: Select all

if self.thoughts[1] == 'give you up' then
   table.remove(self.thoughts,1)
end
 
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: rstar is here for you!

Post by Gunroar:Cannon() »

Nice. Can it be used for something other than collision detection.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
Rick Astley
Prole
Posts: 16
Joined: Sat Mar 13, 2021 11:51 am

Re: rstar is here for you!

Post by Rick Astley »

Gunroar:Cannon() wrote: Wed Aug 04, 2021 7:01 pm 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.

Code: Select all

if self.thoughts[1] == 'give you up' then
   table.remove(self.thoughts,1)
end
 
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: rstar is here for you!

Post by Gunroar:Cannon() »

:o 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?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
BrotSagtMist
Party member
Posts: 607
Joined: Fri Aug 06, 2021 10:30 pm

Re: rstar is here for you! - now with demo

Post by BrotSagtMist »

Sounds awesome.
Sadly the Demo doesnt run here.
I get: game.lua:290: attempt to call field 'mod' (a nil value)
obey
User avatar
Rick Astley
Prole
Posts: 16
Joined: Sat Mar 13, 2021 11:51 am

Re: rstar is here for you! - now with demo

Post by Rick Astley »

BrotSagtMist wrote: Fri Aug 06, 2021 10:51 pm 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.

Code: Select all

if self.thoughts[1] == 'give you up' then
   table.remove(self.thoughts,1)
end
 
Post Reply

Who is online

Users browsing this forum: No registered users and 43 guests