View previous topic :: View next topic |
Author |
Message |
JNewt
Joined: 05 Jun 2008 Posts: 69
|
Posted: Fri Aug 21, 2009 12:31 pm Post subject: Does Blaze use spatial hashing and how can I tap into it? |
|
|
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 |
|
|
zzzzrrr
Joined: 17 Feb 2007 Posts: 139 Location: Washington, DC
|
Posted: Fri Aug 21, 2009 2:47 pm Post subject: |
|
|
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 |
|
|
JNewt
Joined: 05 Jun 2008 Posts: 69
|
Posted: Fri Aug 21, 2009 3:09 pm Post subject: |
|
|
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 |
|
|
zzzzrrr
Joined: 17 Feb 2007 Posts: 139 Location: Washington, DC
|
Posted: Fri Aug 21, 2009 3:36 pm Post subject: |
|
|
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 |
|
|
JNewt
Joined: 05 Jun 2008 Posts: 69
|
Posted: Fri Aug 21, 2009 4:03 pm Post subject: |
|
|
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 |
|
|
zzzzrrr
Joined: 17 Feb 2007 Posts: 139 Location: Washington, DC
|
Posted: Fri Aug 21, 2009 4:05 pm Post subject: |
|
|
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 |
|
|
JNewt
Joined: 05 Jun 2008 Posts: 69
|
Posted: Fri Aug 21, 2009 4:21 pm Post subject: |
|
|
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 |
|
|
JNewt
Joined: 05 Jun 2008 Posts: 69
|
Posted: Fri Aug 21, 2009 4:45 pm Post subject: |
|
|
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 |
|
|
|