Finding connected limbs in limb flow using DFS style algorithm

This post will be a little long, but but please read and give your take on it anyways.

As the title suggests, I want to have a sort of discussion on the most efficient way to find the “limb flow” of a character body. What do I mean?

The character is just as it appears, a block man. The red lines represent the limb flow of the character. What I am trying to do is find which limbs are essentially children of a target limb. So in real use example, if you got shot in the left thigh and it fell off, the limb flow would suggest that also the left knee and left foot limbs would fall off too.

I am thinking of multiple ways to go about this, but this one I think initially would work best:

  1. A DFS style approach.


Limbs have 3 properties:
Parent (name of parent, head parent == root)
Child (might be a little confusing, but this is just a bool saying if it has children, used to identify the leaf nodes)
Checked (if there is a node unchecked by our search, == false)

All limbs would be stored into a list initially.

When something is hit to die, first check if it was head, if it was instant death. Also check if it’s parent == Head, also instant death. If it is not, put that object name (the parent of the hit object) into variable parentObject

If not:

-Store the hit limb into a hitVariable, mark it as checked, and put it into the MFD list (explained further down)

-Iterate the list checking Child statuses, once you find one with status false and checked == false you know you found a leaf that has not been inspected yet. Now start checking parents. Move current item into a temp list Holder and mark property checked as True until one of two collisions:

  1. reached object where parent == head (made it all the way to the root with no collision)
  2. reached object where parent == hitVariable (NOTE* it would still execute this iteration of the loop, probs need to use a stopper variable, then change stopper variable status inside the loop)

if first choice, just move all items from Holder into a list Survivors (all limbs made it to the head without passing the hit)
if second choice, move all items from Holder into a list MFD (all limbs in list will fall off)

Once moved into Survivor or MFD, return to original list and clear Holder, start iterating again until a situation where Checked == false and Child == false, then repeat. Do this until all items in the list are marked checked.

Now, we have three lists. Original, Survivor, MFD. We simply run a loop iterating through MFD, ending objects on every iteration until the list is empty. Now we set our Original list = Survivor and clear Survivor as well.

A picture of a before/after execution to clarify end results:

NOTE: the variable in the picture MFD == Checked, I just made the picture before thinking the variable names out fully

Now we of course need to reset our leaf nodes, as we may have new leaf nodes. We also need to uncheck everything.

Using this setup, could now iterate through the new Original list, and look:

for i in list:
if i[‘parent’] == parentObject: (we now know we did not add any new leafs to our list, as the parentObject still has other children)
#do nothing really
parentObject[‘Child’] = False (The else will trigger if this is now a leaf node)

  i['checked'] = false

I think that should work for the purpose described. Any thoughts an opinions? Especially from the coders out there. This format obviously assumes there is not a crazy number of items in the list, and you will have to have no items with two or more parents, which shouldn’t be to hard just make complex shapes into one object if the situation ever came up.

Why can’t you simply follow the parent-child hierarchy? I don’t know if it’s true for bones, but all GameObjects have “parent” and “childrenRecursive” members.

The limbs are parented already to the actual bone rig that is attached to the model as to animate it and such, I don’t think Blender allows multiple definitions of parents? So like the hand limb can’t be parented to both the rig for manipulation and the forearm for elimination if the forearm was hit.

Maybe I was a little confusing when I started that out, they aren’t actually children, just conceptually they would act as if they were children.

OK, I think I follow what you’re trying to do, but I think you’re trying to engineer a solution when you have the tools already to do what you want.

You should be able to use Python to get the bone associated with the body section you’re looking at. How you do this is up to you and might require some design (i.e. name the body parts something that takes their bone name into account, like “BodyChest”, and name the bone accordingly (“Chest”). This allows you to use the body part’s name to grab the bone).

In Python, the armature’s bones are referred to as Armature Channels, and you can get some information from those pieces of info; you can also get the underlying armature bone data by using the channel’s “bone” property. While bones are read-only, they should have the info you need to get the parent or children of the “destroyed body part” to destroy the others in the “line” accordingly.

Tried JSON?

Hmm, I have never really used the armature channels to access the information about the skin meshes, but I am not sure I follow you here.

If my little block dude is, for example, controlled on his arms by just a hand IK, elbow bone, and should blade bone, wouldn’t it not necessarily yield accurate hit results?


I was under the impression that each part of your character mesh (the blocks for each limb) were separate and parented to the bones of the armature. If you want to detect collisions on each individual limb, then you need to look up how to do that in particular, separate from finding connected limbs.