Collision Managment

Collision detection and managment is an essential part of almost all games and Astro Ducks is no exception. It is usually relatively simple to detect a collision, but harder figuring out how to deal with a collision. What should happen when a collision occurs? Sometimes, its trivial - an enemy either takes damage or dies as a result of getting hit. But when two moving objects collide, that can be trickier. Lets start with the simple stuff first - how to detect a collison.

Since graphical models of enemies can be very complex,we need to make some simplifications to test if they collide. A very common technique used is bounding volumes which is what we will be using as well. Specifically, we want to use the bounding sphere. The reason why is that it will easily fit our objects - the duck, the boat (player(s)) and the projectiles. Lets have a look at the duck again for example

It's obvious that the bounding sphere would be a good candidate for the duck, because it can fit around the duck tighthly and no matter the orientation of the duck, the sphere will encapsulate it. The downside to this approach is that it is not super accurate - there sphere will either not encapsulate the duck fully, or it will encapsulate more than the duck. This is a sacrifice we are willing to make to use the bounding sphere. The bounding sphere also has the great benefit of a super cheap collision test.

bool SphereSphereTest(glm::vec3 &s1Pos, float &s1Radius, glm::vec3 &s2Pos, float &s2Radius)
{
    glm::vec3 dist = s1Pos - s2Pos;

    float sumRadiusSquare = s1Radius + s2Radius;
    sumRadiusSquare = sumRadiusSquare * sumRadiusSquare;

    return dist.x * dist.x + dist.y * dist.y + dist.z * dist.z <= sumRadiusSquare;  
}

So by using squared values, we can get away with very few calculations to determine if there is a collision

Before we start diving into the details of handling collisions, we need a strategy for handling collisions in general. We can think of the game world as being in constant motion - everything moves simultaneously. To work with this in a computer, we need to break it up into separate (discrete) frames that we can evaluate and act upon. If we do so, we can also predict what the next frame would look like before we apply any collision handling. The picture bellow illustrates this.

In the second picture, the grey dotted spheres represent the position of the next game frame. We generate these position from the following code in the main-loop

Duck::CollisionTick(ducks, deltaTime);
Player::CollisionTick(players, deltaTime);

These positions are then feed to the collisionEngine, who can ask the objects to take appropriate action in case there are objects that collided. This approach also ties into our overarching game engine design of keeping things separate so we can process them in batches (you can recap this in the game tick page).

Ok, great so now we can tell if there are any collisions. But we need to do something appropriate when that happens to. There will be a few different cases of collision in the game, lets start by listing them and then going over them:

If two ducks collide, then the ducks will bounce backwards and slightly re-orient themselves. Lets have a look at what we want.

If we try to break a collision up in to game frames it could look something like bellow

The first frame is just before a collision is about to happen. We then calculate the next positions, which are illustrated in the second frame. Here, we can see that the ducks are going to collide, so we need to do something. We will call Divert and Bounceback for each duck that has collided with another duck. In the third frame we can see the bounceback vector that was calculated (the green vector) and that the facing direction of the duck has been adjusted. We also inform the duck that it has collided by calling Collided.

In the next game logic tick of the duck(s) that have collided, we will know that we have collided, and our actual position will not be updated. Why dont we just update the duck to move in the direction of the green vector? There could be a new collision resulting from moving in the bounceback direction as well. In the next CollisionTick, we will evaluate what happens if we were to try and move "backwards". If that is ok (no collision), then we will move backwards. Otherwise we will not move at all.

This is just a slight variation on the duck collide with duck. When the duck hits the world border, it should bounce off the wall, be stunned for a quick moment and at the same time do a full 180 degrees rotation so it faces the other side and finally continue moving in its new direction. Lets have a look at what we want.

This is not very different from the duck collide with duck. The only difference is that we instruct the duck to Divert 180 degrees (plus a small random fraction to make it look a bit more dynamic)

This is the most complex thing to manage, as it requires us to spawn new ducks and delete old ones. When a duck collides with a projectile, it should be removed, a particle explosion effect should be created and depending on its size, new ducks might be spawn. There are three cases:

Before we discuss the details, lets have a look at what it should look like in the video bellow

To create this effect, we need to calculate a couple of things. If we draw the two frames we can easily make out what is needed. The first frame shows the duck just before the explosion and the next shows what we want to have in our next game frame.

This is important - we must not insert or remove any objects during our evaluation (collisionEngine.Tick) . This could "poision" our current collision predictions, if we are considering duck N now and insert 3 new ducks, then considering duck N+1 might result in a duck colliding with a duck that have not even been inserted in this game frame. These new ducks have not been allowed to produce their "next position" yet so this would not make any sense and may result in some strange behaviour further down the road. In our collision prediction we only inform what should happen next - we dot not alter current the current game frame.

First, lets start with the things that are given - f and F - these are the position of the old duck and its facing direction

We find R by taking the cross product of the positive Z axis (0.0f, 0.0f, 1.0f) and F.
RotationMatrix1 is built using glm::rotate, creating a rotation of 135 degrees around the Z axis, RotationMatrix2 is the same - just rotating the opposite way. Since these rotation matrices are constant we build them only once when the game starts up.

A is created by appying RotationMatrix1 to F.
C is created by applying RotationMatrix2 to F.

The positions of the new ducks (a, b and c) are created by starting at the old ducks position (f) and then translating along L, F and R respectively.

Finally, we also create a particle effect and inform the duck that got hit that it should be destroyed. The information about the new ducks and the duck that got hit being destroyed is stored and then processed in the next game logic tick. In this tick, we examine the newly created ducks - if their positions cause and immediate collision, they will not be created at all. This is because inserting them could potentially risk that we introduce a situation where some ducks get "stuck" in each other. It is of course possible to try and re-arrange the newly created ducks so they dont collide, and perhaps we will look into a solution for that in "Astro-Ducks 2.0".

All of this happens in duck.cpp - Destroy(Duck* duck) if you want to look at the implemenation over at gitlab

The solution for the medium duck is just a subset of what happens in the case of the big duck. The facing direction of the two ducks created (a and b) is simply L and R respectively.

This is the same as when the duck collides with a projectile. The only difference is that we also decrease the players health as well

Performance

Doing collision detection can be very heavy. The more objects that need to be tested against each other, the more time will be spent on collision detection. To minimize this, we should try to think of a way to cut away unnecessary tests. Lets have a look at an example

This shows a game frame with 22 ducks in it. Just from looking at it, we can easily see that all ducks can not collide with each other. If we were to just test all of them it would be 22 * 22 = 484 collision test, which is quite a lot. A popular techinque to use when dealing with 2D collision testing is using a quad tree. The idea is to implement a divide and conquer tactic, splitting the 2D playing area into four smaller sub-areas. Lets see if we can try and split our game world

The first picture shows what happens after our first split - we get four new regions (hence the name "quadtree"). After this split we would now have 4 new quadrants:

If we look at the second picture, we can see that quadrant 2 has been split into four new quadrants again. In a quad tree, each sub-area can be split into four new areas if we see it fit.

Notice the green circles? When considering which quadrant a duck belongs to, we look at both its position and its bounding sphere. If the bounding sphere crosses one of the splitting lines, we place it in the quadrants parent. Here is the same data illustrated as a tree
(The yellow circle illustrates the same thing, but this duck would end up in Q2)

Each node in the tree stores the area( (xmin, ymin) and (xmax, ymax) ), a vector of ducks and the depth of the node.

We also have a setting of the maximum number of ducks that each node may store and a maximum depth that we allow the tree to have. These settings are keept to balance the amount of time we allow to spend on building the tree - if there are only X amount of ducks in an area, it might not be worth splitting it up further.

By dividing the world like this, we can safely assume that a duck that sits firmly inside Q1 can only collide with other ducks inside Q1 (and the ducks that span across the splitting lines). This can drastically reduce the amount of collision test that we have to do, and that was the goal of using the quadtree in the first place

int QuadtreeDucks::GetIndex(glm::vec3 &duckPos, float boundingSphereRadius)
{
    int index = -1;

    float vertMiddle = m_xMin + (m_xMax - m_xMin) / 2.0f;
    float horzMiddle = m_yMin + (m_yMax - m_yMin) / 2.0f;

    bool topQuad = duckPos.y < horzMiddle && duckPos.y + boundingSphereRadius < horzMiddle;
    bool bottomQuadrant = duckPos.y > horzMiddle && duckPos.y - boundingSphereRadius > horzMiddle;

    if(duckPos.x < vertMiddle && duckPos.x + boundingSphereRadius < vertMiddle)
    {
        if(topQuad)
        {
            index = 0;
        }
        else if(bottomQuadrant)
        {
            index = 3;
        }
    }
    else if(duckPos.x > vertMiddle && duckPos.x - boundingSphereRadius > vertMiddle)
    {
        if(topQuad)
        {
            index = 1;
        }
        else if(bottomQuadrant)
        {
            index = 2;
        }       
    }

    return index;
}

void QuadtreeDucks::Split()
{
    float subQuadrants[4][4] = {
        { m_xMin, m_yMin, m_xMin + (m_xMax - m_xMin) / 2.0f, m_yMin + (m_yMax - m_yMin) / 2.0f },
        { m_xMin + (m_xMax - m_xMin) / 2.0f, m_yMin, m_xMax, m_yMin + (m_yMax - m_yMin) / 2.0f },
        { m_xMin + (m_xMax - m_xMin) / 2.0f, m_yMin + (m_yMax - m_yMin) / 2.0f, m_xMax, m_yMax },
        { m_xMin , m_yMin + (m_yMax - m_yMin) / 2.0f, m_xMin + (m_xMax - m_xMin) / 2.0f, m_yMax }
    };

    for(int i = 0; i < 4; i++)
    {
        QuadtreeDucks* child = new QuadtreeDucks(m_level + 1);
        child->SetWorldSize(subQuadrants[i][0], subQuadrants[i][1], subQuadrants[i][2], subQuadrants[i][3]);
        m_children.push_back(child);
    }   
}

void QuadtreeDucks::Insert(Duck* duck)
{
    if(!m_children.empty())
    {
        int index = GetIndex(duck->GetPosTry(), duck->GetBoundingSphereRadius());
        if(index != -1)
        {       
            m_children[index]->Insert(duck);
            return;
        }
    }

    m_ducks.push_back(duck);
    if(m_ducks.size() > s_quadTreeMaxOjbs && m_level < s_quadTreeMaxLevels)
    {       
        if(m_children.empty())
        {
            Split();
            int i = 0;
            while(i < m_ducks.size())
            {
                int index = GetIndex(m_ducks[i]->GetPosTry(), m_ducks[i]->GetBoundingSphereRadius());
                if(index != -1)
                {               
                    m_children[index]->Insert(m_ducks[i]);
                    m_ducks.erase(m_ducks.begin() + i);
                }
                else
                {
                    i++;
                }
            }
        }
    }
}

Looks like a lot of code - but it really is not all that complicated. The starting point will be Insert(Duck* duck), we will call this function for all the ducks in the game world.

First we check if we have any children (quadrants). Since we start at the top of the tree, we will start there and then continue down the tree as we keep checking if the children have quadrants of their own.
Once we reach a point in the tree where there are no children, we add the duck to the current node (m_ducks).

After that, we test our setting (s_quadTreeMaxOjbs) - are there more children than we allow in a single node?
We also check if we reached the maximum depth (s_quadTreeMaxLevels)
If ducks > s_quadTreeMaxOjbs and the tree is not to deep, we perform a Split and then we re-distribute the ducks into the new children (quadrants).
If we cant firmly put a duck inside one of the new children, we skip that duck (we get index == -1)

The GetIndex function simply checks the splitting lines. Split creates 4 new children and creates their areas from the existing area (chopping it into 4 new ones)

After the tree is built, we need a way to see which ducks we can collide with. Lets have a look at the code

void QuadtreeDucks::GetCollidables(Duck* duck, std::vector<Duck* > &ducks)
{
    int index = GetIndex(duck->GetPosTry(), duck->GetBoundingSphereRadius());
    if(index != -1 && !m_children.empty())
    {
        m_children[index]->GetCollidables(duck, ducks);
    }
    else
    {
        // We have to get all children as well since we are spanning across one of the boundaries
        for(auto &child : m_children)
        {
            child->GetChildren(ducks);
        }
    }

    /*
        There are two cases where we reach this point:
        * We reached a leaf and we should add the the m_ducks of that leaf
        * We traversed an internal node that has ducks that could not be distributed in the children (spawns the crossing lines) - we have
            to add these ducks as well since they could potentially collide with the duck we are testing for
    */  
    ducks.insert(ducks.end(), m_ducks.begin(), m_ducks.end());
}

We traverse the tree, looking at which child (using the GetIndex) to visit for the duck that we are testing. At each level, we always add ducks that we were not able to place in the nodes children (if it has any). If we reach a point in the tree where we span its splitting lines, we add all the ducks underneath it.

That is pretty much it for the collision managment part. There will be a section covering scenario tests for the quad-tree and the collision managment, you can find them in the verification section

Astro Ducks - A Complete Game Project

Collision Managment

Performance