Recursive child search

This code has been declared by its author to be Public Domain code.

Recursive child search by skn3

2003

As most 3d models are comprised of complex parent->child relations, this function will search all children, children of children, and so on.

It will not call itself over and over to recursively search. Only once does the function go into memory.
The benifits of this are evident, when calling the function many times looking for indervidual bones.

Read the comments in the code, for more instructions on how to use the function:

;### name   : 1-call recursive child search ###
;### by     : jonathan pittock (skn3)       ###
;### contact: skn3@acsv.net                 ###
;### www    : www.acsv.net                  ###

;This value is used to size the buffer bank below. If the data needs more space,
;it will resize the bank in blocks of the amount below. (in bytes, 1k = 1024 bytes)
Const recursive_resize=1024

;This bank is used in each call to the search function. It is outside the function,
;as creating and deleting over and over from memory, can cause fragmentation, not...
;to mention slow downs.
Global recursive_bank=CreateBank(recursive_resize),recursive_size=recursive_resize

;These are misc values, having them defined as global speeds up the function as...
;they don't need to be created/destroyed each time the function is called
Global recursive_entity,recursive_parent,recursive_id,recursive_start,recursive_total,recursive_offset

;The function
;It will return the entity if found, or 0 if not.
;MyChild=findchildentity(entity,"child name")
Function findchildentity(entity,name$)
	name$=Lower$(name$)
	recursive_parent=entity
	recursive_start=1
	recursive_offset=0
	.recursive_label
		recursive_total=CountChildren(recursive_parent)
		For recursive_id=recursive_start To recursive_total
			recursive_entity=GetChild(recursive_parent,recursive_id)
			If name$=Lower$(EntityName$(recursive_entity))
				Return recursive_entity
			Else
				If recursive_offset+8 > recursive_size-1
					ResizeBank(recursive_bank,recursive_size+recursive_resize)
					recursive_size=recursive_size+recursive_resize
				End If
				PokeInt(recursive_bank,recursive_offset,recursive_id+1)
				PokeInt(recursive_bank,recursive_offset+4,recursive_parent)
				recursive_offset=recursive_offset+8
				recursive_start=1
				recursive_parent=recursive_entity
				Goto recursive_label
			End If
		Next
		If recursive_offset=0
			Return 0
		Else
			recursive_start=PeekInt(recursive_bank,recursive_offset-8)
			recursive_parent=PeekInt(recursive_bank,recursive_offset-4)
			recursive_offset=recursive_offset-8
			Goto recursive_label
		End If
End Function

Comments

_PJ_

2015

I never realised that labels could be used within functions...

This actually gives Goto a more valid use!

Yasha

2015

The benifits of this are evident

The whole reason OSen give you a stack frame in the megabytes is to allow you to do this easily, by letting functions call themselves and avoid the gymnastics of a fake stack. The above function can afford to call itself thousands of times. No realistic bone structure will ever overflow the stack unless there's something horribly wrong with your program. Blitz3D uses real recursion internally for functions like this.

Real recursion is where it's at. Probably ten times faster, too.

_PJ_

2015

Sorry Yasha, thanks for replying but that was a little beyond me, are you saying that it's unnecessary for the code above to be using the label/goto because Blitz3D internally can support this with good memory management?

Yasha

2015

Ah yeah, my comment is only directed at the top post. There are uses for labels in functions, as you say - I just don't think this is as good an application of that as skn3 does.

When a function self-calls (recursion), it allocates fresh space for all its local variables. You get either 1MB or 8MB on most modern systems to do this in, which is enough for several thousand nested calls of a modest function, when it has only a few locals like the above.

The code above is worried about what happens when this space runs out (your program dies, no warnings or errors), so instead of using automatically-allocated locals, it extends a bank to hold the data you would put in locals, and uses labels to implement a loop that hops up and down that bank, instead of hopping up and down the "implicit" storage allocated behind the scenes for real local variables.

The problem with this is that it's nowhere near as clear as a recursive version, and that it's going to be (comparatively) a lot slower (PeekInt and PokeInt are hefty function calls that need offsets and math and stuff; reading a local is one machine instruction). Since in practice the application stack will not run out for reasonably-sized meshes (and if it was going to, would do so on a Blitz3D builtin because they also exhibit the "problem" this tries to correct), this is a poor tradeoff.

I mean the performance thing is no big deal (ten times slower than "very fast" is still very fast), but the fact that this is a lot less clear is the big issue. Clarity in code is one of the most important things to aim for.

Code Archives Forum