Video Game Math: Collision Detection

What is collision detection?

Collision detection is one of the most important pieces of math for a programmer to understand. Why? Games are all about collision.

Virtually everything you do in a game depends on collision. Whether it’s a bullet hitting a target, Mario landing on a platform or coming in contact with a pickup, everything about gameplay comes down to collision. A lesser considered, but still critical, collision problem is intercepting mouse and/or touch inputs to determine whether they collide with UI elements.

As with most things in programming, there’s a lot of factors to consider when dealing with collision. The first factor to consider is accuracy. Mathematically speaking, you can make your collisions as accurate as you want, but the more accurate they are, the more they “cost” in terms of processor time and difficulty in coding. Processor cost is measured in “Checks” – how many discrete checks have to be processed in order to validate the collision (or lack of). These Checks are generally run every plausible object that could collide with a given object, so they tend to be exponentially expensive. Since these happen every frame (at a normal framerate of 60-90 frames per second on most devices), that’s a lot of calculations!

Bouding Box & Radius

Perhaps the easiest to code is “box collision” (also known as “bounding box collision”). This is where you enclose an object in either a rectangle (for 2D) or a rectangular prism (3D) aligned on the Origin’s axes. Using a series of checks, you can easily determine whether any part of one object’s box is overlapping another object’s box. The ease of this method makes it a favorite among programmers for simple things like buttons, walls and instances where “close enough” is close enough. The disadvantage is that checking intersection requires four Checks for 2D and six Checks for 3D. This type of collision is also fairly inaccurate – unless the object has 90-degree corners, there’s extra “space” around it that is within the box but not actually part of the object, leading to collisions being counted even in “near miss” situations.

Slightly harder to code, but much more efficient is Circle collision (also known as “Radius collision”, or in 3D “Spherical Collision”). Circle Collision has the major advantage of being only a single Check – even in 3D – but is usually even less accurate than box collision for the opposite reason. Unless your object is actually a circle (or sphere), circular collision will tend to “miss” corners, leading to situations where “barely hit” means “not hit”.

For most games – such as platformers, puzzle games, and RPGs, a combination of box and circle collision works fine. Precise collision detection isn’t usually as critical for these types of games, and designers usually set any imperfection in the collision system in a way that favors the players rather than hindering them, so it doesn’t negatively impact gameplay.

But what about games like Fighting Games and First Person Shooters? Precise detection is crucial for those games, as players will quickly become frustrated if a “near miss” turns into a headshot, or if they “wing” a bad guy with a bullet but it doesn’t damage them.
How do we solve this?

How do we solve this?

To solve those problems in 2D, we use line collision. Line collision can resolve whether two line segments intersect and doesn’t require that they be at 90-degree angles to the Origin. By drawing a series of line segments around our objects, we can determine whether the two objects collide by checking each segment on one object against each segment on the other. This gives us unparalleled accuracy but comes with a cost – the number of Checks required is the number of segments in one object multiplied by the number of segments in the other object. When you’re dealing with lots of objects, this can get expensive very quickly!

By modifying the line collision algorithm, you can also get an equivalent that checks collision between polygons. Since all 3D models are made of a series of triangles (known as the “poly mesh” or just “mesh” for short), you can check each triangle in the first object’s mesh against each other triangle in the other object’s mesh – but this comes at a whopping nine checks PER triangle! That means to determine the total number of checks, you have to multiply the number of triangles in one mesh times the number of triangles in the second mesh, then multiply the total by nine. Since it’s common for modern models to contain tens of thousands of polygons, that can add up fast!

Because of this, it’s common for programmers to take shortcuts – most 3D models are actually made up of “quads” – two triangles put together into a four-sided polygon. That allows programmers to “cheat” and do fewer checks – but it’s still a very expensive way to go.
Another option is to create a “second skin” on the model and use it as your collision mesh. This second mesh has FAR fewer polygons than the original, but is “close enough” that a player wouldn’t notice the differences. This allows for fewer collision checks to be made but still allows for far more accurate collision than spherical or box collision. Even this method is very expensive, however, so should only be used when the extra accuracy is necessary.

Hybrid Types

“Hybrid types”, such as cylinders, ovoids and other simple shapes can be used in conjunction with the second mesh – these shapes allow for a greater degree of collision than simple boxes and spheres, but still come with faster computational speeds. If you think of the human body in terms of nine cylinders and a sphere (sphere for the head, a cylinder for the torso, and two cylinders each for the arms and legs), you can get “pretty good” collision that is still reasonably efficient.

At the end of the day, the best approach is to figure out how much precision is “necessary” and how much you can “flub” – while accuracy is certainly a thing to be valued, if your computer/console can’t actually run the game at an acceptable frame-rate, you don’t have a game.