PriorityQueue должна уметь возвращать наименьший ключ, а также значение, хранимое с этим ключом. Также она должна уметь удалять заданный объект по значению и вставлять объект с заданным ключом (а также изменять ключ для заданного объекта)

Как бы это все эффективнее реализовать?

Идея в том, чтобы хранить ключи в std::vector и вызывать std::sort при добавлении/удалении. Это O(N*logN)

Это позволит иметь ключи в отсортированном виде.

Взять наименьший - просто взять нулевой элемент.

Также будем использовать std::unordered_map. Взять объект - взять ключ из вектора и взять его из мэпа. Это O(2) примерно.

Таким образом две эти структуры должны обеспечивать быструю работу за счет потерь памяти.

Что скажете? Есть идеи лучше?

Объектов много и они будут пользоваться поиском пути часто. Структура должна работать максимально быстро (в идеале еще и object pool юзать, но это уже потом прикрутим)

Переписываю игру на многопоточность (скорее ради образования, чем из-за потребности, все и в одном работает пока что быстро).

Какие части следует вынести в отдельный поток? Рендер? Физику? ИИ?

Я так понимаю, звук стоило бы тоже реализовать в отдельном?

Какие части вы обычно запускаете в отдельных потоках?

Сейчас сделано так: каждый игровой объект, имеющий скелетную анимацию (skinned mesh component) хранит текущее состояние костей в своем UBO. Псевдокод:
class SkinnedComp {
uint UBO;
};
Т.е. под каждый экземпляр игрового объекта создается свой UBO размером по количеству костей. Кость - матрица 3x4,макс костей 256, поэтому вписывается в UBO без проблем. Но что-то подсказывает мне, что создавать для каждого объекта свой буфер не есть хорошо и я решил создать некий аллокатор, псевдокод:

class Allocator {
Uint buffer;
size_t maxSize;
size_t offset;
void init() {
maxSize = sizeof(mat3x4)*MAX_JOINTS*MAX_SKINNED_INSTANCES_PER_FRAME;
buffer = api->createBuffer( maxSize );
}
size_t allocJoints(size_t n) {
size_t sz=n*sizeof(mat3x4);
if ( offset + sz > maxSize ) {
  ошибка или выделяем еще один буфер
}
size_t ofs = offset;
offset += sz;
offset = align(offset);
return ofs;
}
}

class SkinnedComp {
size_t uboBufferOffset;
};

Далее на каждом кадре, после этапа определения видимых объектов:
Instance.bufferOffset = allocator.allocJoints(Instance.numJoints);
api->writeSubData( allocator.buffer, Instance.bufferOffset, Instance.numJoints*sizeof(mat3x4), Instance.currentJointMatrices );

Ну и перед выводом:
api->bindBufferRange( slot, buffer, offset, size ... );

Плюсы:
не создается куча мелких буферов когда попало в рантайме, вместо этого при инициализации резервируется блок памяти (один buffer).
Биндится не буфер целиком, а только диапазон. Если вместо UBO использовать SSBO или TBO, то буфер можно забиндить только один раз, а смещаться по Instsnce.bufferOffset уже в самом шейдере, можно добавить инстансинг.
Минусы: обновлять анимации нужно каждый кадр или с фиксированной частотой.

В случае с хренолионом буферов:
Плюсы: обновляем буфер только при изменении анимации
Минусы: куча биндингов, инстансинг реализовать сложнее(bindless buffers?), больше фрагментация памяти.

Что думаете по этому поводу и как это реализовано у вас?

Обычно темы про гуй касаются конкретных вопросов реализации, а общего обзора методик нет, будто бы это само собой разумеющееся.
Попытаюсь здесь систематизировать информацию о гуе, заодно сам разберусь по ходу дела.

Архитектура

Общий принцип — элементы интерфейса состоят из квадов, на которые натягиваются текстуры.
Способы от простого к сложному:
1. Без прозрачности, все элементы квадратные, рисуем от верхнего к нижнему без блендинга с тестом глубины.
2. Однобитовая прозрачность, рисуем от верхнего к нижнему без блендинга с тестом глубины, дискардим фрагменты в которых альфа!=1.
3. При необходимости использовать антиалиасинг или полупрозрачность элементов, рисуем от нижнего к верхнему с блендингом без теста глубины.
В первых двух способах можно даже не сортировать, а вот для корректной полупрозрачности сортировка обязательна.
Вместо сортировки на ЦПУ можно сортировать на ГПУ с применением алгоритмов OIT(порядко-независимая прозрачность)

Текстуры можно грузить из внешнего файла или генерировать самому(например для миникарт).
Или же вместо текстуры может быть рендеринг текста.

Рендеринг текста

Детальный обзор современных методов рендеринга текста: Digital Typography Rendering
В играх два основных метода — просто рендеринг текстур с глифами и SDF.

1. Рендеринг текстур с глифами

Можно отрендерить заранее и сложить глифы в текстурный атлас, либо генерировать на ходу, например через freetype.
Утилита для генерации текстурных атласов от RPG: UBFG + github.

При генерации на ходу надо как-то организовать хранение отрендереных глифов. Хранить каждый глиф в отдельной текстуре неэффективно.
Есть три эффективных решения:
1. Текстурный атлас, в который пакуются глифы по следующему алгоритму: http://blackpawn.com/texts/lightmaps/
2. Texture Array, где каждый слой — отдельный глиф.
3. Bindless Textures.

Бонус от Frankinshtein: Постпроцессинг шрифтов на лету | Библиотека и редактор Font Effects.

2. Signed Distance Field

Заранее готовится текстура Signed Distance Field от необходимых глифов. Текстура натягивается на квады и рендерится специальным шейдером, на выходе получается глиф. Особенность текстуры такова, что её можно масштабировать как угодно, всегда получая четкий текст.
Ходют слухи, можно даже считать качественный SDF в реалтайме: Генерация SDF символов на GPU от MrShoor

Статьи с описанием алгоритма и примерами:
Improved Alpha-Tested Magnification for Vector Textures and Special Effects
Рендеринг UTF-8 текста с помощью SDF шрифта
Signed Distance Field или как сделать из растра вектор
CPU vs GPU. Distance field
Drawing Text with Signed Distance Fields in Mapbox GL + Онлайн демо
Font Rendering is Getting Interesting
Playing around with distance field font rendering

3. Сравнение двух методов

Особенности классического метода:
+ при генерации под нужный размер идеальное качество с возможностью субпиксельного сглаживания, хинтинга
+ простота реализации — надо всего-лишь натянуть текстуры на квады
+ с фритайпом, простота использования — закинул файл со шрифтом в папку игры и работает без всякой подготовки
- малейшее масштабирование, поворот, проекция, и текст превращается в размытое говно. проблему с масштабированием можно побороть, рендеря глифы заново при изменении размера, но поворот и проекцию побороть невозможно. большое разрешение экрана вместе с большим размером текста будет жрать память.
- для теней, обводки и прочих эффектов надо много дополнительных телодвижений
- с фритайпом — нагрузка на ЦПУ при рендере новых глифов в текстуру

Особенности SDF:
+ векторный и универсальный — текст всегда четкий при любых поворотах, масштабированиях, проекциях и тд.
+ побочный эффект — бесплатное однопроходное размытие, тени и обводка текста
- в целом алгоритм сложнее предыдущего в реализации
- требует прекомпиляции. для хорошего качества нужно дополнительно запариваться с SDF генератором, прекомпиляция занимает значительное время
- проблемы с острыми гранями букв, особенно заметно при большом размере текста. проблема решается усложнением алгоритма до многоканального
- нет субпиксельного сглаживания и хинтинга. хотя про первое где-то встречалась информация что таки есть способ

В общем панацеи нет, каждый метод имеет свою область применения.
Область безусловного доминирования SDF — текст для внутриигровых объектов(когда можно подойти вплотную к объекту и размер текста будет 5000х5000) и мобилки(где разрешения экранов могут отличаться в разы).
Разница наглядно:

Всем привет. Пилю проект на Unity. Мобильная игрушка в которой надо уклоняться от падающих объектов. Не получается ускорять эти самые объекты. В этом не было бы проблемы если бы эти объекты не были префабами. Пытался привязывать ускорение к счетчику очков, к таймеру и т.д., но ничего не вышло. Помогите пожалуйста советом, может есть какие либо идеи. Буду признателен)))

Привет всем!
Есть система частиц, пытаюсь вращать частички через скрипт.
Вращение работает так:

for (int i=0; i < total; ++i) {
//(1)  Нахожу смещение частички относительно transform:
Vector3 radVec = gos[i].position - transform.position;

//(2) Нахожу текущее вращение частички относительно какого-то вектора transform (в данном случае transform.forward)
Quaternion curRot = Quaternion.LookRotation (radVec, transform.forward );

//(3) Вращаю частичку (на самом деле она должна стоять там, где была до этого)
radVec = curRot * radVec.magnitude;

//(4) Сохраняю изменения
gos[i].position = transform.position + radVec;
}

http://milty.nl/grad_guide/basic_implementation/d3d12/command_list.html
Читаю инфу:

На простом треугольнике без текстур и констант буферов команд алокатор ест почти 4 метра ОЗУ памяти ! Зачем так много не ясно.

Странно почему если не делать Reset CommandAllocator , то он каждый кадр берет новые 4 метра ОЗУ.
А ведь это тормозит рендер, когда выделяется память.

Как то костыльно работает CommandAllocator. Скользкий и не приятный момент.

Почему нельзя было нам самим один раз давать\выделять память для каждого GraphicsCommandList ?
Что бы её не выделять динамически на каждом кадре отрисовки.

Интересно как выглядит то что GraphicsCommandList записал в память ?

Правка: 10:52

Речь идёт о генерировании 2д шума (цветное изображение). Есть некоторое ядро, используемое в качестве фильтра, например, гауссовый блюр. Требуется сгененировать шум, который в свёртке с этим ядром даст как можно более константное значение.

Думаю, логичнее всего пойти по пути проекции: взять некоторый исходный шум, например, белый шум, и вычитать из него компоненты свёртки, которые дают ненулевой вклад. Вопрос в том, как вычитать.

Например, таким свойством обладает синий шум — его свёртка с ядром блюра равна примерно константе. Хочется, чтобы это работало в более общем случае.

Правка: 7:31

Дано:

Пулл объектов, управляющих NPC и высчитывающий скорость каждого объекта, перед тем как физический движок их переместит. Обычный steering behavior, ничего необычного

Пытаюсь добавить поиск пути с помощью potencial field. Идея такая: при назначении цели считаем новую карту потенциалов, затем шаг за шагом выбираем следующую клетку пути и стирингом двигаемся в нее. И так по кругу, пока не достигнем цели.

Вопрос вот в чем. Объектов может быть много и у каждого может быть своя карта потенциалов для достижения конкретно его цели. А пересчитывать карту каждый раз при переназначении цели может быть весьма накладно (объектов ведь много)

Как принято делать в этом случае? Как обработать кучу объектов, не сожрав кучу памяти (создавая каждому отдельную карту) и все процессорные циклы (если НПС преследует кого-то, то обновление координат и пересчет карты может вызываться часто).

Если все бегут в одну точку, то легко - всего одна карта потенциалов. Но если враги пытаются реализовать сложную тактику и цель у каждого своя, то как выкрутиться?

Обновлять карту потенциалов редко и в отдельном треде?

Как в HLSL шейдерах версии 5.1 подобное написать ?
А то я делал на  OpenGL 4.5 MultiDrawIndirect, а теперь надо в DX12

Правка: 9:56