В real-time играх и серверах часто возникает задача: из N объектов нужно выбрать K лучших, чтобы обновить их в этом кадре.

• AI для NPC: из 50 000 врагов обновить только 1000 самых важных.

• Анимации: из 10 000 персонажей показать детальные анимации только для 200 ближайших к камере.

• VFX: из 5000 частиц обновить только те, что в поле зрения.

• Сетка LOD: из 100 000 объектов выбрать 5000 для высокого качества.

Типичный подход — посчитать оценку для каждого объекта, затем отсортировать весь массив и взять первые K элементов.

// Наивный подход: полная сортировка
float[] scores = new float[N];
for (int i = 0; i < N; i++)
    scores[i] = Dot(features[i], weights);
Array.Sort(scores, ids); // O(N log N)
// Берём первые K

Проблема: сортировка 200 000 элементов занимает ~16 мс. Это весь бюджет кадра при 60 FPS. А ведь ещё нужно рендерить, обрабатывать физику, тикать AI.

Почему полная сортировка — это перебор

Сложность O(N log N). Для N = 200 000 это примерно 200 000 × 18 = 3.6 млн сравнений. Плюс аллокации временных массивов. Плюс GC-паузы.

А вам нужно всего K = 2000 элементов. Вы выбрасываете 198 000 отcортированных элементов. Это 99% потраченной работы впустую.

Дополнительная проблема: групповые квоты

Часто нужно не просто топ-K, а справедливое распределение между группами:

• Анимации: не более 200 объектов

• AI: не более 500 объектов

• VFX: не более 300 объектов

• Физика: не более 200 объектов

Сумма квот = K = 1200. Но если отсортировать общий список, одна группа (например, враги) может занять все топ-1200 мест, а другие группы (союзники, нейтралы) не получат ничего.

Правильное решение: отобрать топ-K с учётом квот на группу. Но как это сделать без многократной сортировки?

Решение: SIMD + селекция без полной сортировки

GameBudget.Net — библиотека для .NET 8.0+, которая решает обе задачи:

• Топ-K через heap-селекцию: O(N log K) вместо O(N log N)

• Групповые квоты через per-group heap: O(N log qᵍ) (где qᵍ — квота группы)

• SIMD-умножение матриц для скоринга через SlidingRank.FastOps

dotnet add package GameBudget.Net --version 1.0.0

Ключевые идеи

1. Heap-селекция (без полной сортировки)

   • Проходим по всем N объектам.

   • Поддерживаем min-heap размером K.

   • Если новый элемент лучше худшего в куче — заменяем.

   • В конце heap содержит топ-K, извлекаем в отсортированном порядке.

2. Per-group селекция с квотами

   • Для каждой группы свой min-heap размером с квоту группы.

   • Каждый элемент попадает только в heap своей группы.

   • В конце собираем результат: сначала группа 0, затем группа 1, и т.д.

3. SIMD для массового скоринга

   • Вместо scalar-цикла — SIMD-умножение (AVX2, SSE).

   • 16, 32, 64 признака обрабатываются за несколько инструкций.

Отличие от существующих решений

Подробнее о различиях

1. LINQ / Array.Sort

// Типичный LINQ-подход
var topK = items
    .Select(i => new { Id = i.Id, Score = Dot(i.Features, weights) })
    .OrderByDescending(x => x.Score)
    .Take(500)
    .ToArray(); // Множественные аллокации

Проблемы: аллокации на каждый элемент (анонимный тип), полная сортировка, делегаты на каждом шаге.

2. PriorityQueue из .NET

var heap = new PriorityQueue<int, float>();
for (int i = 0; i < N; i++)
{
    float score = Dot(features[i], weights);
    if (heap.Count < K)
        heap.Enqueue(i, -score);
    else if (score > -heap.PeekPriority())
    {
        heap.Dequeue();
        heap.Enqueue(i, -score);
    }
}

Проблемы: нет SIMD (скалярный dot), аллокации узлов внутри PriorityQueue, нет групповых квот.

3. QuickSelect (частичная сортировка)

// O(N) в среднем, но O(N²) в худшем
QuickSelect(scores, k);
var topK = scores.Take(k);

Проблемы: модифицирует исходный массив (нежелательно), нет SIMD, не поддерживает групповые квоты, нет стабильности между кадрами.

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

Шаг 1. Подготовка данных

using GameBudget.Net;
using SlidingRank.FastOps;
int n = 50_000;      // количество объектов
int d = 32;          // количество признаков
int k = 1000;        // сколько выбрать
// Матрица признаков: row-major (каждый объект — d чисел)
float[] featuresData = new float[n * d];
// Веса признаков
float[] weights = new float[d];
// ID объектов (опционально)
int[] ids = new int[n];
for (int i = 0; i < n; i++) ids[i] = i;
// ... заполняем данные ...
var features = new EmbeddingMatrix(featuresData, n, d);

Шаг 2. Топ-K без групповых квот

using var scheduler = new FrameBudgetScheduler(maxEntities: n);
int[] outIds = new int[k];
float[] outScores = new float[k];
int got = scheduler.SelectTopK(
    features: features,
    weights: weights,
    ids: ids,
    k: k,
    outIds: outIds,
    outScores: outScores
);
// outIds и outScores содержат топ-K, отсортированные по убыванию оценки
for (int i = 0; i < got; i++)
{
    Console.WriteLine($"Rank {i}: ID={outIds[i]}, Score={outScores[i]:F4}");
}

Шаг 3. Топ-K с групповыми квотами

int groups = 8;              // количество групп
int[] groupIds = new int[n]; // ID группы для каждого объекта
int[] quotas = new int[groups]; // сколько выбрать из каждой группы
// Пример: равномерное распределение
for (int g = 0; g < groups; g++)
    quotas[g] = k / groups;
quotas[0] += k - (k / groups) * groups; // остаток в первую группу
using var scheduler = new FrameBudgetScheduler(maxEntities: n, maxGroups: groups);
int[] outIds = new int[k];
float[] outScores = new float[k];
int got = scheduler.SelectWithQuotas(
    features: features,
    weights: weights,
    ids: ids,
    groupId: groupIds,
    quotas: quotas,
    outIds: outIds,
    outScores: outScores
);
// Результат сгруппирован: сначала все объекты группы 0 (отсортированы по score), 
// затем группы 1, и т.д.

Полный рабочий пример

using GameBudget.Net;
using SlidingRank.FastOps;
public class AILODScheduler
{
    private FrameBudgetScheduler _scheduler;
    private int[] _outIds;
    private float[] _outScores;
    
    public AILODScheduler(int maxEntities, int maxK)
    {
        _scheduler = new FrameBudgetScheduler(maxEntities);
        _outIds = new int[maxK];
        _outScores = new float[maxK];
    }
    
    public int[] SelectTopNpc(
        float[] featuresData,  // row-major: NpcCount × FeatureDim
        float[] weights,       // FeatureDim
        int[] npcIds,          // NpcCount
        int featureDim,
        int k)
    {
        int npcCount = npcIds.Length;
        var features = new EmbeddingMatrix(featuresData, npcCount, featureDim);
        
        int selected = _scheduler.SelectTopK(
            features, weights, npcIds, k,
            _outIds, _outScores
        );
        
        return _outIds[0..selected];
    }
    
    public void Dispose() => _scheduler.Dispose();
}
// Использование
var scheduler = new AILODScheduler(maxEntities: 50_000, maxK: 2000);
// Каждый кадр
int[] importantNpcs = scheduler.SelectTopNpc(
    featuresData: npcFeatures,
    weights: importanceWeights,
    npcIds: allNpcIds,
    featureDim: 32,
    k: 500
);
// Обновляем AI только для importantNpcs
foreach (int id in importantNpcs)
{
    UpdateAI(id);
}

Производительность

Тестовый стенд: Intel Core i5-11400F, Windows 11, .NET 8, BenchmarkDotNet

Топ-K (dot + селекция)

Групповые квоты (dot + селекция с квотами)

Что это значит для игры:

• 200 000 объектов, выбор топ-2000 с квотами → 2.94 мс вместо 35 мс

• Экономия ~32 мс на кадр

• При 60 FPS это разница между 16 мс (успели) и 35 мс (фреймдроп)

Zero-аллокации: как это работает

В отличие от LINQ и стандартных коллекций, GameBudget.Net не создаёт мусора в горячем пути.

Что аллоцируется один раз при создании FrameBudgetScheduler:

• Внутренние буферы для хранения временных данных

• Heaps для каждой группы (при использовании квот)

Что не аллоцируется на кадр:

• Массивы для результатов (вы передаёте свои)

• Временные массивы для оценок (переиспользуются)

• Объекты в куче (все структуры)

Как достичь zero-аллокаций:

// Плохо: аллокации на кадр
int[] ids = Enumerable.Range(0, N).ToArray(); // новая аллокация
float[] scores = new float[N];                 // новая аллокация
// Хорошо: переиспользование буферов
int[] ids = _cachedIds;       // переиспользуется
float[] scores = _cachedScores; // переиспользуется
Array.Clear(scores);           // без аллокаций

Сценарии использования

Сценарий 1: LOD для AI (тысячи NPC)

Из 50 000 NPC выбираем 1000 самых важных для обновления AI.

// Признаки: расстояние до игрока, здоровье, угроза, участие в бою
float[] npcFeatures = new float[npcCount * featureDim];
// ... заполняем
var importantNpcs = scheduler.SelectTopK(
    features, importanceWeights, npcIds, k: 1000,
    outIds, outScores
);

Сценарий 2: Анимации с групповыми квотами

Из 10 000 персонажей выбираем 500 для детальных анимаций, но с квотами: не более 200 врагов, не более 200 союзников, не более 100 нейтралов.

int[] quotas = new int[] { 200, 200, 100 }; // враги, союзники, нейтралы
int[] selected = scheduler.SelectWithQuotas(
    features, animationWeights, characterIds, groupIds, quotas,
    outIds, outScores
);

Сценарий 3: VFX и частицы

Из 5000 систем частиц обновляем только 300 самых важных (близких к камере или с высокой интенсивностью).

Сценарий 4: Сетка LOD в открытом мире

Из 200 000 объектов выбираем 10 000 для высокого качества рендеринга.

Сравнение с конкурентами (честно)

Когда стоит выбрать Unity Burst вместо GameBudget.Net

• Вы работаете исключительно в Unity и уже используете Burst.

• Вам нужно максимальное SIMD-ускорение за счёт нативного кода.

• Вы готовы писать кастомную реализацию селектора под свою задачу.

Когда стоит выбрать GameBudget.Net

• Вы работаете на чистом .NET (не Unity, или Unity без Burst).

• Нужна поддержка групповых квот.

• Важен zero-аллокации API.

• Нужна простая интеграция без изучения Burst.

Интеграция с Unity

using UnityEngine;
using GameBudget.Net;
using SlidingRank.FastOps;
public class AILODManager : MonoBehaviour
{
    private FrameBudgetScheduler _scheduler;
    private int[] _npcIds;
    private float[] _featuresData;
    private float[] _weights;
    
    void Start()
    {
        int npcCount = 50000;
        int featureDim = 32;
        
        _scheduler = new FrameBudgetScheduler(maxEntities: npcCount);
        _npcIds = new int[npcCount];
        _featuresData = new float[npcCount * featureDim];
        _weights = new float[featureDim];
        
        // Инициализация...
    }
    
    void Update()
    {
        // Обновляем признаки (расстояние до игрока, здоровье, угроза)
        UpdateFeatures();
        
        // Выбираем топ-500 NPC для AI-обновления
        int[] outIds = new int[500];
        float[] outScores = new float[500];
        
        var features = new EmbeddingMatrix(_featuresData, _npcIds.Length, _weights.Length);
        
        int selected = _scheduler.SelectTopK(
            features, _weights, _npcIds, 500,
            outIds, outScores
        );
        
        // Обновляем AI только для выбранных
        for (int i = 0; i < selected; i++)
        {
            UpdateAIForNpc(outIds[i]);
        }
    }
    
    void OnDestroy() => _scheduler.Dispose();
}

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

NuGet: https://www.nuget.org/packages/GameBudget.Net

GitHub (бенчмарки): https://github.com/likeslines-maker/GameBudget.Net

GameBudget.Net — это библиотека для быстрой селекции топ-K объектов с поддержкой групповых квот.

В отличие от полной сортировки (Array.Sort, LINQ) она:

• Работает за O(N log K) вместо O(N log N)

• Использует SIMD для массового скоринга

• Не создаёт аллокаций на кадр

• Поддерживает групповые квоты (честное распределение между категориями)

В отличие от PriorityQueue из коробки:

• Даёт готовый zero-аллокации API

• Поддерживает групповые квоты

• Использует SIMD dot вместо скалярного

В отличие от Unity Burst:

• Работает на любом .NET (не только Unity)

• Не требует изучения Burst и HPC#

• Даёт простой API с групповыми квотами

Если ваш фрейм-бюджет страдает от полной сортировки тысяч объектов — попробуйте GameBudget.Net. Сортировка 200 000 объектов за 16 мс — это слишком дорого для того, чтобы выбросить 99% результата.