Managing collections of objects in XNA: Structs vs. Classes

space shooter
Obviously, these aren’t the final graphics.

A couple of weeks ago, I started working on an XNA space shooter game. It’s 2D and completely sprite based–the type of thing that you wouldn’t think was that hard to do. And yet, I put most of the inner workings of the gameplay through two rewrites in that time.

The first draft

At first, I wrote a nice class structure: every gameplay object originated from an abstract class called GameObjectBase, which defined methods to handle Update, Draw, and intersection with other types of game objects (projectiles, the player’s ship, etc.). Then, each additional type of game object had its own abstract base class that, again, defined key pieces of behavior: EnemyBase, ProjectileBase, PowerupBase. The main game loop itself would keep track of all of these game objects, calling Update and Draw on them as necessary.

The plan here was to be able to define a new class for each type of enemy and weapon so that I can define whatever behavior I need for them. That’s what I’m really going for here: I want the option to do interesting things with various weapon powerups. And I think I’d actually hit upon an elegant solution.

When you first fired it up, the game ran fine for a while. But there was a problem: garbage collection. Each new enemy or bullet created a new object and stuffed it into the main game object list; each time one of these enemies was destroyed it was removed. Considering that the player can fire ten bullets per second, that’s a lot of objects. Eventually, the garbage collector had to clean up all of these old objects, essentially freezing up the game for a few seconds.

Structs to the rescue?

The obvious solution seemed to be converting some of these objects to structs. This presented a challenge: it would gut most of the lovely class structure I’d set up, since there’s no inheritance with structs. But structs are value types and go on the stack, so I could create and destroy them at will without having to worry about incurring the wrath of the garbage collector.

It’s still possible to define methods on structs, so I’d lose very little functionality. And most of the data each class was tracking–speed, position, damage, health, etc.–were value types themselves.

Delegates: they’re not just for events

I hit upon a workaround for inheritance: delegates. Rather than defining a deep inheritance structure, I could define a few basic types (PlayerShip, Projectile, Enemy, Powerup) and define most of the important behaviors as delegates. This would allow more complex behaviors, but rather than defining them as subclasses, they would need to be assembled at run-time from a library of effects. For example:

static class PowerupEffects
{
    public static void HealthPowerup()
    {
        if (GameplayState.Ship.CurrentHealth < GameplayState.Ship.Health) { GameplayState.Ship.CurrentHealth += 1; }
    }
        
    public static void SimpleRapidPowerup()
    {
        GameplayState.Ship.WeaponCooldown = 100;
        GameplayState.Ship.FireWeaponMethod = WeaponSpecs.FireBasicWeapon;
    }
        
    public static void SimpleSpreadPowerup()
    {
        GameplayState.Ship.WeaponCooldown = 750;
        GameplayState.Ship.FireWeaponMethod = WeaponSpecs.FireSpreadWeapon;
    }
}

Structs and collections don’t play nice

And this approach seems perfect–right up until the point you have to compile it. Because you’ll end up with a code block like this:

foreach (Powerup p in Powerups)
{
    p.Update(gameTime);
    if (p.Position.Y > 1.5)
    {
        p.Destroy = true;
    }
}
Powerups.RemoveAll(p => p.Destroy);

And you’ll get a bizarre compiler error that says “Cannot modify members of ‘p’ because it is a ‘foreach iteration variable’.”

OK, you say, let’s try something different. Let’s use a for loop:

for (int i = 0; i <= Powerups.Count; i++)
{    
    Powerups[i].Update(gameTime);
    if (Powerups[i].Position.Y > 1.5)
    {
        Powerups[i].Destroy = true;
    }
}
Powerups.RemoveAll(p => p.Destroy);

Again, you get a compiler error: “Cannot modify the return value of ‘System.Collections.Generic.List.this[int]’ because it is not a variable.”

This blew my mind–but then, I don’t use structs much. I knew that, as value types, you couldn’t just pass them around between methods and modify them like you do reference types, but it never occurred to me that you couldn’t put them into a List and do anything useful with them. (One solution I discovered in the course of writing this blog post would be to define a fixed-size Array of these objects, but you would have to manage this yourself.)

Pooling: more than database connections and threads

At this point, I wished I’d put the project in source control, because I was going to have to undo a lot of what I’d just done down the dead-end that was structs.

I ended up switching back to classes, of course. I kept the flat hierarchy–Projectile, Enemy, Powerup–and used delegates to define the behavior of each type of object. But I also defined a Reset method for each class that would set all of the fields and properties of the object to their defaults:

class Powerup : GameObjectBase
{
    public void Reset(Vector2 position, string spriteName, Action effectMethod)
    {
        Position = position;
        Speed = 0.25f;
        SpriteName = spriteName;
        EffectMethod = effectMethod;
        Destroy = false;
        BoundingSize = new Vector2(0.05f, 0.09f);
    }

    ...

}

Then, in my static GameplayState class, I defined two lists of objects: one for active objects, and one for unused objects. To go along with these, I created methods to swap objects between the two lists:

public static List<Powerup> UnusedPowerups = new List<Powerup>();
public static List<Powerup> Powerups = new List<Powerup>();
        
public static Powerup AllocatePowerup()
{
    if (UnusedPowerups.Count > 0)
    {
        Powerup p = UnusedPowerups[0];
        UnusedPowerups.RemoveAt(0);
        Powerups.Add(p);
        return p;
    }
    else
    {
        Powerup p = new Powerup();
        Powerups.Add(p);
        return p;
    }    
}

public static void DeallocatePowerups()
{
    foreach (Powerup p in Powerups.Where(p => p.Position.Y > 1.5)) { p.Destroy = true; }
    UnusedPowerups.AddRange((from p in Powerups where p.Destroy select p));
            Powerups.RemoveAll(p => p.Destroy);
}

(Now that I think about it, I’m probably butchering the usage of the terms allocate and deallocate here.)

It turns out that this is similar in concept to the Object Pool design pattern, although the point here is to avoid the high cost of destroying objects rather than creating objects.

The Allocate method is called every time a new object is needed–all you have to do is call the Reset method on the object to define its properties. The Deallocate method, which removes any objects that are flagged as destroyed or move off-scrren, is called every update cycle.

I’m sure there are other viable patterns here, but this seems to be easy to manage while giving consistent, stable performance.