Управление несколькими объектами сразу

Question

Я хочу найти способ эффективно отслеживать множество объектов одновременно. Один практический пример, который я могу представить, - это система частиц. Как отслеживаются сотни частиц? Я думаю, что нахожусь на правильном пути, я нашел термин «instancing», и я также узнал о мухоловках. Надеюсь, кто-то может пролить свет на это и поделиться со мной некоторыми приемами. Спасибо.

Answer 1

Как отслеживать объекты во многом зависит от того, что вы хотите с ними делать. Вам нужно быстро получить доступ к некоторым частицам, известным по индексу? Затем используйте vector. Являются ли ваши частицы каким-то образом сопоставлены именами? Затем вы можете использовать map. И так далее.

«Сотни» объектов, безусловно, не должны беспокоиться о C++, если вы не выбрали особенно плохую структуру данных. Почему вы обеспокоены? Вы думаете, что потеряете слишком много памяти? Или, может быть, медленное время работы? В любом случае вы должны точно описать задействованные объекты и необходимые им операции, а затем выбрать соответствующую структуру данных.

Answer 2

Вы не можете обработать их, не пропуская их.

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

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

Для обновления общих характеристик вы просто перебираете этот контейнер.

Одна проблема - эффективное удаление из середины вектора указателей и уникальных деталей. Скопируйте или скопируйте верхний элемент в это пространство, а затем удалите верхний элемент.

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

EDIT - В основном я говорю об интрузивных связанных списках. Код связанного списка очень прост, но вы можете использовать библиотеку Boost intrusive container.

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

EDIT - на плитки.

Очевидный подход к плиткам - большой двумерный массив. Довольно легко итерации по обрезанной области такого массива по строкам.Тем не менее, с помощью рендеринга на основе плитки есть хороший шанс, что вы хотите сразу нарисовать все плитки определенного типа, затем весь следующий тип и т. Д., Где тип определяет текстуру, необходимую для их рендеринга.

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

Answer 3

Вы можете отслеживать множество объектов так же, как и отслеживать многие мелочи.

Если вы хотите «отследить» их по имени или названию свойства, используйте хеш-таблицу.

Если вы хотите «отследить» их в порядке некоторого свойства, используйте отсортированный массив или дерево (двоичный или многопоточный).

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

Если вам нужно несколько из приведенных выше, то вы можете использовать несколько методов.

Answer 4

На сайте GameProgrammingPatterns, take a look at the Object Pool pattern. Это очень хорошо написано.

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