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

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

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

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

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 скрипта стоит добавить вращение. Для поворота объектов есть огромное количество вариантов, но мы возьмём Vector3.RotateTowards, ибо он простой и нам всё равно без разницы. Сначала проверяем нужно ли вообще что-то делать, потом плавно поворачиваем.

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

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

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, который требует вычисления квадратного корня. Для сравнения расстояний его можно заменить Vector3.sqrMagnitude. Заодно поменяем 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 встречается больше дюжины раз и зачастую происходит в цикле. Умножаем это на количество боидов и получается грустная картина. За доступом к transform’у на самом деле скрывается дорогой поиск компонента. Чтобы этого избежать, закешируем его в отдельной переменной во время Awake. Это событие вызывается до начала игры во время загрузки. Заодно можно поменять вызов трансформа из коллайдера на вызов публичной переменной скрипта, а сравнение с собственным коллайдером на условие с квадратом расстояния.

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 начинает захватывать всё большее количество коллайдеров и мы получаем практически ту же самую квадратичную сложность простого перебора по всем боидам.

Согласно интернету, ласточки в стаях ориентируются всего по полудюжине соседей. Чем боиды хуже? Берём и банально ограничиваем цикл ещё одним условием. Для двух условий лучше подойдёт цикл 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 и добавим парочку новых. Добавляем параметр 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.

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

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

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 и отключим проверку столкновений между боидами в настройках физики.

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

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

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

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

Заключение

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

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