Building An Optimised Particle System In MonoGame

I’ve spent the last few days optimising the performance of ‘Jetboard Joust’ and one of the key components of this has been the particle system which is integral to the game’s visual style.

Over the course of doing this I’ve had to think a lot about the way my particle system is designed and have ended up changing it an awful lot to get the most out of performance and usability.

There are a bunch of tutorials on how to build a simple particle system out there, some of them very good, but none of them approach things in quite the way I did so I thought it would be worth sharing where I ended up. As my code is quite tied in to other aspects of my gaming APIs it’s difficult to share the source itself so this post will focus on the overall design and approach rather than the specific implementation. I welcome feedback on things I could do better and other optimisation suggestions. First some general tips…

Avoid Garbage – Recycle
Particle systems generate a lot of objects and memory allocation and deallocation is a very performance-intensive task, particularly when there’s a garbage collector involved as there is in C#. Therefore I allocate as many particle objects as I think I’m going to need at startup and reuse them rather than throwing them away. I use linked lists to manage a list of unused/used particle and emitter objects. Linked lists are much more efficient than array-based lists when allocating additional capacity and inserting and removing objects from the middle of the list making them ideal for this type of task. I use my own simple linked list implementation with each particle and emitter having a pointer to the previous and next one in the list but the generic C# LinkedList implementation is probably just as efficient and a lot easier to debug.

Don’t Switch Textures
Keep all your particles as part of the same texture atlas/sprite sheet so they can be rendered in one batch by the GPU. Switching textures is very performance intensive. If you are using a ‘layered’ 2D drawing approach make sure all your particles are drawn at once, ie you don’t have other sprites intermingled between them which would mean another texture needs to be passed to the GPU.

Pre-Calculate Tweens
If you are using relatively expensive tween based algorithms (particularly ones based on trigonometry) pre-calculate these so they are not having to be calculated per particle per frame. I explain how I manage this in the overall design description as it is not entire straightforward. Generally using tweens looks a lot better than simple linear transforms – I intend to share some tweening code in a later post.

Cull Where Possible
If you are likely to have a lot of offscreen particles don’t pass these to the GPU to be drawn each frame but don’t make an intersection check for each particle. Again, finding the most efficient way to do this is not straightforward but I explain my approach in the design description. Culling ‘invisible’ particles before they are passed to the GPU will also likely mean you can avoid unnecessary calculations for tweens on scale/opacity etc.

Scroll down for a breakdown of the classes I use and design approach and please get in touch via Twitter with any questions or comments…

mockup_3x
Constructivist Northern Lights

mockup_3x
Fun With Scaling And Rotation
ParticleEmitterState
This class represents a ‘snapshot’ of the parameters that apply to any particle emitter. Many tutorials bundle these parameters in with the emitter itself so don’t have a separate ‘state’ object. I find the separate state object makes it much easier both to to manage multiple emitters that have the same appearance and to recycle emitter objects.
namespace com.bitbull.particles
{

	public class ParticleEmitterState
	{
		/*
		 Sets up the state object with some sensible default values 
		 */
		public ParticleEmitterState();

		/*
		 Called once the first time MaxParticleFrames, ParticleFrames or TweenValues is requested.
		
		 This method allocates a float[] the size of MaxParticleFrames and pre-calculates a tween value from 1.0
		 to 0.0 for each frame. These tween values could be thought of as the 'energy' of the particle and are often
		 used to calculate a particle's opacity, rotation or scale.
		
		 An exception will be thrown if either ParticleDuration or ParticleDurationDeviation are set after this has
		 been called making these the only properties that are more-or-less 'immutable' once a state has been set up.
		 */
		private void Initialize();
		
		/*
		Returns a float[] the size of MaxParticleFrames containing a tween value from 1.0 to 0.0 for each frame. These 
		tween values could be thought of as the 'energy' of the particle and are often used to calculate a particle's
		opacity, rotation or scale.
		
		If a TweenAlgorithm has not been set this method returns null and tweening is ignored for this particle.
		
		Read only.
		*/
		public float[] TweenValues;

		/*
		The maximum lifespan of a particle in frames. Read only.
		*/
		public int MaxParticleFrames;
		
		/*
		The minimum lifespan of a particle in frames. Read only.
		*/
		public int ParticleFrames;

		#region particleproperties

		/*
		 Start velocity of particles
		 */
		public float Velocity;
		
		/*
		 Amount of random deviation from start velocity per particle.
		 Particle velocity will run from Velocity-VelocityDeviation/2 to velocity+VelocityDeviation/2 
		 */
		public float VelocityDeviation;

		/*
		 Amount of spawn deviation from emitter centre along the x-axis.
		 Particles will spawn from 0-SpawnDeviationX/2 to 0+SpawnDeviationX/2 
		 */
		public float SpawnDeviationX;
		
		/*
		 Amount of spawn deviation from emitter centre along the y-axis.
		 Particles will spawn from 0-SpawnDeviationY/2 to 0+SpawnDeviationY/2 
		 */
		public float SpawnDeviationX;

		/*
		 Distance of particle from emitter centre on the x-axis before deviation is applied
		 */
		public float SpawnRadiusX;

		/*
		 Distance of particle from emitter centre on the y-axis before deviation is applied
		 */
		public float SpawnRadiusY;

		/*
		 Whether to reverse velocity (implode) on the x axis 
		 */
		public bool ReverseVelocityX;

		/*
		 Whether to reverse velocity (implode) on the y axis
		 */
		public bool ReverseVelocityY;

		/*
		 Start angle of particle spread.
		 */
		public float StartAngle;

		/*
		 End angle of particle spread.
		 */
		public float StopAngle;

		/*
		 Colour of particle
		 */
		public Color Tint;

		/*
		 Some kind of representation of the texture that is to be drawn for the particle - will 
		 most likely be an encapsulation of an Image and a source rect for the area of the image
		 that is to be drawn. 
		 */
		public Drawable Texture;

		/*
		 Overall velocity of particle is multiplied by this per frame. In most cases particles will
		 deccelerate as they lose energy so this will be less than 1.0. 
		 */
		public float Acceleration;

		/*
		 Added to horizontal velocity of particle per frame - single unit vector component between 0 and 1
		
		 In most particle systems this will be zero as gravity tends to pull straight down! 
		 */
		public float GravityX;

		/*
		 Added to vertical velocity of particle per frame - single unit vector component between 0 and 1

		 In most particle systems this will be 1.0 as gravity tends to pull straight down!
		 */
		public float GravityY;

		/*
 		 Amount of gravity added per frame, effectively the 'velocity' of the vector [GravityX,GravityY]
		 */
		public float Gravity;

		/*
		 Lifespan of each individual particle.
		 Trying to set this property once Initialize() has been called will throw an exception.
		 */
		public TimeSpan ParticleDuration;

		/*
		Random variance in lifespan of each individual particle.
		Particles will live from from 0-ParticleDuration/2 to 0+ParticleDuration/2 
		*/
		public TimeSpan ParticleDurationDeviation;
		
		/*
		Some kind of representation of a tweening algorithm to be used for particle 'energy'. 
		*/
		public Tween.TweenAlgorithm TweenAlgorithm;

		/*
		Base opacity of particle.
		*/
		public float Opacity;
		
		/*
		Random variance in opacity of each individual particle.
		*/
		public float OpacityDeviation;
		
		/*
		Change in particle's opacity based on the 'energy' of the particle.
		*/
		public float OpacityTweenAmount;
		
		/*
		Base rotation of particle.
		*/
		public float Rotation;
		
		/*
		Random variance in rotation of each individual particle.
		*/
		public float RotationDeviation;
		
		/*
		Change in particle's rotation based on the 'energy' of the particle.
		*/
		public float RotationTweenAmount;

		/*
		Base scale of particle.
		*/
		public float Scale;
		
		/*
		Random variance in scale of each individual particle.
		*/
		public float ScaleDeviation;
		
		/*
		Change in particle's scale based on the 'energy' of the particle.
		*/
		public float ScaleTweenAmount;
	}

}

Particle
This class represents an individual particle. Typically you will end up with thousands of these being active at any one time so it’s very important that any code executed in the Update() and Draw() methods is as efficient as possible.

Most particle properties are set by the emitter and therefore ‘baked in’ when a particle is emitted, however I maintain a pointer back from each individual particle to a ParticleState object for things like gravity and the array of tween values.

To allow for the fact that there is deviation in the amount of frames each particle lives for I maintain a float value per particle for a ‘tween frame’ and the amount this ‘tween frame’ is incremented per frame (State.MaxParticleFrames/Particle.DurationFrames). At each Draw() call the ‘tween frame’ float is casted to an int so that the appropriate value can be retrieved from State.TweenValues. I don’t like doing this cast every time but it’s the only method I can think of that ensures each particle can move smoothly from maximum to minimum pre-calculated tween values whatever its duration.

using System;

using com.bitbull.meat;
using com.maturus.multipacks.generic;
using com.maturus.genericarcade;

namespace com.bitbull.particles
{
	public class Particle
	{
		/*
		Creates a new particle
		*/
		internal Particle();
		
		/*
		Sets this particle moving based on the supplied ParticleEmitterState
		*/
		internal void Activate( ParticleEmitterState state );
		
		/*
		Draws the particle on the specified graphics object relative to the specified x and y values.
		
		This method should also perform any 'per frame' calculations that can be skipped if the particle
		is offscreen and therefore doesn't need to to be drawn, for example scaling an opacity tweening.  
		*/
		public void draw( float x, float y, Graphics g );

		/*
		Updates the X and Y location of the particle based on its velocity and state gravity.
		
		Increments a frame counter and returns false if the particle has reached its allocated lifespan.
		
		Any 'per frame' calculations that need to be carried out whether or not the particle is 
		visible should also be carried out here, for example increasing or decreasing velocity based
		on acceleration. 
		*/
		internal bool update();
		
		/*
		X Location of particle
		*/
		public float X;
		
		/*
		Y Location of particle
		*/
		public float Y;
		
		/*
		Horizontal velocity component of particle (single unit vector) 
		*/
		public float VX;
		
		/*
		Vertical velocity component of particle (single unit vector) 
		*/
		public float VY;
		
		/*
		Current velocity of particle (ie length of vector [VX,VY]) 
		*/
		public float Velocity;
		
		/*
		Frames elapsed since particle was emitted
		*/
		public int Frame;
		
		/*
		Particle lifespan in frames
		*/
		public int DurationFrames;

		/*
		Initial scale of particle
		*/
		public float Scale;
		
		/*
		Initial opacity of particle
		*/
		public float Opacity;
		
		/*
		Initial rotation of particle
		*/
		public float Rotation;
	}
	
}

ParticleEmitter
This class represents something that emits particles according to a particular ParticleEmitterState. Emitters are managed by a ParticleSystem and each emitter maintains a pointer back to its ‘parent’ ParticleSystem as well as a linked list of particles emitted that are still active.

Each emitter can be set to emit a certain amount of particles for a certain amount of frames and to do this for a number of iterations with a defined pause between each iteration.

An emitter remains active until all the particles it has emitted have expired.

Each emitter has it’s own onscreen location relative to which its particles are drawn – this enables emitters to track another sprite’s movement which is often very useful.

using System;

namespace com.bitbull.particles
{
	public class ParticleEmitter
	{
		/*
		Creates a new particle emitter
		*/
		public ParticleEmitter();
		
		/*
		Sets the parent ParticleSystem for the emitter and resets location
		*/
		public void Activate( ParticleSystem p );
		
		/*
		Forces the emitter to deactivate all currently active particles, set its
		state to non-permanent, and call DeactivateEmitter() on the parent ParticleSystem
		*/
		public void Flush();
		
		/*
		Iterates through and calls Update() on every active particle.
		
		If a particle's Update() call returns false it is deactivated. 
		*/
		public void UpdateParticles ();
		
		/*
		Iterates through and calls Draw() on every active particle.
		
		Active particles are drawn relative to the emitter's own x,y location 
		*/
		public void DrawParticles ( float x, float y, Graphics g );
		
		/*
		Deactivates the supplied particle by removing it from the list of active 
		particles and adding it to the parent ParticleSystem's list of inactive particles
		*/
		public void DeactivateParticle( Particle p );

		/*
		Emits an individual particle based on the parameters in the supplied ParticleEmitterState.

		Particles are not instantiated here but retrieved from the list of inactive particles 
		in the parent ParticleSystem using ParticleSystem.RetrieveParticle()
		
		This method calculates initial x, y, scale, rotation and opacity values for the particle
		as well as the particle's duration in frames based on the 'deviation' parameters set in 
		the ParticleEmitterState.  
		*/
		public void EmitParticle( ParticleEmitterState state );

		/*
		Emits n_particles_per_frame particles for n_frames for n_iterations iterations with frames_pause
		frames pause between each iteration.
		*/
		public void EmitParticles( ParticleEmitterState state, int n_particles_per_frame, int n_frames, int n_iterations, int frames_pause  );

		/*
		Immediately emits the specified amount of particles 
		*/
		public void AddParticles( ParticleEmitterState state, int n );
		
		/*
		Calls UpdateParticles and emits as many particles as necessary this frame.
		
		If the list of active particles is empty and we have no more particles to emit and IsPermanent is
		false calls DeactivateEmitter() on the parent state.
		*/
		public void update();

		/*
		When set to true this emitter will not automatically be deactivated once all particles are emitted.
		*/
		public bool IsPermanent;

		/*
		 Origin of emitted particles on the x-axis
		 */
		public float OriginX;

		/*
		 Origin of emitted particles on the y-axis
		 */
		public float OriginY;

		/*
		Location of emitter on the x-axis
		
		This is different from OriginX in that all particles are drawn relative to LocationX whereas
		OriginX only specifies the location at which new particles appear
		*/
		public float LocationX;
		
		/*
		Location of emitter on the y-axis
		
		This is different from OriginY in that all particles are drawn relative to LocationY whereas
		OriginY only specifies the location at which new particles appear
		*/
		public float LocationY;

	}

}

ParticleSystem
This class is responsible for maintaining a linked list of inactive Particle objects as well as active and inactive ParticleEmitter objects.

The list of inactive Particle objects is static and thus shared across multiple ParticleSystems.

In many situations there is only the need for one ParticleSystem – however in games with large scrolling worlds a ParticleManager can be used which maintains several different ParticleSystem objects and ‘culls’ any that don’t need to be drawn to screen thus improving performance.

Another reason to maintain different ParticleSystems would be to manage the order in which different particle effects are drawn as there is no control of the draw order of ParticleEmitter objects within any one ParticleSystem.

using System;

namespace com.bitbull.particles
{
	public class ParticleSystem
	{
		/*
		The amount of inactive particles to be created at startup
		
		A count is maintained of how many particles are created - if the value set here
		exceeds this amount then additional particles are created as soon as the value
		is set.
		*/
		public static int InitialCapacity;
		
		/*
		Creates a particle and adds it to the list of inactive particles
		*/
		private static void CreateParticle();
		
		/*
		Creates a new particle system
		*/
		public ParticleSystem ();

		/*
		Iterates through and calls Flush() on all active ParticleEmitter objects
		*/
		public void Flush();
		
		/*
		Retrieves a ParticleEmitter object from the list of inactive emitters.
		
		If none are available a new one is created. 
		*/
		public ParticleEmitter RetrieveEmitter();
		
		/*
		Retrieves an emitter and then calls ParticleEmitter.EmitParticles() with the supplied parameters
		*/
		public void EmitParticles( ParticleEmitterState state, float x, float y, int n_particles, int n_frames, int n_iterations, int frames_pause );
		
		/*
		Immediately adds the specified number of particles at the specified location based on the supplied ParticleState
		*/
		public void AddParticles( ParticleEmitterState state, float x, float y, int n );
		
		/*
		Returns the supplied ParticleEmitter object to the list of inactive emitters 
		*/
		public void StashEmitter( ParticleEmitter emitter );

		/*
		Iterates through and calls Update() on all active emitters
		*/
		public override bool update();

		/*
		Iterates through and calls Draw() on all active emitters
		*/
		public override bool drawToScreen (float h, float v, Graphics g);
		
		/*
		Returns the specified particle to the list of inactive particles
		*/
		internal void StashParticle( Particle p );
		
		/*
		Retrieves a particle from the list of inactive particles - this method is only called by
		ParticleEmitter.EmitParticle() so, once retrieved, a particle is always added to the list
		of active particles in a ParticleEmitter. 
		
		If no inactive particles are available a new one is created.
		*/
		internal Particle RetrieveParticle();
	}
}

ParticleSystemManager
This class is used by games with a scrolling play area to manage offscreen culling of particles.

Maintaining a boundary rectangle for each ParticleEmitter would require numerous calculations per frame. Even though these would be relatively ‘cheap’ >< comparisons the amount of them required (potentially many thousands per frame) makes this an ineffective approach.

My solution is more 'fuzzy'. I split the overall play area into a grid of ParticleSystem objects. Each ParticleSystem is assigned an 'emit' rectangle (standard grid coordinates) and an 'overlap' rectangle. The 'overlap' rectangle is larger than the 'emit' rectangle by an amount specified programatically. This overlap needs to be at least as large as the maximum necessary draw radius of any ParticleEmitter so a little trial and error may be needed to find the ideal value

Any ParticleSystem whose 'overlap' rectangle doesn't intersect the screen area at draw time can be safely culled, potentially eliminating a huge amount of particles with one simple Rectangle.Intersects() call.

The only real drawback of this method (apart from the fact that it requires a little trial and error to set up) is that it's only really good for particle emitters that are stationary. In practice though I've found that either using ParticleSystemManager.AddParticles and/or having a separate ParticleSystem for moving emitters to work fine.

using System;

namespace com.bitbull.particles
{

	public class ParticleSystemManager
	{
		/*
		Creates a new ParticleSystem manager to cover the specified world Rectangle broken
		down into a separate ParticleSystem for each 'cell' and with the specified overlap
		between each cell.
		
		Overlap should be at least as much as the radius of the largest particle effect.
		*/
		public ParticleSystemManager( Rectangle world, int cols, int rows, float overlap );

		/*
		Calls AddParticles() on the ParticleSystem that contains the specified x and y values.
		*/
		public void AddParticles( ParticleEmitterState state, float x, float y, int n );
		
		/*
		Calls EmitParticles() on the ParticleSystem that contains the specified x and y values.
		*/
		public void EmitParticles ( ParticleEmitterState state, float x, float y, int n_particles, int n_frames);

		/*
		Iterates through and calls Update() on all ParticleSystems
		*/
		public override bool update ();
		
		/*
		Iterates through all particle systems and calls Draw() on the ones whose bounding 
		rectangle + overlap intersects the screen. 
		*/
		public override bool drawToScreen (float h, float v, Graphics g);

		/*
		Calls Flush() on all ParticleSystems
		*/
		public void Flush();

	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: