The Steem blockchain was upgraded earlier today. You may experience trouble posting and transacting while the new bandwidth system stabilizes. Read more here.

# 3D Collision Detection in video games. Part #1

in gaming •  last year

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.

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.

Sort Order:
·  last year

Really Amazing Stuff and Beautifully Presented...
Thank you for sharing and have a blessed day :)

it will be a pleasure if you check my blog once...
https://steemit.com/@raja

·
·  last year

·  last year

As a game designer this sounds very interesting, I won't say that I understood everything, or most of it :) but it was an interesting insight in the area I'm not good at.

·  last year

This reminds me, one of my best friends from uni went from physics into computer animation - not for games but for movies and documentaries. The theory is the same though, to simulate collisions and things like hair fluttering while running requires some complicated mathematics. Once the dynamic system is established then the coder can take some of the heavy trigonometry functions and approximate them with computationally lighter polynomials. I used to help him out sometimes with the maths.

Thanks

·
·  last year

y thats basically where I'm coming from as well. Did study math and then went into the computer animation stuff. But later on, I focused on industrial applications of all these algorithms.

·
·
·  last year

:-) my friend is now back into sysadmin and the beauty of flow!

·  last year

I mean I get it though, the object surrounding in a sense allows the ease of the math within the coding to be calculated.

·
·  last year

Yeah and modern CPU and GPU can do linear calculation in no time. This method is only popular for its performance. Most games using this method want to use the time between frames for lighting, physics and other stuff and not collsion detection. But a bad collision detection can result in the bug is showned in the post.

·
·
·  last year

Exactly.... I actually had that happened to me where you actually saw the error show up within the game.

·  last year

Wow.. I've been to 3d rendering, but only for architectural purpose.. I would like to try this gaming 3d... I will keep in touch with your post regarding this blogs.. I hope you post more of this... thanks...

·
·  last year

Thx for your kinda words. There will be more content. And especially some methods from modern games. But will take some time to prepare that post .

·  last year

This is extremely interesting to me. Resteeming so I can come back and read when I'm not so tired.

·  last year

I'm just beginner in this association, i've join to this association 5 days ago. My topic is about YuGioh Duel links. it's themed about card trade gaming.
May i know? Can you tell me why every time i post some thing it's can not to reach \$4. I hope some day my post can be a trending.

Thank you for you all steemit friends for your time

·  last year

Nice post

·  last year

Nice post

·  last year

Really good info i played for a long time and did not know this kind of things

So good to bump in to your profile! I don’t program but I work as a concept artist. Please check out my page and feel free to give me any pointers🤪 so cool to see other people nerding out on design :) https://steemit.com/@reeceypie