View Full Version : Re-order array based on hierarchy?

12 December 2007, 06:59 PM
Wow, it took me long enough to stumble upon this forum! I've been Maxscripting for awhile but still consider myself a beginner. There are many concepts I'm not comfortable with or have never tried, and hit the occasional brick wall ...

I often find myself needing to align bones over time to baked copies of themselves. Because bones should be aligned in hierarchical order, I generally have to control-click the nodes to be aligned manually. I'd rather select them all in one go and have a script determine the order in which things should be aligned.

I figure what I need is a function that will take a selection array, and output a new array with the selected nodes in hierarchical order.

I've gotten as far as finding the most ancestral nodes of the input array, by checking each for an undefined parent, or for a parent that is not included in the array. Those nodes are appended to the in-progress output array.

What I'd like to do next is search down each of their lines and add children to the output array in order. I don't know how to do it though, and was hoping someone could provide an example or advice. Is this a job for do/while, simply appending children to the output array until .children returns undefined? What happens when children.count is greater than 1? It reeks of complexity and breaks my brain. :)


12 December 2007, 10:25 PM
This sort of thing wouldn't be too hard to do. I can give you some startup and then others can help you from there, because I'm not 100% sure on what you want. I believe what you've communicated sounds like this.


So what you want to do is pass an array of bones and have them reordered like this? It sounds like you should think through your functionality and interface well so you simplify the process as much as you can.

12 December 2007, 12:38 AM
Heres something I whipped up real quick, it might do what you're looking for but might not. If it doesn't, hopefully it will give some ideas for how to go about doing what you want to do.

heirAr = #()
for x in selection do
parIn = findItem heirAr x.parent
insertItem x heirAr (parIn + 1)
print heirAr

12 December 2007, 08:25 PM
What happens when children.count is greater than 1?

You may need to avoid:

selection: [ grandparent, child, parent ] yielding array: [ child, grandparent, parent ]

I may be wrong, but I think it may be better to build an actual tree, rather than use an array to do this, and then traverse the tree in the way you'd like.

--define a simple tree node type

struct hNode (

--create a tree on given root from given array of objects
--root contains no object, just children.

fn hTreeFromArray root objectArray =(
-- create a bag of unlinked hNodes
hNodeArray = #()
for obj in objectArray do(
append hNodeArray (hNode object:obj children:#())
--link them up, treewise
for candidateChild in hNodeArray do(
soughtParent = candidateChild.object.parent
noParent = true
for candidateParent in hNodeArray while noParent do(
if (candidateParent.object == soughtParent) then (
append candidateParent.children candidateChild
noParent = false
--if no parent found in array then root is parent
if noParent then append root.children candidateChild

--branchwise traversal from rootNode, backing up to last-met forks
--apply aFunction to each node

fn traverseDownBranches rootNode aFunction =(
for child in rootNode.children do(
aFunction child
traverseDownBranches child aFunction

--a test function to apply to each node

fn printObjectName theNode =(


theRoot = hNode children:#()
theObjectArray = selection as array
hTreeFromArray theRoot theObjectArray
traverseDownBranches theRoot printObjectName

No sanity checking here, for sensible selections etc. There's probably a much snappier way for your particular problem .. I'm not really a MaxScripter yet.

12 December 2007, 06:14 PM
I was thinking a binary node tree as well but I think that it might be more then what he needs.

You will need a couple of functions.

First off is one that will find all objects that are the root of the selections. You could have a couple of trees selected so you might find more then one. What it will need to do is pass the selection to the function and have it run through each node checking to see if any of the other nodes in the array are up stream of the one that you are working on. If there is one up stream that you don't want that node. If you find one that has parent in the tree then you can store that to an array. We will call this rootArray.

Now you need to create a recursive function that will have each of the rootArray nodes passed to it one at a time. It will then traverse the hierarchy tree, check if the next node that is in the tree is in the first array and if it is then add it to a sorted array. Will will call this sortedArray.

I don't have time to code it up so Maybe Mat or one of the other guys can take a stab at it if you can't get it right.

And welcome to the cg talk. This has been one of the best places for information for years now. Hey, even the infamous Bobo hangs out here from time to time.

12 December 2007, 08:00 PM
I was thinking a binary node tree as well but I think that it might be more then what he needs

Quite. ( If I've understood your method ). Why build your own tree when you can traverse the ready-made one in the scene? The home-made one would only be more efficient if the selection contained a small subset of the descendants of its own roots, and that's pretty unlikely.


Or a more klunky way, assuming the selection is smallish anyway:

fn sortArrayByHeirarchy objectArray =(
-- first find roots and put them at left
for obj in objectArray do(
if (finditem objectArray obj.parent) == 0
then append sortedArray obj
else append childArray obj
-- now insert children on immediate right of their parents
-- repeat scan until child array is empty
while childArray.count > 0 do(
while i <= childArray.count do(
parentIdx = finditem sortedArray childArray[i].parent
if parentIdx != 0 then(
insertItem childArray[i] sortedArray (parentIdx+1)
deleteItem childArray i
i += 1
sortedArr = sortArrayByHeirarchy (selection as array)
for obj in sortedArr do print

01 January 2008, 06:05 PM
Hey guys, sorry for the late bump (what is the protocol here?), but wanted to say thanks for the help. Mat's suggestion has worked like a charm on everything I've applied it to. The related info that's been provided in this thread is very educational too! Some of it very slightly over my head, but I'm enthusiastically reaching. :) Thanks much!

CGTalk Moderation
01 January 2008, 06:05 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.