# How can I animate a recursive algorithm?

Say I have a recursive algorithm, for example one that generates a random tree:

// Pseudocode, just a simple algorithm: it isn't perfect.
function generate_branch(angle, length, current_depth, max_depth) {
var branch = Branch(angle, length); // creates a new branch
if (current_depth == max_depth) {
return branch;
}
current_depth++;
// random_int(min, max)
branch.subbranches[] = generate_branch(random_int(0, angle + random_int(-30, 30)),
random_int(0, 20)
current_depth,
max_depth);
// ^^^^ recursion
return branch;
}

var trunk = generate_branch(0, random_int(10), 0, 5);
RenderTree(trunk);


The problem is that this will render the entire tree in one frame. If I want to animate this (i.e. grow the tree over time), how would I do that? What is the best way to do this?

The game uses a game loop.

You store the current depth of every branch for each node, and append Rendertree to render all nodes up to a specific depth, given as a parameter.

This way, you can show each depth level seperatly.

Pseudocode could be like this:

Generate tree

While(GameLoopRunning)
begin
for i := 0 to maxdepth do
begin
RenderTree(trunk, i)
delay(250); //should not be like this, will block entire game loop.
end
end


Edit: You might want to use some kind of timer to fire some kind of GrowNow!-Events to your game logic in order to avoid the for-loop and delay in your main game loop.

• Good idea. I can put the "GrowNow!-Event" in the Step() method of the tree. Thanks for the feedback. – rightfold Sep 8 '11 at 14:19
• You could also have the generation and drawing on seperate threads. – Jonathan Connell Sep 9 '11 at 11:55

What you can do is save a stack of the process you need to do (with all the parameters and depth), and only process one branch at a time, which will add one or more other branch to the stack.

This way you'll draw one step at a time. Of course you can choose to process more than one branch from the stack at a time or wait a delay between each process.