2k14 : The Game

[ previous ] [ archive ] [ about ] [ todo ] [ sponsor ] [ next ]

Particle systems - part III

11 Jun 2016

One final post about the particle system implementation, before I’m going to move on to other stuff. Let’s make it quick this time ;-)

Improved particle attribute storage

I’ve optimized the way per-particle attribute data is stored, to further reduce the storage and processing overhead, for improved flexibility, and to be able to toss out quite a few lines of code that were borderline boilerplate.

Previously, particle data was stored in a simple C-style structure-of-arrays, with hardcoded pointers for each of the particle attributes required to implement all known particle effects. This eventually lead to the following data structure:

typedef struct K14ParticleData
{
  unsigned int maxParticles;
  unsigned int currentParticles;
   
  GLKVector2 *positions;
  float *angles;
  GLKVector2 *velocities;
  float *angularVelocities;
  float *lifetimes;
  float *decayRates;
  float *sizes;
  float *phases;
  float *amplitudes;
  float *timestamps;
  GLKVector4 *colors;
  void **box2DBodies;
   
} K14ParticleData;

The advantage of a simple structure like this is that it makes access to per-particle attributes very explicit. Need to generate particle positions? Just write to the positions . Need the color of particle i? Read colors[i]. The locations of all particle attribute arrays are known at compile time, so there are basically no indirections, and no administration is needed to track the location and size of any particle attribute: they follow directly from the layout of the particle data structure. The explicit particle attribute structure also has some notable downsides though:

  1. The set of supported particle attributes is basically fixed at compile time, adding a new particle attribute requires adding an additional field to the particle data structure.
  2. The structure always contains all known particle attributes, even if they are not used by some particle effects, wasting memory and increasing the overhead of copying particle attribute data.
  3. Each particle attribute array is allocated individually, which means particle data is not consecutive in memory, decreasing data locality and possibly reducing cache performance.
  4. Operations on the particle data such as allocating, copying and deleting attributes, need to be hard-coded and repeated for each attribute array.

For particle effects that always use the same set of particle attributes, the above downsides are irrelevant. For a flexible particle system that supports many configurations of generators, updaters and particle attributes, these are valid concerns though. The straightforward C-style particle data structure started to bother me when I added per-particle phase, amplitude and timestamp attributes to the particle data structure, to support pulsating particle sizes for the respawn effect. These attributes are not used by the explosion effect, so why allocate memory and copy them around?

None of the disadvantages mentioned above are impossible to overcome without drastically changing the particle data structure. For example, I briefly thought about storing attributes that are very specific to some effects in a set of custom attributes that particles could use and interpret any way they see fit. This has its own set of problems though. What type would these custom properties have, for instance? Do we add one for floats, one for 2D vectors, one for 4D vectors, etc? And how many different custom properties do we allow for a single particle effect? The memory concerns could be worked around by allocating one big block of memory and setting up pointers into it for each attribute, but how do we know what attributes an effect will use? Do we allocate a memory block large enough to hold all of them, and copy around unused memory?

Instead of trying to come up with answers for all these questions, I decided to deprecate the C-style particle data structure completely, and replace it by a flat block of memory together with a simple high-level interface around it that provides facilities to register and allocate particle attributes. Every particle attribute is represented by a unique id together with the data size of the attribute for a single particle. The particle attributes and data sizes are currently hard-coded using an enumeration type and a fixed-size ‘attribute info’ table, but they could easily be made dynamic in the future. When creating a particle effect, the set of supported particle attributes is passed to the K14ParticleEffect class, which will create a new K14ParticleData class that will allocate a single block of memory exactly big enough to hold all attributes for the maximum number of particles for the system, and setup pointers to each particle attribute. The interface of the K14ParticleData class is actually very simple:

/** 
 Particle data container
 
 This provides a somewhat higher-level abstraction around the flat memory block 
 used to store particle attributes.
*/
@interface K14ParticleData : NSObject<NSCopying>

/** Maximum number of particles for the system */
@property(readonly, nonatomic) unsigned int maxParticles;
/** Current number of live particles */
@property(readonly, nonatomic) unsigned int currentParticles;
/** Particle attributes used by the particle system */
@property(readonly, nonatomic) NSArray *attributes;

// Initializer
-(instancetype) initWithMaxParticles: (unsigned int) maxParticles attributes: (NSArray *) attributes;

// Getting attribute data
-(void *) particleDataForAttribute: (K14ParticleAttribute) attribute;

// Allocating and killing particles
-(unsigned int) allocateParticles: (unsigned int) count;
-(void) killParticle: (unsigned int) particle;

@end

Particle generators and updaters retrieve pointers to the particle attribute data using the particleDataForAttribute method, which for the K14SizeParticleGenerator looks like this, for example:

-(void) generateParticles: (K14ParticleData *) particles
                    first: (unsigned int) first
                    count: (unsigned int) count
               sequenceId: (unsigned int) sequenceId
{
  float *particle_sizes = (float *) [particles particleDataForAttribute:K14ParticleAttributeSize];

  for (unsigned int i = first; i < (first + count); i++)
  {
    particle_sizes[i] = randBetween(_minSize, _maxSize);
  }
}

Allocating and killing particles works just like before: because particle attributes for live particles are packed tightly at the front of their attribute arrays, ‘allocating’ a particle simply means increasing the currentParticles field and initializing the attributes of the particle at the end of the array, while killing a particle means copying each attribute of the last live particle into the location of the dead particle and decreasing currentParticles. The allocateParticles and killParticle methods implement these operations. To efficiently swap particle attributes, which have variable sizes, I use a simple switch statement to directly copy particle attributes with data sizes of 1, 2, 4 or 8 bytes. Larger attribute sizes are copied using memcpy:

-(void) killParticle: (unsigned int) particle
{
  if (particle < _currentParticles)
  {
    if (_currentParticles > 1)
    {
      unsigned int last = _currentParticles - 1;
      
      for (NSValue *attribute in _attributes)
      {
        K14ParticleAttributeInfo *attribute_info = _attributeTable[attribute];
        
        unsigned int attribute_size = attribute_info.size;
        void *attribute_data = _particleData + attribute_info.offset;
        
        switch (attribute_size)
        {
          case 1:
            *((uint8_t *) attribute_data + particle) = *((uint8_t *) attribute_data + last);
            break;
            
          case 2:
            *((uint16_t *) attribute_data + particle) = *((uint16_t *) attribute_data + last);
            break;
          
          case 4:
            *((uint32_t *) attribute_data + particle) = *((uint32_t *) attribute_data + last);
            break;
            
          case 8:
            *((uint64_t *) attribute_data + particle) = *((uint64_t *) attribute_data + last);
            break;
            
          default:
          {
            void *dead_data = _particleData + attribute_info.offset + particle * attribute_size;
            void *last_data = _particleData + attribute_info.offset + last * attribute_size;
            
            memcpy(last_data, dead_data, attribute_size);
            
            break;
          }
        }
      }
    }
    
    self.currentParticles--;
  }
}

Adding all this together, we now have all of the benefits of a flat, tightly packed array of particle data, without having to sacrifice memory for unused attributes or the overhead of having to copy around each individual attribute array or polluting the cache because particle attributes are allocated all over the heap. Copying the K14ParticleData structure, which is done when creating a K14ParticleRenderCommand for a particle system, is done using a single memcpy call.

Starfields

Mostly as a tool to test the intended flexibility of the particle system implementation I added a simple starfield particle effect that can be created from the Lua planet script to draw some variable-sized dots that fade in-out at random locations. The original game had something similar. There’s not much more to say about the effect. I basically added a ‘rectangular area position generator’ that scatters particles emitted by a burst emitter, and an updater that will map particle lifetimes to the alpha component of the particle color using a sinusoidal function, to create the fade-in/fade-out effect. The Lua code to kick off the particle effect, and the K14ParticleSystem setup code look somewhat like this:

Lua code

-- Initialize planet
function Planet0:init()

  -- ...

  -- Create starfield
  local starfield_parameters = {
    type=Game.ParticleSystemType["STARFIELD"],
    numParticles=40,
    origin={ x=0, y=15 },
    extent={ width=40, height=15 },
    minSize=0.05,
    maxSize=0.1,
    minTime=8,
    maxTime=20,
    burst=6, 
    pulse=2,
    color={ r=0.5, g=0.5, b=0.9, a=1 },
  }

  self:particleEffect("starfield", starfield_parameters)

  -- ...

end

Objective-C code

NSArray *generators = @[
  [K14RectangularPositionParticleGenerator generatorWithOrigin:[starfield_parameters[@"origin"] CGPointValue]
                                                        extent:[starfield_parameters[@"extent"] CGSizeValue]],
  
  [K14RealAttributeParticleGenerator generatorWithAttribute:K14ParticleAttributeSize
                                                   minValue:[starfield_parameters[@"minSize"] floatValue]
                                                   maxValue:[starfield_parameters[@"maxSize"] floatValue]],
  
  [K14RealAttributeParticleGenerator generatorWithAttribute:K14ParticleAttributeDecayRate
                                                   minValue:1.0f / max_time
                                                   maxValue:1.0f / min_time],
  
  [K14ColorParticleGenerator generatorWithColor:starfield_parameters[@"color"]],
];

K14BurstParticleEmitter *starfield_emitter = 
  [K14BurstParticleEmitter emitterWithGenerators:generators
                                    maxParticles:0
                                           burst:[starfield_parameters[@"burst"] floatValue]
                                           pulse:[starfield_parameters[@"pulse"] floatValue]];

NSArray *updaters = @[ [K14StarfieldParticleUpdater new] ];

particle_system = [[K14ParticleSystem alloc] initWithEmitter:starfield_emitter
                                                    updaters:updaters
                                                maxParticles:[starfield_parameters[@"numParticles"] intValue]
                                                  attributes:nil];

Video

Not much new to show except for the starfield effect. It’s not particularly impressive to look at right now, but I’ll include a video anyway ;-)

Next steps

In its current form I feel confident this particle system implementation could scale all the way up to the point where you would want to move the whole shebang to the GPU anyway. Maybe I’ll try to stress the implementation a little to create some nice-looking smoke or fire effect at some point. I also still need to add support for textured particles, for example for the star field. And finally, if it ever makes sense from a performance point of view, I might implement some kind of buffered or copy-on-write particle data to eliminate copying particle data altogether. But for the moment, I feel I’ve sufficiently scratched my ‘efficient particle system’ itch ;-)

So instead I will try to fix and extend some of the fundamental gameplay logic: picking up the orb, leaving the planet atmosphere, refueling, reactor self-destruct, etc. Some of these things broke along the way when refactoring the scripting and serialization interfaces, or were never implemented at all. Maybe now is a good time to focus on how the game will actually play, for a while.