Геймдизайнер-телепат
0,1
рейтинг
10 июня 2013 в 11:10

Разработка → Оптимизируем Boid'ов на Unity tutorial



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

Это вторая часть статьи, посвящённая различным хитростям оптимизации Unity и C#, которые увеличивают производительность алгоритма из первой части в пару десятков раз.

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


Напомню на чём мы остановились. Boid.cs из предыдущей части без оптимизаций
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);
}

Заключение


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

Оптимизированная версия Boid.cs
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;
    }
}


Внимание: Код по ссылкам ниже устарел, последнюю версию смотрите в Procedural Toolkit

Исходники на GitHub | Онлайн версия для обладателей Unity Web Player
Даниил Басманов @BasmanovDaniil
карма
190,2
рейтинг 0,1
Геймдизайнер-телепат
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (15)

  • +1
    Вращение лучше на кватернионах делать. Подозреваю, будут проблемы, когда кратчайшим будет поворот из 359 градусов в 1 градус.
    Еще мне кажется, что следовало бы сразу реализовывать инстанциирование боидов в пулл
    • +1
      Не успел дописать про пулл…
      Если завести синглтон или просто статический менеджер боидов с пуллом инстансов, то не нужен будет код, вида:
      boids = Physics.OverlapSphere(tr.position, cohesionRadius, boidsLayer.value);
      

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

      PS: Сейчас боиды инстанциируются один раз при старте (если я правильно понял), но потом может понадобиться изменять размер стаи. Тогда пулл позволит не делать инстанциирование в реальном времени. А инстанциирование, как известно, дорогая операция.
      • 0
        Если пробегаться и сравнивать каждого с каждым, то получаем сложность O(n^2) и потолок в пару сотен боидов. Внутри Physics.OverlapSphere скрывается какая-то оптимизированная магия от Nvidia, которая делит пространство на кусочки и ограничивает область поиска.

        У меня была идея сделать иерархию симуляций боидов, чтобы, например, десять боидов всегда знали о существовании друг друга. У этих десяти боидов есть командир, который знает о существовании девяти других командиров. У них в свою очередь тоже есть кто-то выше и так далее. Но в итоге всё выглядело очень странно, у меня не получилось толком настроить эту мешанину, хотя в интернете встречал такой подход.
        • +1
          Подозреваю, что работать эффективно та магия будет только на железе от Nvidia. Тогда потеряете в переносимости. Как вариант, сделать похожую оптимизацию в логике. Разбить сферу спавна на конечное число зон, разместить по случайным зонам нужное число боидов и статически назначить нужное количество соседей (ну или один раз по радиусу определить). Жестко карать боидов за излишнее смещение боида относительно исходного центра или лидера стаи.

          ПС: извините… Недочитал каммент с мобилы. Вы предложили то же.
          • 0
            У статических соседей проблема оказалась в том, что они статические :) Становится заметно, что все боиды передвигаются кучками. Я пробовал разбавлять иерархию одиночными боидами, но всё равно каша получалась с комочками. По идее, если иногда случайным разбивать группы на одиночек, а потом собирать в новые группы, то будет смотреться лучше. Но как я уже говрил, получается слишком много параметров для настройки, и я забросил этот вариант. Проще на GPU симуляцию делать, десятки тысяч боидов всё равно мало где нужны.
            • 0
              В принципе согласен — если надо облако бацилл, то лучше несколько систем частиц использовать. Так?
              • 0
                Ну да, много самостоятельных боидов могут быть нужны только в серьёзной симуляции, в остальных случаях можно схитрить и с помощью дыма и зеркал заставить игрока думать, что их больше.
  • –2
    Увидев первую картинку, сразу почему-то появились ассоциации с этой статьей)
    • +1
      Действительно, к чему бы это)
      • 0
        Надо добавить опрос «Обращаешь ли ты внимание на автора статьи, Хабраюзер?».
        Третьим вариантом поставить: «Распознаю по тексту. Пока распознавалка дает два варианта: Ализар / неАлизар»
        • +6
          Неправда, три варианта:
          1) Ализар
          2) Мицгол
          3) Ни один из вышеперечисленных
  • 0
    > Проблема решается отделением модели от коллайдера в иерархии
    То есть навесить коллайдер не на модельку птички, а на её родительский (пустой?) объект, который не будет вращаться, но будет перемещаться, так?
    Но тогда вращение нужно делать на внутренний объект с моделью, а перемещение — на внешний с коллайдером и внутренним. Или я что-то не понял?
    Покажите, пожалуйста, скриншот окна иерархии, чтобы было понятнее.
    • 0
      Прошу прощения за долгий ответ. Да, коллайдер в родителе, вращаемая модель внутри. Перемещение и приложение сил отдельно, визуализация вращения отдельно.

      image
  • 0
    Transform и GetComponent

    Я краем уха слышал, что в пятом Юнити уже заоптимизировали этот кейс и можно смело его использовать. Нет?
    • 0
      Надо бы проверить профайлером, но, если мне не изменяет память, разрабы юнити говорили, что кешируется не всё, и в циклах и апдейтах GetComponent всё равно работает медленнее.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.