Как мне лучше всего удалить сущность из моего игрового цикла, когда она мертва?

Итак, у меня есть большой список всех моих сущностей, которые я перебираю и обновляю. В AS3 я могу сохранить это как массив (динамическая длина, нетипизированный), вектор (типизированный) или связанный список (не собственный). В настоящее время я использую Array, но я планирую изменить на Vector или связанный список, если это будет быстрее.

В любом случае, мой вопрос, когда сущность уничтожается, как мне удалить ее из списка? Я мог бы обнулить его позицию, склеить его или просто поставить на нем флаг, чтобы сказать: «Пропусти меня, я мертв». Я объединяю свои сущности, так что сущность, которая мертва, вполне может быть снова живой в какой-то момент. Какова моя лучшая стратегия для каждого типа коллекции и какая комбинация типа коллекции и метода удаления будет работать лучше?

Я бы сохранял все добавления / удаления в отдельных списках и выполнял эти операции после того, как прошел цикл обновления.

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

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

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

void updateGame()
{
  // updateEntities()
  Entity* pSrcEntity = &mEntities[0];
  Entity* pDstEntity = &mEntities[0];
  newNumEntities = 0;
  for (int i = 0; i < numEntities; i++)
  {
    if (!pSrcEntity->isDead)
    {
       // could be inline but whatever.
       updateEntity(pDstEntity, pSrcEntity);
       // if entity just died, don't update the pDstEntity pointer, 
       // and just let the next entity updated overwrite it.
       if (!pDstEntity->isDead)
       {
          pDstEntity++;
          newNumEntities++;
       }
    }
    pSrcEntity++;
  }
}
numEntities = newNumEntities;

Вот характеристики этой схемы:

• естественная компактность объектов (хотя возможно с 1 задержкой кадра до того, как слот объекта может быть восстановлен).
• нет случайных вопросов переупорядочения.
• в то время как дважды связанные списки имеют O (1) вставку / удаление, но их очень трудно предварительно выбрать для оптимального сокрытия задержки кеша. Хранение их в компактном массиве позволяет хорошо работать методам предварительной выборки блоков.
• В случае уничтожения нескольких объектов вам не нужно делать избыточные копии-копии, чтобы поддерживать порядок и компактность (все это делается один раз в течение этапа обновления)
• Вы используете касание данных, которые должны быть в кеше уже во время обновления.
• Это хорошо работает, если ваши исходные и конечные объекты должны разделять массивы. Затем вы можете дважды буферизовать массивы ваших сущностей, чтобы использовать преимущества многоядерности / например. один поток обновляет / записывает объекты для кадра N, тогда как другой поток воспроизводит объекты предыдущего кадра для кадра N-1.
• Компактность означает, что DMA проще всего разложить на гетерогенный процессор, например, для еще большей загрузки ЦП. SPU или GPU.

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

На самом деле мы просто говорили о пуле ресурсов в чате. Это очень хорошая практика, и приятно слышать, что вы делаете это. :)

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

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

Я использовал многоугольные структуры данных в нескольких проектах и ​​был очень доволен ими.

Изменить: Извините, я думаю, что ответ не был очень ясным с точки зрения стратегии удаления: я бы предложил удалить элемент из списка, как только он будет мертв, и добавить его непосредственно в структуру пула (recycle). Поскольку удаление элемента из связанного списка очень эффективно, я не вижу в этом проблемы.

«просто поставьте флаг, чтобы сказать:« Пропусти меня, я мертв ». Я объединяю свои сущности, так что мертвая сущность, скорее всего, снова будет жива в какой-то момент»

Я думаю, что вы ответили на свой вопрос относительно этого конкретного приложения. Я бы избежал массивов, если вы когда-нибудь планируете работать с ними, кроме push и pop. Связанные списки были бы более разумным способом, если вы планируете выполнять тяжелые операции. Учитывая все вышесказанное, если вы планируете реинтегрировать ту же сущность обратно в игру, то имеет смысл установить только логическую переменную и проверять ее во время циклов работы игры.

Одно чистое и общее решение, которое я нашел в используемой мной библиотеке, было использование блокируемой карты.

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

Таким образом, удаление сущности будет иметь следующий псевдокод:

void lockableMap::remove(std::string id) {
   if(isLocked) {
       commandQueue.add(new RemoveCommand(id));
   } else {
       //remove element from map
   }

и когда ты unlock()

isLocked = false
commandQueue.execute(this);

Единственное, что вы должны учитывать, это то, что вы удалите сущность только после цикла.

РЕДАКТИРОВАТЬ: это решение, предложенное Саймоном.

Вот ответ, который я получил от Liosan :
/gamedev//a/46765/24633

У меня есть два метода.

Когда вы вызываете объект для удаления, он действительно устанавливает два флага:

1. Чтобы сообщить контейнеру, что объект был удален

2. Чтобы сообщить контейнеру, какие объекты были запрошены на удаление

void object::deleteObject()
{
    container->objectHasBeenDeleted = true;
    isToDelete = true;
}

Один Используя вектор объектов

std::vector<object*> objects;

Затем в функции обновления проверьте, был ли удален объект, и если это так, выполните итерацию по всем объектам и удалите те, которые имеют флаг удаления.

void container::update()
{
    if (objectHasBeenDeleted)
    {
        std::vector<object*>::iterator ListIterator;
        for(ListIterator=objects.begin(); ListIterator!=objects.end();)
        {
            if( (*ListIterator)->isToDelete )
            {
                ListIterator = objects.erase(ListIterator);
                delete *ListIterator;
            }
            else {
                ++ListIterator;
            }
        }
    objectHasBeenDeleted = false;
    }
}

Два Используя (указатель на) вектор объектов.

std::vector<object*> *objects;

В функции обновления, если объект должен быть удален, выполните итерацию по объектам и добавьте те, которые не должны быть удалены, в новый вектор. удалить вектор объектов и установить указатель на новый вектор

void container::update()
{
    if (objectHasBeenDeleted)
    {
        std::vector<object*> *newVector;
        unsigned long i;
        for (i = 0; i < objects->size(); i++)
        {
            if (!objects->at(i)->isToDelete)
            {
                newVector->push_back(objects->at(i));
            }
        }
        delete objects;
        objects = newVector;
        objectHasBeenDeleted = false;
    }
}