3D Collision Detection in video games. Part #1

Hey good people,

today I want to give you an insight into the background of computer games. Most of us have experienced that some computer games have a very good collision detection and in some games you

• walk against invisible walls
• you stand at a cliff and you should fall down but you don't
• your bullet for some weird reason does not hit the enemy
• your character can walk through obstacles with parts of his body
• your character drops out of the world :)
• ...

Image Source: here

The question is why this happens? Are the programmers of the games bad? Is that an inherent problem of collision detection? Bad Luck? Slow computers?

To understand the problem and See the video game with different eyes
you need to have a basic understanding how you can detect collisions in 3D video games.

1. What is my objective with this blog post series?
   My objective is not to teach you how to program collision detection. I could, but that is not interesting for most of the gamers. My objective is to give you the basics to understand your video game. I will try to keep all the math out of it... but at some point, one needs a least some math. But I'll keep it simple.

2. Why is this a series?
   Well, the problem of 3D collision detection is quite challenging. But this is not the main reason for the series. The reason is that there is no such thing as " the best 3D collision detection algorithm ". There are many ways to deal this problem and each and every approach has its advantages and disadvantages. And the interesting part of this is that if you know the various algorithm that can be used...

you will, from time to time, recognize which of the algorithms is used in your favorite game.
And this is ,in my opinion, very interesting.

---

---

Part #1: Collision detection by using basic bounding volumes

The first approach that we will discuss today is probably the oldest approach to do collision detection in video games. It is the approach of using basic bounding volumes.

1. What is a bounding volume?
   A bounding volume is a geometric object that surrounds our character completely.
   For example in this image:
   
   Image Source: here
   In this picture, the bounding volume is a cylinder. The bounding volume needs to be so large that the character fits in there no matter how the arms, legs... move. And if the character moves the bounding volume " follows". There are many more bounding volumes that can be used. For example:
   
   Image Source: here

2. How ist the collision detection done?
   Well, the basic idea is to give every object (character, walls, monsters ...) in the game world a bounding volume. And if the world changes, e.g. the character moves, the bounding volumes of all the object are tested for collision. The math behind this computation is not straightforward which is why I skip it here.

3. What are the advantages and disadvantages?
   Well, the advantage is speed. Computing the collision between two bounding volumes is, even for very very old computers, done in no time. Therefore, this method is one of the oldest approaches and is used in many many titles. In the games I like to play that uses this technique is the original Unreal Tournament 1999.

Image Source: here

What is the disadvantage? The disadvantage is precision. Assuming that the collision of a complex character, modeled with thousands of triangles, can be treated like a cylinder is...not very accurate. What can u experience?

• If you walk along walls, you sometimes get stuck for no reason.
• you can not get close to the walls
• in some levels you can walk through narrow passages
  *...

And here is the end of this first walk behind the curtains of video games. In the next part, we will discuss the modern extension of this method. The main collision detection approach that is used in modern games.

Have you ever experienced collision detection failures in games? Have you ever programmed a game and did some collision detection? Even the 2D case? Feel free to comment.