A Generic Pool Collection Class

I originally intended to write this article for Ziggy's XNA Article Contest. Unfortunately, real life got in the way in the form of a few weeks of crunch-time at work followed by a much-needed (and fabulous) vacation in Paris. Between those things and spending the little free time I had last month on my Dream-Build-Play entry (and not as much time on that as I'd have liked), I didn't get the article finished in time for his deadline. He received some great entries, though, so if you haven't already, head over there to read them. My favorites are the two HLSL articles by Jamezilla, one on Bloom/Blur Post-Processing and the other on Shockwave Distortion; and the article on Bezier Curves by Cubed2D. But all of the entries are worth a read.

EDIT: It looks like just as I was posting this entry, Ziggy was announcing the contest winner. Congrats to KrisC for his article on Graphic User Interfaces in XNA!

Resource Pools

Games need to be able to maintain collections of various types of resources, including such things as projectiles, particles, enemies, etc. Most non-game .NET applications would simply allocate such resources dynamically and then let the garbage collector dispose of them when they are no longer needed. Unfortunately, dynamic memory allocation and deallocation can, and will, cause slowdowns at indeterminable times. For games, or any real-time software, this is obviously unacceptable. As a game programmer, you need to be in control of when resource allocation and deallocation occurs and how long it takes.

The solution to this is to create resource pools where all of the memory for each resource type is allocated up-front during the game's initialization. When a resource is needed, an available item can be removed from that resource type's pool. When the resource is no longer needed, it can be returned to the pool.

Because a resource pool is a group of objects of the same type that has a fixed size, they are almost always implemented as an array. However a resource pool also has to keep track of which objects are currently being used, and there are multiple ways to do that. One way is to simply add a field in the resource class that specifies whether that particular object is active. The problem with that approach is that you have to rewrite code to manage each particular resource's pool. That is, you'll need separate code to manage your projectile pool and your particle pool, even though the code is doing basically the same thing. You could get around this "block copy" approach by having a parent class that maintains the active flag and contains the methods used to get a free object from the pool, update the active objects in the pool, reset the pool, etc. But that requires that all of your resource classes inherit from that parent, which isn't always desirable (and sometimes may not even be possible).

The most flexible approach is to have a generic Pool class, similar to the other .NET generic collections, that handles the maintenance of resource pools and can hold any type of object. In this article, we'll look at an efficient implementation of a Pool class and how to use it for a variety of different resource types.

Along the way, I'll describe some of the design decisions and trade-offs that go into writing generic classes. However, this is not intended to be a tutorial on writing C# generics. If that's what you are looking for, I recommend first reading a good book or online tutorial that covers the topic.

Desired Features of a Generic Pool

The following features are required for our Pool class to be useful.

Get — Takes a free item from the pool and marks it as active.

Return — Returns an active item to the pool and marks it as available.

Clear — Returns all active items to the pool and makes them all available.

Capacity — Gets the total number of items in the pool, both available and active.

AvailableCount — Gets the total number of available items in the pool. This is necessary to ensure the user doesn't attempt to Get more than the available number of objects. Therefore any call to Get should be preceeded by a test to ensure there are objects available.

ActiveCount — Gets the total number of active items in the pool.

CopyTo — Copies all of the active objects in the pool to a one-dimensional array. This is needed so that a resource pool can hold vertex data which can be easily copied to an array for passing to the GPU.

GetEnumerator — Gets an enumerator that can iterate over the pool's active items.

AllNodes — Gets an enumerator that can iterate over all of the items in the pool, active and inactive. This can be useful if there is one-time initialization that needs to be performed on all of the resource objects in a pool before they are ever used. Generally, however, after initialization, users should only be accessing active objects.

efficiency — Because resources such as particles and projectiles are generally being allocated and returned many times per frame, the pool class must be as efficient as possible. Where possible, all methods should be constant time — O(1) — and none should be worse than linear — O(n).

encapsulation — The implementation details should be hidden from the user as much as possible. In particular, the user should not have direct access to the active flag which should be modified only by the Pool class itself.

ease-of-use — The class should put as few restrictions on the user as possible so that it can be used as easily as other collection classes. In particular, it should have very little restriction on the types of objects that it can hold.

Implementation

To meet the efficiency requirements, the Pool class is implemented as an array along with a Queue containing the available (non-active) objects. By maintaining the list of available objects as a queue, the Get and Return methods can be O(1).

To meet the encapsulation requirements, the pool array is not an array of the objects being held by the pool, but an array of a Node struct. Each node contains the item being stored in the Pool along with the index of that item in the array. Because the node has to be given to the user so that it can be returned to the pool when the user is finished with it, the active flag is not stored in the node itself. If it were, the user would have direct access to it and could change it themselves, which we want to avoid. Instead, there is a separate array of booleans whose elements correspond to the elements in the pool array. Thus the NodeIndex field in the Node struct provides the index into both the pool array and the active array.

Finally, the ease-of-use requirements are mostly met by virtue of the class being implemented as a generic. As mentioned earlier, this removes the limitation of having a parent class for all resources that are to be stored in pools. However, since we are storing the actual resource objects inside Node structs, we need to be able to allocate each one when we create the nodes in the array. This means we have to limit resources to types that have a public, parameterless constructor. In other words, you can't store basic data types such as ints, floats, etc., inside a Pool. Since this Pool class is intended for holding resources that are more complicated than the basic data types, that restriction shouldn't be a problem.

The use of nodes when getting and returning pool elements is another design trade-off that slightly limits ease-of-use, in that the user has to deal with another data structure besides the one they want to store in the pool. To remove the slight burden this presents, the iterator returned by the GetEnumerator method provides direct access to the resource objects rather than nodes. Another enumerator is provided by the ActiveNodes property which can be used to iterate through nodes. This gives the user the flexibility to access active resource objects directly, or to access nodes for times when they may need to return an item to the pool. In general, I'd recommend using the ActiveNodes property inside an Update method, where the update may cause the resource to be finished and need to be returned to the pool; and the GetEnumerator property inside a Draw method, where you just want to go through all of the active resources and draw them.

The other disadvantage of storing the resource objects inside Node structs in this way, is that for value types (structs) stored in a pool, the user will only ever get a copy of the object instead of having direct access to it. That means that when using a Pool of a struct type, setting the node's Item field doesn't change the value of the item in the pool. To get around this problem, the SetItemValue method is provided to update the value of a given node in the pool.

Using the Pool Collection

Hopefully the comments provided with the class are fairly self-explanatory. The following subsections provide an overview of how to use the class.

Initialization

To use a Pool collection, all you have to do is construct it with the number of elements to be stored, generally at program initialization. This number of elements in the pool should be more than you will likely need, but not many more. It may require some tweaking to get that number just right for each specific use but generally you should have a pretty good idea of how many elements you need based on the design of your game and how many of each projectile, particle, etc. are likely to be active.

class Missile { private Vector2 position; private Vector2 velocity; private int configValue; public Missile() { } public void Init(int configValue) { this.configValue = configValue; } public void Fire(Vector2 position, Vector2 heading) { this.position = position; this.heading = heading; } public bool Update() { // Move missile, etc. ... // See if missile is finished if (reachedMaxDistance) { return false; } return true; } public bool Collided(Rectangle otherObject) { if (otherObject.Intersect(position)) { return true; } return false; } public void Draw() { // Draw missile ... } } public Pool missilePool; public void Init() { missilePool = new Pool<Missile>(MaxMissiles); // If there is any one-time initialization of all // resources, it can be done here. Generally, // though, this shouldn't be needed. foreach (Pool<Missile>.Node missile in missilePool.AllNodes) { missile.Init(ConfigValue); } }

Update

During the update portion of each frame, you will get items from the pool if needed, update all active items, and return items that are no longer needed.

public void Update() { // See if the user has fired a missile // (and verify there are some left in the pool) if (MissileFired && missilePool.AvailableCount > 0) { // Get a missile from the pool. Missile missile = missilePool.Get().Item; // Initialize the missile's position and velocity. missile.Fire(player.Position, player.Heading); } foreach (Pool<Missile>.Node node in missilePool.ActiveNodes) { if (!node.Item.Update()) { // If something happened during its Update to // make the missile no longer active, return // it to the pool. missilePool.Return(node); } else { // Note that if Missile was a struct instead // of a class, you would have to do the // following here: // missilePool.SetItemValue(node); // Loop through objects it might hit. foreach (GameObject item in ActiveObjects) { if (node.Item.Collided( item.BoundingRectangle)) { missilePool.Return(node); } } } } }

Draw

During the draw portion of each frame, you will get items from the pool if needed, update all active items, and return items that are no longer needed.

public void Draw() { // Draw each active missile foreach (Missile missile in missilePool) { missile.Draw(); } }

XNA Creator's Club Particle Sample

To provide a more complete example of using the Pool collection, I've modified Microsoft's XNA Creator's Club Particle Sample. The only changes from the original are the inclusion of the Pool class itself, in Pool.cs; and modifications to the ParticleSystem class, in ParticleSystem.cs. All changes have been marked with conditional compilation instructions (#if USE_POOL_CLASS) to make it easy to compare the original code with the new code.

Pool Collection Class

You can download the source file here.