Transform Hierarchy Decomposition

Future Colossal Blog

by James Fulop

Deleting a large number of objects at once can cause a Unity game to skip a couple of frames. In our game, Shadows of Isolation, there are a number of times that we have to delete several hundred objects while maintaining a seamless experience as the games load in and out different sub scenes. For my example I'll be using an asteroid field with a few thousand rigidbodies.

asteroid field
asteroid field

Lets start by just calling Delete(gameObject) on the parent object. Here's our latency on an i7 processor on a single frame.

Destroy1500AtOnce
Destroy1500AtOnce

My strategy to get around this spike was to first disable all of the objects. This way are functionally out of the scene, then to start deleting one object per frame. I could have just left the objects disabled in my scene, but those objects were still taking up space in memory. For this particular example the memory footprint was low, as there were only a few meshes and textures, but when destroying more varied scenes it had a large impact on reducing my memory foot print.

In my case, I tend to keep my sub scenes as different groups of objects parented to one thing. That sub scene game object then consists of a deep hierarchy. We are going to need a shallow list of objects starting with the deepest and ending with the shallowest. Otherwise we will have spikes in performance as objects with deep transform hierarchies are deleted before being decomposed.

4th Tier

Heirarchy4Deep_2
Heirarchy4Deep_2

3rd Tier

Heirarchy3Deep_2
Heirarchy3Deep_2

2nd Tier

Heirarchy2Deep_2
Heirarchy2Deep_2

1st Tier

Heirarchy1Deep_2
Heirarchy1Deep_2

I decided the best way to do this was to create separate lists for each depth level.

One of the sometimes fun, sometimes hard parts of programming is naming your file. I decided to go with the macabre name DecomposeChildren, to each his own.

To start, here's how we declare a generic list of type GameObject. This list will eventually contain all of our objects in the order we want.

using UnityEngine; using System.Collections; using System.Collections.Generic; public class DecomposeChildren : MonoBehaviour { private List<GameObject> shallowList; void Start() { shallowList = new List<GameObject>(); } }

We can then make a list of lists so the script is flexible and will work with any sort of transform hierarchy.

using UnityEngine; using System.Collections; using System.Collections.Generic; public class DecomposeChildren : MonoBehaviour { private List<GameObject> shallowList; private List<List<GameObject>> masterList; void Start() { shallowList = new List<GameObject>(); masterList = new List<List<GameObject>>(); } }

Now to fill these lists with objects. The best way seems to be with recursion for its flexibility. While iterating the children of a transform, if that child has its own children (read:grandchild), then recursively call at that depth. If while iterating over the hierarchy we end up deeper than we have before, add a list to our masterList for that depth. After generating these lists we can just iterate through the list of lists from last to first, adding their values to shallowList.

using UnityEngine; using System.Collections; using System.Collections.Generic; public class DecomposeChildren : MonoBehaviour { private List<GameObject> shallowList; private List<List<GameObject>> masterList; void Start () { shallowList = new List<GameObject>(); masterList = new List<List<GameObject>>(); PopulateLists(transform, 0); for (int i = masterList.Count - 1; i >= 0; i--)// fill from deepest to shallowest { shallowList.AddRange(masterList[i]); } } private void PopulateLists(Transform parent, int depth) { for (int i = 0; i < masterList.Count - 1; i++) { if (depth > masterList.Count-1)//initialize new lists for each depth { List<GameObject> list = new List<GameObject>(); masterList.Add(list); } masterList[depth].Add(parent.GetChild(i).gameObject); //recurse into next layer if (parent.GetChild(i).childCount != 0) { PopulateLists(parent.GetChild(i), depth + 1); } } } }

Now we just need to start calling delete, which we put into a very simple coroutine. Here's the full script!

using UnityEngine; using System.Collections; using System.Collections.Generic; public class DecomposeChildren : MonoBehaviour { private List<GameObject> shallowList; private List<List<GameObject>> masterList; void Start () { shallowList = new List<GameObject>(); masterList = new List<List<GameObject>>(); PopulateLists(transform, 0); for (int i = masterList.Count - 1; i >= 0; i--)// fill from deepest to shallowest { shallowList.AddRange(masterList[i]); } StartCoroutine(Delete(shallowList)); } private void PopulateLists(Transform parent, int depth) { for (int i = 0; i < masterList.Count - 1; i++) { if (depth > masterList.Count-1)//initialize new lists for each depth { List<GameObject> list = new List<GameObject>(); masterList.Add(list); } masterList[depth].Add(parent.GetChild(i).gameObject); //recurse into next layer if (parent.GetChild(i).childCount != 0) { PopulateLists(parent.GetChild(i), depth + 1); } } } //call once private IEnumerator Delete(List<GameObject> shallowList) { for (int i = 0; i < shallowList.Count; i++ ) { Destroy(shallowList[i]); yield return new WaitForSeconds(0); } Destroy(this.gameObject); } }

Lets see how this performs.

performance
performance

So our performance is about one fourth of the Destroy(gameObject) call, with miniscule Destroy calls on subsequent frames. Luckily we can potentially run the Start() function at the start of the game if we know that the transform hierarchy will not be changing during gameplay.

I hope this helps someone out there! Thanks for reading!