spatial partitioning benchmarks

hello serumas,

Not sure if it is of any use but I was thinking of setting out a challenge to flash developers to come up with the fastest/optimal solution to a set simulation.

In prep for this I put together a quick benchmark using a grid.

Something like 5,000 dynamic elements each moving in 2d.

Every frame each element is updated and collision tested against each other.

Was able to getting running pretty quick and that was in flash. So you should be able to smash it's doors in if you are running native.

I used a spatial grid and for 5000 elements get the following stats:

Clear: 1ms; //time to clear the structure

Update: 0ms; //time to update the elements positions (simple velocity x/y and wall bounce)

Insert: 1ms; //time to fill the structure

Query: 1ms: //time to detect collisions (AABB vs AABB true/false only)

So a total of 3-4 ms for 5000 dynamic objects.

Which is quite fast for flash, could probably be optimised further too.

If you are interested I will make an effort to polish up the test and bung it on line so you can see it in action yourself.

So in summary, 5,000 objects collision tested in in 2d in under 3ms when running on the latest flash player on a modern browser.

I think in a real world situation I would probably use a combination of grids and quad-trees. Grids for the dynamic shizzle and quad-trees for the static stuff.