Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
A Vector's length is not fixed, but it is typed, and that makes it superior over Array. The drawback is there's no quick syntax to define a pre-filled list, but you don't need that I think. –  Bart van Heukelom Aug 13 '10 at 8:51

9 Answers 9

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

share|improve this answer

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.

share|improve this answer
1  
+1 for flixel. Recycling the dead really helps with the performance. –  Snow Blind Aug 5 '12 at 8:33

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. :)

share|improve this answer
1  
If update order is not important splicing should be as simple as moving the last entity to the current index and decreasing your pool count and iterator index. –  Kaj Aug 12 '10 at 19:24
    
Wow, very good point Kaj! :) –  Ricket Aug 12 '10 at 20:23

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.

share|improve this answer
1  
I assume that you suggest a double-linked list here? (forward/back)? Also: Are you suggesting some sort of pool over the link-elements or are you dynamically allocating each pointer-holder in the linked list? –  Simon Aug 12 '10 at 19:45
    
Yes, it would have to be a double-linked-list that's best suited for that task. Thanks for pointing that out! Regarding re-using of items: I was thinking about a specialised pooling class/datastructure, one that creates new objects on demand or uses existing instances if there are some in the pool. Therefore it would be good to actually remove "dead" items from the list and add them to the pool for later usage. –  bummzack Aug 12 '10 at 20:09
    
A singly linked list will do fine. Doubly linked lists only give the advantage of iterating in both directions. To iterate through a singly linked list with option of removing the current item you'll need to keep track of the previous entry. –  deft_code Aug 12 '10 at 20:29
    
@caspin yes exactly. If you're using a single-linked-list, then you need to keep track of previous nodes and link their next pointer to the node after a deleted one. If you don't want the hassle of doing this yourself, a double-linked-list would be the DataStructure of choice. –  bummzack Aug 12 '10 at 21:16

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.
share|improve this answer
    
+1. I like this. Although I hardly ever need ordered updates within a pool I'll add it to the bag of things to remember if I run into the situation :o) –  Kaj Aug 12 '10 at 21:21

"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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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;
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.