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.

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

Right now, I have an ArrayList like this:

List<Enemy> enemies = new ArrayList<Enemy>();

When an enemy dies, how can I remove it? Should I use a different type of list, array, or set?

share|improve this question
    
Without more information, this will be difficult to address completely. –  Clockwork-Muse Jan 3 '13 at 22:11
    
I've edited your title to something that fits the actual context of your question =) –  Sidar Jan 3 '13 at 22:17
add comment

marked as duplicate by Byte56, Josh Petrie, bummzack, Sean Middleditch, Nicol Bolas Jan 5 '13 at 8:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers

up vote 5 down vote accepted

Please, don't use a set, you don't need it. There's a simple trick that can help improve @Jake-Woods' answer.

From my experience, if you keep a lot of enemies (or other entities) in an array, you don't really care about the order in the array. The trick is, it's possible to remove an object from an array with a small and constant amount of operations (O(1)), if you allow for the order to change. The algorithm is as follows:

  • Iterate over the entities in your array
    • If you find an item that needs to be removed
      • Swap it with the last element
      • Remove the last element from the array

It's quite easy to write, but takes some work to understand that this works properly for corner cases (like removing the last element from the array). Here's a code sample from my project:

   public void update(int dt) {
            for (int i = 0; i < entities.size(); /* conditional incr */){
                    Entity entity = entities.get(i);
                    entity.update(dt);

                    if (entity.isToBeDestroyed()){
                            int lastEntity = entities.size()-1;
                            entities.set(i, entities.get(lastEntity));
                            entities.remove(lastEntity); 
                    } else {
                            i++;
                    }
            }
    }

This particular variant uses update and remove in a single loop, but depending on your context you might want to split those into separate loops (so that entities don't disappear during the update phase).

share|improve this answer
add comment

The java List interface provides two methods for removing objects, one taking an instance of the object and one taking an index. You can see all the methods on the list interface here

Regardless of what list implementation you use all lists will have those methods. The difference is in the speed of certain operations. The JavaDocs for list implementations provide a good overview of the performance tradeoffs: ArrayList, LinkedList

To remove an element from any list it depends on if you're iterating or not. If you want to remove an element from a list while you're looping over the list you need an iterator:

List<MyObject> objects = getMyObjects();
Iterator<MyObject> iterator = objects.iterator();
while(iterator.hasNext()) {
    MyObject current = iterator.next();

    if(enemyIsKilled) {
        iterator.remove(); // Removes the current object.
    }
}

If you're not iterating and you just want to remove the enemy outside the loop, then we can just use the list.remove method:

List<MyObject> objects = getMyObjects();
MyObject instance = objects.get(2); // Get the 3rd object, could be any MyObject instance in the list
objects.remove(instance);

The choice of what collection to use depends on two things: What collection makes logical sense to use and what collection has the best performance for my application.

The answer to these two questions is the age old "it depends". The choice between a list and a set is a choice between duplicate and non-duplicate elements and sometimes between ordered and unordered elements. The choice between an ArrayList and LinkedList is a tradeoff where ArrayLists are faster to iterate over but LinkedLists are faster to remove from/insert to.

When you're just starting out you don't know where your performance bottlenecks are going to be. My advice would be to use List everywhere and just pick either ArrayList or LinkedList as the underlying type. If later on in development you notice the game is going slow you should use a profiler to determine if traversal or removal is the problem, if it is then you can look at changing the underlying list type that you use.

Remember: The golden rule is don't optimize prematurely

share|improve this answer
4  
+1 - A decently thought out answer that, y'know, actually usefully answers the question (given the current information). –  Clockwork-Muse Jan 3 '13 at 22:11
    
There is a lot of good info in this answer, but it's possible to easily remove items from an "unordered" ArrayList in O(1), which I find a very good solution to this problem. See my answer. –  Liosan Jan 4 '13 at 7:52
    
@Liosan that's a good point, the swap trick is certainly useful if removing is too slow. I still think you shouldn't bother with that until performance becomes an issue (or if the container naturally supports it) but it's very useful to know about. –  Jake Woods Jan 4 '13 at 9:20
    
Agreed there's no need to implement it before it becomes a problem. But actually knowing it exists solves issues of "which data structure to choose", since ArrayList with the swap trick beats sets and linked lists by a large margin, in both iteration and removal. Unless you want an ordered list, or some form of pooling objects. –  Liosan Jan 4 '13 at 11:08
add comment

First off do you need to actually 'remove' them? Another alternative would be to set a flag on them to 'dead' or 'disabled' or something, anything that sees that (such as your rendering function) will just skip over them.

If that is a good idea or not will depend on the usage of your program.

If you have a limited number of guys spawned at the start of the level then it works fairly well. It can also make things like reloading saves much faster (you just unset the disabled flag and reset their other attribues). But it does have some runtime costs as you will still be looping over all the dead guys (although you would be doing the full load at the beginning anyway).

If you are continuously spawning and killing of waves of bad guys then that's not a great solution. In that case you need a data structure that is quick to insert and delete. An array is not a good choice as the entire memory must be copied each time. You want a linked list instead. Linked lists have a little bit of overhead compared to an array as each item points to the next one, it's also harder to access a specific element in the array as you have to iterate over each one, but generally it's good enough to not worry about for real world applications. You could always combine the LinkedList with a Array you use for indexing.

Games often try and reduce the allocation of memory at runtime as much as possible. Games are generally fairly predictable. You know there will be a finite number of bad guys, the only unknowns are plays input (maybe there is a way for the player to cause bad guys to spawn), in that case they will guess a fairly good maximum and add a saftey factor and provide a fallback runtime way to increase the size (or just put some limits in place since otherwise the player could spawn so much they run out of memory).

You can create new guys at runtime using what is called a Pool. Basically they allocate the guys in advance and pull out a new one when it's needeed.

share|improve this answer
1  
+1 because this answer gives several tips I've never thought of, in particular using an Array to index a LinkedList. Combining the ideas of leaving entities in the Array and disabling them, or using a Pool, would it not be sufficient to disable an entity in an Array, and later re-enable it with new coordinates and attributes, to simulate pulling from a Pool? It's always there, and only used when needed. Just a thought, and what I've been doing. –  jonhopkins Jan 4 '13 at 14:10
    
Reusing an entity in an array works fine for a fixed number of entities or if there all of 1 data type (specifically size), but it isn't so good for lots of dynamic data types, you need safety factors meaning lots of lost memory. Under the hood, Pool's are just an array. When they are initialized rather than remaining empty, the 'empty' memory each cell points to the location of the next unused cell and the pool itself keeps a 'head' pointer to the first free cell. If you need a new object, the pool looks up the head cell and replaces the head pointer with the cell the current head points too –  David C. Bishop Jan 5 '13 at 3:13
    
@jonhopkins: Of course with a pool you still need an index structure (or more than 1) to find anything. The best structure will depend on the way you are commonly searching for things. If you are rendering them or searching for them based on location, then you will want a scene graph of some kind (For example an Octree, BSPTree), otherwise if you are looking them up based on an ID, StringName or hashed string (close to the efficacy of numerical id with the human readability of string) then you will want a hash map, if you are just scanning through them in sequential order then a linked list. –  David C. Bishop Jan 5 '13 at 3:22
    
@jonhopkins: There's a article on pools [neculamarian.blogspot.com.au/2012/11/…. My Java's a little rusty, I'm not totally sure how pools work in Java since it doesn't have pointers like in C/C++ and the casts seem to be conversions so maybe you will need a linked list with indexes of free cells instead of keeping the pointers in unused cells but the memory use shouldn't be much worse and the performance should be about the same. To simplify thing keep your memory allocation and your entity indexing separate, choose an index that fits your lookup operation(s) –  David C. Bishop Jan 5 '13 at 3:34
add comment

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