IsoSpriteSorting Improved

IsoSpriteSorting.cs

using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using Zenject;

public enum IsoSortType {
    Point,
    Line
}

/// <summary>
/// Solves a variety of isometric sorting issues with a combination of point
/// and line sorting. Point sorting is similar to the traditional pivot point
/// sorting method. But for isometric games, it fails spectacularly in many
/// cases. For those cases, we rely on line sorting, that lets us declare a
/// range of sorting possibilities for each sprite. It's similar to the sorting
/// we'd achieve if the sprite were cut into tiles, but just done via maths.
///
/// For an explainer, see https://www.youtube.com/watch?v=yRZlVrinw9I.
/// Code courtesy of https://github.com/markv12/IsoSpriteSortingDemo.
/// </summary>
public class IsoSpriteSorting : MonoBehaviour, IComparable<IsoSpriteSorting>, ISerializationCallbackReceiver {
    public bool renderBelowAll;
    public IsoSortType sortType = IsoSortType.Point;
    public List<Vector3> sorterPositionOffsets;
    public Renderer[] renderersToSort;

    [NonSerialized]
    public bool registered = false;
    [NonSerialized]
    public bool forceSort;

    private List<Vector3> points = new List<Vector3>(4);
    private readonly List<IsoSpriteSorting> dependencies = new List<IsoSpriteSorting>(8);
    private Bounds2D bounds;

    [Inject]
    protected IsoSpriteSortingManager _manager;

    public List<Vector3> Points => points;
    public Bounds2D Bounds => bounds;

    public Vector3 AsPoint => sortType == IsoSortType.Line
        ? MedianVector(Points)
        : Points[0];

    public float SortingLineCenterHeight => sortType == IsoSortType.Line
        ? MedianY(Points)
        : throw new Exception("Sorting type is not line");

    public int SortingOrder {
        get {
            return renderersToSort.Length > 0
                ? renderersToSort[0].sortingOrder
                : 0;
        }
        set {
            foreach (var renderer in renderersToSort) {
                renderer.sortingOrder = value;
            }
        }
    }

    /// <summary>
    /// The list of sprites whose ordering influences this sprite's ordering.
    /// It's necessary for the topological sort to work. The sorting manager
    /// will update this list automatically.
    /// </summary>
    public List<IsoSpriteSorting> Dependencies => dependencies;

    protected Vector3 MedianVector(List<Vector3> vectors) => vectors.Aggregate(Vector3.zero, (acc, v) => acc + v) / vectors.Count;
    protected float MedianY(List<Vector3> vectors) => vectors.Sum(v => v.y) / vectors.Count;

    private void Start() {
        Setup();
    }

    protected void Update() {
        if (transform.hasChanged) {
            RefreshBounds();
            RefreshPoints();
            transform.hasChanged = false;
        }
    }

    private void OnDestroy() {
        Unregister();
    }

    public void Unregister() {
        _manager.UnregisterSprite(this);
    }

    public void Setup() {
        if (renderersToSort == null || renderersToSort.Length == 0) {
            renderersToSort = GetComponentsInChildren<Renderer>();
        }

        RefreshBounds();
        RefreshPoints();

        _manager.RegisterSprite(this);
    }

    public void OnBeforeSerialize() {
    }

    /// <summary>
    /// Add at least one point at the origin, which results in the same sorting
    /// as using the sprite pivot point.
    /// </summary>
    public void OnAfterDeserialize() {
        if (sorterPositionOffsets.Count == 0) {
            sorterPositionOffsets = new List<Vector3> { Vector3.zero };
        }
    }

    public int CompareTo(IsoSpriteSorting other) {
        return IsoSortComparisons.CompareIsoSorters(this, other);
    }

    private void RefreshBounds() {
        var groupBounds = renderersToSort[0].bounds;
        foreach (Renderer renderer in renderersToSort.Skip(1)) {
            groupBounds.Encapsulate(renderer.bounds);
        }
        bounds = new Bounds2D(groupBounds);
    }

    private void RefreshPoints() {
        points = sorterPositionOffsets
            .Select(p => p + transform.position)
            .ToList();
    }

    // Only for use in the editor
    public void InjectManager(IsoSpriteSortingManager manager) {
        _manager = manager;
    }
}

IsoSpriteSortingEditor.cs

#if UNITY_EDITOR
using UnityEditor;
using UnityEditor.SceneManagement;
using UnityEngine;
using UnityEngine.SceneManagement;

#pragma warning disable 618

[CustomEditor(typeof(IsoSpriteSorting))]
public class IsoSpriteSortingEditor : Editor {
    const float HANDLE_SIZE_FACTOR = 0.06f;

    public void OnSceneGUI() {
        var sorter = (IsoSpriteSorting)target;
        if (sorter.sorterPositionOffsets.Count == 0) return;

        switch (sorter.sortType) {
            case IsoSortType.Point:
                sorter.sorterPositionOffsets[0] = MoveHandleForIndex(sorter, 0);
                break;
            case IsoSortType.Line:
                DoLineHandles(sorter);
                break;
        }

        if (GUI.changed) {
            Undo.RecordObject(target, "Updated Sorting Offset");
            EditorUtility.SetDirty(target);
        }
    }

    protected void DoLineHandles(IsoSpriteSorting sorter) {
        for (var idx = 0; idx < sorter.sorterPositionOffsets.Count; idx++) {
            sorter.sorterPositionOffsets[idx] = MoveHandleForIndex(sorter, idx);
            if (idx > 0) {
                Handles.DrawLine(
                    sorter.transform.position + sorter.sorterPositionOffsets[idx - 1],
                    sorter.transform.position + sorter.sorterPositionOffsets[idx]
                );
            }
        }
    }

    protected Vector3 MoveHandleForIndex(IsoSpriteSorting sorter, int index) {
        return Handles.FreeMoveHandle(
            sorter.transform.position + sorter.sorterPositionOffsets[index],
            Quaternion.identity,
            HANDLE_SIZE_FACTOR * HandleUtility.GetHandleSize(sorter.transform.position),
            Vector3.zero,
            Handles.DotHandleCap
        ) - sorter.transform.position;
    }

    /// <summary>
    /// The sort manager is typically a singleton managed by Zenject,
    /// but in the editor we don't have that. Instead, we'll just make
    /// a temporary GameObject to hold the manager, perform the sorting,
    /// then delete it immediately after.
    /// </summary>
    public override void OnInspectorGUI() {
        DrawDefaultInspector();
        var self = (IsoSpriteSorting)target;

        if (GUILayout.Button("Sort Visible Scene")) {
            if (Application.isPlaying) {
                Debug.LogWarning("Cannot sort while in play mode");
                return;
            }

            var temporaryContainer = new GameObject();
            var manager = temporaryContainer.AddComponent<IsoSpriteSortingManager>();
            SortScene(manager);
            DestroyImmediate(temporaryContainer);
        }
    }

    /// <summary>
    /// While in the editor, we can't see changes to sprite sort order
    /// automatically, but we can use this GUI helper function to update it.
    /// </summary>
    private void SortScene(IsoSpriteSortingManager manager) {
        var isoSorters = FindObjectsOfType<IsoSpriteSorting>();
        foreach (var sorter in isoSorters) {
            sorter.InjectManager(manager);
            sorter.Setup();
        }

        manager.UpdateSorting();

        foreach (var sorter in isoSorters) {
            sorter.Unregister();
        }

        EditorSceneManager.MarkSceneDirty(SceneManager.GetActiveScene());
    }
}
#endif

IsoSpriteSortingManager.cs

using System.Collections.Generic;
using System.Linq;
using UnityEngine;

/// <summary>
/// Manages the list of IsoSpriteSorting objects, assigns dependencies based on
/// bounds checks, and performs a topological sort to determine their rendering
/// order.
/// </summary>
public class IsoSpriteSortingManager : MonoBehaviour {
    private readonly List<IsoSpriteSorting> backgroundSpriteList = new List<IsoSpriteSorting>(64);
    private readonly List<IsoSpriteSorting> actorSpriteList = new List<IsoSpriteSorting>(64);

    private List<IsoSpriteSorting> visibleActorSpriteList;

    protected void Update() {
        UpdateSorting();
    }

    /// <summary>
    /// Update the sort order with the following steps:
    ///
    /// 1. Filter the list of all sprites to only include those that are visible
    /// 2. Populate dependency lists for each sprite based on their bounds
    /// 3. Perform a topological sort on the sprites to determine their order
    /// </summary>
    public void UpdateSorting() {
        visibleActorSpriteList = FilterByVisibility(actorSpriteList);
        visibleActorSpriteList.ForEach(s => s.Dependencies.Clear());
        AddDependencies(visibleActorSpriteList);

        var sortedSprites = TopologicalSort.Sort(visibleActorSpriteList);
        SetSortOrderBasedOnListOrder(sortedSprites);
    }

    public void RegisterSprite(IsoSpriteSorting newSprite) {
        if (!newSprite.registered) {
            if (newSprite.renderBelowAll) {
                backgroundSpriteList.Add(newSprite);
                backgroundSpriteList.Sort();
                SetSortOrderNegative(backgroundSpriteList);
            } else {
                actorSpriteList.Add(newSprite);
            }
            newSprite.registered = true;
        }
    }

    public void UnregisterSprite(IsoSpriteSorting spriteToRemove) {
        if (spriteToRemove.registered) {
            if (spriteToRemove.renderBelowAll) {
                backgroundSpriteList.Remove(spriteToRemove);
            } else {
                actorSpriteList.Remove(spriteToRemove);
            }
            spriteToRemove.registered = false;
        }
    }

    /// <summary>
    /// A dependency between two sprites exists when they have overlapping
    /// bounds. We compare two overlapping sprites and add a dependency based
    /// on their sort order. This allows us to perform a topological sort.
    /// </summary>
    private void AddDependencies(List<IsoSpriteSorting> sprites) {
        var pairs = sprites.UniqueCombinations(2);
        foreach (var pair in pairs) {
            var left = pair.First();
            var right = pair.Last();

            if (left.Bounds.Intersects(right.Bounds)) {
                int compareResult = IsoSortComparisons.CompareIsoSorters(left, right);
                if (compareResult == 1) {
                    left.Dependencies.Add(right);
                } else if (compareResult == -1) {
                    right.Dependencies.Add(left);
                }
            }
        }
    }

    private void SetSortOrderBasedOnListOrder(List<IsoSpriteSorting> spriteList) {
        for (int order = 0; order < spriteList.Count; order++) {
            spriteList[order].SortingOrder = order;
        }
    }

    /// <summary>
    /// Start at a negative index and count forward to zero. This is for
    /// background sprites (aka, renderBelowAll).
    /// </summary>
    private void SetSortOrderNegative(List<IsoSpriteSorting> spriteList) {
        int startOrder = -spriteList.Count - 1;
        for (int i = 0; i < spriteList.Count; ++i) {
            spriteList[i].SortingOrder = startOrder + i;
        }
    }

    public List<IsoSpriteSorting> FilterByVisibility(List<IsoSpriteSorting> fullList) {
        var forcedSort = fullList.Where(s => s.forceSort).ToList();
        var visible = fullList.Where(s => s.renderersToSort.Any(r => r.isVisible)).ToList();
        forcedSort.ForEach(s => s.forceSort = false);
        return forcedSort.Concat(visible).ToList();
    }
}

public static class Combinations {
    public static IEnumerable<IEnumerable<T>> UniqueCombinations<T>(this IEnumerable<T> elements, int k) {
        return k == 0
            ? Enumerable.Repeat(Enumerable.Empty<T>(), 1)
            : elements.SelectMany((e, i) =>
                elements.Skip(i + 1)
                    .UniqueCombinations(k - 1)
                    .Select(c => Enumerable.Repeat(e, 1).Concat(c))
            );
    }
}

TopologicalSort.cs

using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public static class TopologicalSort {
    private static readonly HashSet<int> visited = new HashSet<int>();
    private static readonly Dictionary<int, bool> circularDepData = new Dictionary<int, bool>();
    private static readonly List<IsoSpriteSorting> circularDepStack = new List<IsoSpriteSorting>(64);

    /// <summary>
    /// Perform a topological sort on the given list of sprites.
    /// </summary>
    public static List<IsoSpriteSorting> Sort(IReadOnlyList<IsoSpriteSorting> sprites) {
        var workingCopy = new List<IsoSpriteSorting>(sprites);

        // Keep breaking cycles until there are no more
        while (true) {
            circularDepStack.Clear();
            circularDepData.Clear();

            bool removedDependency = false;
            foreach (var sprite in workingCopy) {
                if (RemoveCircularDependencies(sprite)) removedDependency = true;
            }

            if (!removedDependency) break;
        }

        var sorted = new List<IsoSpriteSorting>(sprites.Count);
        visited.Clear();

        foreach (var sprite in sprites) {
            Visit(sprite, sorted, visited);
        }

        return sorted;
    }

    /// <summary>
    /// Recursively walks the graph, visiting each node in DFS fashion.
    /// </summary>
    private static void Visit(IsoSpriteSorting sprite, List<IsoSpriteSorting> sorted, HashSet<int> visited) {
        int id = sprite.GetInstanceID();

        if (!visited.Contains(id)) {
            visited.Add(id);

            foreach (var dependency in sprite.Dependencies) {
                Visit(dependency, sorted, visited);
            }

            sorted.Add(sprite);
        }
    }

    private static bool RemoveCircularDependencies(IsoSpriteSorting sprite) {
        circularDepStack.Add(sprite);
        bool removedDependency = false;

        int id = sprite.GetInstanceID();
        bool alreadyVisited = circularDepData.TryGetValue(id, out bool inProcess);
        if (alreadyVisited) {
            if (inProcess) {
                RemoveCircularDependencyFromStack();
                removedDependency = true;
            }
        } else {
            circularDepData[id] = true;
            for (int idx = 0; idx < sprite.Dependencies.Count; idx++) {
                if (RemoveCircularDependencies(sprite.Dependencies[idx])) removedDependency = true;
            }
            circularDepData[id] = false;
        }

        circularDepStack.RemoveAt(circularDepStack.Count - 1);
        return removedDependency;
    }

    private static void RemoveCircularDependencyFromStack() {
        if (circularDepStack.Count <= 1) return;

        var startingSorter = circularDepStack.Last();
        int repeatIndex = 0;
        for (int i = circularDepStack.Count - 2; i >= 0; i--) {
            IsoSpriteSorting sorter = circularDepStack[i];
            if (sorter == startingSorter) {
                repeatIndex = i;
                break;
            }
        }

        int weakestDepIndex = -1;
        float longestDistance = float.MinValue;

        FindWeakestDependency(
            repeatIndex,
            ref weakestDepIndex,
            ref longestDistance,
            (left, right) => left.sortType == IsoSortType.Point && right.sortType == IsoSortType.Point
        );

        if (weakestDepIndex == -1) {
            FindWeakestDependency(
                repeatIndex,
                ref weakestDepIndex,
                ref longestDistance
            );
        }

        var left = circularDepStack[weakestDepIndex];
        var right = circularDepStack[weakestDepIndex + 1];
        left.Dependencies.Remove(right);
    }

    /// <summary>
    /// Compares pairs of sprites in the stack and determines the weakest
    /// dependency as those furthest apart on the x-axis. This is essentially a
    /// weighting function on the topological sort that lets us break cycles.
    /// </summary>
    private static void FindWeakestDependency(
        int repeatIndex,
        ref int weakestDepIndex,
        ref float longestDistance,
        Func<IsoSpriteSorting, IsoSpriteSorting, bool> predicate = null
    ) {
        for (int i = repeatIndex; i < circularDepStack.Count - 1; i++) {
            var left = circularDepStack[i];
            var right = circularDepStack[i + 1];

            if (predicate?.Invoke(left, right) ?? true) {
                float dist = Mathf.Abs(left.AsPoint.x - right.AsPoint.x);
                if (dist > longestDistance) {
                    weakestDepIndex = i;
                    longestDistance = dist;
                }
            }
        }
    }
}