Optimization of Boids

Boids - a model of collective behavior of birds, bees, fish and other animals. Despite the simplicity of the model, it demonstrates emergent properties: Boyd gather together, fly in flocks around.

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

Modification

Before

using UnityEngine;

public class Boid : MonoBehaviour
{
    public Vector3 velocity;

    private float cohesionRadius = 10;
    private float separationDistance = 5;
    private Collider[] boids;
    private Vector3 cohesion;
    private Vector3 separation;
    private int separationCount;
    private Vector3 alignment;
    private float maxSpeed = 15;

    private void Start()
    {
        InvokeRepeating("CalculateVelocity", 0, 0.1f);
    }

    void CalculateVelocity()
    {
        velocity = Vector3.zero;
        cohesion = Vector3.zero;
        separation = Vector3.zero;
        separationCount = 0;
        alignment = Vector3.zero;

        boids = Physics.OverlapSphere(transform.position, cohesionRadius);
        foreach (var boid in boids)
        {
            cohesion += boid.transform.position;
            alignment += boid.GetComponent<Boid>().velocity;

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

        cohesion = cohesion / boids.Length;
        cohesion = cohesion - transform.position;
        cohesion = Vector3.ClampMagnitude(cohesion, maxSpeed);
        if (separationCount > 0)
        {
            separation = separation / separationCount;
            separation = Vector3.ClampMagnitude(separation, maxSpeed);
        }
        alignment = alignment / boids.Length;
        alignment = Vector3.ClampMagnitude(alignment, maxSpeed);

        velocity += cohesion + separation * 10 + alignment * 1.5f;
        velocity = Vector3.ClampMagnitude(velocity, maxSpeed);
    }

    void Update()
    {
        if (transform.position.magnitude > 25)
        {
            velocity += -transform.position.normalized;
        }

        transform.position += velocity * Time.deltaTime;

        Debug.DrawRay(transform.position, separation, Color.green);
        Debug.DrawRay(transform.position, cohesion, Color.magenta);
        Debug.DrawRay(transform.position, alignment, Color.blue);
    }
}

Let's start with a few cosmetic changes that will facilitate further work and get closer to the code that may be encountered in real life. Let's change model Boyd, that it was more like a bird, and at the same time contained less triangles. Unpretentious pyramid of Blender. will suffice. Throw .blend file in the project folder, do inspector and import settings. Turning off the excess. Copy the old prefab and make a new one, which will make experiments.

Because prefab now appeared the direction in Update script should add rotation. To rotate objects have a lot of options, but we take Vector3.RotateTowards, because it is simple and we still do not care. First, check if we need to do something, then gradually turn.

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

At the same time remake code that puts Boyd on stage. Litter in the hierarchy - bad practice, so hide all Boyd via Transform.parent.

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

In this cycle three times subtracts transform.position - boid.transform.position. Better to poke result in a variable. Boyd is on a hundred may not matter, but on a couple of thousand in the cycle and even several times a second difference will already be.

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

There's also near there Vector3.magnitude, which requires the calculation of the square root. For comparison it can be replaced distances Vector3.sqrMagnitude. At the same time change the magnitude in the formula of calculating the weighted vector, it does 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, call transform found more than a dozen times, and often occurs in a loop. Multiply this by the number of Boyd. For access to transform'u actually hiding an expensive search component. To avoid this, we cache it in a separate variable during Awake. This event is raised before the game starts at boot time. At the same time, you can change the call from the transformer to the challenge collider public script variable, and a comparison with its own collider on the condition of the square of the distance.

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

Replace all references to transform to 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++;
    }
}

Move on...

FPS still slows when Boyd strongly converging. And all because Physics.OverlapSphere begins to capture a growing number of colliders and we get almost the same quadratic complexity of a simple listing of all Boyd.

According to the internet, swallows in flocks are guided by just half a dozen neighbors. Boyd than worse? Take the limit cycle and corny one more condition. For two conditions, we use cycle for. Also, it makes sense to limit not only the maximum number of neighbors, but the minimum. Add an exit condition when there is no neighbors. In addition, we have to change the denominator in the calculation of vectors, otherwise at high crowding neighbors of Boyd no chance to escape.

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 - too often we update the vector velocity. We make all the important variables are public, but some attribute to hide HideInInspector and add a couple of new ones. Add option tick.

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);

Exhibit refresh rate of 2 seconds. In twenty times less than we had. At the same time will correct factors. Now, instead of hundreds of Boyd we can create a thousand.

A new problem. Once every two seconds all Boyd started calculating new vectors and appears noticeable ripple. The effect, of course, interesting, but the birds do not know how. Do another simple optimization - resound computation time using Random.value.

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

At the start of the simulation did not look too strange in Awake add an element of randomness of Random.onUnitSphere.


velocity = Random.onUnitSphere * maxSpeed;

Also ...

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

For the creation of temporary variables in a cycle. Sweep cleaner
 will kill our processor. If we know that regularly do the same steps, you can create a permanent variables.

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

We should not forget that sometimes instead of code optimization to better optimize logic. In the Update we have a check for exceeding the limits of the areas where normalization is used.

velocity += -tr.position.normalized;

It's too precise function for this purpose. If we do not need a strict unit vector, and only the direction, the vector can simply be divided.

velocity += -tr.position/25;

We can knock off a couple of milliseconds calculations, if tolerated Boyd turn into a separate function and will start the 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 have probably noticed that we do not use physics, if you do not take into account the search colliders. We can save a little more resources, if tolerated Boyd in a separate layer, we seek colliders via LayerMask and disable scanning of clashes between Boyd settings physics.

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

FPS can be obtained if you turn Solver Iteration Count in Physics Manager. In addition, you can try to play with Fixed Timestep and Maximum Allowed Timestep in Time Manager, but if you get excited about much, the simulation will become chaotic and unattractive.

Another nuance is associated with rotation. When we turn to the model, we turn to attach to it a spherical collider. The problem is solved by separating the model collider in the hierarchy. So you can get more FPS.

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 off moving piles of objects in the frame and search for neighbors. With the first hard something about it, but for a second you need to do to stop using physics and change it on the sly data structures, but that's a topic for another article.

The latest version, see the Procedural Toolkit

 

using UnityEngine;

public class Boid : MonoBehaviour
{
    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;
    public Transform model;
    public LayerMask boidsLayer;

    [HideInInspector] public Vector3 velocity;
    [HideInInspector] public Transform tr;

    private Collider[] boids;
    private Vector3 cohesion;
    private Vector3 separation;
    private int separationCount;
    private Vector3 alignment;

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

    void Awake()
    {
        tr = transform;
        velocity = Random.onUnitSphere*maxSpeed;
    }

    private void Start()
    {
        InvokeRepeating("CalculateVelocity", Random.value * tick, tick);
        InvokeRepeating("UpdateRotation", Random.value, 0.1f);
    }

    void CalculateVelocity()
    {
        boids = Physics.OverlapSphere(tr.position, cohesionRadius, boidsLayer.value);
        if (boids.Length < 2) return;

        velocity = Vector3.zero;
        cohesion = Vector3.zero;
        separation = Vector3.zero;
        separationCount = 0;
        alignment = Vector3.zero;
        
        for (i = 0; i < boids.Length && i < maxBoids; i++)
        {
            b = boids[i].GetComponent<Boid>();
            cohesion += b.tr.position;
            alignment += b.velocity;
            vector = tr.position - b.tr.position;
            if (vector.sqrMagnitude > 0 && vector.sqrMagnitude < separationDistance * separationDistance)
            {
                separation += vector / vector.sqrMagnitude;
                separationCount++;
            }
        }

        cohesion = cohesion / (boids.Length > maxBoids ? maxBoids : boids.Length);
        cohesion = Vector3.ClampMagnitude(cohesion - tr.position, maxSpeed);
        cohesion *= cohesionCoefficient;
        if (separationCount > 0)
        {
            separation = separation / separationCount;
            separation = Vector3.ClampMagnitude(separation, maxSpeed);
            separation *= separationCoefficient;
        }
        alignment = alignment / (boids.Length > maxBoids ? maxBoids : boids.Length);
        alignment = Vector3.ClampMagnitude(alignment, maxSpeed);
        alignment *= alignmentCoefficient;

        velocity = Vector3.ClampMagnitude(cohesion + separation + alignment, maxSpeed);
    }

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

    void Update()
    {
        if (tr.position.sqrMagnitude > 25 * 25)
        {
            velocity += -tr.position / 25;
        }
        tr.position += velocity * Time.deltaTime;
    }
}

 

 

All data posted on the site represents accessible information that can be browsed and downloaded for free from the web.

http://habrahabr.ru/post/182690/

 

User replies

No replies yet