Tips For Optimizing Collision

Collision In Computers

In the world of games the logic for detecting collision can either make or break your game. There are many different methods for detecting collision which are dependent on what you are trying to collide. For instance, if you try to collide two squares then you can just see if the left/right/top/bottom side of either shape simply overlaps the sides of the other which is known as AABB collision detection. The same logic applies in 3D space except instead of having to deal with an XY point you have to handle the Z dimension as well. On the other hand, if you want to collide two circles or spheres then you need to check to see if the distance between the centers of each circle (or sphere in 3D) is less than the radius of the two shapes. 

These are pretty simple scenarios, but collision can become rather complex when you have to begin dealing with collision between different shapes such has colliding a square with a circle. You cannot use the circle collision logic because that logic breaks if the square is rectangular and the distance to each side of the square from the center is not constant. You cannot use the AABB logic because that relies on the left/right/top/bottom points which would trigger a collision if the square moved into the empty corner spaces of the circle. 

The solution for this scenario is not all that complicated, but my intent was to just explain that collision isn't always straightforward. These algorithms may or may be computationally expensive and in order to keep the game performing well we only want to check for collisions when we need to.

But How Can I Check For Collisions Only When Necessary If I Need To Be Checking Constantly?

It might be hard to comprehend how you can only limit collision when every object needs to be ready to respond to a potential collision with every other object, and it might be actually difficult to improve in some scenarios, but we should take a step back and really analyze the requirements for the game to see if there are areas for improvement.  

Group Objects Into Trees

There may be opportunities to group objects together to assist which detecting which object was collided with faster similar to searching a word in a dictionary using the index. How the collision manager works in a game (in a nutshell) is that for each object in the game that has collision enabled it will look at every other object in the game and see if they are actively intersecting with each other. Consider a game that has 1,000 objects that are all supposed to be able to collide with each other, that's 1,000,000 collision checks all of which have their own methods collision detection.

What we can do to improve this is to group these objects into trees (as the heading suggests). Imagine there are 3 stacks of boxes and each stack has 100 boxes. That means there are 300 boxes and using the previous logic of everything can hit everything that means there are currently 90,000 iterations each frame. If we instead child each stack under some parent object known as the root, then at idle we've reduced the number of computations each frame (ideally 60 frames in a second) from 90,000 down to 9. Those savings are huge! When the collision manager detects a collision between any of the objects it can then begin going through the list to try and pinpoint where the collisions happened. Currently that would mean at least 10,000 potential checks, but there can be additional groups in each stack to improve this to reduce this significantly. In the Realtime Architecture class at DePaul, using this method was the beginning of implementing Double Dispatch to program specific code for specific collisions, but that's a bit much for this post.

***I keep saying collision, but collision is specifically used for physics and shouldn't be confused with intersection which is generally what I mean

Add State Flags

So adding our objects into trees is pretty powerful, but there is always more that we can consider adding. We can add flags representing the state (if collision is allowed or not). This can be something as simple as a flag called isAlive or even collisionEnabled. It's really up to you. Actually, with trees when the object is removed from the tree that will be one less object that is processed which is nice but there might be scenarios where you don't want collision while it lives in the tree such as playing an effect to destroy the object after a collision. If you remove the object from the tree you could be potentially removing the effect from the game as well. You can add some logic into your collision manager to skip over any objects that are "dead" to improve performance.

Use Layer Masks

Depending on how your collision is setup you may either be specifying pairs of objects that will only be checked for collision with each other (think the trees of boxes) with each other or the collision manager might be check for collision with every object against every other object. If the method is the latter and you want to implement something that functions like the former such as boxes can only collide with other boxes and balls then layer masks can help with that. A layer mask is essentially a bunch of flags combined into a single value. The long painful way for implementing what we want to do is by adding a bunch of flags (canCollideWithBox, canCollideWithBall, etc. etc.) onto each of our objects that has collision enabled. Over time this will be painful and hard to manage. Instead we can capitalize on the fact that data is made up of a number of bits.

A variable is made up of a series of bits and with this knowledge we can assign each layer a single bit. We can combine multiple bits to create an integer that represents each layer that we want that object to be able to collide with. When the collision manager is processing the objects it will look at the layer mask each object is assigned and check what layer the object that it is potentially colliding with is on. Although we haven't reduced the number comparisons that are being processed that frame, we have limited the number of times the potentially expensive (computationally resource intensive) collision algorithms will be executed.

Avoid Square Root In Distance Check

This is just a small note about distance checking for circle/sphere collision that is applicable to any sort of distance check, but something that I never considered until my 3D Geometry (Linear Algebra) class this past quarter was to square the number that I was checking the distance against. The distance formula is the square root of the sum of all the coordinate values of the position (XYZ). The issue is that calculating the square root is very expensive and shouldn't be done repeatedly often. Let's say we wanted to see if the distance of Point A from the origin is within 5 units. Instead of doing the square root of the sum of the squares, what we can do is square 5 (which is 25) and see if the sum of the square of the points is less than 25. The result would be the same as applying the square root and checking if it is less than 5.