Take the 2-minute tour ×

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
add comment

4 Answers

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.



share|improve this answer
add comment

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
add comment

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
add comment
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



share|improve this answer
add comment

Your Answer


