Game Programming Essentials: Groups of Objects

Getting together lots of items at once, be they: enemies, bombs, powerups, particles or even the stars in the background.
If I remember on some of my very old code, I used to have:

int ex1,ey1, ex2,ey2, ex3,ey3; // locations for each enemy

But obviously that doesn’t scale.  And you should be moving onto arrays of sprite or arrays of enemies.
A say ‘should’ because I still see assignments which are handed in which have the “ex1,ey1,ex2,ey2” code in them.  These are the ones which are usually awful code, and get very little marks.
There is no hard & fast rule for how to design your Sprite class, but here are the things that I expect to see:

• Position (must have)
• Update & Draw function (must have)
• IsAlive flag or a life variable (must have, more on that later)
• Rotation, velocity, acceleration variables (good to have, more on those later)

You will need to be proficient with your game engine & programming language to know how to create this kind of class & manage groups of them.  Some game engines may provide you with a class with most of these features, but you will need to know how to be able to add extra functions/variables if you need it.

Note:
No amount of tutorials can cover every language/ game engine.  As I mentioned at the beginning this is general concepts.  So expect to have to do quite a bit of reading up to match this to your engine.  This set works will for XNA & C++, but might not for your engine.

Simple example: a starfield

Let’s start with a really simple example. A few hundred stars moving across the screen in a continual star field.

To do this we need a lot of stars (Sprites), an array to hold them & an update function to move them across the screen.  Here is the code is pseudo C#:

class Star: Sprite{
  void Update(float dt)
  {
    const Vector2 VELOCITY=new Vector2(-100,0);
    this.Pos += VELOCITY * dt; // move it
    // deal with off screen
    if (this.Pos.x <0)  this.Pos.x+=640; // wrap around
  }
}
List<Star> stars=new List<Stars>();
...

Idiot Warning:
DO NOT COPY THIS CODE IN AND EXPECT IT TO WORK!
We are covering concepts, not exact code.  So you will need to adapt the code to you individual language/game engine.

This is a simple example for a bunch of stars all going in the same direction & a simple wrap around routine to spot when they moved off the screen & put them on the other side.

Sharing Variables: Introducing statics

This starfield code is fine, but what happens if we wanted to change the speed of the starfield?  Answer: we cannot!  Its hard coded into the class.  Many times, that’s fine, but sometimes it might not be.   For example, what it you wanted the stars to move faster/slower when the player speeds up/slows down.  What about if the player starts flying upwards?
So let’s think of an alternative.

1. Add a public Vector2 Velocity to the Star class, then each star could move at its own speed
2. Add a public static Vector2 Velocity to the Star class, then all stars could move at the same speed

Now both of these options are good & valid.  The solution is should we use?  Answer, depends upon your real needs.  Remember these posts are about general concepts, not specific solutions.  If there was one fix-all solution, I will tell you.  But there isn’t.  Let’s look at this graphically, it might be a bit clearer:

As you can see: on both cases the star has a position attribute. But in option 2, there is only one velocity attribute which is ‘shared’, while in option 1, each has its own velocity.
For this particular case, I feel that option 2 (the static) is probably more suitable, as this is a single variable to control the movement of all stars at the same time.
So now its just a matter of getting your programming manual & looking up how to implement a static variable in the desired programming language.  Here in pseudo C# is looks like this:

class Star: Sprite
{
  public static Vector2 Velocity=new Vector2(-100,0);
  void Update(float dt)
  {
    this.Pos += Velocity * dt; // move it
    // deal with off screen
    if (this.Pos.x <0)  this.Pos.x+=640; // if off left: wrap around
    // will need to add in the other cases (right, top & bottom) 
  }
}

Collisions & Destructions (Attempt1)

Next item on our topic list is a common topic, collisions & destroying things.  We are going to start with a simple concept, space invaders:

In this case, we will need a list of invaders and a list of bullets (player shots).  I’m going to also assume a list of list of explosions which will nicely animate.

List<Invader> invaders=new List<Invader>();
List<Bullet> bullets=new List<Bullet>();
List<Explosion> explosions=new List<Explosion>();

I will also assume that Invader, Bullet & Explosion are based upon the same Sprite class.

For simplicity: I’m going to put most of my code inside the Game class, rather than the individual classes (its simpler that way).
Lets tackle the most complex bit first, the collisions:

Collisions Done Badly

At first this might seem like a good idea:

for(int e=0; e< invaders.length; e++)
{
  for(int b=0; b< bullets.length; b++)
  {
    if (bullets[b].CollidesWith(invaders[e])) // bullet hits enemy
    {
      createExplosion(invaders[e].position); // big explosion
      invaders.removeAt(e); // remove the enemy
      bullets.removeAt(b); // remove the bullet 
    }
  }
}

Note: if you are a C++ programmer, it will be delete’ing the objects.

How does this code look? Reasonable?
Well, no its not, this code will probably crash within the first 30 minutes of testing.  Let me give you an example:

1. Assume 10 enemies & 5 bullets.
2. The code loops through checking each invader against each enemy
3. This cycle, bullet 0 hits invader 9, the explosion is created
4. The code then removes bullet 0, since its an array, all the other bullets are moved up
5. The code then removes invader 9, the invaders array is now reduced to 9 items long
6. The cycle now continues to check seeing if bullets 1,2,3 hit enemy 9
7. BUT: If didn’t check one of the bullets (the one in slot 1, since it got moves to slot 0)
8. AND: it crashes since there is no enemy 9 anymore as the enemies are 0..8

You can try thinking some creative solutions to this problem.  But the bottom line is this.

If you start adding or removing object from an array while you are looping over the array, sooner or later it will break.

This is a well known programming topic: a quick google on “removing objects from a collection while iterating through it” will give you a lot of hits and a lot of ideas.  But rather than try to fix it, let me present you with a different way to approach the problem.

Detour: Object Pool

Recycling is a good idea, reusing stuff & so on.  But did you know that you can recycle in programming too?

Let me give you an idea:

In our space invaders game, how about we create up the array of 40 or so invaders we need at the start of the game.  While we play the game if an invader gets killed, we just set a ‘dead’ flag on the enemy, but leave it in the array.  When moving invaders we skip the dead ones & obviously we don’t draw them either.  However when the next level begins, or the game restarts, we just need to go through the array cancelling all the invader’s ‘dead’ flags.

Seems quite a reasonable idea, just adding a single flag to it and a few if statements. Now let me expand the idea:

In our space invaders game, they invaders can only have a maximum of 3 bombs on the screen at once (an arbitrary limit).  So we have an array with 3 bomb sprites in it.  Each bomb again has this ‘dead’ flag, and at first, all bombs are marked as being ‘dead’.
Each time an invader decides it wants to drop a bomb: it checks the bomb sprite array to see if there are any bombs marked as ‘dead’.  If it finds one, it sets the bombs location just below itself and marks the bomb as not ‘dead’.  If there are no spare bombs, the invader will have to not drop the bomb yet.
The live bombs will drop down and once it hits the ground it marks itself as ‘dead’ and wait to be reused.

I hope you are starting to get the idea on this idea.  Its known as an ‘object pool’, its not only used in games, but its commonly found in games especially those on low memory requirements.

An expanded idea is instead of having a Boolean ‘alive/dead’ attribute, why not have a ‘life’ attribute.  Many sprites in a game need to be hit many times to be killed, so why not use the ‘life’ attribute to determine if a sprite is alive or dead?  For one-hit-kill sprites, just give them life=1!

Technical Note: 
In XNA on the Xbox 360 and the Window Phone and on many other mobile devices there are often lots of warnings about allocating/deallocating too much memory, as the garbage collectors are get overloaded quite quickly.  Therefore having an object pool helps a lot.
And even if you are programming in C++, by not continually new-ing and delete-ing objects you save yourself a lot of pointer headaches by using an object pool.

Collisions & Destructions (Attempt2)

Ok, back to our collision problem we hit earlier.  Let’s use the object pool concept & assume the Sprite class has an ‘isAlive’ attribute which we can use in our game.

Let’s have a look how the code has changed.

for(int e=0; e< invaders.length; e++)
{
  if (!invaders[e].isAlive) continue; // ignore dead invader
  for(int b=0; b< bullets.length; b++)
  {
    if (!bullets[b].isAlive) continue; // ignore dead bullets
    if (bullets[b].CollidesWith(invaders[e])) // bullet hits enemy
    {
      createExplosion(invaders[e].position); // big explosion
      invaders[e].isAlive=false; // enemy is dead
      bullets[b].isAlive=false; // bullet is dead too
    }
  }
}

Other than the additional checking for alive objects, the code is generally much neater.

Note on naming: 
Do you notice that I named my loop variables e and b, not x,y or i,j?
There is a simple reason for this.  What happens if I try accessing bullets[e]?
Answer: it crashes quite quickly.  There are probably only a few bullets in the array, but e was used to index the invaders & probably goes up to 40.  Therefore in this case, I always use a clear loop variable name so I know which is which.
Alternatively you can use an iterator or a foreach, if your programming language supports it.

Other odds & ends

This is a quick wrap up, since we have covered all the main topics.  But here are a few things to consider:

• Keep your eyes open for common sprite attributes & specific sprite attributes
• In my examples above: position & isAlive are common to all
• As it the CollidesWith() function
• But the Velocity attribute might or might not be a common
• Think carefully before adding to the base class, but go ahead and add new stuff to the derived class
• Sometimes I see students adding strange features to the base class, because they don’t know how to use the derived class or manage up-casting & down-casting. (If you don’t know what that means, do look it up)
• My example above ran with a single Boolean for isAlive, but it could so easily have been an integer variable:

class Sprite
{
  int life;
  bool isAlive(){return life>0;}
  void Destroy(){life=0;}
  void Damage(int amount){life-=amount;}
  ...
}

• Then we can have the invader injured by a bullet using:

    if (bullets[b].CollidesWith(invaders[e])) // bullet hits enemy
    {
      invaders[e].Damage(5); // damage invader
      bullets[b].Destroy(); // remove bullet
      if (!invaders[e].isAlive()) // its just died
        createExplosion(invaders[e].position); // big explosion
    }

• Be careful with object pool sizes:
• The more objects you put in the pool, the more you can have active at once. But the more memory it takes, (having a large pool of dead objects does take a little CPU, but not much) 
• Ask yourself, do you really need 1000 enemies ‘just in case’?
• Also remember that it is possible that all pool members might be busy, so always check for it. Eg.

void createExplosion(Vector2 position) // big explosion
{
  // look for spare explosion
  Sprite spare=null;
  foreach(Sprite s in explosions)
  {
    if (!s.isAlive)
    {
      spare=s;
      break;
    }
  }
  // VITAL: check to make sure there is a spare
  if (spare==null) return; // no spares
  ... // do whatever you need

• Clever programmers will spot the foreach loop & recognise that it could be moved to a function
• Really clever programmers will realise it can be make into a template/generic function
• Learn how to tell when it’s better to use two lists of sprites, or combine them into a single list of sprites.
• I don’t have a good ruling on this one.  Having a list of different types of sprites is what polymorphism is all about isn’t it?  The trouble is that taken too far can cause so much complexity, that it’s easier to separate them.
• Generally though, it often keep my sprites apart

Conclusion

Although I didn’t touch the 3D sprites, the concepts for both these are exactly the same.  Its all about managing the groups of objects.

Hope this helps get you thinking along the right tracks.

Mark