Black Golem

Two months ago I wrote an article about collision detection optimization for Nordenfelt. At that time the basic problem emerged from the fact that the engine used rectangles for collision detection. In this article I want to explain why I dropped the rectangle approach.

Simple Collision Shapes

There are two simple solutions for collision detection: Using rectangles or circles. Testing rectangles for intersection is as simple as the following code shows:

bool Intersect(Rectangle& a, Rectangle& b)
{
    return a.Left < b.Right && a.Top < b.Bottom &&
           b.Left < a.Right && b.Top < a.Bottom;
}

Collision detection between circles is a no-brainer to:

bool Intersect(Circle& a, Circle& b)
{
    Vector2D distance = a.Center - b.Center;
    return distance.Length < a.Radius + b.Radius;
}

The calculation of the distance length is rather expensive due to the need for a square root (length = Squareroot(x*x + y*y)). Therefore we use a common trick and compare the squared values (length*length = x*x + y*y):

bool Intersect(Circle& a, Circle& b)
{
    Vector2D distance = a.Center - b.Center;
    float radiusSum = a.Radius + b.Radius;
    float squaredDistanceLength = distance.x * distance.x +
                                  distance.y * distance.y;

    return squaredDistanceLength < radiusSum * radiusSum;
}

Detecting points inside a rectangle or circle are special cases where the point is a rectangle/circle with an area equal zero:

bool Intersect(Rectangle& r, Vector2D& v)
{
    return r.Left < v.x && r.Top < v.y && v.x < r.Right && v.y < r.Bottom;
}

bool Intersect(Circle& c, Vector2D& v)
{
    Vector2D distance = c.Center - v;
    float squaredDistanceLength = distance.x * distance.x +
                                  distance.y * distance.y;

    return squaredDistanceLength < c.Radius * c.Radius;
}

I don't know how good triangles would fit into collision detection. I did not investigate this shape. The simplicity of rectangle and circle was enough for me.

A Wrong Choice

Back in the days when I planned to use pixel art for Nordenfelt I chose rectangles as physical representation atoms. Airplanes, turrets, ships and other war machines have angular shapes. So rectangles were the first choice. The only drawback were rotations. Only axis-aligned rectangles provide simple collision detection routines. But pixel art is not rotatable anyway (without ugly distortions) so that was no problem.

After some graphical experiments I dropped the pleasing idea of pixel art - sob :( - and switched over to rendered 3D models and higher screen resolutions. Now rotations became possible and were included right away. This created the demand for rectangle rotation which was solved by including polygons for physical representation. Complex algorithms and some trickery were needed to make them usable for the engine.

Circles have a huge advantage over rectangles and polygons: Rotation is faster (rotation of one center compared to rotating every polygon corner) and does not change the shape, related to axis alignment. I thought about using circles instead of polygons. Laziness stopped me pondering.

Profound Refactoring

Integration of the new power-ups (coming in Nordenfelt 0.2) created a refactoring demand for state machines, animations and sprite management. Why not kill two birds with one stone and replace the awkward polygon shapes with circles? So I dived deep into the "physics" code again.

After four days of refactoring the results manifested as hierarchical circle structures. These structures can easily be scaled, translated and rotated. The hierarchic struture speeds up collision tests. When the envelope circle does not intersect neither do the inner circles:

Bonus

Another advantage of circles over polygons and rectangles appeared while coding: Line intersection is a breeze and can easily be extended with line thickness:

float GetSquaredLength(Vector2D& v)
{
    return v.x * v.x + v.y * v.y;
}

float GetDotProduct(Vector2D& v1, Vector2D& v2)
{
    return v1.x * v2.x + v1.y * v2.y;
}

bool Intersect(Circle& c, Vector2D& p1, Vector2D& p2, float lineThickness)
{
    float virtualRadius = c.Radius + (lineThickness / 2);
    float squaredVirtualRadius = virtualRadius * virtualRadius;
    Vector2D f = c.Center - p1;

    if(GetSquaredLength(f) < squaredVirtualRadius)
        return true;
 
    if(GetSquaredLength(p2 - c.Center) < squaredVirtualRadius)
        return true;

    Vector2D distance = p2 - p1;
    float t = GetDotProduct(f, distance) / GetSquaredLength(distance);
 
    if(0 <= t && t <= 1)
        return GetSquaredLength(f + (t * distance)) < squaredVirtualRadius;
    else
        return false;
}

This intersection would be much more complex, slower and uglier for rectangles and polygons.

Line intersection is needed e.g. for shots which need to check their trace. Otherwise they may fly through an object without detecting the collision:

Conclusion

I don't know if there are better collision detection solutions out there. I bet there are. Finally hierarchical circle structures are a beautiful, fast and easy to understand method for body representations. It also applies to 3D very well. Simply add axis Z in the vectors and it works in three dimensions. Try this with polygons :)

Cheers,
Thomas