So my first program was a color line that moved across screen with a beep as it hit the top. Instant haxxor.
There are two parts of collision detection, the first is to detect if something is not colliding and the second is to detect if something is colliding. Generally speaking the second part is slow and takes many calculations. By finding objects that do not interact as soon as possible in the physics system it need to do less hard work later. They are called broad phase and narrow phase.
The focus of this phase is to get a list of all the objects that have no possibility of colliding in the next simulation update.
This is the no broad phase at all option. Loop all objects and check them against each other and if they collide do something. Works for few objects and if the test is really simple.
for(j=i+1; i<numObjects; i++)
collideInfo info = collides(obj[i], obj[j])
Split the world into smaller areas based on some rule. Ex are quadtrees, octrees, bsp trees or any sort of tree really. Insert the object into any cells that it's axis aligned bounding box touch. Build a list of object pairs that occupy the same cells as they need to be tested against each other. Next frame rebuild the data.
Sweep and Prune
- GPG 1: p228-238
Here the focus is on is object A colliding with object B and if so how to we get all the information we need about the collision. What happens when the object's that collides does not matter here, thats the response part of the collision.
Physics for Game Programmers - 2013
Convex Hull Generation - 2013
Sweep and prune - 2007
igCollision - 2007
Collision Detection and Spatial Indexes - 2012