Collision Detection, Part 1

For today's post I will be getting closer to the bare metal of game design and discuss one of the cornerstones of video game programming: collision detection. Collision detection has been around since the beginning of real-time video games and has remained an ever-present mechanic of video games of today. I will be discussing some of the theory and practical application of collision detection, beginning with early two-dimensional side-scrollers and gradually moving on to more advanced three-dimensional techniques.

In the days of the original NES (Nintendo Entertainment System), collision detection was usually the most computationally expensive aspect of a game. When the old 2-D side-scrollers would lag from having too many objects on the screen at once, it was mostly from having to calculate all of the possible collisions. The reason for this is fairly obvious: every object that could collide with the player with some direct effect warrants a separate collision check. As more objects fill up the screen, more collision checks have to be made every frame. With the limited computing power of the NES a few dozen collision checks every frame (if that) was enough to cause noticeable lag.

Most collision detection algorithms revolve around the concept of a "hit box." A hit box is a simple shape (usually one or more rectangles, occasionally circles as well) that is roughly the same shape as the actual object. Hit boxes allow the in-game sprites or models to remain detailed without hindering the collision detection algorithms with needlessly complicated objects. The original hit boxes were, naturally, as simple as can be: a single rectangle.

Two objects are considered to be colliding if one or more edges of one object crossed with an edge of another, or if one object completely encapsulated another. Of course, actual collision detection algorithms use simpler calculations for the sake of speed. (To avoid repetition, all the following examples will only discuss colliding along a single axis. Each calcuation will necessarily need to be done for each dimension.) One such method is comparing the location of the right edge of one hit box with the left edge of the other, and vice versa. If the location of the right edge is less than the location of the left, there is no collision. Alternatively, one could compare the difference between the location of both object's left edge with the width of the left-most object's hit box. If the difference is greater than the width of the left-most object's hit box, there is no collision.

As mentioned before, hit boxes aren't limited to just rectangles. Although requiring more computation, circles provide a form of hit box that requires only a single check to be made regardless of the game engine being in two or three dimensions. This can make collision detection faster and less error-prone in three-dimensional environments than even simple boxes. The more straight-forward method of collision detection using circles or spheres as hit boxes is to calculate the distance between the two objects' centers and compare that to the combined radii of the two. If the sum of the radii is greater than the distance between centers, there is a collision.

Unless spheres are used as hit boxes, collision detection gets more complicated during the move from two dimensions to three. The simplest way to do 3-D collision detection with rectangular boxes is with a single cube-shaped hit box that doesn't change orientations (unlike the actual object, which can rotate freely). With this simple approach, collision detection becomes the same as using a single rectangle in 2-D with an extra check for the extra dimension.

Of course, with simplicity comes inflexibility. If the object this rectangular box is supposed to represent is a person, one runs into the problem of appendages either being ignored or causing the hit box to be expanded to occupy a lot of air in order to encompass them. To more accurately detect collisions, groups of free-rotating three dimensional hit boxes need to be used. At this point, the algorithms to detect collision cease being simple and fast.

In the next update, I'll be discussing some optimizations to speed up the collision detection process, as well as a brief explanation of hit detection used in shooter games to detect whether or not a projectile has successfully hit its mark.