It has been a while since I shared my knowledge on game engine development. The reason has not been laziness. Quite the contrary, I have been very focused on my Game Engine. But this morning while heading to the gym, I had a desired to share with you a bit about Collision Detection in game engines.
To be honest, the most complicated aspect of a Game Engine is implementing Collision Detection. The difficult part is not the main algorithm. As a matter of fact, the main algorithm for Collision Detection takes about twenty lines of code. The difficult part are the vast amount of peripheral code you need to implement. And this makes a Collision implementation very tricky and time-consuming.
So, I want to share with you some tips that may alleviate the pain of implementing a Collision Detection system in your engine.
1) Get this book Real-Time Collision Detection NOW
There is no way you will develop a Collision Detection System without this book. I couldn't have. It explains everything about Collision Detection but more importantly it provides code snippets that you can use as a reference. This book is about $100 bucks and NO, it is not expensive. Trust me. It will save you hundreds of hours in development.
2) Start Small: Implement Collision Detection with Spherical Bounding Volumes
Collision Detection works by detecting if two bounding volumes are penetrating each other. Each character in a game is wrap with a bounding volume. There are different types of bounding volumes, such as spheres, Axis-Aligned Bounding Boxes (AABB), Oriented Bounding Boxes (OBB), Convex-Hull Bounding volume, etc. Spheres provide the fastest collision detection and are simple to implement, but they are the least precise. Collision Detection with Convex-Hulls are expensive but provide very accurate collision detection.
You may want to implement a Collision Detection system using Convex-Hull volumes and avoid spending time using spheres or AABB. But don't do that. The problem with Collision Detection is that You Don't Know, What You Don't Know.
See, Collision Detection is an art as much as is a science. It is a new language, so to speak. For one, you need to be comfortable with Computational Geometry. Second, you need to familiarize yourself with Collision Detection algorithms. Thirdly, Collision Detection requires a vast amount of peripheral code. Most of them related to Computational Geometry. For example, you need to determine if a point in space lies within a Tetrahedron.
Therefore, Start Small. Implement a Collision Detection system that uses Spheres as bounding volumes instead of Convex bounding volumes. It will not give you a precise collision, but it will help you get comfortable with various algorithms.
3) Start Slow: Implement collision detection with non-moving objects at first
Implementing a Collision Detection System is all about taking baby steps. Is about learning little by little as you fall. Don't rush into implementing a collision detection algorithm suitable for moving objects. All you will be doing is opening a Pandora box. So, start Small and Slow. Implement a Collision Detection System suitable for static objects first.
Unfortunately, the book "Real-Time Collision Detection" does not cover collision detection of moving objects using Convex-Hull volumes. Nonetheless, the book gives you the groundwork necessary for you to implement a collision detection system for moving objects. When you are ready to implement a collision detection system for moving objects, then you need to get a copy of this book Game Physics Pearls.
4) Use a fast language
In other words use C++. I don't want to get into a discussion but if you think Java is fast, then go ahead. If you think Python is fast, then go ahead and implement a Collision Detection System with those languages. But don't be scratching your head if you notice that the detection is slow.
One of the tricky parts of implementing Collision Detection is that you need to determine:
- If a collision has occurred
- And if so, provide a Collision Response as fast as possible.
Therefore, you will need to implement several data structures that will help speed up this process such as the Bounding Volume Hierarchy Tree algorithm and Broad-Phase Detection. Everything in a Collision Detection system needs to be fast and C++ my dear friend, is damn fast.
But if you think another language is faster, then go ahead. (But you should use C++)
5) Collision Detection is all about Computational Geometry, Convex sets and Geometric Algebra
Yep. Collision Detection boils down to knowing Computational Geometry, Theory of convex sets and Geometric Algebra. It is about determining if a point lies in a Convex-Hull. It is about determining on which side of a plane a point is located. Is about determining the closest point to a Tetrahedron, etc.
When I started developing the game engine, I thought that the only math I needed was Linear Algebra. I was wrong. Very wrong. See, when it comes to implementing a Rendering Engine, then you do apply Linear Algebra concepts. But when it comes to Collision Detection, is all about Geometry.
If you didn't take Computational Geometry or Geometry for Computer Graphics class in college, these books may help:
Real-Time Collision Detection
Geometry for Computer Graphics
Computational Geometry in C
6) Use Tolerance when comparing floating-point values
Don't compare floating-point values as if they were integer-point value. For example, this is wrong
if(2.3423==2.3422){...}
Instead, use tolerance to compare floating-point values, like this:
if(areEqual(2.3423,2.3422,epsilon)){...}
Keeping this in mind is paramount. The sensitive nature of the algorithms involved in Collision Detection requires a robust numerical comparison. Else, you may end up missing collisions. I ended up wasting several weeks of development because I didn't follow this advice. In one instance, I had several objects colliding. Everything seemed fine except that now and then, the engine would miss a collision. What made it strange is that it would only happen at particular angles, and it was intermittent. After weeks of debugging, I found the problem. I was comparing floating-point values as if they were integer-point values.
Here is a nice blog post from the author of Real-Time Collision Detection regarding this tip: http://realtimecollisiondetection.net/blog/?p=89
Well, I hope these tips can help you develop a Collision Detection System for your game engine.
