Каков наиболее эффективный контейнер для хранения динамических игровых объектов? [закрыто]

20

Я делаю шутер от первого лица и знаю о множестве различных типов контейнеров, но я хотел бы найти контейнер, который является наиболее эффективным для хранения динамических объектов, которые будут добавляться и удаляться из игры довольно часто. EX-Пуля.

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

Я пишу это в C ++, кстати.

Также я придумала решение, которое, я думаю, будет работать.

Для начала я собираюсь выделить вектор большого размера, скажем, 1000 объектов. Я собираюсь отследить последний добавленный индекс в этом векторе, чтобы я знал, где находится конец объектов. Затем я также создам очередь, в которой будут храниться индексы всех объектов, которые «удалены» из вектора. (Никакого фактического удаления не будет сделано, я просто буду знать, что этот слот свободен). Поэтому, если очередь пуста, я добавлю к последнему добавленному индексу в векторе + 1, иначе я добавлю к индексу вектора, который был в начале очереди.

msawayda
источник
На какой конкретный язык вы ориентируетесь?
Phill.Zitt
На этот вопрос слишком сложно ответить без множества дополнительных подробностей, включая аппаратную платформу, язык / рамки и т. Д.
PlayDeezGames,
1
Совет, вы можете сохранить список свободных в памяти удаленных элементов (поэтому вам не нужна дополнительная очередь).
Джефф Гейтс
2
Есть ли вопрос в этом вопросе?
Тревор Пауэлл
Обратите внимание, что вам не нужно отслеживать самый большой индекс и не нужно предварительно выделять несколько элементов. std :: vector позаботится обо всем за вас.
API-Beast

Ответы:

33

Ответ всегда заключается в использовании массива или std :: vector. Типы, такие как связанный список или std :: map, обычно абсолютно ужасны в играх, и это определенно включает случаи, такие как наборы игровых объектов.

Вы должны хранить сами объекты (не указатели на них) в массиве / векторе.

Вы хотите непрерывную память. Вы действительно этого хотите. Итерирование любых данных в несмежной памяти приводит к большим потерям кэша в целом и устраняет возможность для компилятора и ЦП выполнять эффективную предварительную выборку кэша. Одно это может убить производительность.

Вы также хотите избежать выделения памяти и освобождения. Они очень медленные, даже с быстрым распределителем памяти. Я видел, как игры получают 10-кратное увеличение FPS, просто удаляя несколько сотен выделений памяти в каждом кадре. Не похоже, что это должно быть так плохо, но это может быть.

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

Например, для удаления игровых объектов вы можете использовать swap-and-pop. Легко реализуется с помощью чего-то вроде:

std::swap(objects[index], objects.back());
objects.pop_back();

Вы также можете просто пометить объекты как удаленные и поместить их индекс в свободный список для следующего раза, когда вам нужно будет создать новый объект, но лучше использовать swap-and-pop. Это позволяет вам делать простой цикл for для всех живых объектов без разветвления, кроме самого цикла. Для интеграции физики пули и тому подобного это может значительно повысить производительность.

Что еще более важно, вы можете найти объекты с простой парой поиска таблиц из стабильного уникального использования структуры карты слотов.

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

Карта слотов требует двух уровней косвенности, но оба являются простыми поисками массива с постоянными индексами. Они быстрые . Действительно быстро.

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

Когда вы создаете объект в основном списке, вы находите неиспользуемую запись в списке косвенных ссылок (используя свободный список). Запись в списке косвенных ссылок указывает на неиспользуемую запись в основном списке. Вы инициализируете свой объект в этом месте и присвойте его уникальный идентификатор индексу выбранной записи списка косвенного обращения и существующему тегу версии в основном элементе списка плюс один.

Когда вы уничтожаете объект, вы делаете swap-and-pop как обычно, но вы также увеличиваете номер версии. Затем вы также добавляете индекс списка косвенности (часть уникального идентификатора объекта) в свободный список. При перемещении объекта как части «своп-и-поп» вы также обновляете его запись в списке косвенного обращения на новое место.

Пример псевдокода:

Object:
  int index
  int version
  other data

SlotMap:
  Object objects[]
  int slots[]
  int freelist[]
  int count

  Get(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      return &objects[index]
    else:
      return null

  CreateObject():
    index = freelist.pop()

    objects[count].index = id
    objects[count].version += 1

    indirection[index] = count

    Object* object = &objects[count].object
    object.initialize()

    count += 1

    return object

  Remove(id):
    index = indirection[id.index]
    if objects[index].version = id.version:
      objects[index].version += 1
      objects[count - 1].version += 1

      swap(objects[index].data, objects[count - 1].data)

Уровень косвенности позволяет вам иметь стабильный идентификатор (индекс уровня косвенности, где записи не перемещаются) для ресурса, который может перемещаться во время сжатия (основной список объектов).

Тег версии позволяет вам сохранить идентификатор объекта, который может быть удален. Например, у вас есть идентификатор (10,1). Объект с индексом 10 удаляется (скажем, ваша пуля попадает в объект и уничтожается). Объекту в этом месте памяти в главном списке объектов затем повышается номер версии, давая ему (10,2). Если вы попытаетесь снова найти (10,1) из устаревшего идентификатора, поиск вернет этот объект через индекс 10, но увидит, что номер версии изменился, поэтому идентификатор больше не действителен.

Это самая быстрая структура данных, которую вы можете иметь со стабильным идентификатором, который позволяет объектам перемещаться в памяти, что важно для локальности данных и согласованности кэша. Это быстрее, чем любая возможная реализация хеш-таблицы; Хеш-таблица, по крайней мере, должна вычислять хеш (больше инструкций, чем поиск в таблице), а затем должна следовать цепочке хеширования (либо связанный список в ужасном случае std :: unordered_map, либо список с открытым адресом в любая не глупая реализация хеш-таблицы), а затем должна выполнять сравнение значений для каждого ключа (не дороже, но, возможно, дешевле, чем проверка тега версии). Очень хорошая хеш-таблица (не та, которая есть ни в одной реализации STL, поскольку STL требует хеш-таблицу, которая оптимизируется для других вариантов использования, чем вы играете для списка игровых объектов), может сэкономить на одной косвенности,

Существуют различные улучшения, которые вы можете внести в базовый алгоритм. Например, использовать что-то вроде std :: deque для основного списка объектов; один дополнительный уровень косвенности, но позволяет вставлять объекты в полный список без аннулирования любых временных указателей, которые вы получили из карты слотов.

Вы также можете избежать сохранения индекса внутри объекта, так как индекс может быть рассчитан по адресу памяти объекта (это - объекты), и даже лучше требуется только при удалении объекта, в этом случае у вас уже есть идентификатор объекта (и, следовательно, индекс) в качестве параметра.

Извинения за рецензию; Я не чувствую, что это самое ясное описание. Уже поздно, и это трудно объяснить, не тратя больше времени, чем я, на примеры кода.

Шон Миддледич
источник
1
Вы тратите лишние деньги и высокую стоимость (своп) за каждый доступ к «компактному» хранилищу. По моему опыту с видеоиграми, это плохая сделка :) YMMV конечно.
Джефф Гейтс
1
Вы на самом деле не делаете разыменование, что часто в сценариях реального мира. Когда вы это сделаете, вы можете хранить возвращенный указатель локально, особенно если вы используете вариант deque или знаете, что не будете создавать новые объекты, пока у вас есть указатель. Итерации по коллекциям - это очень дорогая и частая операция, вам нужен стабильный идентификатор, вам нужно сжатие памяти для изменчивых объектов (таких как пули, частицы и т. Д.), И косвенное обращение очень эффективно на модемном оборудовании. Эта техника используется в более чем нескольких очень мощных коммерческих двигателях. :)
Шон Миддледич
1
По моему опыту: (1) Видеоигры оцениваются по наихудшей производительности, а не по средней. (2) Обычно у вас есть 1 итерация для коллекции на кадр, поэтому сжатие просто «делает ваш худший случай менее частым». (3) У вас часто бывает много выделений / освобождений в одном кадре, высокая стоимость означает, что вы ограничиваете эту возможность. (4) У вас есть неограниченные разыграды на кадр (в играх, над которыми я работал, включая Diablo 3, часто разыменность была самой высокой стоимостью исполнения после умеренной оптимизации,> 5% от нагрузки на сервер). Я не хочу пренебрегать другими решениями, просто указываю на мой опыт и рассуждения!
Джефф Гейтс
3
Я люблю эту структуру данных. Я удивлен, что это не более известный. Это просто и решает все проблемы, которые заставляют меня биться в течение нескольких месяцев. Спасибо, что поделился.
Джо Бейтс
2
Любой новичок, читающий это, должен очень осторожно относиться к этому совету. Это очень вводящий в заблуждение ответ. «Ответ всегда заключается в использовании массива или std :: vector. Такие типы, как связанный список или std :: map, обычно абсолютно ужасны в играх, и это, безусловно, включает в себя случаи, такие как наборы игровых объектов». сильно преувеличено. Ответа «ВСЕГДА» нет, иначе эти другие контейнеры не были бы созданы. Сказать, что карты / списки «ужасны» - это тоже гипербола. Есть много видеоигр, которые используют их. «Наиболее эффективный» не является «наиболее практичным» и может быть неверно истолкован как субъективный «Лучший».
user50286
12

массив фиксированного размера (линейная память)
с внутренним свободным списком (O (1) alloc / free, стабильные индикаторы)
со слабыми ссылочными ключами (повторное использование слота делает недействительным ключ)
нулевые разыменования служебной информации (когда известно-допустимо)

struct DataArray<T>
{
  void Init(int count); // allocs items (max 64k), then Clear()
  void Dispose();       // frees items
  void Clear();         // resets data members, (runs destructors* on outstanding items, *optional)

  T &Alloc();           // alloc (memclear* and/or construct*, *optional) an item from freeList or items[maxUsed++], sets id to (nextKey++ << 16) | index
  void Free(T &);       // puts entry on free list (uses id to store next)

  int GetID(T &);       // accessor to the id part if Item

  T &Get(id)            // return item[id & 0xFFFF]; 
  T *TryToGet(id);      // validates id, then returns item, returns null if invalid.  for cases like AI references and others where 'the thing might have been deleted out from under me'

  bool Next(T *&);      // return next item where id & 0xFFFF0000 != 0 (ie items not on free list)

  struct Item {
    T item;
    int id;             // (key << 16 | index) for alloced entries, (0 | nextFreeIndex) for free list entries
  };

  Item *items;
  int maxSize;          // total size
  int maxUsed;          // highest index ever alloced
  int count;            // num alloced items
  int nextKey;          // [1..2^16] (don't let == 0)
  int freeHead;         // index of first free entry
};

Обрабатывает все: от пуль до монстров, от текстур до частиц и т. Д. Это лучшая структура данных для видеоигр. Я думаю, что это произошло от Bungie (еще во времена марафона / мифов), я узнал об этом в Blizzard, и я думаю, что это было в жемчужинах игрового программирования того времени. Это вероятно во всей игровой индустрии на данный момент.

Q: «Почему бы не использовать динамический массив?» A: Динамические массивы вызывают сбои. Простой пример:

foreach(Foo *foo in array)
  if (ShouldSpawnBaby(*foo))
    Foo &baby = array.Alloc();
    foo->numBabies++; // crash!

Вы можете представить случаи с более сложными (например, глубокие стеки вызовов). Это верно для всех массивов, таких как контейнеры. При создании игр у нас достаточно понимания нашей проблемы, чтобы заставить размеры и бюджеты на все в обмен на производительность.

И я не могу сказать этого достаточно: действительно, это лучшая вещь когда-либо. (Если вы не согласны, опубликуйте свое лучшее решение! Предостережение - необходимо решить проблемы, перечисленные в верхней части этого поста: линейная память / итерация, O (1) alloc / free, стабильные индексы, слабые ссылки, нулевые издержки или есть удивительная причина, почему вам не нужен один из них;)

Джефф Гейтс
источник
Что вы имеете в виду с динамическим массивом ? Я спрашиваю об этом, потому что DataArrayкажется, что динамическое выделение массива в ctor. Так что в моем понимании это может иметь какой-то иной смысл.
Эонил
Я имею в виду массив, который изменяет размеры / записывает во время его использования (в отличие от его конструкции). Вектор stl является примером того, что я бы назвал динамическим массивом.
Джефф Гейтс
@JeffGates Очень нравится этот ответ. Полностью согласен с принятием наихудшего случая в качестве стандартной стоимости выполнения. Поддержка свободного связанного списка с использованием существующего массива очень элегантна. Вопросы Q1: Цель maxUsed? Q2: Какова цель хранения индекса в младших битах идентификатора для выделенных записей? Почему не 0? Q3: Как это обрабатывает поколения сущностей? Если это не так, я бы предложил использовать младшие биты Q2 для подсчета генерации ushort. - Благодарность.
Инженер
1
A1: Макс. Используемый позволяет вам ограничить вашу итерацию. Также вы амортизируете любую стоимость строительства. A2: 1) Вы часто выходите из пункта -> id. 2) Это делает сравнение дешевым / очевидным. A3: я не уверен, что означает «поколения». Я буду интерпретировать это как «как отличить 5-й предмет, выделенный в слоте 7, от 6-го?» где 5 и 6 - поколения. Предложенная схема использует один счетчик глобально для всех слотов. (На самом деле мы начинаем этот счетчик с другого номера для каждого экземпляра DataArray, чтобы легче было различать идентификаторы.) Я уверен, что вы могли перенастроить биты на отслеживание элемента, что было важно.
Джефф Гейтс
1
@JeffGates - я знаю, что это старая тема, но мне действительно нравится эта идея, не могли бы вы дать мне некоторую информацию о внутренней работе void Free (T &) над void Free (id)?
TheStatehz
1

На это нет правильного ответа. Все зависит от реализации ваших алгоритмов. Просто выберите тот, который вы считаете лучшим. Не пытайтесь оптимизировать на этой ранней стадии.

Если вы часто удаляете объекты и воссоздаете их, я предлагаю вам посмотреть, как реализованы пулы объектов.

Редактировать: зачем усложнять вещи со слотами, а что нет. Почему бы просто не использовать стопку, не убрать последний элемент и не использовать его повторно? Поэтому, когда вы добавляете один, вы будете делать ++, а когда вы добавляете один, который вы делаете - чтобы отслеживать конечный индекс.

Sidar
источник
Простой стек не обрабатывает случай, когда элементы удаляются в произвольном порядке.
Джефф Гейтс
Честно говоря, его цель была не совсем ясна. По крайней мере, не для меня.
Сидар
1

Это зависит от вашей игры. Контейнеры различаются по тому, как быстро осуществляется доступ к определенному элементу, как быстро удаляется элемент и как быстро добавляется элемент.


  • std :: vector - быстрый доступ, удаление и добавление в конец быстро. Удаление с начала и середины происходит медленно.
  • std :: list - Итерирование по списку не намного медленнее, чем вектор, но доступ к определенной точке списка медленен (потому что итерирование - в основном единственное, что вы можете сделать со списком). Добавление и удаление элементов в любом месте происходит быстро. Больше всего памяти. Non-непрерывный.
  • std :: deque - Быстрый доступ и удаление / добавление в конец и начало быстро, но медленно в середине.

Обычно вы хотите использовать список, если вы хотите, чтобы ваш список объектов сортировался не так, как в хронологическом порядке, и, следовательно, нужно вставлять новые объекты, а не добавлять, в противном случае - деку. Deque обладает повышенной гибкостью по сравнению с вектором, но на самом деле не имеет большого недостатка.

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

API-Beast
источник
Не верно re: list. Совет deque полностью зависит от реализаций deque, которые сильно различаются по скорости и исполнению.
метаморфоза