Blugen's Collision Detection & Resolution

Jan. 30, 2018, 11:57 p.m.

Hello everyone, today I am going to talk about how I implemented collision resolution in Blugen.

Blugen is written in the MonoGame framework which uses C#, and this code uses no external libraries, so you should be able to plug it straight into whatever you're doing. For now, Blugen only pushing between two enemies; this will be expanded upon much later in the lifecycle to include platforms and such. Just keep that in mind while reading this post.

First, I need to explain LocalCoord. Blugen (like MUGEN) lets you define the coordinate system for the character as well as the game itself. It translates the character's coordinate system to the game's coordinate system, meaning that any velocities and positions defined in the character will show up properly in the game coordinate system.

In this post, the game's LocalCoord is 640×480, whereas the characters' LocalCoord is 320×240. This means all positions and velocities are scaled by a factor of two in order to match the game's coordinate system.

So first, here's the relevant logic for the Player update logic in the Game class:


// For keeping track of enemy-to-enemy collisisons.
var collisions = new List<PushResolution>();

// Player update logic
for (int i=0; i < Players.Length; i++)
{
    if (Players[i] != null)
    {
        Players[i].Update(this, gameTime, superPauseEntityList);
        for (int j=0; j < Players.Length; j++)
        {
            // Only push against other enemies.
            if ((i%2) != (j%2))
                Players[i].DeterminePush(this, Players[j], gameTime, ref collisions);
        }
    }
}

// Resolve collisions
foreach (var collision in collisions)
{
    if (!collision.Resolved)
    {
        CollidableEntity.ResolvePush(this, collision);
        collision.Resolved = true;
    }
}


This is actually the key. You do not want to resolve collisions instantly in the Player Update() function. This will lead to weird inconsistencies since this means whichever Player first sees the collision (which in this logic, would always mean Player 1), will be the first to resolve the collision! However, this is not correct (as it took me several hours to figure out). Why is this?

Well, it's simple: even with information about P2's position and velocity, Player 1 will resolve the collision before P2 even has a chance to update! This means that while the logic does work perfectly for Player 1, Player 2 will always overlap Player 1. This is why I made the PushResolution class to keep track of every colliding pair of entities:

// Used to keep track of resolved collisions.
public class PushResolution
{
    // The first collidable entity.
    public CollidableEntity Entity1 { get; private set; }

    // The second collidable entity.
    public CollidableEntity Entity2 { get; private set; }

    // True if this collision has been resolved, false otherwise.
    public bool Resolved { get; set; }

    // Determines if two <see cref="PushResolution"/> objects are between the same two entities.
    public override bool Equals(object obj)
    {
        if (obj is PushResolution)
        {
            var cr = obj as PushResolution;

            // Return true only if both Entities match (doesn't matter which one, long as they're the same 2)
            bool oneEqual = cr.Entity1 == this.Entity1 || cr.Entity2 == this.Entity1;
            bool otherEqual = cr.Entity1 == this.Entity2 || cr.Entity2 == this.Entity2;
            return oneEqual && otherEqual;
        }

        return false;
    }

    // The hash function for this object.
    public override int GetHashCode()
    {
        // Prime numbers pulled out of my ass to reduce hash collisions.
        int hash = 19;
        hash += 43*Entity1.GetHashCode();
        hash += 43*Entity2.GetHashCode();
        return hash;
    }

    // Creates an object to use for determining collision resolution.
    public PushResolution(CollidableEntity entity, CollidableEntity other)
    {
        this.Entity1 = entity;
        this.Entity2 = other;
    }
}


This keeps track of three things: the first entity, the colliding entity, and whether or not the collision has been resolved.

I overrode Equals so that it can detect if the PushResolution is between the same two colliding entities, regardless of whether they're Entity1 or Entity2. This prevents the same collisions from being resolved. I won't go into the details of GetHashCode() since there are plenty of articles and Stackoverflow posts about that, but know that it's to detect the same thing.

So now here is the DeterminePush method in the CollidableEntity class:

// Determines if two pushboxes are overlapping.
public void DeterminePush(Game game, CollidableEntity otherEntity, GameTime gameTime, ref List<PushResolution> collisions)
{
    Blugen g = (Blugen)game;

    // Don't do anything if the pushbox is empty.
    if (this.PushRegion.IsEmpty || otherEntity.PushRegion.IsEmpty)
        return;

    if (this.PushRegion.Intersects(otherEntity.PushRegion))
    {
        var collision = new PushResolution(this, otherEntity);
        if (!collisions.Contains(collision))
            collisions.Add(collision);
    }
}


I call the Rectangle.Intersects(Rectangle other) method and if it returns true, add it to the PushResolution list. Wow, that was hard. Like I said, I'm using the MonoGame framework, so the code is pretty much pure C# so I didn't even have to test intersections myself, nor should I. I didn't want to reinvent the wheel. PushRegion is a Microsoft.Xna.Framework.Rectangle struct, just so you know.


Now to the fun part: resolving the collisions. This is the ResolvePush method in the CollidableEntity class:

// Resolves pushing between two entities in the defined <see cref="PushResolution"/>.
public static void ResolvePush(Game game, PushResolution resolution)
{
    Blugen g = (Blugen)game;

    CollidableEntity e1 = resolution.Entity1;
    CollidableEntity e2 = resolution.Entity2;

    // Until something says otherwise, we're still performing operations on these values.
    float velX = e1.Vel.X * g.LocalCoord.X / e1.LocalCoord.X, velY = e1.Vel.Y * g.LocalCoord.Y / e1.LocalCoord.Y;

    float xPosToAdd = (velX - (e2.Vel.X * g.LocalCoord.X / e2.LocalCoord.X));
    float yPosToAdd = (velY - (e2.Vel.Y * g.LocalCoord.Y / e2.LocalCoord.Y));

    // Get the penetration distance
    float p_d1 = (e2.PushRegion.Left - e1.PushRegion.Right);
    float p_d2 = (e2.PushRegion.Right - e1.PushRegion.Left);

    bool usePD1 = Math.Abs(p_d1) < Math.Abs(p_d2);

    if (usePD1)
    {
        if (xPosToAdd > 0)
            e2.Pos -= new Vector2(p_d1, 0);
        else if (xPosToAdd < 0)
            e1.Pos += new Vector2(p_d1, 0);
        else
        {
            e2.Pos -= new Vector2(p_d1/2, 0);
            e1.Pos += new Vector2(p_d1/2, 0);

            float newDist = e2.PushRegion.Left - e1.PushRegion.Right;
            if (newDist != 0)
            {
                e2.Pos -= new Vector2(newDist / 2, 0);
                e1.Pos -= new Vector2(newDist / 2, 0);
            }
        }
    }
    else
    {
        if (xPosToAdd > 0)
            e2.Pos -= new Vector2(p_d2, 0);
        else if (xPosToAdd < 0)
            e1.Pos += new Vector2(p_d2, 0);
        else
        {
            e2.Pos -= new Vector2(p_d2/2, 0);
            e1.Pos += new Vector2(p_d2/2, 0);

            float newDist = e2.PushRegion.Right - e1.PushRegion.Left;
            if (newDist != 0)
            {
                e2.Pos -= new Vector2(newDist/2, 0);
                e1.Pos -= new Vector2(newDist/2, 0);
            }
        }
    }
}


This may be obvious to others, but for me, was extremely difficult. Why? Well recall earlier how I said the key was resolving collisions AFTER all calculations have been done. I seriously cannot stress this part enough. You have to let all updates happen, THEN resolve collisions! That's why I made a PushResolution class and a list of such objects. Now time for the explanation of what this method does.

First, it calculates the difference in velocities between the two entities. This is what determines which one is pushing. The CollidableEntitiy with the greatest velocity should be pushing out the other more. If both velocities are the same, they will cancel out and as such, will return 0. Next, it calculates the penetration distance between each sides of the rectangles. Then it finds what the minimum penetration distance is in order to determine how much to push out. Finally, it checks the velocity difference and determines which entity needs to get pushed.

If xPosToAdd is greater than 0, then that means Entity 1 has the greater velocity, so Entity 2 should be pushed out. Similarly, if it is less than 0, that means Entity 2 has the greater velocity, so Entity 1 should be pushed out. If both velocities cancel each other out, then they both get pushed out by half the penetration distance so that both are equal. If, after that, the distance is still not zeroed out (usually due to a turn), then it will check the new penetration distance and account for that.


That's it!

Keep in mind, however, that this code only handles pushing on the X axis, so it will not work so nicely for platforms and such. Many modifications need to be made to accommodate such behavior. But because most fighting games only push on X, this isn't much of a problem.
Back to top