Collection with fast removal/iteration/insertion that recycles objects in Android/Java programs?

Question

I'm programing a game for Android. As an example, the game might involve bullets, enemies, gems etc. which need to be:

• created and destroyed in the game world during gameplay e.g. a bullet is fire and then disappears when it hits a wall.

• accessed a lot in sequence e.g. all updated in sequence, then all drawn in sequence.

Based on what I know so far from my work in Android, to keep my frame rate up, I need to consider the following:

• Not to allocate objects when you don't have to because the garbage collector will kick in and ruin your framerate.

• Prefer e.g. local variable accesses to accessing object fields and calling functions.

For the game objects mentioned above in a PC game, I'd usually just something like use something like a Vector or LinkedList. However, these would not recycle objects and using Iterator will create a new object as well as involve several function calls when iterating.

What is a suitable collection to use?

What I've found works well at the moment is to create e.g. a standard array of 100 bullets where all 100 bullets are created upfront. I then keep a count of how many bullets are active, when all the active bullets appear at the start of the array. Whenever I'm iterating over an array of bullets and I need to destroy one, I simple swap the current bullet index with the last active bullet index, then decrease the active bullet number. This changes the bullet order, but that's fine.

This works quite well:

Pros: Recycles objects, few/no function calls Cons: Error prone (especially removal) when not implemented as a collection class

Can anyone suggest a better alternative? I've seen many classes for managing object pools, but I'm not sure which are suitable for me.

Thanks.

Answer 1

I was programming games in the late 80s and more recently in Java for mobile devices. I can tell you that you're going to kill your framerate if you use LinkedList or Vector to store Java objects corresponding to things as trivial as bullets. That's not how efficient mobile games are programmed. Efficient mobile games are programmed by considering that "every bit matter". It is one of these domains where optimization reigns king.

Over simplification, but imagine you have a game with currently four bullets "alive" (it's not really "on screen", your "active world" can and typically should be a little bit bigger than your screen, it makes a lot of processing easier).

(20,30,3) (10, 50, 2) (30, 40, -3) (50, 50, 5)

So bullet one is at pixel (20,30) in your coordinate space and going at a speed of 3 (whatever a speed of 3 means, it's just an example) to the right (over simplification, it's just to explain), bullet two is at (10,50) going at a speed of 2 to the right, bullet 3 is at (30,40), going at a speed of 3 to the left (minus here means left) and last bullet is at (50,50,5) going at a speed of 5 to the right.

How is this represented in memory in current mobile games?

Like this, in an int[]:

int[] = { 4, 20, 30, 3, 10, 50, 2, 30, 40, -3, 50, 50, 5, ..., ..., ... };

The first 4 tells us that this "data structure a 4 elements. And you know each one is made of 3 values (in our oversimplified example).

Now imagine bullet 2 hits a wall and disappear, what happens?

This:

int[] = { 3, 20, 30, 3, 50, 50, 5, 30, 40, -3, 50, 50, 5, ..., ..., ... };

We simplify decremented the first int to 3, to indicate that only 3 bullets are left in our game world as of now and we've simply moved (50, 50, 5) to position '2', replacing (10,50,2) by (50, 50, 5). That's because the order of our bullet has no importance (they all have the same effect) and "moving all the int[] elements to the left" would be really inefficient.

Note that we didn't even bother to 'clear' the '4th bullet': the old (50,50,5) is still there at the end, but we know we only have 3 elements left, so we don't care.

So altough in memory it looks like this:

int[] = { 3, 20, 30, 3, 50, 50, 5, 30, 40, -3, 50, 50, 5, ..., ..., ... };

You're only concerned by this:

int[] = { 3, 20, 30, 3, 50, 50, 5, 30, 40, -3, ..., ..., ..., ..., ..., ... };

THAT is how it is done in most current mobile games: zero object creation for "bullets processing" in the main loop. You manage such simple data structures yourself, using arrays of primitives.

And the int[] is initialized at the beginning of your game of your level to the maximum number of bullets that can possibly happen in your game/level.

There goes your "reusable bullets pool".

If you start to think in term of having a Java object for something as trivial as a bullet and using LinkedList or Vector that you'd be modifying at each frame, you'll never ever get acceptable performance: you'd be generating countless needless object 50 times per second and triggering the GC way too often.

Now I'm certainly not saying that OO programming doesn't have its place in a mobile game: I'm simply saying that if your thinking in terms of objects for things as trivial as bullets, you'll never get acceptable performance.

My "bullet removal" technique involves here one decrement (the number of bullets) and 3 int copies. You can't beat that ;)

And it works for a lot of things: bullets, particle effects, ennemies, items, bonus, whatnots :)

Trivial things that are likely to be deleted/re-created often in your game loop should probably not be modeled using objects and certainly should not be put in Vector nor in LinkedList.