-

# Flocking Algorithm Optimization

25 Aug, 2015

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];
}