Как обслуживать 10 000 NPC в кадре без просадок GC

В двух словах о проблеме

Допустим, вы делаете симуляцию города. Или RTS. Или RPG с открытым миром. И у вас в сцене одновременно находится 5, 10, а то и 20 тысяч живых существ. У каждого свои цели, приоритеты, эмоции, социальные связи.

Ваша архитектура AI начинает трещать по швам.

Классический подход — дать каждому NPC компонент с методом Update() — перестаёт работать где-то после 500–1000 объектов. Дальше начинаются проблемы:

• 10 000 вызовов виртуальных методов за кадр → промахи кэша и давление на предсказатель переходов.

• LINQ-запросы для поиска ближайшего врага → аллокации и GC.

• Пересчёт эмоций по полному графу → O(N²) на каждое распространение.

• Сортировка всех NPC для выбора топ-10 → пустая трата O(N log N) сравнений.

В результате ваши 60 FPS превращаются в 30, а потом в 15. Игроки жалуются на фризы (это GC собрал 20 мегабайт временных массивов). Вы начинаете нанимать отдельного инженера по оптимизации AI.

Этого можно избежать, если с самого начала заложить правильные примитивы.

Что лежит в коробке

Библиотека GameAI.Net — это не фреймворк. Это набор низкоуровневых алгоритмических кирпичей. Вы не обязаны использовать всё. Вы можете взять только то, что нужно, и встроить в свою архитектуру.

Версия: 0.1.7
Целевая платформа: .NET 8.0+
Установка: dotnet add package GameAI.Net

Четыре модуля:

1. Behavior Tree на стероидах

Вместо иерархии объектов — плоский массив инструкций. Вместо рекурсии — цикл с индексом. Вместо виртуальных вызовов — переключатель по NodeKind. Результат: дерево для 10 000 NPC тикает за 285 микросекунд.

Есть две формы хранения чёрной доски:

• Blackboard — для быстрого прототипирования (по одному NPC).

• BlackboardSoA — Structure of Arrays для массовых тиков (рекомендовано).

2. Utility Scoring с SIMD

Батчевая оценка пригодности через взвешенную сумму признаков. Внутри — SIMD-инструкции (AVX2/SSE), которые процессор выполняет за один такт на несколько значений.

ScoreAll принимает матрицу (кандидаты × признаки) и вектор весов. Для 100 000 кандидатов с 64 признаками однопоточный расчёт занимает 4.68 мс, параллельный — 1.16 мс на i5-11400F.

3. Эмоциональный граф

Разреженный граф в CSR-формате для распространения влияния между NPC. Поддерживает два режима:

• Step — полный обход всех узлов (дорого).

• StepActive — только узлы, изменившиеся в этом кадре (рекомендовано).

Для 100 000 узлов с 10% активных источников и обновлением раз в 4 кадра — ~0.45 мс на кадр.

4. Селектор толпы с квотами

Задача: из набора кандидатов выбрать топ-K в каждой группе (например, 3 ближайших врага, 2 с низким здоровьем, 5 с высоким уроном). Без полной сортировки, без аллокаций.

SelectWithQuotasInto использует быстрый selection на стеке для малых квот.

Быстрый старт

Поведенческое дерево

using GameAI.Net.BehaviorTree;using GameAI.Net.Core;// Условие: float[0] > 0.5var condition = new ConditionProgram(new[]{    new Instruction(OpCode.LoadFloat, argI: 0),    new Instruction(OpCode.PushConst, argF: 0.5f),    new Instruction(OpCode.Gt)});// Дерево: Selector(Sequence(Condition, Attack), Idle)var nodes = new[]{    new Node(NodeKind.Selector, 0, 0),    new Node(NodeKind.Sequence, 0, 0),    new Node(NodeKind.Condition, 0, 0),    new Node(NodeKind.Action, 1, 0),  // Attack    new Node(NodeKind.Action, 0, 0)   // Idle};var children = new[] { 1, 4, 2, 3 };var childStart = new[] { 0, 2, 4, 4, 4 };var childCount = new[] { 2, 2, 0, 0, 0 };var tree = new BehaviorTree(nodes, children, childStart, childCount,     new[] { condition }, new MyActions());// Для одного NPCvar bb = new Blackboard(floats: new float[8]);bb.SetFloat(0, 0.9f);tree.TickFast(new TickContext(1f/60f, bb));// Для 10 000 NPC (SoA)var bbSoA = new BlackboardSoA(10000, floatSlots: 8);for (int i = 0; i < 10000; i++){    bbSoA.SetFloat(i, 0, Random.Shared.NextSingle());    tree.TickFast(1f/60f, bbSoA, i);}

Пакетная оценка пригодности

using GameAI.Net.Utility;using SlidingRank.FastOps;int agents = 10000;int featuresCount = 32;var data = new float[agents * featuresCount];// ... заполняем признаки ...var features = new EmbeddingMatrix(data, agents, featuresCount);var weights = new float[featuresCount];var scores = new float[agents];UtilityScorer.ScoreAll(features, weights, scores);      // последовательноUtilityScorer.ScoreAllParallel(features, weights, scores); // параллельно

Граф эмоций

using GameAI.Net.Emotion;int npcCount = 5000;int[] start = new int[npcCount + 1];int[] to = new int[totalEdges];float[] weight = new float[totalEdges];var graph = new EmotionGraph(npcCount, start, to, weight);// Только активные источникиbool[] active = new bool[npcCount];active[42] = true; // NPC 42 разозлилсяgraph.StepActive(active, 1f/60f);

Выбор с квотами

using GameAI.Net.Crowd;Span<Candidate> candidates = stackalloc Candidate[5000];// ... заполняем ...Span<GroupQuota> quotas = stackalloc GroupQuota[]{    new(1, 2), // группа 1: 2 кандидата    new(2, 1), // группа 2: 1 кандидат    new(3, 3)  // группа 3: 3 кандидата};Span<int> output = stackalloc int[100];int written = CrowdDirector.SelectWithQuotasInto(candidates, quotas, output);

Цифры, которые имеют значение

Тесты на Intel Core i5-11400F, Windows 11, .NET 8.0, BenchmarkDotNet 0.15.8.

Сложим всё вместе для 10 000 NPC с полным AI (поведение + скоринг + эмоции раз в 4 кадра):

• Behavior Tree: 0.285 мс

• Utility Scoring (параллельно): 1.16 мс (доля от 10 000 из 100 000)

• Emotion Graph: 0.45 мс

Итого: ~1.9 мс на кадр. Остаётся 14+ мс на рендеринг, физику, анимации и сеть.

Почему это работает

Отсутствие аллокаций в горячем цикле

В библиотеке всё, что можно предвыделить — предвыделено при инициализации. То, что можно разместить на стеке — размещается на стеке через stackalloc. Временные массивы не создаются. GC просто нечего собирать.

Кэш-локальность

BlackboardSoA хранит все значения одного типа подряд. Когда вы тикаете 10 000 NPC подряд, процессор загружает в кэш непрерывный блок памяти, а не дёргает указатели на разбросанные объекты.

SIMD без вашего участия

SIMD-инструкции включены через SlidingRank.FastOps. Вам не нужно писать Vector<T> или Span<T>. Вы просто вызываете ScoreAll, а внутри уже решено: есть AVX2 — используем его, нет — SSE, нет SSE — обычные float.

Слабая связность модулей

Можете использовать только Utility Scoring, игнорируя остальное. Можете переписать свой селектор толпы, но взять граф эмоций. Можете даже не использовать библиотеку в горячем пути, а только для прототипирования.

Архитектурные паттерны

LOD для AI

if (distance < 20f){    // Полный AI каждый кадр    tree.TickFast(deltaTime, bb, i);    scorer.ScoreAll(features, weights, scores);}else if (distance < 50f && frame % 3 == 0){    // Только поведение, каждый 3-й кадр    tree.TickFast(deltaTime, bb, i);}else if (frame % 10 == 0){    // Минимальное обновление состояния    bb.SetFloat(i, "lastSeen", Time.time);}

Один мастер-тик вместо тысячи Update()

В Unity особенно важно: не вешайте скрипт с Update() на каждого NPC.

public class AIScheduler : MonoBehaviour{    private static BlackboardSoA _blackboard;    private static BehaviorTree _tree;        void Update()    {        for (int i = 0; i < _blackboard.AgentCount; i++)        {            _tree.TickFast(Time.deltaTime, _blackboard, i);        }    }}

Активные источники в графе эмоций

Вместо Step() (полный пересчёт) используйте StepActive() и ведите массив флагов isDirty. Эмоция изменилась только у нескольких NPC → обновите только их и их соседей.

Чего библиотека не делает

GameAI.Net сознательно не включает:

• Навигацию — вы используете A*, NavMesh, потоковые поля отдельно.

• Анимации — это ответственность вашей анимационной системы.

• Сеть — синхронизация состояний NPC остаётся за вами.

• Редактор — вы определяете деревья поведения в коде или генерируете их из визуального редактора сами.

• Готовые шаблоны — библиотека даёт кирпичи, а не дом.

Масштабирование за пределы одного ядра

Параллельный ScoreAllParallel уже использует Parallel.For. Для остальных модулей многопоточность пока не встроена — вы можете сами разбить массив NPC на диапазоны и запустить несколько задач.

var options = new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount };Parallel.For(0, _blackboard.AgentCount, options, i =>{    _tree.TickFast(deltaTime, _blackboard, i);});

Предупреждение: Parallel.For создаёт аллокации (разделители диапазонов, делегаты). Для строгой zero-alloc-многопоточности используйте свой пул воркеров или Unity Jobs.

Бесплатное тестирование — без ограничений. Коммерческое использование требует лицензии.

GameAI.Net решает конкретную задачу: обслуживание тысяч NPC с предсказуемой латентностью без GC-спайков.

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

Попробуйте на своих данных. Если ваш AI тормозит и фризит — возможно, вы нашли ответ.