Hi All, I wrote a couple versions of a Transform Extension iterator function, that allows me to looks through all descendants of a transform, rather than just it’s immediate children, using a foreach loop. I wrote both a recursive, and since I heard that’s not a good always a good idea, a non-recursive version. I hoping this will prove useful to people, and looking for feed-back on improving them.
usage:
foreach (Transform t in transformToDisplay.AllDecendantsNonRecursive())
//foreach (Transform t in transformToDisplay.AllDecendants())
{
Debug.Log(t.position.ToString());
}
Here are the actual extension functions:
class TransformExtensions
{
public static Transform[] GetChildrenArray(this Transform transform)
{
Transform[] childArray= new Transform[transform.childCount];
int index=0;
foreach(Transform c in transform)
{
childArray[index++]= c;
}
return childArray;
}
//! Extension provided to enable foreach through transform and all decendants, rather than just children.
public static IEnumerable<Transform> TransformAndAllDecendants(this Transform transform)
{
yield return transform;
foreach (Transform decendant in transform.AllDecendants())
{
yield return decendant;
}
}
//! Extension provided to enable foreach through all decendants, rather than just children.
public static IEnumerable<Transform> AllDecendants(this Transform transform)
{
// yield return transform;
foreach (Transform c in transform)
{
yield return c;
if (c.childCount > 0)
{
foreach (Transform decendant in c.AllDecendants())
{
yield return decendant;
}
}
}
}
private static Transform currentTransform;
private static int currentChildIndex;
private static List<Transform> stack;
private static List<int> Istack;
private static List<Transform[]> childArrayStack;
private static Transform[] currentTransformChildrenArray;
private static Transform child;
public static IEnumerable<Transform> AllDecendantsNonRecursive(this Transform transform)
{
stack = new List<Transform>();
Istack = new List<int>();
childArrayStack = new List<Transform[]>();
currentTransformChildrenArray = transform.GetChildrenArray();
currentTransform = transform;
currentChildIndex = 0;
while(true)
{
if (currentChildIndex < currentTransform.childCount)
{
child = currentTransformChildrenArray[currentChildIndex++];
yield return child;
if (child.childCount > 0)
{
stack.Add(currentTransform);
Istack.Add(currentChildIndex);
childArrayStack.Add(currentTransformChildrenArray);
currentTransform = child;
currentChildIndex = 0;
currentTransformChildrenArray = currentTransform.GetChildrenArray();
}//current child has children
}
else //reached beyond last child, pop up.
{
//pup up
int lastIndex = stack.Count - 1;
if (lastIndex >= 0)
{
currentTransform = stack[lastIndex];
currentChildIndex = Istack[lastIndex];
currentTransformChildrenArray = childArrayStack[lastIndex];
stack.RemoveAt(lastIndex);
Istack.RemoveAt(lastIndex);
childArrayStack.RemoveAt(lastIndex);
}
else
{
// top node, stop popping up: all done
yield break;
}
}// if done with all children for current transform
}// end loop
}// end AllDecendantsNonRecursive
}
Yeah, when doing a non-recursive tree search, going layer by layer is a simpler algorithm, which is why I go with that one.
This is primarily just to avoid garbage. It avoids the whole creating new arrays when one already exists.
Unity recently started implementing methods like this themselves, like the ‘GetComponents’ method that accepts a list, or the Physics.RayCastNonAlloc method.
I tried to follow your example of using the output list to do the child iteration, but I found myself stuck using INSERT(index), to get the output order I’m looking for
static public List<Transform> AllDecendantsList(this Transform transform)
{
List<Transform> returnValue = new List<Transform>();
foreach(Transform t in transform)
{
returnValue.Add(t);
}
int CurrentTransformIndex=0;
while (CurrentTransformIndex<returnValue.Count)
{
Transform currentTransform= returnValue[CurrentTransformIndex++];
if (currentTransform.childCount > 0)
{
int childCounter = 0;
foreach (Transform t in currentTransform)
{
returnValue.Insert(CurrentTransformIndex + childCounter, t);
childCounter++;
}
}
}
return returnValue;
}
It’s basically the same algorithm you used in GetAllChildren(thisTransform t, IList lst), except instead of just adding to the end, I use Insert(index,item) to put the children in the order I was looking for (immediately after their parent).
Though it IS an insert operation, I suspect this version is far superior to all the crappy stack stuff I was doing before. Many thanks for the examples!
Edit:
Here we go, now it sorts either way…
static public List<Transform> AllDecendantsList(this Transform transform, bool groupByLevel=false)
{
List<Transform> returnValue = new List<Transform>();
foreach(Transform t in transform)
{
returnValue.Add(t);
}
int CurrentTransformIndex=0;
while (CurrentTransformIndex< returnValue.Count)
{
Transform currentTransform= returnValue[CurrentTransformIndex++];
if (currentTransform.childCount > 0)
{
int childCounter = 0;
foreach (Transform t in currentTransform)
{
if (groupByLevel)
returnValue.Add(t);
else
returnValue.Insert(CurrentTransformIndex + childCounter, t);
childCounter++;
}
}
}
return returnValue;
}
The fastest way to get the order you want is with a stack… but you don’t need to create one, there’s a stack (in the form of a link list) already in place.
Transform.parent
With that in mind, this should work:
public static void GetAllChildren(this Transform t, IList<Transform> lst)
{
//traversed as pre-order instead of level-order
for (int i = 0; i < t.childCount; i++)
{
Transform node = t.GetChild(i);
while (!object.ReferenceEquals(node, null))
{
lst.Add(node);
if (node.childCount > 0)
{
node = node.GetChild(0);
}
else
{
int j = node.GetSiblingIndex() + 1;
while (node.parent != t && j >= node.parent.childCount)
{
node = node.parent;
j = node.GetSiblingIndex() + 1;
}
node = (node.parent == t) ? null : node.parent.GetChild(j);
}
}
}
}
note, I didn’t really test this, I just used the standard pre-order traversal algorithm and inserted the link list to remember the trail instead of a stack.
Ah, GetSiblingIndex(): slick. I didn’t realize that data was available (I didn’t even count on it being consistent). Normally when working with tree structure it is NOT safe to assume nodes are in any particular order. I should have realized that is NOT the case with a transform tree, since GetChild(int) is provided.
I assume this value represents the order the transforms are displayed, under the parent, in the hierarchy tree? Just to confirm, this does NOT effect ANYTHING else, right?
The method only fills a list using pre-order traversal of the tree, it doesn’t change anything.
Pre-ordered depth first search is the name of the traversal you prefer. Where as my original code was in ‘level-order’ or ‘breadth-first search’. See: https://en.wikipedia.org/wiki/Tree_traversal
I realized I tried to compile my forum post, but THAT much was clear
I was talking about the unity provided GetSiblingIndex. I understand what it represents, I just wonder what that value actually does in Unity, and when it might change.
So the hierarchy tree in unity allows multiple children, and those children are indexed. This way their order is preserved. So like when you like in the hierarchy view, the order of the children from top to bottom is the index order of those children.
It changes if you move its indexed position. This can be done through the hierarchy view, or programmatically via the sibling indexing methods:
Or if a new GameObject is added to the child list.
While you’re doing this traversal, and because we know that the Unity API is single threaded, we can be sure that this value won’t change while gathering the information (unless you explicitly call those methods in the algorithm).
I didn’t even realize what was bugging me about the sibling index stuff: that was exactly it. (And why I don’t need to worry about it. I just can’t STORE that index, and expect it to be the same later.)
