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

2018-10-28

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:

https://www.azurefromthetrenches.com/introductory-guide-to-aabb-tree-collision-detection/

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):

Running tree-based benchmark
    Ran 1000 objects 6000 times in 1.845779 sec
    3250660.01942811 objects/sec
    54177.6669904685 per frame @60 fps

Running brute force benchmark
    Ran 1000 objects 6000 times in 6.201839 sec
    967454.975854742 objects/sec
    16124.249597579 per frame @60 fps

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.