 |
Castle Paradox
|
| View previous topic :: View next topic |
| Author |
Message |
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA
Joined: 19 Feb 2003
Posts: 518
Location: Halifax
|
 Posted: Sat May 01, 2010 6:53 pm Post subject: Slice Tree Traversal |
 |
|
I've got a tree of slices that store information.
I've written a tree traversal in order to tinker with the tree data:
| Code: |
######################
# BB Data Slice Tree Traversals #
######################
SCRIPT, Slice Tree Postorder, sl,operation, BEGIN
VARIABLE (i,child,numChildren)
child := FIRST CHILD (sl)
numChildren := GET SLICE EXTRA (sl,1) # This number does not include extra children slices used for data storage
FOR(i,1,numChildren) DO(
Slice Tree Postorder(child,operation)
child := NEXT SIBLING (child)
END
RUN SCRIPT BY ID (operation,sl)
END
### |
I invoke the traversal by saying:
Slice Tree Postorder (SliceRoot,@ScriptNameThatDoesStuffToEachSlice)
Now, this works all peachy - but the stinky thing is, I'm not able to pass arguments (other than the data stored within the slices themselves).
Is there a way to implement this in a general way that would accommodate scripts which require variable numbers of arguments?
I know it's possible to have optional arguments, but how do I avoid feeding a function too many arguments?
If I do it this way:
| Code: |
######################
# BB Data Slice Tree Traversals #
######################
SCRIPT, Slice Tree Postorder, sl,operation,a1=0,a2=0,a3=0,a4=0,a5=0,a6=0,a7=0,a8=0,a9=0,a10=0, BEGIN
VARIABLE (i,child,numChildren)
child := FIRST CHILD (sl)
numChildren := GET SLICE EXTRA (sl,1) # This number does not include extra children slices used for data storage
FOR(i,1,numChildren) DO(
Slice Tree Postorder(child,operation,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10)
child := NEXT SIBLING (child)
END
RUN SCRIPT BY ID (operation,sl,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10)
END
### |
and my "operation" script requires no arguments, then this code wouldn't work, yeh?
EDIT:
Oh! Uh, so I did some experiments, and it looks like extra arguments are ignored.
Anyways - I'm still looking for advice, I'm not used to doing this kind of programming, and if there's anything I should look out for, please let me know :-)
_________________
Working on rain and cloud formation |
|
| Back to top |
|
 |
TMC
On the Verge of Insanity
Joined: 05 Apr 2003
Posts: 3240
Location: Matakana
|
| Posted: Sat May 01, 2010 7:12 pm Post subject: |
|
|
Actually, it will work, because if you pass too many arguments to a script with runscriptbyid the rest are silently ignored.
Maybe it should show a minor warning message when that happens, at a severity that is not shown by default. But I'm not going to make it an error, so go ahead.
You could also pass the arguments around using global variables. That would be faster as well (though it's probably pretty neglible).
_________________
"It is so great it is insanely great." |
|
| Back to top |
|
|
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA
Joined: 19 Feb 2003
Posts: 518
Location: Halifax
|
| Posted: Sat May 01, 2010 7:35 pm Post subject: |
|
|
Here's where scripts returning multiple values would be handy ...
I have a script which recursively iterates over my slice data tree, but I'm unable to implement it using a traversal (I think ... :-S)
Here's why:
Values calculated at each parent node need to be passed onto each child.
So, if I rig up a Preorder traversal like so:
| Code: | SCRIPT, Slice Tree Preorder, sl,operation,a1=0,a2=0,a3=0,a4=0,a5=0,a6=0, BEGIN
RUN SCRIPT BY ID (operation,sl,a1,a2,a3,a4,a5,a6)
VARIABLE (i,child,numChildren)
child := FIRST CHILD (sl)
numChildren := GET SLICE EXTRA (sl,1) # This number does not include this tree's 4 dataslice children
FOR(i,1,numChildren) DO(
Slice Tree Preorder(child,operation,a1,a2,a3,a4,a5,a6)
child := NEXT SIBLING (child)
END
END |
I can't use the RUN SCRIPT BY ID to return the multiple new arguments needed at the next recursive call.
What I'm doing is calculating Boulderbeast slice positions. The hand's positioning depends on the forearm's positioning, which depends on the arm, which depends on the torso, which depends on the entire body. I don't think globals would work in this case - I'd need to reserve a zillion of them. With recursion, I can take advantage of variable scope, and 100+ values are treated neatly with 6 variable names.
Oh! Right ... I actually can do this if I store the numbers in the slice extra data. A child slice can retrieve the necessary numbers by accessing extra data of the parent slice.
Of course when I say "extra data" I'm storing more than 3 values at each slice node, so I'm attaching extraneous children to each node for extra storage.
By the way, why are there 3 slice extra slots? I'm just curious why a more base-2 number wasn't picked...2 or 4 or something.
_________________
Working on rain and cloud formation |
|
| Back to top |
|
|
TMC
On the Verge of Insanity
Joined: 05 Apr 2003
Posts: 3240
Location: Matakana
|
| Posted: Sat May 01, 2010 10:49 pm Post subject: |
|
|
Is this part of the solution to your out-of-order rotations problem? I'm still meaning to inspect your scripts in more detail to see how you did things.
So your solution is to add more child slices to each boulder slice? That's an OK solution. If I were building this, I would be worried about how fast this thing actually runs, but I don't really know if it's actually a problem.
You can also do recursive tree computation like that, using an explicit stack rather than the implicit function call stack (incidentally, this is exactly how positions for 3D objects are calculated in OpenGL, etc, composing rotation matrices and pushing the intermediate results to a stack). Psuedocode:
| Code: | function recursive_computation (slice)
temp := do_calculation(slice, stack_top(stack))
set_slice_data(slice, temp)
push_on_stack(stack, temp)
for each child slice do
recursive_computation(child)
end for
pop_stack_top(stack)
end function
push_on_stack(stack, initial data) #(position and orientation of root slice)
recursive_computation (root slice)
|
Here do_calculation calculates the position and orientation of a slice using the parent position and rotation.
You could implement the stack either using globals, or using a list of slices (this would result in fewer slices than if you gave every slice its own children to store its parents data, so would probably be faster. In fact, the code could easily be simpler be simpler as well)
| Bagne wrote: | | By the way, why are there 3 slice extra slots? I'm just curious why a more base-2 number wasn't picked...2 or 4 or something. |
Someone gave slices 3 extra data elements completely arbitrarily (yes, pretty bizarre). I thought this was confusing so standardised NPCs to have 3 extras (originally they had 2) as well. I wish we had just one extra, and dictionaries were implemented, then that would be enoguh to store anything. There's no way to decide how many extras there should be.
_________________
"It is so great it is insanely great." |
|
| Back to top |
|
|
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA
Joined: 19 Feb 2003
Posts: 518
Location: Halifax
|
| Posted: Sun May 02, 2010 12:15 am Post subject: |
|
|
No, I've put off the rotation order thing for now :-)
I'm not absolutely 100% sure it's my problem, and the Beast looks good enough to animate for now anyways.
I might investigate at a future point in time just for sake of understanding how these rotations work.
EDIT: I also think that a lot of these problems can be avoided If I use certain combinations of body part rotations. I have three degrees of freedom to work with - so you can do stuff like mimic a 90 deg Rx rotation with a 90 deg Ry and Rz rotation ... if you get my meaning.
I've mostly been working on animating the Beast, but it turns out that I need to be varying a lot (!!!) of parameters to do so, and so scripting can get really clunky. So, I've been trying to make my scripts cleaner and easier to use. I'm not sure I've succeeded in doing so in all cases :-S
Here's an example of some outrageously clunky code.
Don't bother reading it over in detail, but look at how long it is! All this does is makes the beast take a single step forward:
| Code: | SCRIPT, BB Step Right Forward, BBDsl, BEGIN
VARIABLE(torso,lArm,lForearm,lleg,lForeleg,lFoot,
rArm,rForearm,rLeg,rForeleg,rFoot)
torso := BB torso (BBDsl)
lArm := BB lArm (BBDsl)
lForearm := BB lForearm (BBDsl)
lLeg := BB lLeg (BBDsl)
lForeleg := BB lForeleg (BBDsl)
lFoot := BB lFoot (BBDsl)
rArm := BB rArm (BBDsl)
rForearm := BB rForearm (BBDsl)
rLeg := BB rLeg (BBDsl)
rForeleg := BB rForeleg (BBDsl)
rFoot := BB rFoot (BBDsl)
VARIABLE(torso_tr_i,lArm_tr_i,lForearm_tr_i,lleg_tr_i,lForeleg_tr_i,
rArm_tr_i,rForearm_tr_i,rLeg_tr_i,rForeleg_tr_i)
VARIABLE(torso_tr_f,lArm_tr_f,lForearm_tr_f,lleg_tr_f,lForeleg_tr_f,
rArm_tr_f,rForearm_tr_f,rLeg_tr_f,rForeleg_tr_f)
# Beginning to midstep
torso_tr_i := Grab Angle Triplet (torso)
lArm_tr_i := Grab Angle Triplet (lArm)
lForearm_tr_i := Grab Angle Triplet (lForearm)
lLeg_tr_i := Grab Angle Triplet (lLeg)
lForeleg_tr_i := Grab Angle Triplet (lForeleg)
rArm_tr_i := Grab Angle Triplet (rArm)
rForearm_tr_i := Grab Angle Triplet (rForearm)
rLeg_tr_i := Grab Angle Triplet (rLeg)
rForeleg_tr_i := Grab Angle Triplet (rForeleg)
# I got the following angles from playing with the puppet Boulderbeast
torso_tr_f := Create Triplet( 0,0, 3)
lArm_tr_f := Create Triplet( 5,0, 0)
lForearm_tr_f := Create Triplet( 0,0, 0)
lLeg_tr_f := Create Triplet(-10,0, 0)
lForeleg_tr_f := Create Triplet( 6,0, 0)
rArm_tr_f := Create Triplet( -5,0, 0)
rForearm_tr_f := Create Triplet( 0,0, 0)
rLeg_tr_f := Create Triplet( 20,0, 0)
rForeleg_tr_f := Create Triplet(-20,0, 0)
VARIABLE(numSteps,step,anchor)
anchor := Grab tn Triplet(lFoot)
numSteps := 5
FOR (step,1,numSteps) DO(
Interp BB Angles (torso, torso_tr_i, torso_tr_f, numSteps,step)
Interp BB Angles (lArm, lArm_tr_i, lArm_tr_f, numSteps,step)
Interp BB Angles (lForearm,lForearm_tr_i,lForearm_tr_f,numSteps,step)
Interp BB Angles (lLeg, lLeg_tr_i, lLeg_tr_f, numSteps,step)
Interp BB Angles (lForeleg,lForeleg_tr_i,lForeleg_tr_f,numSteps,step)
Interp BB Angles (rArm, rArm_tr_i, rArm_tr_f, numSteps,step)
Interp BB Angles (rForearm,rForearm_tr_i,rForearm_tr_f,numSteps,step)
Interp BB Angles (rLeg, rLeg_tr_i, rLeg_tr_f, numSteps,step)
Interp BB Angles (rForeleg,rForeleg_tr_i,rForeleg_tr_f,numSteps,step)
BB anchor(BBDsl,lFoot,anchor)
wait(1)
END
Destroy Triplets (torso_tr_i,lArm_tr_i,lForearm_tr_i,lleg_tr_i,lForeleg_tr_i,
rArm_tr_i,rForearm_tr_i,rLeg_tr_i,rForeleg_tr_i,
torso_tr_f,lArm_tr_f,lForearm_tr_f,lleg_tr_f,lForeleg_tr_f,
rArm_tr_f,rForearm_tr_f,rLeg_tr_f,rForeleg_tr_f)
# Midstep to endstep
torso_tr_i := Grab Angle Triplet (torso)
lArm_tr_i := Grab Angle Triplet (lArm)
lForearm_tr_i := Grab Angle Triplet (lForearm)
lLeg_tr_i := Grab Angle Triplet (lLeg)
lForeleg_tr_i := Grab Angle Triplet (lForeleg)
rArm_tr_i := Grab Angle Triplet (rArm)
rForearm_tr_i := Grab Angle Triplet (rForearm)
rLeg_tr_i := Grab Angle Triplet (rLeg)
rForeleg_tr_i := Grab Angle Triplet (rForeleg)
# I got the following angles from playing with the puppet Boulderbeast
torso_tr_f := Create Triplet( 0,0, 6)
lArm_tr_f := Create Triplet( 10,0, 0)
lForearm_tr_f := Create Triplet( 0,0, 0)
lLeg_tr_f := Create Triplet(-20,0, 0)
lForeleg_tr_f := Create Triplet( 12,0, 0)
rArm_tr_f := Create Triplet(-10,0, 0)
rForearm_tr_f := Create Triplet( 0,0, 0)
rLeg_tr_f := Create Triplet( 12,0, 0)
rForeleg_tr_f := Create Triplet( -4,0, 0)
FOR (step,1,numSteps) DO(
Interp BB Angles (torso, torso_tr_i, torso_tr_f, numSteps,step)
Interp BB Angles (lArm, lArm_tr_i, lArm_tr_f, numSteps,step)
Interp BB Angles (lForearm,lForearm_tr_i,lForearm_tr_f,numSteps,step)
Interp BB Angles (lLeg, lLeg_tr_i, lLeg_tr_f, numSteps,step)
Interp BB Angles (lForeleg,lForeleg_tr_i,lForeleg_tr_f,numSteps,step)
Interp BB Angles (rArm, rArm_tr_i, rArm_tr_f, numSteps,step)
Interp BB Angles (rForearm,rForearm_tr_i,rForearm_tr_f,numSteps,step)
Interp BB Angles (rLeg, rLeg_tr_i, rLeg_tr_f, numSteps,step)
Interp BB Angles (rForeleg,rForeleg_tr_i,rForeleg_tr_f,numSteps,step)
BB anchor(BBDsl,lFoot,anchor)
wait(1)
END
Destroy Triplets (torso_tr_i,lArm_tr_i,lForearm_tr_i,lleg_tr_i,lForeleg_tr_i,
rArm_tr_i,rForearm_tr_i,rLeg_tr_i,rForeleg_tr_i,
torso_tr_f,lArm_tr_f,lForearm_tr_f,lleg_tr_f,lForeleg_tr_f,
rArm_tr_f,rForearm_tr_f,rLeg_tr_f,rForeleg_tr_f,anchor)
END |
You might also notice that most of those commands are scripts that I had to define in order to make coding more manageable.
It took forever, but I just finished this walking script (like ... right now), and it works!!! He walks! I haven't had any problems with frame rates ... not that I noticed.
I can make him march around the screen, and turn 90 degrees with the arrow keys. I'm going to update the Tech demo shortly so that you can switch between "puppet mode" and "walkabout mode".
Okay - I think I get what's going on with that OpenGL stuff ... although I'll need to look at it again when it's not 4:30 in the morning.
For if/when you choose to look at my scripts, I'll explain my use of slices.
All of the visible Boulderbeast sprites are stored in a single container named BBslice. These slices don't store any information, they're simply positioned, and are sorted according to their 3D y coordinate (which is calculated and stored elsewhere). There's maybe ... 25 of these sprites.
I have a separate set of slices which I use for data storage. The root is named BBDsl (Boulderbeast data slice). This slice stores info on the BB's body. It has three children: Torso, lLeg and rLeg which each have their own children like so:
BBDsl
|-Torso
|.|-Head
|.|.|-Face
|.|.|-LEye
|.|.|-rEye
|.|-LArm
|.|.|-LForearm
|.|.|.|-LHand
|.|.|.|-LElbow
|.|.|-LBicep
|.|.|-LShoulder
|.|-rArm
|.|-|-rForearm etc ...
|.|-Upper back
|.|-Lower back etc ...
|-LLeg
|.|-LForeleg
|.|.|-LFoot
|.|.|-LKnee
|.|-LHip
|-rLeg etc ...
Only the leaves of this tree structure correspond to a visual sprite of the Boulderbeast, and they store the sprite's handle. They also store the x.y.z components of a vector which describes the body part's position with respect to its parent when the Boulderbeast is in a neutral standing position. I called this "Home Position".
The non-leaf slices also store a home position vector, as well as a set of 3 angles (which are defined w.r.t. the parent slice).
When positioning a given slice, I rotate its home coordinates using the parent's angles. The rotated home coordinates are then added to the parent's (already calculated) actual position to give the slice's actual position. A slice's angles are calculated by adding its designated angles to its parent's angles.
So, I've been using slices to store sprite handles, home coordinates, and angles.
If I implement the simple harmonic oscillators, I'll need to store at least another 9 values in each slice-leaf, which means adding more child data slices.
If arrays could be stored in extras, I'd need way fewer slices. I'd be using maybe 40-50 rather than ... oh, I don't know, 200-250. My data slice structure is set to visible=false, so I don't need to waste time computing their position and so on.
Did you experience any problems with slowdown or anything? I haven't.
_________________
Working on rain and cloud formation |
|
| Back to top |
|
|
|
|
You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
