Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've been trying to implement a spatial partitioning algorithm in my game, but both spatial hashes and quadtrees aren't what I'm looking for.

My level size is not supposed to have a limit (only Int32 limits). I need a spatial partitioning algorithm that doesn't need a "Level Width" and a "Level Height".

I have many moving physical objects. I need the algorithm to be fast enough to support 500+ objects.

Any alternative?

share|improve this question

4 Answers 4

This is very close to a similar question asked here on Gamedev, but seeing as you're concerned with performance and not file storage, perhaps my answer there will be of more use to you. I'll include the bulk of it here for completeness, but the original answer provides a little more depth if you want to look into it.

I ran into a similar problem and decided to create my own structure to handle the data. It's based loosely on a quadtree, but has infinite (at least as big as an Int) expandability in all directions. It was designed to handle grid-based data which expanded from a central point, much like Minecraft does now. It is space efficient in memory, and very fast.

My code can be found here. The code is complete, tested (unit- and load-tests), and quite optimized. The inner workings aren't too well documented yet, however, but all the public methods are so it should be usable. If anyone decides to try it out, feel free to contact me with questions or comments.

share|improve this answer

Dynamic Tree

Box2D is a well optimized engine designed by an experienced physics/game programmer. Originally Box2D used a hash grid that required a fixed height and width.

When Erin upgraded to a better broadphase algorithm he went with Nathanael Presson's btDbvt. This is the broadphase used by Bullet Physics. Erin modified and optimized the algorithm for 2d.

You can read a super high level overiew in the Box2D manual ( §4.11, or search for Dynamic Tree).

Here's an except from the in code documentation (which is very good considering it's not part of the public API).

A dynamic AABB tree broad-phase, inspired by Nathanael Presson's btDbvt. A dynamic tree arranges data in a binary tree to accelerate queries such as volume queries and ray casts. Leafs are proxies with an AABB. In the tree we expand the proxy AABB by b2_fatAABBFactor so that the proxy AABB is bigger than the client object. This allows the client object to move by small amounts without triggering a tree update.

Nodes are pooled and relocatable, so we use node indices rather than pointers.

My understanding of the Dynamic Tree's algorithm is this. The Dynamic tree is the cross between a classic avl binary tree and a quadtree. The end effect is a quadtree that that only splits each node in half, and the split line isn't fixed (the two halves aren't equal sized like a quad tree). AVL comes in because quadree with dynamic splits can degenerate to essentially a list (O(n) lookup speed). The AVL is used to rebalance subtrees so to ensure O lg(N) lookup speed.

Best of all the code is MIT so feel free to copy / derived / shamelessly-steal / etc.

share|improve this answer
    
Looks... complex! I will take a look at it, though. Someone suggested me using the "sweep and prune" or "sort and sweep" technique but I couldn't find anything about a C# or .NET implementation. I found a c++ example but it's confusing and it didn't work (I tried to implement it anyway). Do you think SAP would be easier to implement? Is there are .NET implementation? –  Vittorio Romeo Jul 24 '11 at 13:59

Maybe the r-tree algorithm is what you are looking for.

I works really well for static geometry, but you can also use it for moving objects by removing and adding objects at their new positions.

share|improve this answer
    
I tried a C# implementation, and the performance was way too bad when "removing and adding objects at their new position". –  Vittorio Romeo Jul 22 '11 at 22:58
up vote 0 down vote accepted

I've decided to go with fixed 2D grids.

I've made two videos which explain in-depth how I implemented them, and the current implementation is available on my GitHub page: https://github.com/SuperV1234/SSVSCollision

http://www.youtube.com/watch?v=7HY_SqqaoL4

http://www.youtube.com/watch?v=vYB37BDtHuQ

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.