Posted: 2007-11-06 12:24
I was curious to see how spatial hashing would improve the efficiency of collision detection on 2d spheres (to be more precise, disks), which resulted in me implementing it to see just how good this magical solution works. I was surprised with the results. For a simple test case (minor variation in sphere size, grid cell size and hash table size tweaked to specific situation) I can test for collisions between many more spheres than I would dare do the old (brute force) way.
I used the hash function from paper titled "Optimized Spatial Hashing for Collision Detection of Deformable Objects" from here. It seems to perform pretty well (I pick z=0, and stubbornly pick p1, p2, p3 to be 549977, 1002049 and 1171301 respectively).
The screenshot shows 600 spheres (actually less since the image is cropped) that are collision-checked.
An explanation for the stats in the upper left corner: the FPS line shows two values (left: 1/frametime, right: number of frames during previous second). The second line shows the number of checks performed this frame / the number of tests if all spheres were to be checked against all other spheres. The fourth line shows the result of the division from line 2, and the third line is the inverse of line 4.
Now to add this to the old crummy 2d shooter I once made... (which suffered from slow collision detection).
.
