Collision Part I: Manager and Component

September 9th, 2024

Hello! What I'll be showing is an old version of my collision system. Right now, I have a proper Sweep and Prune algorithm, Swept AABB detection, and discrete collision for stopping a moving object from going through a wall. I plan on doing separate posts for each of these topics. Today, I'll be covering the foundation of my collision system. I'll walk through the Collision Manager and Collision Component classes. The collision system revolves around AABBs. 

What is an AABB?

AABB stands for Axis-Aligned Bounding Box. It means that a game object has a box surrounding it that will always align with each axis, regardless of the object's rotation. It's a simple way to represent collisions. 

Outline

I'll briefly outline how the system will work, and then go into specifics about each class. When an entity needs to support collision, the user will give it a Collision Component. Every object that has a Collision Component is observed by the Collision Manager. When the manager detects that two entities have collided, it will collect data about the collision. That data will be passed to both entities in their respective OnCollision functions. 

The Object Class

I created a struct called CollisionData. This stores information relevant to a collision event which is queried by the Collision Manager:

I'll introduce a new class, Object. It is a small class that inherits from Entity and most game objects will inherit from it. By default, it has a Transform Component to show its location in the world. It also has functions for different OnCollision events to be called by the Collision Component, which takes in CollisionData. They are marked virtual so an object can define its own reaction to a collision:

The Collision Component

Moving onto the component, here are the members and functions: 

The mAABB is a rectangle with a position (x, y), width, and height. The function pointers will map to the owning object and call their OnCollision… functions if they're set. The member mShowCollisionSprite is a debug feature for drawing the AABB on the screen. There is only one constructor to force the user to set the AABB's dimensions. 

The Init function adds the owning entity to a list of all other objects with colliders. This list is accessed by the CollisionManager. I'll probably make a post for the grouping system later but for now, just know that the all objects with colliders are in the HasCollider group.

We have to make sure the AABB keeps up with the object as it moves, so I'll update it's position and size in the component's Update function:

The SetOnCollision… functions simply set their respective mOnCollision members. The Component's OnCollision… functions validate the pointers and the owning object before calling the function. 

IsColliding is a simple AABB check that returns a bool. The '&&' operator is overloaded for convenience: 

The Collision Manager

Collision is typically divided into two phases, the broad phase and narrow phase. The broad phase is meant to generate a small list of objects that could be colliding. The narrow phase performs object-to-object collisions, using the list generated by the broad phase. For now, I'll be using naive detection, which compares each object against every other object. This has exponential complexity O(n^2), which will absolutely tank performance when there are a lot of objects. In the next post, I'll show how I've implemented the Sweep and Prune algorithm, which has a better time complexity. 

Here is the class:

The typedef CollisionMapDEP* is a map of maps. Each object will have a map of other objects that it could be colliding with. The map is generated by the BroadPhase and the NarrowPhase goes down that list and determines if there was a collision. The mPrevMap is used to determine if a collision happened on the previous frame or not. This helps determine whether to call each component's OnCollisionBegin/End/Ongoing functions. 

* - It's postfixed with DEP for deprecated because I created a new version that I'll explain in a later post.

Collisions will be checked every frame, so the Update function calls BroadPhaseCollision. That only function calls the NaiiveDetection:

Alright, now onto the NaiiveDetection. It contains a for-loop with a nested for-loop to create every possible combination of collisions:

Each object's map entry is marked false by default. This will be marked as true if they are colliding, which is the Narrow Phase's job. 

As stated previously, the Narrow Phase simply goes down every map entry and checks if objects are colliding: 

As collisions are determined, the mPrevMap is updated so we know if a collision happened last frame. 

Demonstration

With this foundation, I'll give a demonstration of the component. In my player class, I'll set all three of the OnCollision… functions after giving it a collision component. In the override, I'll print the name of the other object and the nature of the collision. I'll have the console print a green message OnCollisionBegin, red OnEnd, and white OnOngoing. 

I'll also create an obstacle that has a collision component. 

When the two collide, a message will be output to the console:

Conclusion

That is the foundation of my collision system! In hindsight, my CollisionMapDEP typedef wasn't a great idea. Having an unordered map of unordered maps definitely wasn't the best data structure to use. The details of the rework I came up with will be described in the next post, so stay tuned. 

Thanks for reading,

Jamari