-

Flocking Algorithm Optimization

25 Aug, 2015Ariel Schoch

I often encounter a situation where I need all the objects in a scene to react to the positions of all other objects. One such example is when simulating flocking behaviour of hundreds of agents.

If we have n objects (or 'agents') in our scene, then every one of those n agents will need to check its position against every other agent.
In other words we will need to do comparisons.
If we have four agents which we name a, b, c, and d, then the required position comparisons would look something like this:

aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd
Thats 16 checks, giving us the running time: $$T(n) = O(n^2)$$ However, since checking the distance between two positions will be the same regardless of the direction we measure from, we can assume that ab = ba and so on.
aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd
So the new amount of checks we need to do equals: $${n(n+1)} \over {2}$$

In addition, we won't have to check agent positions against themselves, so we can get rid of aa, bb, cc, and dd.

aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd

Which is equivalent to summing all the numbers from one to n minus one. $$1+2+..+(n-1) = {n(n-1) \over 2}$$

The resulting loop:

for (int i = 0; i < n; i++)
{
    for (int j = i; j < n; j++)
    {
        // skip if we are checking against ourselves
        if (i == j)
            continue;
        // pass direction vector info to agent[i] and agent[j]
        Vector3 dir = agent[i] - agent[j];
        agent[i].AddDirection (dir);
        agent[j].AddDirection (dir * -1);
    }
}
Notice that the integer j of the inner for loop is set to i, so that as i increases the number of iterations of the inner loop decreases. In the above demo this improved performance noticeably compared to the standard checks.