Guide to Game Development/Theory/Collision detection

Collision detection is split up into two parts: broad-phase and narrow-phase. Broad-phase finds the objects that need to be checked, narrow-phase actually checks for a collision of objects.

Broad-phase

This is the method of checking which objects need to be checked. This basically means that if an object is too far away, then this test will say that the object doesn't need to be tested for collision detection. This is because the actual collision detect is resource heavy, so eliminating the amount of objects will mean that there are less calculations that need to be made.

Here are the different types:

• Sweep and Prune

• QuadTree partitioning

• BSPTrees

• SphereTrees

• Spatial partitioning

• Object partitioning

Narrow-phase

This is the accurate collision detection that is resource heavy (compared to broad-phase).

• Discrete vs. Continuous

Demonstrating the differences between discrete and continuous collision detection.

Types

• AABB intersection

Axis-aligned bounding box (only works for items aligned to axes, but you can translate them, perform the test and translate them back).

• OBB intersection

Oriented bounding box.

• Separating axis theorem

The idea of creating new virtual axes based upon your geometry and comparing them.

• Circular

Circular collision detection.

• Ray casting

A linear vector equation with a limit that goes through the air to check for a collision of sorts.

• Mesh

This is where you actually test for collisions of an object exactly, you build a mesh of polygons around the object and check for collisions around that.

External links

• "Collision detection for dummies."