Black Golem

The Nordenfelt game engine is a young in-house engine. It is a half year old and was developed without any premature optimization by now. Premature optimization is adaption of code for better performance based on estimation instead of measurement. It affects software design and often results in less maintainable code.

The last post showed that now there are weaknesses raising from the engine's ground. Collision detection proved to be the most significant part here. The physical bodies of objects like ships or turrets are represented as 2D polygons. Testing polygons for intersection is a non-trivial task and therefore needs many CPU cycles to execute. Using axis aligned rectangles would be faster here but they lack the needed flexibility for rotation.

The Enveloping Technique

There are several concepts for optimization which can be applied. The best optimization for slow code is to not execute the code at all. Therefore my solution for speeding up collision detection is "enveloping". It is based on the simple idea of making a quick but inaccurate test to avoid the exact but slow test.

The collision detection algorithm takes two polygons (A and B) and tells if they overlap. The basic steps of the algorithm are:

There is no intersection when none of these tests detects an intersection. This is the worst case (speak most expensive to compute). The best case would be when the first test finds an intersection for the first tested point. The problem is that in most cases there are no intersections. This makes the worst case the common case. How can we avoid this?

The enveloping technique imposts polygons with fast testable and circumscribing shapes. I chose axis aligned rectangles because they have a fast intersection test function:

bool Intersection(Rectangle& a, Rectangle& b)
{
    int min, max;

    min = (a.left > b.left ? a.left : b.left);
    max = (a.right < b.right ? a.right : b.right);

    if(min >= max)
        return false;
 
    min = (a.top > b.top ? a.top : b.top);
    max = (a.bottom < b.bottom ? a.bottom : b.bottom);
 
    return min < max;
}

When the impostors don't intersect the enclosed polygons do neither:

When the envelopes intersect the accurate but slow polygon-vs-polygon algorithm has to be used. In this case we have the cost of testing the envelopes plus testing their polygons. This is even slower than just testing the polygons. But finally the reduced occurrence of this case makes it non-relevant.

Improvement

The funny thing about this post is that I discovered an even better way for solving the problem while writing it.

Rotation of a polygon forces a recalculation of the envelope. Using a circle as envelope would render this step obsolete. The circle won't change as long as the rotation center and the envelope center are the same. Collision detection of circles is even simpler than of rectangles:

bool Intersection(Circle& a, Circle& b)
{
    int distanceX = a.x - b.x;
    int distanceY = a.y - b.y;
    int radiusSum = a.radius + b.radius;

    return (radiusSum * radiusSum)
           >=
           (distanceX * distanceX) + (distanceY * distanceY);
}

Cheers,
Thomas