I want to take a little time to write about the design and implementation of the particle system for the Tengu Engine. I have programmed particle systems for some of my earlier projects, but they all took a similar approach which suffered from several short comings, as I will explain. My previous systems were all very rudimentary; All of the particles were stored in a large fixed length array, which was entirely updated and rendered once each frame, and as new ones are created they replace the oldest ones in this list. I had also tried a similar technique using a linked list in place of the array, which solves a few of the short comings, however not all of them. Linked lists are generally slower too since many different memory areas have to be accessed in one traversal of all the particles. The problem of using a fixed length list is that it imposes a very hard limit on the number of particles that may exist at any one time. This may be acceptable if the list is large enough, or if there is quite a consistent rate of death and birth.

The linked list approach removes this limit since new items can be added to the list at any time, so we can always add more if we need them. In the simplest implementation, we need to allocate more particles when they are born and de-allocate them when they die, each being a fairly expensive operation. This could be avoided by never de-allocating a particle, and instead, upon its death it is removed from the particle list and added to a list of free particles. When an allocation request comes in, we just pick one from this list of free particles. This has the benefit of being simple and reducing the allocation and de-allocation requests to almost zero for a steady game state. If the free list is empty when we ask for a new particle only then will we have to allocate a new particle, or better still, a bunch of them, adding the excess to the free list to give the system a little head room.

This strategy is in fact something that I may try at some point for a simple project since there are many advantages too it, but there are also some disadvantages that remain. Each particle must store a pointer to the next particle in the list. This increases the particle size by 4bytes for each one, not terrible, but quite wasteful since there are ways to avoid it. Another downside is that memory accesses are fragmented, because the next particle in the list might have been allocated somewhere far away in terms of its memory location. Fortunately both of these problems can be solved, or minimized with one technique, which I will now explain.

I call this technique clustering. Instead of allocating particles on the individual level, I instead allocate many in one go, from the same memory space. In my current implementation I allocate 64 particles at once, but this was just a number picked out of the air. Each cluster forms a linked list, so they can be chained together so that the particles don’t have to have any information about the list they are in. So I ended up with something like this:

//
struct sParticle
{
    float x, y;
    float vx, vy;
    float age;
    // ....
};
//
struct sCluster
{
    sParticle particle[ 64 ];
    sCluster *next;
};
//
struct sEmitter
{
    sCluster *firstCluster;
    float age;
};

I also followed a similar strategy to that mentioned above since a cluster is not de-allocated when all the particles it contains are dead, it merely gets removed and added to a free cluster list instead. When a emitter runs out of free particles and it needs to create new ones, is finds a cluster from the free list and adds it to its own cluster list instead which provides an immediate gain of more free particles giving it some headroom. If the free list is empty then we have to bite the bullet and just allocate a new cluster, or perhaps several at once. Emitter objects are small and created rarely, so for the time being I simple allocate them as they are needed, however they could just as easily have their own free emitter list.

I wanted to retain as much flexibility as possible for the effects that could be created so I also chose to implement callback functions into the main events of the particle system so that custom code could be plugged in to achieve different effects. There are really two main places where it is desirable to change the functionality, being the specifics of the creation of a particle, and the main update routine of each emitter, as it advances all the particles that it owns.

The emitter class becomes something like this now:

//
struct sEmitter
{
    // called whenever a particle is created
    void (*onCreate)( sEmitter *e, sParticle *p );
    // called once each frame to advance the particles of this emitter
    void (*onTick )( sEmitter *e );
    // particle list
    sCluster *firstCluster;
    // emitter details
    float x, y;
    float age;
};

In practice there were a few points that made the implementation not quite as simple as this, but at a high level this strategy works very nicely for me. I did in fact take this strategy much farther then this, but after using it in the engine, this is actually all that really needs to be implemented for a nice, flexible particle system.