Знаете ли вы, что кузнечики, будучи брошенными в ведёрко, начинают маршировать по кругу как на анимации выше? Правда сверху не кузнечики, а Boids — модель коллективного поведения птичек, пчёлок, рыбок и другой живности. Несмотря на простоту модели, она демонстрирует эмерджентные свойства: боиды собираются в кучу, летают стаями по кругу, нападают на людей.
В первой части статьи мы бесхитростно реализовали алгоритм боидов. Правда он плохо масштабируется и больше сотни боидов наша демонстрация не держала. Путём различных манипуляций это число можно увеличить в пару десятков раз. Вторая часть статьи посвящена оптимизациям алгоритма и различным трюкам.
Парочка модификаций
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
Автор: BasmanovDaniil