Sorting sprites based on Z index

Question

I am working on a 2D game engine in C# using OpenGL. I am trying to find a collection to satisfy my needs for sprite ordering, and I can't seem to find the combination of performance and functionality.

The following is the criteria I am after:

The ability to be iterated over in order according to "Z" value, which may change for any sprite at any time
Possible for many sprites to be added/removed within a single frame, so sorting each time a value was added/removed will have large performance impact without the correct implementation
Insertion/removal speed is much lower priority than access speed during enumeration
Have no need for indexing
Only unique values, but with the correct collection, I can manage that manually if the base collection does not implement it, as I do in the example

Currently, this is the best I could come up with. (I removed all the interface implementations for clarity, leaving only the important stuff)

    public class SpriteBatch : ICollection<IRenderable>
{
    private readonly Dictionary<uint, IRenderable> _dict;
    private readonly List<uint> _keys;
    private bool _needSort;

    public SpriteBatch()
    {
        _dict = new Dictionary<uint, IRenderable>();
        _keys = new List<uint>();
        _needSort = false;
    }

    public void Add(IRenderable renderable)
    {
        if (renderable == null)
            throw new ArgumentNullException(nameof(renderable), "Item cannot be undefined.");
        if (_dict.ContainsKey(renderable.Id))
            return;
        _needSort = true;
        renderable.Disposed += (sender, args) => Remove(renderable);
        renderable.ZChanged += (sender, args) => _needSort = true;
        _keys.Add(renderable.Id);
        _dict.Add(renderable.Id, renderable);
    }

    public bool Remove(IRenderable renderable)
    {
        if (renderable == null)
            return false;
        _dict.Remove(renderable.Id);
        return _keys.Remove(renderable.Id);
    }

    public IEnumerator<IRenderable> GetEnumerator()
    {
        if (_needSort)
            _keys.Sort((a, b) => _dict[a].Z.CompareTo(_dict[b].Z));
        foreach (var key in _keys)
            yield return _dict[key];
    }
}

Was curious if anyone else had a better approach, or what the "standard" tried-and-true way of doing this is?

Use Depth Buffer to do the sorting for you - for essentially free - it will be massively faster. Sorting sprites on CPU only makes sense for the sprites which have order-dependent blending going on — JBeurer
– JBeurer, Commented Jun 18, 2018 at 22:22
As far as I am aware, this will largely complicate alpha blending, which nearly every sprite on each layer requires. Correct me if I am wrong, my first though was using the depth buffer for its obvious simplicity, but everything I have read indicates the hell it is going to play on blending and the frag shader, which each sprite may have individual settings, not just each layer. Currently each sprite has its individual shader settings, and each "layer" or "viewport" does as well, which is rendered to its own buffer. — ForeverZer0
– ForeverZer0, Commented Jun 19, 2018 at 0:49

MrCranky · Accepted Answer · 2018-06-07 08:24:54Z

Deferred sort (lazy so it only sorts at the last moment before the sorted values are needed) as you've done is the typical approach I've used in the past, so I'd say your current solution is pretty good.

Depending on your insert/remove demographics (i.e. the ratio of inserts / deletions to items that stay the same each frame), you may get slightly higher performance if you maintain a separate collection of new keys instead of tacking them onto the end of the sorted list. Then you can sort those keys on insert, and then use multi-way/k-way merging to combine them with the existing sorted collection. That way your sort should be able to avoid having to check all the existing items are still in the right place, instead it just has to find the right spot for each of the new items. But that will start to break down, as the ratio of insertions to existing sorted items rises, plus it means that to handle removes you have to traverse both main and new collections.

I do like the idea of a separate list for new keys, that is a clever and easy to implement, something that I didn't think of. For most cases, the number of sprites should not be too large. My main concern was that I was implementing a weather system, but honestly, I would be stupid to not just simply use a shader for that. Or at the very least make a separate type that doesn't worry about sorting for high volume stuff like particle emitters. Thanks for the advice, greatly appreciated. — ForeverZer0
– ForeverZer0, Commented Jun 7, 2018 at 10:48

Stack Exchange Network

Sorting sprites based on Z index

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Sorting sprites based on Z index

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions