We optimize Boid's on Unity

Did you know that grasshoppers, being thrown into a bucket, begin to march in a circle as in the picture above? True, the top is not grasshoppers, and the Boids are a model of the collective behavior of birds, bees, fish and other living creatures. Despite the simplicity of the model, it demonstrates the emergent properties: boids gather in a heap, fly in flocks in a circle, attack people.

This is the second part of the article, devoted to various tricks of Unity and C # optimization, which increase the performance of the algorithm from the first part a couple of dozen times.

A couple of modifications

Let's start with a few cosmetic changes that will simplify further work and bring the code closer to what can be found in real life. Let's change the model of the boat so that it looks more like a bird and at the same time contains fewer triangles. A simple Blender pyramid will be enough. We throw the .blend file into the project daddy, select it in the inspector and disable the extra in the import settings. We copy the old prefab and make a new one, on which we will conduct experiments.
')


Since the prefab now has a direction, you should add a rotation to the Update script. There are a huge number of options for turning objects, but we’ll take Vector3.RotateTowards , because it’s simple and we don’t care. First, we check whether we need to do something at all, then turn it smoothly.

 if (velocity != Vector3.zero && transform.forward != velocity.normalized) { transform.forward = Vector3.RotateTowards(transform.forward, velocity, 10, 1); } 

At the same time we will alter the code that puts boids on the stage. Junk hierarchy is bad practice, so we’ll hide all the boids with Transform.parent .

 var boid = Instantiate(boidPrefab, Random.insideUnitSphere * 25, Quaternion.identity) as Transform; boid.parent = transform; 

Getting down to business

Let's start with the banal. In our cycle, we subtract transform.position three times - boid.transform.position. This is bad, better shove the result into a variable. On a hundred Boids, this may not matter, but on a couple of thousands in a cycle, and even a few times a second, the difference will already be.

 var vector = transform.position - boid.transform.position; if (boid != collider && vector.magnitude < separationDistance) { separation += vector / vector.magnitude; separationCount++; } 

In the same place , there is Vector3.magnitude , which requires square root calculations. To compare distances, you can replace Vector3.sqrMagnitude . At the same time, we will change the magnitude in the formula for calculating the weighted vector, this will not greatly affect the result.

 if (boid != collider && vector.sqrMagnitude < separationDistance * separationDistance) { separation += vector / vector.sqrMagnitude; separationCount++; } … if (transform.position.sqrMagnitude > 25 * 25) { velocity += -transform.position.normalized; } 

Transform and GetComponent

In our code, the transform call occurs more than a dozen times and often occurs in a loop. We multiply this by the number of boids and we get a sad picture. Behind the access to transform is actually an expensive component search. To avoid this, we cache it in a separate variable during an awake . This event is fired before the game starts at boot time. At the same time, you can change the transform call from the collider to a call to a public script variable, and compare with your own collider to a condition with a square of distance.

 public Transform tr; void Awake() { tr = transform; } 

Replace all transform references with tr.

 foreach (var boid in boids) { var b = boid.GetComponent<Boid>(); cohesion += b.tr.position; alignment += b.velocity; if (vector.sqrMagnitude > 0 && (tr.position - b.tr.position).magnitude < separationDistance) { separation += (tr.position - b.tr.position) / (tr.position - b.tr.position).magnitude; separationCount++; } } 

Optimize further

Well, already much better, but the FPS still sags when the boids get very close. And all because Physics.OverlapSphere begins to capture an increasing number of colliders and we get almost the same quadratic complexity of a simple search through all boids.

According to the Internet , swallows in flocks are oriented in just half a dozen neighbors. Than boida worse? We take and tritely limit the cycle to one more condition. For two conditions, the for loop is better suited. In addition, it makes sense to limit not only the maximum number of neighbors, but also the minimum. Add an exit condition if there are no neighbors nearby. In addition, we will have to change the denominator in the calculation of vectors, otherwise, with a large crowding of neighbors, the Boids will not have a chance to get out.

 private int maxBoids = 5; … boids = Physics.OverlapSphere(tr.position, cohesionRadius); if (boids.Length < 2) return; … for (var i = 0; i < boids.Length && i < maxBoids; i++) { var b = boids[i].GetComponent<Boid>(); cohesion += b.tr.position; alignment += b.velocity; var vector = tr.position - b.tr.position; if (vector.sqrMagnitude > 0 && vector.sqrMagnitude < separationDistance * separationDistance) { separation += vector / vector.magnitude; separationCount++; } } cohesion = cohesion / (boids.Length > maxBoids ? maxBoids : boids.Length); 

Now the main problem is that we update the velocity vector too often. Let's step aside a bit and put things in order in the inspector to make it easier to tweak the algorithm. Let's make all important variables public, but hide some with the HideInInspector attribute and add a couple of new ones. We add the tick parameter, we substitute it in a timer on the timer.

 public int turnSpeed = 10; public int maxSpeed = 15; public float cohesionRadius = 7; public int maxBoids = 10; public float separationDistance = 5; public float cohesionCoefficient = 1; public float alignmentCoefficient = 4; public float separationCoefficient = 10; public float tick = 2; [HideInInspector] public Vector3 velocity; [HideInInspector] public Transform tr; … InvokeRepeating("CalculateVelocity", 0, tick); 

Next, do the feint ears and set the update rate of 2 seconds. Yes, yes, you heard right, twenty times less often than we had. At the same time adjust the factors. Now, instead of hundreds of boids, we can create a thousand.

Optimized, optimized, but not optimized

New problem. Every two seconds, all boids start the calculation of new vectors and there is a noticeable ripple. The effect is, of course, interesting, but the birds do not know how. We do one more simple optimization - we distribute calculations on time with the help of Random.value .

 InvokeRepeating("CalculateVelocity", Random.value * tick, tick); 

Well, so that the start of the simulation does not look too strange, in Awake we also add an element of randomness from Random.onUnitSphere .

 velocity = Random.onUnitSphere * maxSpeed; 

We look at our code more closely.

 var b = boids[i].GetComponent<Boid>(); … var vector = tr.position - b.tr.position; 

For the creation of temporary variables in the cycle, the evil garbage collector will sooner or later eat off our processor. If we know that we regularly do the same actions, then we can create permanent variables.

 private Boid b; private Vector3 vector; private int i; 

We should not forget that sometimes, instead of optimizing the code, it is better to optimize the logic. In Update, we have a check for going beyond the boundaries of the sphere where normalization is used.

 velocity += -tr.position.normalized; 

This is too accurate a function for such a purpose. If we need not a strict unit vector, but only a direction, then the vector can be simply divided.

 velocity += -tr.position/25; 

We can knock off another couple of milliseconds of calculations if we take out the turn of the boids into a separate function and run on a timer.

 InvokeRepeating("UpdateRotation", Random.value, 0.1f); … void UpdateRotation() { if (velocity != Vector3.zero && model.forward != velocity.normalized) { model.forward = Vector3.RotateTowards(model.forward, velocity, turnSpeed, 1); } } 

Physics

You probably noticed that we do not use physics at all, if we do not take into account the search for colliders. We can save a little more resources if we move the boids into a separate layer, we will look for colliders using LayerMask and turn off collision checking between boids in the physics settings.

 public LayerMask boidsLayer; … boids = Physics.OverlapSphere(tr.position, cohesionRadius, boidsLayer.value); 

A bunch of FPS can be obtained if you unscrew to the minimum the Solver Iteration Count in the Physics Manager . In addition, you can try to play with the Fixed Timestep and Maximum Allowed Timestep in the Time Manager , but if you get carried away, the simulation will become chaotic and unattractive.

One more nuance is associated with rotation. When we rotate the model, we rotate the spherical collider attached to it. Expensive and useless. The problem is solved by separating the model from the collider in the hierarchy. So you can win another FPS heels.

 public Transform model; … if (velocity != Vector3.zero && model.forward != velocity.normalized) { model.forward = Vector3.RotateTowards(model.forward, velocity, turnSpeed, 1); } 

Conclusion

That's all. The bulk of resources eats away moving heaps of objects in a frame and searching for neighbors. It's hard to do something with the first one, but for the second one you need to stop using physics altogether and change it to tricky data structures, but this is a topic for a separate article. I hope that the wise hackers in the comments will offer their options for accelerating the boids.


Note: The code for the links below is outdated; see the Procedural Toolkit for the latest version.

Sources on GitHub | Online version for owners of Unity Web Player