My game has a list of enemies objects. What’s the best way to manage memory when an enemy object is killed?
In C++, my initial reaction is to create two linked lists of objects – one for “dead” enemies and another for “live” enemies.
As an enemy dies, I would just send it to the list of dead enemies. As I need a new enemy, I would just yank one from the list of dead enemies (recycle memory).
Unfortunately, Java has no pointers.
What’s the best way of dealing with this scenario?
Option one:
Don’t even bother. You can allocate tens of thousands objects per second.
Option two:
Why would you need pointers? In Java you can also have Lists to move your objects around
Le sigh. Everytime I ever hear anyone say this, it’s always a C or C++ programmer who’s utterly failed to grasp some of the basics of Java. I think you need to go back to the basics and actually read up on how java object references work.
Slightly more helpfully, there’s nothing to stop you having a ‘dead’ and ‘alive’ lists just like you would[1] in C++. If you need a fresh enemy and your ‘dead’ list is empty, then just ‘new’ one.
However unless you’ve got thousands of new enemies spawning each frame, or you’re on some radically constrained platform (iPhone?) then there’s no reason why you shouldn’t just new them when you need a new enemy, and just remove it from your alive list when it’s dead (and like the gc clean up the memory).
[1] Except that even in C++, I wouldn’t do things like this, as it’s a needless micro-optimisation. I’d just be new-ing and delete-ing as this avoid a whole bunch of object lifetime issues which can cause obscure and difficult to track bugs.
public class Enemy
{
private int var1, var2, var3;//, etc.
private boolean isMarkedForDeletion;
public boolean isMarkedForDeletion()
{
return isMarkedForDeletion;
}
public void die()
{
isMarkedForDeletion = true;
}
}
private ArrayList<Enemy> enemies;
public void mainLoop()
{
for (int i = enemies.size()-1; i >= 0; i--)
{
Enemy e = enemies.get(i);
e.act();
if (enemyHitABullet(e))
{
e.die();
}
if (e.isMarkedForDeletion())
{
enemies.remove(i);
}
}
}
There you go. just give all your entities a marked for deletion boolean, then on the next pass they’ll be deleted. Because the ArrayList does in fact just hold pointers to each Enemy (like every single object reference in Java), when it gets removed from the list, the garbage collector will find that the object has no pointers to it and will therefore get removed from memory.
Memory management in Java is quite easy - if you don’t want to keep an object, don’t have references to it anymore. The only difficult cases are rare - mostly involving multithreading or having a lot of people working on the same program so some people don’t know what others are doing. Just have good design and you’re fine.
Excuse my French: Bullshit.
Instead of being rude, maybe tell me why I’m wrong?
@ikaruga: Have a look-see at this link, it is pretty helpful about the cases when you can have memory management problems. http://www.ibm.com/developerworks/java/library/j-jtp06243.html
Right. So… you can just give somebody advice, by making guesses, and when you are blatantly wrong, are not taking criticism lightly…
Ok, I will elaborate: the GC doesn’t do reference counting, it determines whether an object is reachable, by other reachable objects. It holds a list of ‘root’ references - you can observe that in heapdumps, if you want proof. This is also one of the reasons the GC is so fast: upon GC, it doesn’t figure out which objects can be disposed, it will only track which are reachable, and move those around the heap. The GC will completely ignore all garbage, unless it has an overriden finalize() method, or is tied to a ReferenceQueue.
[quote=“Demonpants,post:6,topic:34285”]
I’ve been very inactive on the forums lately. But wait, you’re calling me a troll? I might be harsh, very critical, but… a troll?? You might want to PM me about your personal grunt, I’m not going to derail this thread any further.
Anyway…
What a useful class @Demonpants@! Doing a google search also revealed a LinkedList class.
Isn’t it more efficient to use a linked list? For 1000+ enemies, I’m sure there is significant overhead each time you delete an enemy in the ArrayList (the list gets reordered, etc.). Or does it not matter as @Riven@ seems to imply?
well, your main question is going to be,
are you crunching for that last inch of performance. If yes, then I assume taht an arrayist might be slower, but I am not sure. Dont lists have order though. But I guess they dont have the empty.
I suppose that a linked list mgith be faster…
from the tests I’ve run in the past, ArrayLists are almost always faster than LinkedLists.
Cache-coherance and not having to use an iterator usually mean an ArrayList is going to be faster. And if removal is a particular problem then a nice trick is to swap the element to be removed with the last element, and then remove it, which avoids having to reshuffle the other objects. Obviously this means you can’t rely on the objects being in a particular order, but for entities that rarely matters.
Wow. ArrayLists are faster than LinkedLists in Java – would not have seen that coming 
@Orangy Tang@ - so to confirm, swapping the last element is as simple as:
Enemy tmp = enemies.get( enemies.size() - 1 );
enemies.set( enemies.size() - 1, enemies.get(i) );
enemies.set(i,tmp);
The “set” is actually a copy by reference, right?
It’s pretty much the same in C++ as well - often std::vector is faster than std::list unless you’re doing lots of insert/removes or if you’re holding big types by value.
But yeah, your swap looks fine.
I wasn’t guessing, I honestly thought that was the case.
ArrayList is a lot faster than LinkedList because you’re dealing with a single block of memory versus needing to follow pointers all over the place. LinkedList is really only faster if you’re swapping items in your list in, out, and all around, changing its size, reordering it, etc. But even so, like people have already said, ArrayList will usually be faster anyway. You’ve really got to be moving a lot of stuff around to see a reason to use LinkedList. In a lot of situations in games (like say when you want to remove your enemies from your list), you’d store the index of object in the list somewhere for quicker removal. In a LinkedList you’ve got to browse through n elements to get to the nth element, whereas ArrayList is O(1). Of course, removal in LinkedList is O(1) and O(n) in ArrayList, but they this is just another place LinkedList can’t really top ArrayList - in order to remove any element you usually need to get to that index anyway, so it just becomes O(1) + O(n) = O(n)… not any faster than ArrayList, even where it is “supposed” to be. It’s also, IMO, annoying to use Iterator to access the items in LinkedList and not just be able to do it via array locations. Say you’re using an Iterator with your object deletion case - if you try to remove anything from the list while you’re using that same Iterator you can very easily get ConcurrentModificationExceptions. Index access is much cleaner and more predictable.
But of course, if you’ve got some sort of implementation that specifically will work better for a LinkedList, then go for it.
Well that seems to settle the issue for me. Thanks all.
One last quick question: out of curiosity @Demonpants@ why are you traversing the array backwards? I noticed the same setup in another ArrayList tutorial…
That has to do with removing, sorry I meant to explain that but I forgot.
Say you have an array:
A, B, C, D, E, F
And you want to remove ones that are marked for deletion, which we’ll say are the bold ones, B and E. Iterating forward does this:
index = 0;
object[index].act(); //A.act()
index = 1;
object[index].act(); //B.act();
remove[index]; //Array becomes A, C, D, E, F
index = 2;
object[index].act(); //D.act() ! Here's the problem - the object at index 2 is what was formerly at index 3
etc.
You can see that the indices being used are now off whenever something gets removed, and you’ll start skipping things. Whereas if you go backwards, you know that you’ve already called everything that will be affected by the removes:
index = 5;
object[index].act(); //F.act()
index = 4;
object[index].act(); //E.act();
remove[index]; //Array becomes A, B, C, D, F
index = 3;
object[index].act(); //D.act() Note that is is all correct now. Although F goes from index 5 to index 4, we've already called it so that's okay.
index = 2;
object[index].act(); //C.act();
etc.
If you really wanted to go upwards instead of downwards, you can always compensate for your remove like this:
for (int i = 0; i < enemies.size(); i++)
{
Enemy e = enemies.get(i);
e.act();
if (enemyHitABullet(e))
{
e.die();
}
if (e.isMarkedForDeletion())
{
enemies.remove(i);
//Compensate for something getting removed.
//Our browsing index is effectively one less.
i--;
}
}
Of course, that’s n more operations (even if subtraction is super cheap) and it’s bad practice to mess with your loop variable inside a for loop. Might as well go backwards, it works better all around.
You are creating a post, with only one word, apparently disagreeing. He has to ask you if you would please explain why you are in fact disagreeing.
Not very contributing.
Where I come from, thats a troll.
You might have missed my post where I explain how the GC cleans up these circular references: by ignoring them completely.
On a sidenote: wouldn’t you think your post would fit the ‘not very contributing’ category?
come on as much as I like to read this stuff during science ;).
keep it to pm messages, as not to derail this guys thread :).
The implementation you give earlier in the thread specifically works better with LinkedList. Just replace the backwards iteration over indices with use of an iterator. Since you’re already iterating through the list removal of dead enemies will be O(1) with no added O(n), whereas removal from an ArrayList in your example will be O(n).
So the two implementations that OP should be profiling are:
// enemies is an ArrayList
for (int i = enemies.size()-1; i >= 0; i--)
{
Enemy e = enemies.get(i);
e.act();
if (enemyHitABullet(e))
{
e.die();
}
if (e.isMarkedForDeletion())
{
int n = enemies.size() - 1;
enemies.set(i, enemies.get(n));
enemies.remove(n);
}
}
and
// enemies is a LinkedList
Iterator<Enemy> it = enemies.iterator();
while (it.hasNext())
{
Enemy e = it.next();
e.act();
if (enemyHitABullet(e))
{
e.die();
}
if (e.isMarkedForDeletion())
{
it.remove();
}
}
Both have O(1) removal time, and I would expect the ArrayList one to be faster.
??? If you have a situation where you’re getting ConcurrentModificationExceptions then using index access doesn’t sound very predictable at all. At least with CME you get a notification that things went wrong and a hint for what to look for.