Smoke particle system

Question

Please note that I'm working on a game on Windows Phone 8 using Monogame. The game is fine (60 FPS) all the time, except when the particle system is activated. This is just a smoke particle system that begins to emit when the player jumps and stop to emit as the player is at "0" y velocity after the jump. When this particle system is activated it goes down to 20-30 FPS, which is very frustrating.

I watched my game with a profiler and it says that the bottleneck is here at the particle system, in particular with Update/Draw functions.

What can I do to improve it?

The particle

public class Particle : IDisposable
{
    public Texture2D texture_ { get; set; } 
    public Vector2 position_ { get; set; }  
    public Vector2 velocity_ { get; set; }

    public float angle_ { get; set; }
    public float angular_velocity_ { get; set; }

    public Color color_ { get; set; }            
    public float scale_ { get; set; }
    // The 'time to live' of the particle
    public int TTL { get; set; }

    private Rectangle source_rectangle_;
    private Vector2 origin_;

    public Particle(Texture2D texture, Vector2 position, Vector2 velocity,
        float angle, float angularVelocity, Color color, float size, int ttl)
    {
        texture_ = texture;
        position_ = position;
        velocity_ = velocity;
        angle_ = angle;
        angular_velocity_ = angularVelocity;
        color_ = color;
        scale_ = size;
        TTL = ttl;

        source_rectangle_ = new Rectangle(0, 0, texture_.Width, texture_.Height);
        origin_ = new Vector2(texture_.Width / 2, texture_.Height / 2);
    }

    public void Dispose()
    {
    }

    public void Update(GameTime gameTime)
    {
        float elapsed = (float)gameTime.ElapsedGameTime.TotalSeconds;

        --TTL;
        position_ += velocity_ * elapsed;
        angle_ += angular_velocity_ * elapsed;
    }

    public void Draw(SpriteBatch spriteBatch)
    {
        spriteBatch.Draw(
            texture_,
            position_,
            source_rectangle_,
            color_,
            angle_,
            origin_,
            scale_,
            SpriteEffects.None,
            0f);
    }
}

The particle emitter

public class ParticleEngine : IDisposable
{
    private static Random random_;
    private Vector2 emitter_location_ = Vector2.Zero;
    private LinkedList<Particle> particles_;
    private LinkedList<Particle> fading_particles_;
    private List<Texture2D> active_textures_;

    private int spread_factor_ = 160;
    private int density_ = 5;

    private bool enabled_ = true;

    private Color[] list_of_colors_ = new Color[] { 
        new Color(111, 86, 41) * 0.8f,
        new Color(65, 44, 32) * 0.8f,
        Color.LawnGreen * 0.8f,
        Color.Yellow * 0.8f
        };

    public ParticleEngine(List<Texture2D> textures, Vector2 location)
    {
        random_ = GameManager.random_;
        emitter_location_ = location;
        this.active_textures_ = textures;
        this.particles_ = new LinkedList<Particle>();
        this.fading_particles_ = new LinkedList<Particle>();

        active_textures_ = Loader.scoregge_;
    }

    public void Dispose()
    {
        for (LinkedListNode<Particle> p = particles_.Last; p != particles_.First; p = p.Previous)
            p.Value.Dispose();

        for (LinkedListNode<Particle> p = fading_particles_.Last; p != fading_particles_.First; p = p.Previous)
            p.Value.Dispose();
    }

    public bool Enabled
    {
        get { return enabled_; }
    }

    public Vector2 EmitterLocation
    {
        get { return emitter_location_; }
        set
        {
            enabled_ = true;
            emitter_location_ = value;
        }
    }

    private Particle GenerateNewParticle()
    {
        Texture2D texture = active_textures_[random_.Next(active_textures_.Count)];
        Vector2 position = emitter_location_;
        Vector2 velocity = new Vector2(
                 (float)(random_.NextDouble() * spread_factor_),
                 (float)(random_.NextDouble() * spread_factor_));
        float angle = 0;
        float angularVelocity = (float)(random_.NextDouble() * 5);
        Color color = list_of_colors_[random_.Next(list_of_colors_.Count())];
        float size = (float)random_.NextDouble();
        int ttl = 15 + random_.Next(30);

        return new Particle(texture, position, velocity, angle, angularVelocity, color, size, ttl);
    }

    public void StopEmitting()
    {
        LinkedListNode<Particle> p = particles_.Last;
        while (p != null)
        {
            fading_particles_.AddLast(p.Value);
            particles_.RemoveLast();

            p = p.Previous;
        }

        enabled_ = false;
    }

    public void Update(GameTime gameTime)
    {
        if (enabled_)
        {
            for (int i = 0; i < density_; i++)
            {
                particles_.AddLast(GenerateNewParticle());
            }
        }

        LinkedListNode<Particle> p = particles_.Last;
        while (p != null)
        {
            LinkedListNode<Particle> p_prev = p.Previous;            
            Particle particle = p.Value;

            particle.Update(gameTime);

            if (particle.TTL <= 0)
            {
                fading_particles_.AddLast(particle);
                particles_.Remove(p);
            }

            p = p_prev;
        }

        p = fading_particles_.Last;
        while (p != null)
        {
            LinkedListNode<Particle> p_prev = p.Previous;
            Particle particle = p.Value;

            particle.Update(gameTime);
            particle.color_ *= 0.98f;

            if (particle.color_.A <= 0.0f)
            {
                fading_particles_.Remove(p);
            }

            p = p_prev;
        }
    }

    public void Draw(SpriteBatch spriteBatch)
    {
        LinkedListNode<Particle> p = particles_.Last;
        while (p != null)
        {
            p.Value.Draw(spriteBatch);
            p = p.Previous;
        }

        p = fading_particles_.Last;
        while (p != null)
        {
            p.Value.Draw(spriteBatch);
            p = p.Previous;
        }
    }
}

Answer 1

I believe the root of the problem is using Linked Lists. Have a read of this discussion about why in C#, the general case is List<T> will outperform LinkedList<T> most of the time. https://stackoverflow.com/questions/5983059/why-is-a-linkedlist-generally-slower-than-a-list

In particular, the Update method is calling AddLast a lot. This is not very efficient when using linked lists. Calling Remove is probably also quite slow.

SebastianStehle is right that there are lots of little micro-optimizations you can do to improve the performance, but I think (without profiling the code myself) you can get the biggest bang for buck by changing the LinkedList's to List's, or even better, fixed sized arrays.

The next thing probably is to limit the number of memory allocations (calling new) for each particle. There are a few ways to do this. One simple idea is to use flags on the particles instead of adding and removing them from the lists. Perhaps IsActive and IsFading in your case.

Oh, one last thing.. I just noticed this line:

Texture2D texture = active_textures_[random_.Next(active_textures_.Count)];

Be very careful that you're not switching textures a lot. In modern graphics hardware, switching textures is one of the biggest bottlenecks. If you need to support different shaped particles consider storing them in a texture atlas.

Good luck and happy coding :)

Answer 2

I don't have a solution, but here are some tips:

1. Measuring the difference between structs and classes for particles can make a difference.
2. Do not use properties for particles; use simple fields.
3. Calculate values once (e.g. pass totalseconds to your particles, not gametime).
4. Use object pooling for your particles; don't create them on the fly.
5. Decide how many particles you want to support and use simple structures like arrays.
6. Draw the particles manually without spritebatch.
7. Calculate everything you need at the beginning; don't create new objects.

Some of the tips are micro-optimizations and are totally useless in other scenarios, but they are very helpful in particle systems.