Collision Detection Is Hard
I decided to roll my own physics code, however I have had zero experience in writing professional grade collision code. This destinction here is important. If you are anything like me you read tutorials online and watch YouTube videos explaining stuff. However the stuff which is available on YouTube is not usable in a professional game engine. Let me explain why. Most of the stuff you can find online are only mearly scratching the surface of this topic, but are presented in a way that make you think that after consuming the tutorial that you can go and build your custom collision solution. Unfortuneatly this is not the case. There are so many “game devs” who themselves don’t know what they don’t know about the topic. They will showcase their phyics systems and try to impress you with visuals.
Oh look, how many hecking objects ““my”” code can handle
Most of those “devs” also just copy/pasted code and make it look like they came up with something great.
If you are lucky you will come across more advanced stuff like GJK or some derivative of it. However they will not mention, that GJK is not a silver bullet.
All of the videos I’ve seen only attempt to solve a “static collision resolution”, meaning they just compare objects to check if any are stuck inside each other. They don’t solve for “dynamic collisions” or “continious collision detection”. The moment you realize that static collision detection is really not suitable for player movement, bullet movement, or any movement which does affect gameplay, you understand how screwed you are. People try cope by trying to increase the physics update frequency by 2x, 4x, etc. in order to not miss collisions. However, even if collisions are not missed they are not resolved properly. You don’t JUST want to “uncollide” objects, but you want to prevent penetration. You want to slide along walls, you don’t want to get stuck on corners or geometry edges.
And this is where the journey actually begins. Researching continious collision detection was a painful experience.
I came across a variety of potential solutions. Namely Sphere vs. Sphere CCD, Ellipsoid CCD, etc. Besides an poorly performing GJK CCD derivative I didn’t find anything which did solve generic cases. I did manage to write a custom solution for AABB vs AABB, which actually works really great. It features wall sliding, NOT STICKING TO SHIT, not getting stuck on geometry edges and performing well. However I did not want to limit myself to just AABB collisions. So I had to come up with something more flexible.
At this point I have started digging into Quake 1 source code once again and started researching how they’ve solved it in the 90s. I found some articles and random forum posts about the collision system Carmack wrote for Q1.
“Collision detection was pretty hard,” he admitted. “There was a good period where we were making interesting pictures, but movement only worked smoothly as long as you were sliding along walls with obtuse angles—you would get ‘stuck’ on sharp corners.”
Carmack refined code until he arrived at a solution, albeit not an optimal one. Quake’s collision detection functions by expanding the size of every object on a map by half the player’s size, treating players as a point moving through terrain. “This was robust and extremely efficient, but it meant that each unique size of entity that moved through the world had to have a special version of the map automatically generated for it,” said Carmack. “This cost both memory and processing time during level building.”
I can’t speak for Quake 3, I heard somewhere they were using the brushes, but Q1 definitely uses axis-aligned bounding boxes for the objects and collides them with the BSP tree. The way they do this is that they store 4 different trees, one regular tree used for culling and three collision hull trees, used for 3 different sized objects (missiles, small things, people).
The BSP trees are ‘expanded’ at compile time which means that the collision engine only needs to clip a single line segment into the BSP tree in order to determine whether it is in solid or in space (and also where the collision takes place). The actual technique is a little more involved (requires bevelling) so try searching the web
After reading all that I was a bit disappointed. I did not want to prebake BSP trees and I certainly did not want to limit myself to using only a handful of AABB sizes. I came across a paper by Stefan Melanx about dynamic collisions with BSP trees, where he introduced the concept of shifting planes. Dynamic Plane Shifting BSP Traversal BSP Collision Detection As Used In MDK2 and NeverWinter Nights
I dont want to “push” BSP’s on anyone. For example, if you can bang off a simple robust AABB implementation in a day, and it does what you need, then why not just use that?- Stefan Melax