Let’s say we have 1000 boids: little worms, birds or what-ever-animal is your favorite, moving around in a canvas (restricted to X and Y coordinates, that is a plane). The boids form a beautiful swarm. Collectively they seem to be following some invisible leader, while avoiding crashing each other.
Can we somehow optimize the calculation of distances?
Boids make a fantastically realistic depiction of flocking behavior due to 3 simple rules:
Boids in this context are considered only as a graphics simulation. Boids have AI context as well: in Particle Swarm Optimization (PSO), the search happens via a group of boids. We’re not covering PSO aspects in this post.
Why distances are important for boids?
Boids, as simulated by computers, only “see” the world through distance calculation alone. So every boid wants to know the distance to every other boid. If there’s 1000 boids, we need to calculate “from each boid, the Euclidean distance to each other boid”.
Boids follow a few rules, and they are based on the distances:
- cohesion (of swarm)
- avoid being in the edges of a swarm
- don’t collide to other boids
So how much is it? How many CPU-based calculations do we need? Is there a low-hanging fruit, some optimization we might use in the algorithm?
Naturally we’re looking at a FOR (loop). In fact, FOR each boid, go through all other boids. So it’s nested FOR.
for each v in vertices: for t in (vertices - v): dist[v,t] = sqrt(pow(v.x-t.x,2) + pow(v.y-t.y,2))
Since the distance (=edge length) between two vertices is symmetric (from Bob to Alice is same amount as from Alice to Bob), we only need count the distance pairs between all boids. This reduces calculation by 50%.
Let’s induce the “number of edges” formula in a very short manner:
|Vertices||# of Edges|
How many CPU cycles needed to calculate one distance?
Approximations will do. We’re quite low level here, not quite exact CPU cycle counting — but close enough. You might have seen this same formula in a bit different format, but it wants to say: you need to calculate a square root of a sum. the sum is composed of second powers of X- and Y- distances (differences) of the two points.
Distance (an edge) is thus:
sqrt( Dx^2 + Dx^2 )
- Dx is (X1 – X2)
- Dy is (Y1 – Y2)
- sqrt counts for 1 CPU operation (op)
- sum (the ‘+’) is also 1 op
- powers (^2) are both 1 op, so 2 op total for powers
- total 4 arithmetic operations per each boid pair
Distance calculation details for boids
- take one boid as center
- calculate lines (pythagorean distance) to all N-1 other boids
- dist = sqrt[ (delta_x)^2 + (delta_y)^2 ]
- a little trick: there is symmetry. The distance from the other boid to “us” is same as from us to there
- thus we need only calculate once the distance between two boids
- store the value so that both boids can use it
We would otherwise do unnecessary calculations. But is the “50% off” of the algorithm runtime the best we can get? Can we shave more out of the algorithm? Or should we ask, at what point it makes sense to even try to shave more off? It’s always sane to optimize only in the right places, what comes to coding. But then again… Well, you get the point, before we’re entering an infinite recursion.
As aside – for practical purposes in a game engine, I’d like to add a “stress causing factor” for the boids. This is related to the density of units in an area, centered around each boid. The stress level would need one thing first calculated: distance of all other boids to the boid itself.
When we have the distances, we can cut-off the population of boids to 2 sets: those within R (range), and the rest are outside of range.
The stress comes from necessity of making a lot of adjustments in a small period of time. So if a worm needs to jiggle a lot, it gets stressed. The jiggle amount is interesting metric. How should I define it in practical terms?