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

Допустим, вы делаете симуляцию города. Или 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.5
var 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());
// Для одного NPC
var 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 тормозит и фризит — возможно, вы нашли ответ.