FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Does Blaze use spatial hashing and how can I tap into it?

 
Post new topic   Reply to topic     Forum Index -> Blaze
View previous topic :: View next topic  
Author Message
JNewt



Joined: 05 Jun 2008
Posts: 69

PostPosted: Fri Aug 21, 2009 12:31 pm    Post subject: Does Blaze use spatial hashing and how can I tap into it? Reply with quote

I guess the title says it all. I'm working on a 2d platformer and was previously using a quadtree to store my game elements. I did this primarily for very fast visibility testing as my levels are very long. Now that I'm starting a rewrite with Blaze, I'm wondering if I can simply tap into it for my rendering instead of trying to keep a quadtree in sync. Is there a function which I can call with a rectangular area and 1) get all bodies overlapping/within the rectangle OR 2) run a callback on each of said bodies?
Back to top
View user's profile Send private message
zzzzrrr



Joined: 17 Feb 2007
Posts: 139
Location: Washington, DC

PostPosted: Fri Aug 21, 2009 2:47 pm    Post subject: Reply with quote

JNewt wrote:
I guess the title says it all


No, Blaze does not use a spacial hash.

JNewt wrote:
Is there a function which I can call with a rectangular area and 1) get all bodies overlapping/within the rectangle


Yes, this is very similar to what one would do for mouse selection in the demo framework. Look at the function World.query, and at function pickShape in test.d for an example.


JNewt wrote:
2) run a callback on each of said bodies?


Yes, Blaze supports collision callbacks.

I would also suggest you take a look at the Box2D wiki / API for other functionality info.
Back to top
View user's profile Send private message
JNewt



Joined: 05 Jun 2008
Posts: 69

PostPosted: Fri Aug 21, 2009 3:09 pm    Post subject: Reply with quote

Thanks, it looks like that query method will do the trick. Do you have any idea how it'll perform with many thousands of shapes spread over a large area? I ask, because I'll need to perform the query for every frame.
Back to top
View user's profile Send private message
zzzzrrr



Joined: 17 Feb 2007
Posts: 139
Location: Washington, DC

PostPosted: Fri Aug 21, 2009 3:36 pm    Post subject: Reply with quote

JNewt wrote:
Thanks, it looks like that query method will do the trick. Do you have any idea how it'll perform with many thousands of shapes spread over a large area? I ask, because I'll need to perform the query for every frame.


It will probably be slow.
Back to top
View user's profile Send private message
JNewt



Joined: 05 Jun 2008
Posts: 69

PostPosted: Fri Aug 21, 2009 4:03 pm    Post subject: Reply with quote

Hmmm, Ok. Does Blaze check all shapes for collisions against all other shapes every update? Or does it have some mechanism for segmenting the world into manageable chunks? Looking at the Box2D docs, it looks like all objects are managed in one pool, which means either O(n^2) for collisions or else some sort of caching (as far as I can see, anyways).
Another Box2D derivative, Chipmunk, does do spatial hashing to increase efficiency, which, from my experience with quadtrees, can have a pretty dramatic effect. Are there plans to integrate something like this?
Back to top
View user's profile Send private message
zzzzrrr



Joined: 17 Feb 2007
Posts: 139
Location: Washington, DC

PostPosted: Fri Aug 21, 2009 4:05 pm    Post subject: Reply with quote

JNewt wrote:
Looking at the Box2D docs, it looks like all objects are managed in one pool, which means either O(n^2) for collisions or else some sort of caching (as far as I can see, anyways)


Nope, it has a fast broadphase collision detection method called Sweep & Prune.
Back to top
View user's profile Send private message
JNewt



Joined: 05 Jun 2008
Posts: 69

PostPosted: Fri Aug 21, 2009 4:21 pm    Post subject: Reply with quote

Are the sorted results of the Sweep & Prune available to the query method? If so, it seems like a very fast bounds query could be done by skipping along the chain, especially if the user could supply some information about the largest reasonable size of a single object.

My concern is basically that all bodies not be checked against the boundary rectangle in the query; if you already have the bodies sorted by, say, the x-axis, then many objects could be eliminated without checking (assuming there are no really wide objects).
Back to top
View user's profile Send private message
JNewt



Joined: 05 Jun 2008
Posts: 69

PostPosted: Fri Aug 21, 2009 4:45 pm    Post subject: Reply with quote

I'm reading over the source, and it appears that some sort of limiting is occurring in bzBroadPhase.query; the source at that point isn't really commented, so I'm not sure. It looks like it'll be worth giving Blaze a try and seeing how performance works out before I go to the work of importing Chipmunk. Thanks for your help on this, and please post any other bits of info you think relevant.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> Blaze All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group