Faster collision check - Finding Morton

In many small games it is sufficient to check collision between objects, with 2 imbricated loops. But this double loop is very inneficient.

E.g. in Mean-Max referee code):

for( int i = 0; i < NbObjects; ++i) {
    for( int j = i + 1; j < NbObjects; ++j) {
        getCollisionWith( i, j);
    }
}

The problem

Problem of this double loop, is that:

it has O(N²) complexity (which hurt as soon as number of objects grows),
probably not so many object are colliding, but we are checking them all anyway.

What may be acceptable for the game engine, may become a problem, if you want to simulate a lot of turns for an AI for that game, especially if the collision check is not trivial, and is a costly function.

To illustrate this, simulating 10 000 time a world containing 11 objects with this code lead to:

1 000k call to getCollisionWith(),
approx run time of 25ms (our basis for comparison).

Looking for a simple solution

In Codingame contest, you have a limited amount of resource (time being one), porting the referee to an other langage, is alreadt quite boring and time consuming, you may end like me unwilling to do more.

In late December, I ended 85th with my ruby code in Mean-Max contest, already having converted the java referee to Ruby once, I was happy with my rank (it was my initial goal) and having beaten all my collegues :-), but having been 25 sits away from the Legend League at some point in the contest, I wanted more.

When you read the postmortem of the leading guy like Agade and Robostac they all seems to use Genetic Algorithm GA for their AI. So I was willing to try to implement one king of GA AI myself to see how it works. But for that kind of AI you need to simulate a lot of moves. And so you need some efficient code, since you are limited to 50ms per turn in the contest.

At that time the Mean-Max challenge had re-opened and I had rewritent everything in C++, just to ensure performance would not be an issue. So it was my second port of the referee from Java to an other langage (and was quite fed up with it).

My first attemps with GA, did not give good results (I staty stucked in Bronze for a long time). My hypothesis then, was that it was because I was not able to simulate enough generation with the original referee port. Profiling it shows that most of the time (60%) was spent in the collisions check above. So I was looking for a quick win to solve that issue.

Bounding Box

First simple idea was to use bounding box to have a simple check before deciding to call costly function getCollisionWith(). The bounding box is defined by a topLeft and a bottomRight points, by combining xy pos and then xy + v and taking account object radius.

We only need to call getCollisionWith() if bounding boxes overlap, otherwise their is no need to. But this alone does not reduce the double loop complexity. The key improvement come from the next stage. Note that what we are looking for is a criteria to use to discard calls to getCollisionWith() when there can’t be any collision at all.

Indexing the 2D plan

Wouldn’t it be cool if we could stop the second loop, when there is no more collsiion pssible with the current object from the main loop ?

We could do that if we had a mapping from the 2D plane to one dimensionnal index with the property that given index( mainBox) < index( otherBox) then no more collision are possible.

Hilbert Curve

The idea jump to my sofa, was from an xkcd article which mapped the internet using Hilbert curve that I remembered then. But it was not suitable here: while Hilbert coordinate have the propety to ussually keep locality (point in plane that are close stay close in general with Hilbert index) they are difficult to compute and they don’t fit this problem well. Fotunately wikipedia gave me hint to other space filling curves, one being the Z-order curve from Morton.

Z-Order curve

The Z-order curve index is built by multiplexing bits from the x and y coordinate of a point. There is several way to implement this so far I just picked one, without looking further (it doesn’t show in my benchmark).

It has nice property and is used to speed up range check. With that in mind the collision arlgorithm became:

sort object by their bouding box accoring to the z-order of topLeft corner

for( int i = 0; i < NbObjects; ++i) {
    main = object[i]

    for( int j = i + 1; j < NbObjects; ++j) {
        other = object[j]

        if( other.z.topLeft > main.z.bottomRight)
            break;  // there can't be any collision with the two boxes.

        getCollisionWith( i, j);
    }
}

This is what I ended using with very good results. This simple test improve a lot the performance of this double loop reducing the number of iteration of the second loop to just a few.

The same 10 000 time world simulation now does:

290k call to getCollisionWith(),
approx run time of 18ms

Not bad!

Norm2

When writting this article it comes to me that the Norm2 of xy coordinates would have the same kind of properies that is usefull in the Z-order curve if we compare norm( other.topLeft) vs norm( main.bottomRight) and restricting us to the bottom right quandrant (where x and y are positive).

There is one drawback, Norm2 is ‘less’ ordered: every point at the same radius get the same value.

Is it that simple ?

Well nearly. In Mean Max when object collide they bounce. So we have to update the bounding box after the bounce, to be able to compute next-collision.

The way it’s done, bouncing imply only 2 objects at a time, so there is only 2 ojbects at most to update, and put in the right place in the ordered list.

But in meany case the assumption that initial bounding is still valid is sufficient.

Epilogue

Naturally, all this has already been found before:

How to use Morton Order(z order curve) in range search?

caption

#4577