When to Use Collision Detection Methods

Question

I've done some research into different collision detection methods but I don't know when I should be using one over the others. Some I've seen are:

• Continuous Collision Detection (CCD) or Raycasting
• Quadtrees
• Discrete stepping

So for example if I want to shoot a bullet which method would I use? Well I've herd CCD is the way to go for that. But what if I have an unrealistic machine gun that has a huge rate of fire making 100 bullets shot at any given time. I don't know if I should be using a quadtree or be consistent and use CCD or even use something else.

Could I get some clarification on what each method is best suited for? That way I'm confident I'm using the right method for the situation. Also if you know of any other good collision detection methods let me know. Oh and if the dimensions matter I'm talking 2D here.

Thanks.

Answer 1

Quad trees are a totally different thing than the collision method. Quad trees are a form of spatial partitioning. Spatial partitioning helps weed out distant objects when trying to find pairs of colliding objects or testing ray collisions. Spatial partitioning is technically entirely optional, but in practice is required for performance.

Continuous vs discrete determines how often collisions are checked for. Continuous collision detection works without stepping time, instead checking to see when the next collision would occur and telling you what time that collision will be. Some folks also call swept volumes a form of continuous collision detection.

The primary advantage of continuous collision testing is to avoid tunneling. Tunneling occurs in discrete systems because objects are only checked for collision at specific intervals. If an object is small and fast enough, it may be completely on one side of a wall at one time and the next increment it will be completely on the other side. Continuous collision detection also provides more accurate results, as it can tell you the precise moment two objects will collide, while discrete systems only find out about collisions after the objects have penetrated each other.

The primary advantage of discrete detection is that it tends to be much faster and simpler for objects with complex shape or large size. Continuous collision detection requires mathematical descriptions of all objects and their motions and the solving systems of equations, which can be difficult, slow, or outright impossible in many circumstances.

Swept volumes are a way of using discrete detection while solving tunneling. You can take an objects current position and old position and enclose a shape around both of them ( this would be a line if your objects are points, a capsule if your objects are spheres, etc ). It is not as accurate as continuous collision, but simpler.

In general for simpler physics engines, use discrete methods for most objects and use a ray cast (continuous) for bullets. Specific games might need to use continuous or swept volumes more often, depends entirely on the specific game.

For things like your machine gun, consider simply reducing the number of bullets. Players really aren't going to notice 100 individual bullets when you can "cheat" and simply draw a bullet spray wffect and use a much smaller number of rays for actual hit tests.

Answer 2

A lot of shooters tend to use limited range on their bullets making line collision detections instead of using rays. This is quite a bit faster than raycasting because it has an extent. You could also do updated line collision, making smaller lines that move over a few frames to do accurate collisions so you don't get shot and killed as soon as someone pulls the trigger, this being most noticeable on long range weapons such as a sniper.

You can also use a combination of both line collisions and a tree, allowing you to only grab the areas that you know the bullet will be within and check with in those.