Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

How exactly does a collision engine work?

This is an extremely broad question. What code keeps things bouncing against each other, what code makes the player walk into a wall instead of walk through the wall? How does the code constantly refresh the players position and objects position to keep gravity and collision working as it should?

If you don't know what a collision engine is, basically it's generally used in platform games to make the player acutally hit walls and the like. There's the 2D type and the 3D type, but they all accomplish the same thing: collision.

So, what keeps a collision engine ticking?

share|improve this question
3  
You can cheat with bounding boxes and spheres, the intersection of which is fast to determine. Then you can inspect more closely. cs.unc.edu/~dm/collision.html en.wikipedia.org/wiki/Collision_detection You can always do this slowly with a naive algorithm. Comp Geometry has some tricks that take advantage of the geometrical nature of the problem and makes the algorithm faster. Here is a very good paper: cs.hku.hk/research/techreps/document/TR-2005-01.pdf –  Job Mar 24 '12 at 14:35
    
what is a collision engine? –  gnat Mar 24 '12 at 14:42
3  
@gnat a collision engine is basically an engine used in games (generally) so that your player (call him bob), whenever bob moves into a wall, bob stops, bob does not walk through the wall. They also generally handle the gravity in a game and environmental things like that. –  JXPheonix Mar 24 '12 at 15:13

6 Answers 6

up vote 94 down vote accepted
+250

I feel this question is a little broad for the StackExchange format, but here's the gist of things:

First, there is a big difference between a collision engine and a physics engine. They do not do the same thing, although the physics engine generally relies on a collision engine.

The collision engine is then split into two parts: collision detection and collision response. The latter is generally part of the physics engine. This is why collision engines and physics engines are usually rolled into the same library.

Collision detection comes in two forms, discrete and continuous. Advanced engines support both, as they have different properties. In general, continuous collision detection is very expensive and only used where it is really needed. The majority of collision and physics is handled using discrete methods. In discrete methods, objects will end up penetrating each other, and the physics engine then works to push them apart. So the engine does not actually stop a player from walking partially through a wall or the floor, it just fixes it up after detecting that the player is partially in the wall/floor. I'm going to focus on discrete collision detection here, since that's what I have the most experience implementing from scratch.

Collision Detection

Collision detection is very simple. Every object has a transform and a shape (possibly multiple shapes). At the simplest, the collision engine just does an O(n^2) loop through all object pairs and tests if there's overlap between the pairs. On the far end, there are multiple spatial data structures (e.g., for static vs dynamic objects), a bounding shape for each object, and multi-part convex sub-shapes for each object.

The spatial data structures include things like KD-Trees, Dynamic AABB trees, Octrees/Quadtrees, Binary Space Partitioning trees, and so on. Each has their advantages and disadvantages, which is why some higher end engines use more than one. Dynamic AABB trees for instance are really really fast and good for handling lots of moving objects while a KD-Tree may be more suitable for the static level geometry that objects collide with. There are other options as well.

The broad phase uses the spatial data structures and an abstract bounding volume for each object. A bounding volume is a simple shape that encloses the entire object, generally with the goal of enclosing it as "tightly" as possible while remaining cheap to do collision tests with. The most common bounding shapes are Axis-Aligned Bounding Boxes, Object-Aligned Bounding Boxes, Spheres, and Capsules. AABBs are generally considered the fastest and easiest (Spheres are easier and faster in some cases, but many of those spatial data structures would require converting the sphere into an AABB anyway), but they also tend to fit many objects rather poorly. Capsules are popular in 3D engines for handling character-level collisions. Some engines will use two bounding shapes, such as an AABB for the first level of detection and then an OABB or Capsule for the second.

The last phase of collision detection is to detect exactly where the geometry is intersecting. This usually implies using the a mesh (or a polygon in 2D), though not always. The purpose of this phase is to find out if the objects really truly do collide, if a fine level of detail is required (say, bullet collision in a shooter, where you want to be able to ignore shots that just barely miss), and also to find out exactly where the objects collide, which will affect how the objects respond. For example, if a box is sitting on the edge of a table, the engine must know at what points the table is pushing against the box; depending on how far the box is hanging over, the box may begin to tilt and fall off.

Contact Manifold Generation

Algorithms used here include the popular GJK and Minkowski Portal Refinement algorithms, as well as the simple Separating Axis test. Because the popular algorithms typically only work for convex shapes, it is necessary to break many complex objects into convex sub-objects, and do collision tests for each individually. This is one of the reasons why simplified meshes are used for detailed collision, as well as the reduction in processing time for simplified geometry.

Some of these algorithms not only tell you that the objects have collided for sure, but where they collided -- how far they are penetrating each other and what the "contact points" are. Some of the algorithms require additional steps, such as polygon clipping, to get this information.

Physical Response

At this point, a contact has been discovered, and there is enough information for the physics engine to process the contact. The physics handling can get very complex. Simpler algorithms work for simpler games, but even something as simple as keeping a stack of boxes stable turns out to be quite difficult and requires a lot of work and non-obvious hacks.

At the simplest level, the physics engine will do something like this: it'll take the colliding objects and their contact manifold and calculate the new positions required to separate the collided objects. It will move the objects to these new positions. It'll also calculate the velocity change resulting from this push, combined with restitution (bounciness) and friction values. The physics engine will also apply any other forces acting on the objects, such as gravity, to calculate the objects' new velocities, and then (next frame) their new positions.

More advanced physics response gets complicated quickly. The simple approach above will break down in many situations, including one object sitting on top of two others. Simply dealing with each pair by itself will cause "jitter" and the objects will bounce around a lot. The most basic technique is to simply do a number of velocity-correction iterations over the pairs of colliding objects. For example, with a box "A" sitting on top of two other boxes "B" and "C", the collision A-B will be handled first, causing box A to tilt further into box C. Then the A-C collision is handled, evening out the boxes somewhat, but pulling A down and into B. Then another iteration is done, so the A-B error caused by the A-C correction is slightly resolved, creating a bit more error in the A-C response. Which is handled when A-C is processed again. The number of iterations done is not fixed, and there is no point at which it becomes "perfect," but rather just whatever number of iterations stops giving meaningful results. 10 iterations is a typical first try, but it takes tweaking to figure out the best number for a particular engine and a particular game's needs.

Contact Caching

There are other tricks that turn out to be really handy (more or less necessary) when dealing with many types of games. Contact caching is one of the more useful ones. With a contact cache, each set of colliding objects is saved in a lookup table. Each frame, when a collision is detected, this cache is queried to see if the objects were previously in contact. If the objects were not previously in contact, then a "new collision" event can be generated. If the objects were previously in contact, the information can be used to provide a more stable response. Any entries in the contact cache that were not updated in a frame indicate two objects that separated, and a "separating object" event can be generated. Game logic often has uses for these events.

It's also possible for the game logic to respond to new collision events and flag them as ignored. This is really helpful for implemented some features common in platforms, like platforms that you can jump up through but stand on. Naive implementations may just ignore collisions that have a downward platform->character collision normal (indicating the player's head hit the bottom of the platform), but without contact caching, this will break if the player's head pokes up through the platform and then he begins to fall. At that point, the contact normal may end up pointing upward, causing the player to pop up through the platform when he shouldn't. With contact caching, the engine can reliably look at the initial collision normal and ignore all further contact events until the platform and player separate again.

Sleeping

Another very useful technique is to mark objects as being "asleep" if they are not being interacted with. Sleeping objects do not get physics updates, do not collide with other sleeping objects, and basically just sit there frozen in time until another non-sleeping object collides with them.

The impact is that all the pairs of colliding objects that are just sitting there doing nothing don't take up any processing time. Also, because there is not a constant amount of tiny physics corrections, stacks will be stable.

An object is a candidate for sleeping when it has had a near-zero velocity for more than a single frame. Note that the epsilon you use for testing this near-zero velocity will probably be a bit higher than the usual floating point comparison epsilon, as you should expect some jitter with stacked objects, and you want whole stacks of objects to fall asleep if they're staying "close enough" to stable. The threshold will of course require tweaking and experimentation.

Constraints

The last major bit of many physics engines are the joint/constraint resolution engines, but I believe that goes beyond your initial question. The purpose of such systems is to facilitate the implementation of things like springs, motors, wheel axis, simulated soft-bodies, cloth, ropes and chains, and sometimes even fluid (though fluid usually is implemented as an entirely different system).

Even the basics of this stuff gets very math-intensive, and there are already good articles on this site going over that stuff.

share|improve this answer
11  
Wow! This answer was amazing. Thanks a lot! –  JXPheonix Mar 30 '12 at 23:07
    
if your going to address the minimum number of collision resolutions then you should probably also address the need to keep the number as low as possible considering that in a complex setup allowing a high number of collision reposes will greatly decrease frame rate. then when you were talking about the number of iterations was that per pair, or was that for all collisions. –  gardian06 Mar 30 '12 at 23:46
1  
@gardian06: it's a quickly written overview, sure it could be expanded quite a bit. i forgot to mention object sleeping, for instance, which is pretty darn useful. for the iterations, I iterate over all collections of pairs, and even with relatively large iteration counts (20+) I've never noticed a performance problem (but again, that's with object sleeping, so a relatively small number of active collisions to resolve). –  Sean Middleditch Mar 30 '12 at 23:56

The general problem: determine which of all the possible combinations of objects has a nonzero intersect volume.

The naive, general approach is simple: For each possible pair of objects, compute the volume of intersect. This is usually not practical, since it requires O(n^2) relatively expensive intersect operations.

Hence, practical implementations are often specialized, making certain assumptions to allow the avoidance of intersect checks, or reduction of their cost. Spatial partitioning takes advantage of the fact that objects are typically small relative to the total volume, and will typically reduce the number of comparisons to O(n log n). Axis-aligned bounding boxes and bounding spheres provide inexpensive coarse intersect checks, as long as objects obey certain compactness assumptions. And so on.

share|improve this answer

One "collision engine" I used felt extremely easy to grasp.

Basically, API provided a kind of objects having method collidesWith, such that

  1. its parameters were different kinds of objects that were "eligible" for collision
  2. it returned true or false depending on whether collision happened or not
  3. there was an option allowing to choose whether all the bounding rectangles for the objects trigger collision event or only opaque pixels within these rectangles (pixel-level detection)

In my application, I just periodically invoked collidesWith to find out whether collision happened or not.

Pretty simple isn't it?


Maybe the only thing that required a minor stretch of imagination was when plain bounding rectangles were not sufficient to simulate geometry of colliding objects. In this case one would simply have to use several collidable objects instead of one.

Generally, when you find out that single collision rectangle doesn't do what you need, you invent a way to decompose things to more rectangular sub-elements so that when combined, these elements simulate / approximate desired behavior.

  • End users just don't care how many objects are there behind the scene. They're happy as long as end result feels about like they expect, eg like a house with a backyard fence around it:

    http://i.stack.imgur.com/4Wn5B.jpg

share|improve this answer

At the graphics-card level (where you're dealing with usually triangles), the general idea is to partition your scene in some way so you don't have to check all N triangles (this can be done as a pre-processing step), and then figure out where you are in the scene and check only those 10-50 triangles in that partition.

See BSP and Kd trees for more info. There are also other partitioning approaches.

share|improve this answer

I think you are a little confused on what you are talking about, and are talking about a few different things.

the ability to say that this item is moved from location X to location Y is based on the physics (this also attacks how they move, and why they move)

the method that is used for collision detection is determined based on the structure of your game. if your game is a large open world then you should greatly consider Space partitioning (quad-tree [oct-tree for 3D], BSP, a traditional Grid, or the old fashioned test everything approach)

the best way to implement a collision detection system is to do so in steps.

  1. place all objects into a generic bounding volume/shape, and then test those

  2. if 1 passed then repeat with a more complex volume/shape repeat until ready to test absolute geometry

  3. test absolute geometry the number of time you repeat step 2 is to be determined on the complexity of your shapes, and how accurate those shapes are.

you should consider each of these steps to be early out, and to be for the purpose of eliminating collisions as you go, and only returning true on step3 if they really are touching.

Then for the last part is collision resolution. this determines what happens after you find a collision and have proven that it really is a collision, and what to do about it. this is usually handled by the physics.

the traditional loop looks like this:

receive input
update physics
collision detection
collision resolution
render
repeat
share|improve this answer
    
I'd just like to point out that it's rare that game engines will go into testing absolute geometry for collisions. Usually the algorithm will only go as far as step 2 in your outline. –  ktodisco Mar 30 '12 at 21:56
    
Most game engines test absolute geometry in many (not all) cases. Without doing so there will be very very obvious "glitches" in the physics response. Most engines will have a simple broad phase (spatial partitioning), a simple bounding volume test (AABB most commonly), and then (when necessary) a simplified geometry test (e.g., not the same geometry as the full-LOD rendering geometry, but still raw geometry that is likely one of the low LOD versions of the rendered mesh). –  Sean Middleditch Mar 30 '12 at 22:40
    
@seanmiddleditch that was more of my intention being that an approximation would be tested usually trying to avoid testing concave polygon/polyhedrons. –  gardian06 Mar 30 '12 at 22:52
    
@ktodisco it depends on the concavity of the figure, and how accurate it needs to be, and then what needs to be returned for the physics system to resolve the collision as this can vary based on the physics engine, and the intended accuracy of the response –  gardian06 Mar 30 '12 at 22:54
    
@guardian06 seanmiddleditch's explanation is a lot more feasible, though testing for absolute intersections between characters made up of thousands of polygons is still not a good idea. –  ktodisco Mar 31 '12 at 0:48

Firstly, I think a collision engine's most important job is to determine what doesn't need to be checked for collision in any particular situation on a frame by frame basis and cull those objects from further checks.

Secondarily, but also important, check in a more detailed (accurate) fashion against the remaining objects that weren't culled in that first step.

Thirdly, utilize the most efficient/appropriate methods to perform the checks.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.