How do I best remove an entity from my game loop when it is dead?

Question

Ok so I have a big list of all my entities which I loop through and update. In AS3 I can store this as an Array (dynamic length, untyped), a Vector (typed) or a linked list (not native). At the moment I'm using Array but I plan to change to Vector or linked list if it is faster.

Anyway, my question, when an Entity is destroyed, how should I remove it from the list? I could null its position, splice it out or just set a flag on it to say "skip over me, I'm dead." I'm pooling my entities, so an Entity that is dead is quite likely to be alive again at some point. For each type of collection what is my best strategy, and which combination of collection type and removal method will work best?

Answer 1

I would store all add/removes in separate lists and do those operations after I've iterated through the update-loop.

Answer 2

The Flixel framework uses the dead flag (actually several flags that determine whether it should be drawn, updated, and so on). I'd say that if you're going to revive entities, and if performance is an issue, you use the dead flag. In my experience, instantiating new entities is the most expensive operation in the use case you describe, and splicing out or nulling elements may lead to memory bloat given Flash's sometimes-squirrely garbage collection.

Answer 3

While some techniques are inherently more efficient than others, it'll only matter if you're running out of cycles on your target platform. Use whatever technique allows you to get your game done quicker. Try not to rely on the specific implementation of your container data structures in the meantime and it'll help you to optimize afterwards if you need it.

Just to address some of the techniques already discussed by others here. If order of entities is important, then a dead flag can allow you to splice during your update loop on the next frame. eg. very simple pseudocode:

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;

These are the characteristics of this scheme:

• natural compactness of entities (albeit with possibly 1 frame latency before an entity slot can be reclaimed).
• no random re-ordering issues.
• while doubly Linked lists have O(1) insertion/deletion, but are very hard to prefetch for optimal cache latency hiding. Keeping them in a compact array allows block prefetching techniques to work nicely.
• In the case of multi-object destruction, you don't have to do redundant shift-copies to maintain order and compactness (it all gets done once during the update pass)
• You take advantage of touching data that will need to be in cache already during the update.
• It works well if your source and destination entity poitners are to separate arrays. You can then double-buffer your entity arrays in order to take advantage of multicore/ eg. one thread updating/writing the entities for frame N, while another thread is rendering the previous frame's entities for frame N-1.
• Compactness means it's easier to DMA the whole lot to a heterogenous processor for even more CPU work offloading eg. SPUs or GPUs.

Answer 4

Speaking in terms of my general programming experience, splicing is usually a slow operation, involving shifting all existing elements up one. I'd think setting it to null would be the best solution here; a dead flag would work but you'd need to take care to not let it make your code messy.

We were just actually talking about resource pooling in the chatroom though, actually. It's a very good practice, and good to hear you are doing that. :)

Answer 5

Personally, I would use a linked list. Iterating over a liked list is fast, as well as adding and removing items. Using an Array or Vector would be a good choice if you need direct access to items in the structure (eg. access to an index), but it doesn't sound like you need that.

Whenever you remove an item from the linked list, you could add it to a pool of objects which can then be re-cycled to save on memory-allocation.

I have used the polygonal-datastructures in several projects and have been very happy with them.

Edit: Sorry, I think the answer wasn't very clear in terms of removal strategy: I'd suggest to remove the item from the list, as soon as it's dead and add it directly to the pooling-structure (recycle). Since removing an item from a linked list is very performant, I don't see a problem in doing so.

Answer 6

"just set a flag on it to say "skip over me, I'm dead." I'm pooling my entities, so an Entity that is dead is quite likely to be alive again at some point"

I think you answered your own question with regards to this specific application. I would get away from arrays if you ever plan to do work on them other than push and pop. Linked lists would be a smarter way to go if you plan on doing heavy operations. With all that said, if you plan to re-integrate the same entity back into the game then it makes sense to only set a boolean variable and check for it during game operation loops.

Answer 7

One clean and general solution i found on a lib i used was using a lockable map.

you have 2 operations lock() and unlock(), while you iterate over the map you'll lock(), now from this point every operation that changes the map doesn't take effect, it just gets pushed into a CommandQueue that will run once you call unlock().

So removing an entity would have the following pseudo-code:

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

and when you unlock()

isLocked = false
commandQueue.execute(this);

Only thing you have to consider is that you'll only remove the entity after the loop.

EDIT: this is the solution proposed by Simon.

Answer 8

Here's an answer I got from Liosan:
https://gamedev.stackexchange.com/a/46765/24633

Answer 9

I have two methods.

When you call an object to be deleted, it really sets two flags:

1.One to tell the container that an object has been deleted

2.One to tell the container which objects have been requested to be deleted

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

One Using a vector of objects

std::vector<object*> objects;

Then in the update function, check to see if an object has been deleted and if so iterate through all the objects and remove the ones that have a delete flag

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

Two Using a (pointer to a) vector of objects.

std::vector<object*> *objects;

In the update function, if an object is to be deleted, iterate through the objects and add the ones that aren't to be deleted to a new vector. delete the objects vector and set the pointer to the new vector

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