Custom AABB collision boxes for an entity tutorial

Introduction

This article will probably appear very technical and it relies on understanding object orientated programming to comprehend it in full detail, but don't fret, my target audience of this article is not the hardcore programmer.

In this article I will try not to be too abstract - abstraction is to a certain degree unavoidable due to the nature of programming - aid you with images that visualizes the concept and keep the details simple.

First I will explain the issue and what caused the need for a solution, I present 3 solutions.
Then I will go over the solution as a concept - I expect it should be enough for a programmer to implement it.
Finally I leave room for the potential of a more technical walkthough with code, should it be requested by you

The problem and solution

In Update #23 I wrote about how the collision system didn't work as I expected it would for the Getsuga attack. This tutorial aims to solve the problem in general, but uses the Getsuga attack as an example, so I would recommend reading it to get a better understanding of the issue.

The collision system in Half-Life uses Axis-Alligned Boundary Boxes (AABB), that works pretty well with spheres and squares and to some degree also rectangular boxes and cylinders. (read more on different collision systems here)

A good example is the player character which is Width:32, Length:32 Height:72. As the character only rotates around the upward axis, the AABB doesn't have to change since the player model is fully encapsulated with insignificant error.
If the character on the other hand had to bow or make cartwheels (rotation around a shorter axis, i.e. width or length) the AABB would have to change accordingly. However, due to the use of AABB it can only encapsulate the rectangular/cylindrical object tightly when the long axis parallel to the x, y or z axis (rotation with 90 degrees), the more diagonal the rotation is between the axis the resulting AABB will take the shape of a square.
That is a similar issue I had with the Getsuga, as the rotation would be around a short axis and not limited to only 90 degrees; additionally the model is more like a plane than a cylinder.

There are 3 primary ways to handle it:

1. Live with the margin of error, this can in many cases be acceptable and performance wise the best solution.
2. Split the collision box up into smaller collision boxes. This suffers from the same limits of AABB, but can decrease the error significantly on the cost of performance
3. Make your own collision system. Many collision systems uses AABB for broad collision detection and then uses an Orientated Boundary Box or some other detailed collision detection to determine if the collision actually occurs. The catch, detailed collision detection takes more performance and you would have to use a lot of time to write the system. Should you be interested in this approach, then you can use the CBaseEntity::Touch(*CBaseEntity) function to call your custom collision detection system.

The solution I went with was number 2, as I wouldn't be satisfied with solution 1 and certainly don't have the time for solution 3.

In the image below you can see the problem and solution shown in 2D.
In the top you see the original AABB and in the bottom you see the solution of filling the object with smaller AABBs.

Something that is important to keep in mind is the direction of movement the object will take. It could be all directions for a player character or AI, while a rocket or similar primary direction is forward.
If you look at the left top shape and consider the top(Y direction) to be its front, then depending on the object's speed we can argue that AABB is alright.
However, turn the object 45 degrees and you get the result on the right. Now it is colliding ahead of the visible object and even far behind. Players would not expect this behaviour, and damage based on range would not be inflicted correctly.

Have you noticed that there are a lot of red squares in the solution?
All these squares are the new collision boxes, they are actually a CBaseEntity object with some extra data - you can read more about that in the next section.
But each of those requires memory and CPU, they are all individually another collision detection check.
Fortunately AABB is fast to calculate. Yet for Half-life I found it to be wise to stay below 10 collision boxes for the Getsuga attack. The number depends on how many Getsuga's we can expect in the air at the same time and still stay below 1200 entities. The number can be increased, but there is a high risk of performance drop at that rate.

I believe the best solution would be to implement solution 3 (custom collision system), with an orientated boundary box, given one has the time for it. Keep the above in mind and analyse ahead, are you going to one or multiple objects with this issue? are all the collision boxes in need of independent functionality or can they just call the same function. Finally don't forget that you can implement solution 2 in solution 3 if you need it, ex for concave objects.

Solution concept

In this section we are going to have a closer look at how solution 2 is implemented. This section is highly related to Half-Life, but there is nothing that prevents you from using that outside of half-life.
I have tried to keep the concept description to two images, a class diagram and a flow diagram. Knowing UML and OOP/OOAD is generally helpful in this section, but I will try to describe the concept in text - if you are not familiar with these diagrams then just try to use them as a visual aid and don't worry too much about the details in them.

First I will present the classes so it makes some sense even if you are unfamiliar with the structure of Half-Life.

Half-Life is build in a way that sort of splits the object in to several main sections and for each of those sections is a base class that a lot of classes derives from. A derived class can do the same thing as the class it derives from, and the easiest way to think of it is that the derived class is the class it derives from plus the additional elements there is added in it.
Of course this can make things slightly difficult work as you usually will have to make a specific function to handle certain classes in a different way than others or otherwise convert them to a base-class.

Ex: the Grenade/satchel/smoke (all in CGrenade) ,our practice-dummy (CBaseDummy) and the player-class (CBasePlayer) are all a CBaseMonster, we say that CBaseMonster is their base class.
That means the grenade, dummy and the player are all a "monster", they have all the functionality and variables that CBaseMonster has. (who had though a grenade was considered a monster?...)
If I have a function that wants to take a grenade, dummy or player as input, I could write 3 functions, or i could simply take CBaseMonster as reference and use the variables written in here.
If the variables and functions I need are all in the dummy, grenade and player class, but not in the monster class , then I will have to move those variables and functions into the monster class so I can reference them.
In implementing the collision box I do the same thing with the CBoxFunc(*CBaseEntity) as the getsuga and the cero will have CGrenade as their base class.
The benefit from taking the base reference is that you don't always have the ability to predict what class it is, this is also the reason why the collision functions Touch(*CBaseEntity) and CBoxFunc(*CBaseEntity) functions takes the very base class possible, as it is impossible to know what class our attack might collide with.
The second benefit is that the derived class getsuga (CGetsugaRocket) can define the CBoxFunc(*CBaseEntity) and that function will be used instead of the one in the base class. (this will make better sense when you see the flow diagram)
I could go into more detail, but I digress, this is not a lecture in object orientated programming.

This image shows a very simplified class diagram.

First some clarification:
CCero and CCeroRocket are imaginary classes to aid in the understanding of why it is made the way it is.
CCero and CGetsuga are luncher that create their respective rockets: CCeroRocket and CGetsugaRocket.
CCeroRocket and CGetsugaRocket each holds a set of collision boxes (CCollisionBox)
The collision detection is made in the engine and call the Touch(*CBaseEntity) function, this function is in the CBaseEntity class, meaning that all objects has an AABB.

In regards to the collision detection in CCeroRocket and CGetsugaRocket, I simply ignore the Touch(*CBaseEntity) (I will get back to that in the Final notes section), and instead uses the Touch function in the CCollisionBox. The CCollisionBox then calls Owner->CBoxFunc(object reference). We don't know if the Owner is CCeroRocket or CGetsugaRocket and we don't care, because they are derived from CGrenade so we know there is some definition for CBoxFunc, and that is all that matters for the program.

The following image shows the process of a collision detection.

In the Touch function there will be code that determines if the collision is valid. Ex did we collide with a collision box from our own object?, if yes, then ignore, else tell the collision box we collided with that we hit it. (Half-life collision detection is sequential and doesn't ensure that both of the colliding objects are triggered - we have to do that, otherwise it will only destroy one object).
If we already did collide with something valid, then ignore any further calls (and prevent crashes).

If a collision was valid the CBoxFunc(object reference) will be called, and depending on whether the function is defined or not the CBoxFunc will either run from the CGrenade object or one of its derived classes.

And that is basicly how it is possible to handle the collision detection with custom collision boxes.

Final notes

I left out a lot of details and some of them also argue for why I chose CGrenade as the base class for the CBoxFunc. One of the reasons I chose CGrenade is that not all objects should hold a custom collision box in our situation, the only thing that needs it are the ranged attacks where the traditional AABB ( Touch() ) is insufficient. This saves memory on runtime as not all object will hold additional variables and functions like CBoxFunc() - It was however necessary to put the CBOwner reference into the CBaseEntity, as you can collide with everything, and if it had a collision box then we needed to get the reference for validation check.

There are however, a completely different way to do this and it could potentially improve the functionality of the collision box. That is, saving the function that the collision box should call as a reference. Instead of just being able to use CBoxFunc() we could provide any function that acts the same way.
This could be really cool as the edge of getsuga then could use a different function than the center of the getsuga, this function could then check if the element it hit was a wall, and spawn sparks, while doing something different to the player, either blow up like the center would or perhaps just give a little damage, but fly on.

I tried to make this work before I wrote this tutorial, unfortunately it didn't work because the function created a new object (CGetsugaRocket) and ran the function from it instead of running the function from the referenced rocket as I thought it would. However, if the function also was provided the reference to a CGrenade then any variable I might need for these functions, could be stored in CGrenade and thus provide the collision box with more flexibility.

So how is that made? Well that is rather complicated, and the easiest way is to copy the implementation of the Touch(*CBaseEntity) and SetTouch(a) definition from the CBaseEntity class.
In the last section I wrote that I simply ignore the Touch(*CBaseEntity) in CCeroRocket and CGetsugaRocket. That is done by setting the Touch function to Null with SetTouch(NULL). It means that the Touch function will call nothing. Before I made the collision box it would have been something like SetTouch(RocketTouch) and it would call RocketTouch(*CBaseEntity).

Copying the definition into the CCollisionBox and then adding an extra parameter of CGrenade to the function would potentially make it work. I haven't tried it as the implementation is a bit complicated and I didn't want to make a function that took its own reference as reference - it felt silly at the time, especially if I'm only going to make a few weapons that ends up using it.

A more simple way could be to make a set of functions like CBoxFunc1 , CBoxFunc2 etc... and then provide the collision box with an int that is stored to select the appropriate function when the time comes. That is an ugly way of doing it, but it is simple and will suffice if the solution doesn't have to scale into a large set of different functions.

These words took a lot of time to write, so I hope I provided them in a way that didn't make you doze off half way though. I also hope that I was general enough, so that you may be able to use the concept outside Half-Life.
To keep it simple I skipped on a lot of issues, like the rotation of the model and the collision boxes, this is almost a tutorial of its own but I will be happy to include it if you request it.
I will also put some actual code up if you request it.

Thank you for taking your time and getting this far.
I would like to see your feedback and use it to improve the tutorial, so please comment on it.

Thanks

Thanks to Cathal aka sourcemodding for contacting me and using this tutorial as inspiration for Where is Poppy - Your First Custom Entity. Check it out to get a better understanding of the AABB boxes described in this tutorial and how to render them. His tutorial is great and his illustrations are very intuitive.