Sorting sprites based on Z index

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?

Answers 1

  • 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.


Related Questions