Jump to content
  • Advertisement
Sign in to follow this  

spatial partitioning benchmarks

This topic is 2119 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Year ago I have made VERY simplified and hacked grid partitioning algoritm.

Now I just want to know is it fast.


Could someone give me benchmarking info(obj count) and stats(ms), or even benchmarking application (made with cpp with no multitasking) what I could recreate situation and compare my results with yours? It can be any algorithm (sap,quadtree,uniform frid,...).


If it stupid thing, please suggest how to test the algorithm.

Edited by serumas

Share this post

Link to post
Share on other sites

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.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!