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):
|
1 2 3 4 5 6 7 8 9 |
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.
