Count Children Recursive?
Blitz3D Forums/Blitz3D Beginners Area/Count Children Recursive?
| ||
| Hey all, For some reason, this problem isn't coming to me in a simple way. I've check the forums, and I can't find anything on the subject, so hopefully I'm not bringing up something that's been discussed before. Basically, I would like to be able to count all of the children in my mesh, but Blitz's CoundChildren stops at 4, when in reality, my model has closer to 100. I've taken some sample code I've seen earlier and tried to re-work it, but it's making no sense at all. Here's the sample code that I saw recently, which will DebugLog all of the names of the children in the mesh. I've tried it, and it works beautifully. ;Thanks to GNS and Malice for the sample Function DebugNameChildren(Ent) DebugLog(EntityName$(Ent)) n=CountChildren(Ent) If (n) For i = 1 To n DebugNameChildren(GetChild(Ent,i)) Next End If This is what I've come up so far: Function CountChildrenRecursive(entity,temp = 0) n = CountChildren(entity) If (n) temp = temp + n For i = 1 To n temp = CountChildrenRecursive(GetChild(entity,i),temp) Next EndIf End Function I use the function like this in my program: ;... Text 0,0,"Count Children Recursive: " + CountChildrenRecursive(MyModel) Obviously, my take on this modified function is way off. It always returns a big, fat Goose Egg, no matter how many times I re-work it. Any help or insight would be greatly appreciated. Thanks! |
| ||
I don't see a return value... doesFunction CountChildrenRecursive(entity,temp = 0) n = CountChildren(entity) If (n) temp = temp + n For i = 1 To n temp = CountChildrenRecursive(GetChild(entity,i),temp) Next EndIf return temp End Function help? no blitz available to me tonight Last edited 2010 |
| ||
| Holy shit, how the hell did I miss that? I guess the function works, but it would be nice to return the restult! Thanks! |
| ||
| hehe Always those little obvious things cause the most problems :D Glad it's sorted! |
| ||
Or you could do it non-recursively (and more slowly but more intuitive maybe):alien = LoadAnimMesh("alien.b3d")
count = 0
ent = alien
While ent
cnt = cnt + 1
ent = NextChild(ent)
Wend
Function NextChild(ent)
Local siblingcnt
If CountChildren(ent)>0
Return GetChild(ent,1)
EndIf
Local foundunused=False
Local foundent = 0, parent,sibling
While foundunused=False And ent<>0
parent = GetParent(ent)
If parent<>0
If CountChildren(parent)>1
If GetChild(parent,CountChildren(parent))<>ent
For siblingcnt = 1 To CountChildren(parent)
sibling = GetChild(parent,siblingcnt)
If sibling=ent
foundunused = True
foundent = GetChild(parent,siblingcnt+1)
EndIf
Next
EndIf
EndIf
EndIf
ent = parent
Wend
Return foundent
End FunctionTaken from here: http://blitzmax.com/codearcs/codearcs.php?code=796 |
| ||
| but you only go a discrete number of layers deep though, so you could miss a bunch no? |
| ||
| I am not sure, probably Beakers code creates a list of children, no? (Those tabs make me blind, no idea why) I however once solved a similar issue by putting all children into a onedimensional array or bank in order to make parsing easier. You can parse the hierarchy "pseudo-recursively" with a bank: simply store all children in the bank, and remember the last index, then parse all stored children and add their children to the end of the list. Do this until none of them has any children anymore. Or you may use types for the same purpose. Basicly nothing's wrong with true recursion. But sometimes there may be a certain risk for eternal recursion, resulting in a stack overflow, caused by millions of return addresses from the nested function calls. Working with return values in recursive functions is also rather confusing, sometimes. I often prefer to use global variables in recursive functions. |
| ||
| Recursion is one of those things that I've always felt like maybe I don't fully understand. I've used recursion exactly once in my programming career (for the same purpose too, to traverse a tree of children, although not in Blitz) but I keep hearing other people trumpet how recursion is the most useful thing ever. |
| ||
| Recursion is something you'll hear a lot of if you talk to any CS students. It's popular because it combines simplicity with power: any algorithm that can be expressed as a loop can be expressed with recursion, and it'll be simpler while it's at it. The reason you don't hear a lot of it from anyone else is that most people in the real world don't use Lisp or Haskell, and as a result are vulnerable to stack overflows. Of course, this isn't a huge threat - default stack size on Windows is something like a megabyte which translates to about 14000 B3D function calls, which is usually enough to traverse most practical mesh structures. But it does scare people, because of the total disaster that occurs if you get it wrong and allow infinite recursion (in B3D, the program will simply quit without error or MAV, even in debug mode). |
| ||
| Especially we Basic-Coders may easily forget to add an exit condition to a recursive function, so there should be a bit of respect. Even a simple Thing like Function a() a() end function could crash Blitz or even the Machine in theory. |
| ||
So, taking jfk's idea, would this version of the function above be a way to avoid infinite recursion?
Function CountChildrenRecursive(entity,temp = 0)
n = CountChildren(entity)
If (n)
temp = temp + n
For i = 1 To n
temp = CountChildrenRecursive(GetChild(entity,i),temp)
If temp > 10000 Then Exit
Next
EndIf
Return temp
End Function
It's very unlikely that any model would ever have more than 10,000 children in it. I'm not even sure if I'm using exit in the right way or not. Will that break out of a For...Next loop? This is all great information to have if I decided to keep this function in my game. |
| ||
What you really want to limit, is the number of times the funciton is repeating itself, rather than the number of children. This would require either a Gkobal counter variable, or adding a new parameter to the function to keep track:
Global RecurseCounter%=0
Function CountChildrenRecursive(entity,temp = 0)
RecurseCounter=RecurseCounter+1
If (RecurseCounter <= 50)
n = CountChildren(entity)
If (n)
temp = temp + n
For i = 1 To n
temp = CountChildrenRecursive(GetChild(entity,i),temp)
Next
EndIf
Return temp
End If
End Function
Function CountChildrenRecursive(entity,temp = 0,RecurseCounter%)
RecurseCounter=RecurseCounter+1
If (RecurseCounter <= 50)
n = CountChildren(entity)
If (n)
temp = temp + n
For i = 1 To n
temp = CountChildrenRecursive(GetChild(entity,i),temp,RecurseCounter)
Next
EndIf
End If
Return temp
End Function
You could even use a lower value if you're sure it's unlikely to be valid, I've often heard of this limit in recursive loops as a 'sanity check'. |
| ||
| Counting the children as a recursion depth test may not work reliably because there can be many children on every level of recursion. Instead I'd use an independant, global depth counter. You have to use the depth limiter before you branch to the Function internally, because whatever comes after the function call will be executed the first time when the deepest recursion returned due to n=0. Imagine it will branch recursively like a pyramid and the line after the function call will maybe never be reached, even if the function called itself a thousand times.
global depth
....
Function CountChildrenRecursive(entity, allkids=0)
If depth > 10000 Then Return allkids ; or maybe better show error msg?
depth=depth+1
n = CountChildren(entity)
allkids = allkids + n
If (n)
For i = 1 To n
allkids=CountChildrenRecursive(GetChild(entity,i),allkids)
Next
EndIf
depth=depth-1
return allkids
End Function
BTW "It's very unlikely that any model would ever have more than 10,000 children in it" - the problem with recursion is more bugs in files that will lead to loops, eg. a parent that is attached to its own child. AS far as I remember Blitz3D will detect such loops and refuse to load a B3D like that, but basicly it's a risk with recursion. Edit. Malice was faster. Last edited 2010 |
| ||
| So, in other words, be careful with recursion...Originally, I only needed this function for debugging purposes and it won't appear in any of my executables, but it's a useful skill to have, nonetheless. |
   |