Оптимизируем Boid’ов на Unity

Знаете ли вы, что кузнечики, будучи брошенными в ведёрко, начинают маршировать по кругу как на анимации выше? Правда сверху не кузнечики, а Boids ^[1] — модель коллективного поведения птичек, пчёлок, рыбок и другой живности. Несмотря на простоту модели, она демонстрирует эмерджентные свойства: боиды собираются в кучу, летают стаями по кругу, нападают на людей.

В первой части статьи ^[2] мы бесхитростно реализовали алгоритм боидов. Правда он плохо масштабируется и больше сотни боидов наша демонстрация не держала. Путём различных манипуляций это число можно увеличить в пару десятков раз. Вторая часть статьи посвящена оптимизациям алгоритма и различным трюкам.

Парочка модификаций

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

Начнём с нескольких косметических изменений, которые упростят дальнейшую работу и приблизят код к тому, что может встретиться в реальной жизни. Поменяем модельку боида, чтобы она была больше похожа на птицу и в то же время содержала меньше треугольников. Простенькой пирамидки из Blender'а будет достаточно. Кидаем файл .blend в папочку проекта, выделаем в инспекторе и в настройках импорта отключаем лишнее. Копируем старый префаб и делаем новый, на котором будем ставить эксперименты.

Поскольку у префаба теперь появилось направление, в Update скрипта стоит добавить вращение. Для поворота объектов есть огромное ^[3] количество ^[4] вариантов ^[5], но мы возьмём Vector3.RotateTowards ^[6], ибо он простой и нам всё равно без разницы. Сначала проверяем нужно ли вообще что-то делать, потом плавно поворачиваем.

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

Заодно переделаем код, который расставляет боиды на сцене. Мусорить в иерархии — плохая практика, поэтому спрячем все боиды с помощью Transform.parent ^[7].

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

Приступаем к делу

Начнём с банального. В нашем цикле три раза выполняется вычитание transform.position — boid.transform.position. Это плохо, лучше засунем результат в переменную. На сотне боидов это может не иметь значения, но на паре тысяч в цикле да ещё и несколько раз в секунду разница уже будет.

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

Там же неподалёку есть Vector3.magnitude ^[8], который требует вычисления квадратного корня. Для сравнения расстояний его можно заменить Vector3.sqrMagnitude ^[9]. Заодно поменяем magnitude в формуле вычисления взвешенного вектора, это не сильно повлияет на результат.

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

Transform и GetComponent

В нашем коде вызов transform ^[10] встречается больше дюжины раз и зачастую происходит в цикле. Умножаем это на количество боидов и получается грустная картина. За доступом к transform'у на самом деле скрывается дорогой поиск компонента. Чтобы этого избежать, закешируем его в отдельной переменной во время Awake ^[11]. Это событие вызывается до начала игры во время загрузки. Заодно можно поменять вызов трансформа из коллайдера на вызов публичной переменной скрипта, а сравнение с собственным коллайдером на условие с квадратом расстояния.

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

Заменим все обращения к transform на 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++;
    }
}

Оптимизируем дальше

Ну что, уже значительно лучше, но FPS всё равно проседает, когда боиды сильно сближаются. А всё потому, что Physics.OverlapSphere ^[12] начинает захватывать всё большее количество коллайдеров и мы получаем практически ту же самую квадратичную сложность простого перебора по всем боидам.

Согласно интернету ^[13], ласточки в стаях ориентируются всего по полудюжине соседей. Чем боиды хуже? Берём и банально ограничиваем цикл ещё одним условием. Для двух условий лучше подойдёт цикл for. Кроме того, имеет смысл ограничить не только максимальное количество соседей, но и минимальное. Добавим условие выхода, если поблизости нет соседей. Кроме того, нам придётся изменить знаменатель в вычислении векторов, иначе при большой скученности соседей у боидов не будет шанса выбраться.

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

Теперь самая главная проблема — мы слишком часто обновляем вектор velocity. Немного шагнём в сторону и наведём порядок в инспекторе, чтобы было проще настраивать алгоритм. Сделаем все важные переменные публичными, но некоторые спрячем с помощью атрибута HideInInspector ^[14] и добавим парочку новых. Добавляем параметр 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);

Далее делаем финт ушами и выставляем частоту обновления 2 секунды. Да-да, вы не ослышались, в двадцать раз реже, чем у нас было. Заодно подкорректируем множители. Теперь вместо сотни боидов мы можем создавать тыщу.

Оптимизировали-оптимизировали, да не выоптимизировали

Новая проблема. Раз в две секунды у всех боидов запускается вычисление новых векторов и появляется заметная пульсация. Эффект, конечно, интересный, но птицы так не умеют. Делаем ещё одну простую оптимизацию — разносим вычисления по времени с помощью Random.value ^[15].

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

Ну и чтобы старт симуляции не выглядел слишком странно, в Awake тоже добавим элемент случайности из Random.onUnitSphere ^[16].

velocity = Random.onUnitSphere * maxSpeed;

Приглядываемся к нашему коду ещё внимательнее.

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

За создание временных переменных в цикле злой мусоросборщик рано или поздно отъест у нас процессор. Если мы знаем, что регулярно делаем одни и те же действия, то можно создать постоянные переменные.

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

Нельзя также забывать, что иногда вместо оптимизации кода лучше оптимизировать логику. В Update у нас есть проверка на выход за границы сферы, где используется нормализация.

velocity += -tr.position.normalized;

Это слишком точная функция для такой цели. Если нам нужен не строгий единичный вектор, а только направление, то вектор можно просто поделить.

velocity += -tr.position/25;

Мы можем скостить ещё пару миллисекунд расчётов, если вынесем поворот боидов в отдельную функцию и будем запускать по таймеру.

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

Физика

Вы наверное заметили, что мы совсем не используем физику, если не принимать в расчёт поиск коллайдеров. Мы можем сэкономить ещё немного ресурсов, если вынесем боидов в отдельный слой, будем искать коллайдеры с помощью LayerMask ^[17] и отключим проверку столкновений между боидами в настройках физики.

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

Кучу FPS можно получить если выкрутить на минимум Solver Iteration Count ^[18] в Physics Manager ^[19]. Кроме того, можно попробовать поиграться с Fixed Timestep и Maximum Allowed Timestep в Time Manager ^[20], но если сильно увлечься, то симуляция станет хаотичной и непривлекательной.

Ещё один ньюанс связан с вращением. Когда мы поворачиваем модель, мы поворачиваем привязанный к ней сферический коллайдер. Дорого и бесполезно. Проблема решается отделением модели от коллайдера в иерархии. Так можно выиграть ещё пяток FPS.

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

Заключение

На этом всё. Основную часть ресурсов отъедает перемещение кучи объектов в кадре и поиск соседей. С первым сложно что-то поделать, а вот для второго нужно вообще перестать использовать физику и поменять её на хитрые структуры данных, но это уже тема для отдельной статьи. Надеюсь, что мудрые читатели в комментариях предложат свои варианты ускорения боидов.

Исходники на GitHub ^[21] | Онлайн версия для обладателей Unity Web Player ^[22]

Автор: BasmanovDaniil

Источник ^[23]