search

vrld / HC

General purpose collision detection library for the use with LÖVE.
http://hc.readthedocs.org/
394 stars 47 forks source link

Performance Issues #9

Closed dannyfritz closed 12 years ago

dannyfritz commented 12 years ago

I was wondering about the performance of hardoncollider. I'm currently using it for a tile-based game and noticed it tends to chug along pretty slowly. I have tons of passive objects, and for each active object I add the FPS decreases ~10%.

This program initializes a few hundred passive objects. And then you hit spacebar to add an active object one-by-one. Notice the FPS. http://dl.dropbox.com/u/559759/HardonCollider%20Stress%20Test.love

I haven't done too much snooping around, but I messed around with the initializer's cell_size which had some effect. I wonder if the hashtable bins are properly sized or if this O(n^2) algo is as fast as it can get already.

I might be looking into LuaJIT builds soon.

vrld commented 12 years ago

From the documentation:

[HardonCollider:new()] Choosing a good cell size depends on your application. To get a decent speedup, the average cell should not contain too many objects, nor should a single object occupy too many cells. A good rule of thumb is to choose the cell size so that the average object will occupy one cell only.

[Spatialhash()] Choosing a good cell size depends on your application. To get a decent speedup, the average cell should not contain too many objects, nor should a single object occupy too many cells. A good rule of thumb is to choose the cell size so that the average object will occupy one cell only.

Your cell size if 32x32px, which is smaller than the average object (which is 50x50px). This means that every shape will span four cells. Increasing the cell size results in better performance.

However, the framerate drop when adding new shapes still remains. I think it's because the actual collision detection algorithm - separating axes theorem - is relatively expensive. Furthermore, your test case is not very friendly towards collision detection: each frame every active object collides with at least four other shapes. If that's the case for your game too you might be better off using axis aligned rectangles (i.e. your own detection).

In any case, I am looking into a possible alternative implementation at the moment: GJK. Hopefully this will be a little faster than using the SAT.

dannyfritz commented 12 years ago

Thanks for the info.

However, LuaJIT has helped a ton.

But, I'm still thinking about forking HC and using your spatial hash implementation and removing shapes. Then only allowing non-rotating rectangles that perform AABB checks on each other. 'Flaccid Collider' possibly.

vrld commented 12 years ago

Finally implemented GJK/EPA. The new approach is significantly faster. I think it's the best I can do at the moment ;)

dannyfritz commented 12 years ago

I'm glad you did more performance optimizations. I made Flaccid Collider and it only gave me a 5x performance increase on the stress test I made. Shows me for not profiling I guess.