Как бороться с удалением объекта при непрерывном размещении?

Question

Недавно я обнаружил преимущества Data Oriented Design. Это выглядит очень впечатляюще. Одним из моментов является группирование данных по типу и доступу, причем не все вместе в объектах, а в массивах, чтобы предотвратить ошибки кэша и улучшить обработку.

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

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

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

Как человек может справиться с этим в DOD?

Итак, выставьте требования:

• это должен быть массив (ы), чтобы уменьшить количество кеш-ошибок в DOD
• он должен иметь быстрое случайное удаление объекта позиции, max o(log n)
• объекты не могут перемещаться с момента их создания, потому что на них можно ссылаться в неизвестных местах, поэтому это приведет к неправильному поведению программы

Answer 1

Это на самом деле довольно просто, не используйте прямые ссылки. Используйте слой косвенности, такой как идентификаторы. Например:

Допустим, у вас есть FooManager, который управляет всеми вашими "объектами" Foo (не объектами в смысле ООП, а набором массивов для каждого свойства Foo). Насколько я понимаю, сейчас вы просто возвращаете индекс. Допустим, Foo #42 - это Foo, данные которого расположены в индексе 42 всех массивов. Теперь вы хотите удалить Foo #42, который проделает дыру в вашем массиве. Вы можете переместить все остальные записи массива, но тогда Foo #43 больше не будет указывать на фактический индекс 43.

Поэтому мы добавляем таблицу идентификаторов и вместо возврата индекса вы возвращаете идентификатор. Когда вы создаете новый Foo, вы добавляете его данные в первый свободный индекс в массивах (скажем, 42). Затем вы генерируете новый неиспользуемый идентификатор (скажем, 1337). Теперь вы можете обновить таблицу идентификаторов (для этого отлично подходит карта (хэш)), указав, что идентификатор 1337 указывает на индекс 42. Теперь вы можете вернуть идентификатор 1337 вызывающей функции. (Обратите внимание, что вызывающая функция никогда не узнает, где на самом деле хранятся данные, это не имеет значения)

В следующий раз, когда Foo необходимо обновить из другого фрагмента кода, используется идентификатор. Поэтому функция setBar в FooManager вызывается с идентификатором 1337 и новым значением Bar в качестве аргументов. FooManager ищет 1337 в своей таблице идентификаторов, обнаруживает, что он все еще находится в индексе 42, и обновляет индекс 42 массива баров новым значением бара.

Теперь эта система получает свое значение, давайте удалим Foo 1337. Метод removeFoo из FooManager вызывается с идентификатором 1337 в качестве аргумента. Он смотрит на 1337, он находится по индексу 42. Тем не менее, за это время было добавлено 10 новых Foos. Итак, теперь мы можем просто заменить значения в индексе 42 значениями в 52, фактически переместив 52 в 42. Это вызовет большую проблему в старой системе, но сейчас нам нужно только обновить таблицу индексов. Таким образом, мы ищем, какой идентификатор указывает на 52 (скажем, это 1401), и обновляем его до 42. В следующий раз, когда кто-то пытается обновить Foo с идентификатором 1401, он ищет его в таблице индексов и находит, что он находится в индексе 42.

Таким образом, мы сохранили данные в непрерывной памяти, удаление требует только очень небольшого количества операций копирования данных (по одной копии для каждого свойства Foo), а код "вне" FooManager даже не осознает, что что-то произошло. Это даже решает проблемы мертвой защиты. Предположим, что некоторый код все еще имеет удаленный идентификатор 1337 (висячий рефлекс, это плохо!), Когда он пытается получить к нему доступ или изменить его, FooManager ищет его, видит, что 1337 не существует (больше) и может выдать хорошее чистое предупреждение /error и callstack, которые позволяют вам напрямую определить, какой код все еще имеет привязанную ссылку!

Есть только один недостаток, который заключается в дополнительном поиске в таблице идентификаторов. Теперь хеш-таблица может быть очень быстрой, но это все равно дополнительная операция для каждого изменения объекта Foo. Однако в большинстве случаев доступ извне менеджера происходит гораздо реже, чем доступ внутри менеджера. Когда у вас есть BulletManager, он будет обновлять каждую пулю каждый кадр, но доступ к Bullet для изменения / запроса чего-либо и вызовы для создания / удаления маркеров менее вероятны. Если это наоборот, вам, вероятно, следует обновить структуры данных, чтобы оптимизировать их для этой ситуации. Опять же, в такой ситуации больше не имеет значения, где находятся данные в памяти, чтобы вы могли жить либо с "дырами" в ваших массивах, либо даже использовать совершенно разные макеты данных.

Answer 2

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

РЕДАКТИРОВАТЬ: если вы поддерживаете внешние указатели в массиве, ими можно управлять с помощью интеллектуальных указателей, базовые адреса которых обновляются (shared_ptr::reset) когда элемент массива перемещен. в итоге вы получите 2 параллельных массива одинаковой длины:

typedef std::vector<thing> thingVec;
thingVec things;

// smart pointers for each object
std::vector<boost::shared_ptr<thingVec::iterator>> references;

в вашем createThing функция, вы бы вернули shared_ptr с пользовательским средством удаления (которое будет автоматически обновлять массив после удаления всех ссылок):

http://www.boost.org/doc/libs/1_51_0/libs/smart_ptr/sp_techniques.html

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