C++ Game Dev 18: Object Collision System

This is part of an ongoing series where we write a complete 2D game engine in C++ and SFML. A new tutorial is released every Monday. You can find the complete list of tutorials here and download the source code from the projects GitHub page.We’ve been working on the collision system for the last three weeks and we’ve made a lot of progress in that time. So far we’ve:

Created a collider component. This component holds a rectangular area that we will use to check for collisions. We need to attach this component to every object that we want to collide.
Created the quadtree. This is a method of efficiently storing collidables to minimise the number of collision checks we need to perform.

So the final piece of the puzzle (for now) is creating the system that will take advantage of the collider components and the quadtree. And that’s exactly what we’ll do this week. One quick thing we need to do before we create the collision system is to remove the assertion in Objects GetComponent function that checks if the class we are trying to retrieve derives from Component. We’re removing this check because we’ve previously created C_Drawable which is a base class for any drawable component but does not actually inherit from Component. We want to be able to call GetComponent() in future which would fail because it does not inherit from Component so we remove the assert as it is no longer suitable.

Object.hpp

template <typename T> std::shared_ptr<T> GetComponent()
{        
    // Removed check to see if we are trying to get a class that derives from component.

	for (auto& exisitingComponent : components)
    {
    	if (std::dynamic_pointer_cast<T>(exisitingComponent))
        {
        	return std::dynamic_pointer_cast<T>(exisitingComponent);
        }
    }
        
    return nullptr;
};

Object.hpp

template <typename T> std::shared_ptr<T> GetComponent()
{        
    // Removed check to see if we are trying to get a class that 
	// derives from component.

	for (auto& exisitingComponent : components)
    {
    	if (std::dynamic_pointer_cast<T>(exisitingComponent))
        {
        	return std::dynamic_pointer_cast<T>(exisitingComponent);
        }
    }
        
    return nullptr;
};

With that done it’s on to the main event: the collision system. This will follow a similar structure to that of the drawing system. Before we write anything, let’s define what we want from our collision system:

To be able to pass the collision system a vector of newly added objects and for the collision system to work out which objects have collidables and only include those in its system.
When an object is removed from the game we need the collision system to remove it from its collection as well.
Every frame we need to check if objects are colliding and if they are we want the objects collider components to resolve the collision.

S_Collidable.hpp

#ifndef S_Collidable_hpp
#define S_Collidable_hpp

#include <vector>
#include <memory>
#include <set>

#include "Object.hpp"
#include "Quadtree.hpp"
#include "Bitmask.hpp"

class S_Collidable
{
public:
    S_Collidable();
    
    void Add(std::vector<std::shared_ptr<Object>>& objects);
    void ProcessRemovals();
    void Update();
    
private:
    void Resolve();
    void ProcessCollisions(std::vector<std::shared_ptr<Object>>& first, std::vector<std::shared_ptr<Object>>& second);
    
	// This is used to store collision layer data i.e. which layers can collide.
    std::map<CollisionLayer, Bitmask> collisionLayers;

	// The collision system stores all collidables along with their layer.
    std::map<CollisionLayer, std::vector<std::shared_ptr<C_BoxCollider>>> collidables;
    
	// The quadtree stores the collidables in a spatial aware structure.
    Quadtree collisionTree;
};

#endif /* S_Collidable_hpp */

In our constructor, we will setup collisionLayers. We’ll use this structure to define which layers collide by storing a map along with a bitmask. Using the bitmask we can set specific bit positions that will represent other layers. Hopefully, this will become clearer shortly.

S_Collidable.cpp

#include "S_Collidable.hpp"

S_Collidable::S_Collidable() 
{
    Bitmask defaultCollisions; // 1
    defaultCollisions.SetBit((int)CollisionLayer::Default);   // 2 
	collisionLayers.insert(
		std::make_pair(CollisionLayer::Default, defaultCollisions)); // 3
    
    collisionLayers.insert(std::make_pair(CollisionLayer::Tile, Bitmask(0)));
    
    Bitmask playerCollisions;
    playerCollisions.SetBit((int) CollisionLayer::Default);
    playerCollisions.SetBit((int) CollisionLayer::Tile);
    collisionLayers.insert(std::make_pair(CollisionLayer::Player, playerCollisions));
}

For each collision layer we:

Create a bitmask to store the collision data.
We set the bit for each layer that this layer will collide with. Remember that we specified integer values for our CollisionLayer enum. We use those values to set that position in the bitmask if we want collisions with that layer. For example, we only want the default layer colliding with itself so we only set the bit at position 1 (the integer value we gave to the default layer in the CollisionLayer enum). We don’t want the tile layer colliding with any other layer so we set its bit mask to 0. And we want the player layer colliding with the default and tile layer so we set both of those bits.
We then add this value to our collisionLayer map. We’ll read from this map when we are resolving collisions.

Next up is the Add function. The Add function accepts a vector of objects, iterates over these objects and checks if they have a collidable component. If the object does have a collidable component then it is added to this system. If the object does not have a collider then it is ignored.

S_Collidable.cpp

void S_Collidable::Add(std::vector<std::shared_ptr<Object>>& objects)
{
    for (auto o : objects)
    {
        auto collider = o->GetComponent<C_BoxCollider>();
        if (collider)
        {
            CollisionLayer layer = collider->GetLayer();
            
            auto itr = collidables.find(layer);
            
            if (itr != collidables.end())
            {
                collidables[layer].push_back(collider);
            }
            else
            {
                std::vector<std::shared_ptr<C_BoxCollider>> objs;
                objs.push_back(collider);
                
                collidables.insert(std::make_pair(layer, objs));
            }
        }
    }
}

We add the colliders to the map along with their collision layer so that when it comes to resolving collisions we can ignore batches of them that have a bitmask of 0. This will be explained more when we write the Resolve function.Now we can add objects we’ll write the function that removes objects from the system.

S_Collidable.cpp

void S_Collidable::ProcessRemovals()
{
    for (auto& layer : collidables)
    {
        auto itr = layer.second.begin();
        while (itr != layer.second.end())
        {
            if ((*itr)->owner->IsQueuedForRemoval())
            {
                itr = layer.second.erase(itr);
            }
            else
            {
                ++itr;
            }
        }
    }
}

We loop through each collision layer in our collidables map and check if the object is queued for removal. If it is, it is removed from this system. This may look familiar to you as it is the same way we remove objects from the ObjectCollection and our drawing system.The collidable systems update function is called each frame. It will be responsible for initialising the quadtree and then calling the Resolve function, which performs the actual collision checks.

S_Collidable.cpp

void S_Collidable::Update()
{
    collisionTree.Clear();
    for (auto maps = collidables.begin(); 
		 maps != collidables.end(); ++maps)
    {
        for (auto collidable : maps->second)
        {
            collisionTree.Insert(collidable);
        }
    }
    
    Resolve();
}

Before the system can call the Resolve function it needs to clear the quadtree and re-insert all the collidables. We have to do this because if the objects move around the game and transition from one quadtree node to another, we currently have no way of dynamically updating its node in the quadtree. In future we can look at writing dynamic node updates but for now this will do. Because the quadtree prevents many unnecessary collision checks I am not too concerned about the performance hit we take here. For more information on quadtrees see my previous tutorials. The last function to write is Resolve. This is the method that will actually perform the collision checks. It’s quite a big function as it needs to do a few checks (mostly to minimise the number of collision checks we need to perform each frame) but it is mostly straightforward and brings together everything we’ve written so far.

S_Collidable.cpp

void S_Collidable::Resolve()
{
    for (auto maps = collidables.begin(); maps != collidables.end(); ++maps) // 1
    {
        // If this layer collides with nothing then no need to 
		// perform any further checks.
        if(collisionLayers[maps->first].GetMask() == 0)
        {
            continue;
        }
        
        for (auto collidable : maps->second) // 1
        {
            // If this collidable is static then no need to check if 
			// it's colliding with other objects.
            if (collidable->owner->transform->isStatic())
            {
                continue;
            }
            
            std::vector<std::shared_ptr<C_BoxCollider>> collisions 
				= collisionTree.Search(collidable->GetCollidable()); // 2
            
            for (auto collision : collisions) // 3
            {
                // Make sure we do not resolve collisions between the same object.
                if (collidable->owner->instanceID->Get() 
					== collision->owner->instanceID->Get())
                {
                    continue;
                }
                
                bool layersCollide = 
					collisionLayers[collidable->GetLayer()].GetBit(((int)collision->GetLayer()));
                
                if(layersCollide) // 3a
                {
                    Manifold m = collidable->Intersects(collision); // 3b
                    
                    if(m.colliding)
                    {
                        if(collision->owner->transform->isStatic())
                        {
                            collidable->ResolveOverlap(m); // 3c
                        }
                        else
                        {
                            
                            //TODO: How should we handle collisions when both 
							// objects are not static?
                            // We could implement rigidbodies and mass.
                            collidable->ResolveOverlap(m); 
                        }
                        
                    }
                }
            }
            
        }
    }
}

We loop over every collidable stored within this system.
We pass the collidables area to the quadtree and retrieve a vector of objects that intersect with that area.
For every object we are colliding with:
1. We check if the two layers collide. If not then we can skip resolution.
2. The collision is passed to the collidable component of the initial object. This performs an additional collision check and returns a manifold that contains the collision data. We need to perform another check here because as we resolve collisions and move objects around we may no longer be colliding with some objects in the vector.
3. If they are still colliding we pass the manifold to the collidable component of the initial object, which will resolve the collision by moving the object so it is no longer intersecting.

It’s also worth mentioning how we are reducing the number of collision checks we need to perform each frame:

If a collision layer does not collide with any other layer (such as the tile layer) we do not perform checks on that layer.
If an object is static we do not need to check if it is colliding with other objects. We’ll still check if other objects collide with the static object. For example, if the player walks up to a chest that is marked static, they can still collide/interact with the chest. We just don’t need to check every frame if the chest is colliding with anything else.
If a layer does not collide with the layer of the other object based on its entry in collisionLayers then we do not perform any collision checks/resolutions.
And of course, by using the quadtree we only retrieve a small subset of objects so we do not need to check if every object is colliding with every other object.

You may have noticed the ‘TODO’ near the end of the function. We currently have no satisfactory way of resolving collisions between two non-static objects. This is definitely something we want to change sooner rather than later but as our player will only be colliding with static objects (tiles) for the moment we can leave this as it is. In next weeks tutorial, we’ll add the collider components to the tiles and player objects and finally have something to show for all of the work we’ve done on the collision system over the last few weeks. Trust me it will be worth it. While we will be updating and changing the collision system as we go along, having a robust system from the start puts us in a good position moving forward. As always, if you have any suggestions for what you would like covered or are having any trouble implementing a feature, then let me know in the comments and I’ll get back to you as soon as I can. Thank you for reading 🙂