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