Como melhor removo uma entidade do meu loop de jogo quando está morta?

Ok, então eu tenho uma grande lista de todas as minhas entidades que eu percorrer e atualizar. No AS3, posso armazenar isso como uma matriz (comprimento dinâmico, sem tipo), um vetor (digitado) ou uma lista vinculada (não nativa). No momento, estou usando o Array, mas pretendo mudar para Vector ou lista vinculada, se for mais rápido.

Enfim, minha pergunta, quando uma Entidade é destruída, como devo removê-la da lista? Eu poderia anular sua posição, dividi-la ou simplesmente colocar uma bandeira nela para dizer "pule sobre mim, estou morto". Como estou agrupando minhas entidades, é provável que uma Entidade que esteja morta esteja viva novamente em algum momento. Para cada tipo de coleção, qual é a minha melhor estratégia e qual combinação de tipo de coleção e método de remoção funcionará melhor?

Eu armazenaria todos os add / remove em listas separadas e faria essas operações depois de percorrer o loop de atualização.

A estrutura Flixel usa o sinalizador morto (na verdade, vários sinalizadores que determinam se ele deve ser desenhado, atualizado etc.). Eu diria que, se você quiser reviver entidades e se o desempenho for um problema, use o sinalizador morto. Na minha experiência, instanciar novas entidades é a operação mais cara no caso de uso que você descreve, e juntar ou anular elementos pode levar ao inchaço da memória, devido à coleta de lixo às vezes esquisita do Flash.

Embora algumas técnicas sejam inerentemente mais eficientes do que outras, só será importante se você estiver sem ciclos na plataforma de destino. Use qualquer técnica que permita concluir seu jogo mais rapidamente. Tente não confiar na implementação específica de suas estruturas de dados de contêiner enquanto isso, e isso ajudará você a otimizar posteriormente, se necessário.

Apenas para abordar algumas das técnicas já discutidas por outras pessoas aqui. Se a ordem das entidades for importante, um sinalizador morto poderá permitir a emenda durante o loop de atualização no próximo quadro. por exemplo. pseudocódigo muito simples:

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;

Estas são as características deste esquema:

• compactação natural de entidades (embora com possivelmente 1 latência de quadro antes que um slot de entidade possa ser recuperado).
• sem problemas de reordenação aleatória.
• embora duplamente as listas vinculadas tenham inserção / exclusão de O (1), mas são muito difíceis de buscar previamente para ocultar a latência ideal do cache. Mantê-los em uma matriz compacta permite que as técnicas de pré-busca de blocos funcionem bem.
• No caso de destruição de vários objetos, você não precisa fazer cópias de turno redundantes para manter a ordem e a compactação (tudo é feito uma vez durante a atualização)
• Você tira vantagem de tocar em dados que já precisam estar no cache durante a atualização.
• Funciona bem se os autores da entidade de origem e de destino separarem matrizes. Você pode fazer buffer duplo de suas matrizes de entidade para tirar proveito do multicore / por exemplo. um segmento atualizando / gravando as entidades para o quadro N, enquanto outro segmento está processando as entidades do quadro anterior para o quadro N-1.
• A compactação significa que é mais fácil DMA para um processador heterogêneo, permitindo ainda mais descarregamento do trabalho da CPU, por exemplo. SPUs ou GPUs.

Falando em termos de minha experiência geral em programação, a emenda geralmente é uma operação lenta, envolvendo a troca de todos os elementos existentes em um. Eu acho que defini-lo como nulo seria a melhor solução aqui ; um sinalizador morto funcionaria, mas você deve tomar cuidado para não deixar seu código confuso.

Na verdade, estávamos falando sobre o pool de recursos na sala de chat. É uma prática muito boa e bom saber que você está fazendo isso. :)

Pessoalmente, eu usaria uma lista vinculada. A repetição de uma lista de curtidas é rápida, além de adicionar e remover itens. Usar uma matriz ou vetor seria uma boa opção se você precisar de acesso direto aos itens da estrutura (por exemplo, acesso a um índice), mas não parece que você precisa disso.

Sempre que você remove um item da lista vinculada, pode adicioná-lo a um conjunto de objetos que podem ser reciclados para economizar na alocação de memória.

Eu usei as estruturas de dados poligonais em vários projetos e fiquei muito feliz com elas.

Edit: Desculpe, acho que a resposta não foi muito clara em termos de estratégia de remoção: sugiro remover o item da lista assim que estiver morto e adicioná-lo diretamente à estrutura de pool (reciclagem). Como remover um item de uma lista vinculada é muito eficiente, não vejo problema em fazê-lo.

"apenas defina uma bandeira para dizer" pule sobre mim, eu estou morto. "Estou agrupando minhas entidades, portanto é provável que uma entidade que esteja morta esteja viva novamente em algum momento"

Acho que você respondeu sua própria pergunta com relação a esse aplicativo específico. Eu me afastaria das matrizes se você planeja trabalhar nelas, além de empurrar e soltar. Listas vinculadas seriam um caminho mais inteligente, se você planeja realizar operações pesadas. Com tudo isso dito, se você planeja reintegrar a mesma entidade de volta ao jogo, faz sentido definir apenas uma variável booleana e verificá-la durante os ciclos de operação do jogo.

Uma solução limpa e geral que encontrei em uma lib que usei estava usando um mapa bloqueável.

você tem duas operações lock()e unlock(), enquanto itera sobre o mapa lock(), agora, a partir deste ponto, todas as operações que alteram o mapa não entram em vigor, apenas são inseridas em uma CommandQueueque será executada quando você ligar unlock().

Portanto, a remoção de uma entidade teria o seguinte pseudocódigo:

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

e quando você unlock()

isLocked = false
commandQueue.execute(this);

A única coisa que você deve considerar é que você somente removerá a entidade após o loop.

EDIT: esta é a solução proposta por Simon.

Aqui está uma resposta que recebi da Liosan :
/gamedev//a/46765/24633

Eu tenho dois métodos

Quando você chama um objeto a ser excluído, ele realmente define dois sinalizadores:

1.Um para informar ao contêiner que um objeto foi excluído

2.Um para informar ao contêiner quais objetos foram solicitados a serem excluídos

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

Um usando um vetor de objetos

std::vector<object*> objects;

Em seguida, na função de atualização, verifique se um objeto foi excluído e, se for o caso, repita todos os objetos e remova os que possuem um sinalizador de exclusão

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;
    }
}

Dois Usando um (ponteiro para um) vetor de objetos.

std::vector<object*> *objects;

Na função de atualização, se um objeto deve ser excluído, repita os objetos e adicione os que não devem ser excluídos a um novo vetor. exclua o vetor de objetos e defina o ponteiro para o novo vetor

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;
    }
}