Game::Collisions v0.1 – Fast 2D collision detection

Some years ago, I wrote a little top-down shooter in Perl. It was not a good game, and was never released, but I learned a lot making it. One problem I encountered was collision detection. Checking every object for collisions against every other object is not feasible past a small size. Especially in pure Perl, since this is a straight numeric problem, but it’s still a struggle for C to do it.

We have faster processors now, so the number of objects you can throw in there has increased a lot. Still, it’d be better to have a faster algorithm than brute force. The typical choice is to use a binary partition tree to split up Axis Aligned Bounding Boxes. This lets you do very fast collision detection even with gigantic lists of objects. I won’t go into detail here, as there’s an excellent blog post that already goes into it:

Most likely, you would use this to quickly prune the list of possible collisions (“broad phase”), and then use more expensive techniques to get pixel-perfect (“narrow phase”).

This is what’s implemented in Game::Collisions v0.1. Here’s some benchmarks comparing the tree-based technique to brute force (running on a modest laptop CPU, an Intel i7-6500U):

This creates a tree of 1000 leaf objects and then gets all the collisions for a specific AABB. As the number of AABBs increases, we would expect brute force to go up linearly, but the tree method to go up logarithmically, so these numbers will get further apart as the tree grows.

Website Pin Facebook Twitter Myspace Friendfeed Technorati Digg Google StumbleUpon Premium Responsive

Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

This site uses Akismet to reduce spam. Learn how your comment data is processed.