I’m excited to post my first Cool Creation!
TreeEngine: A Pipeline for Generating Trees
Procedural tree generation is almost a rite of passage for beginners looking to explore procedural generation and computational geometry. However, most folks stop after generating a simple fractal tree. Others stop at generating a few types of trees. But I had the question:
Could I generate all the trees?
…with all the trees being not just any reasonably tree-shaped tree, but also at any point in its lifetime.
With the help of data structures, component-oriented design, and patience, the answer was, “well, this is a good start!”
For those who don’t want to stick around for the nerd rabble…
You can check out the demo here.
Or, if you can’t be bothered, check out these pretty gifs:
Figure 1: Finished Tree
Figure 2: Attachment System Demo
Figure 3: In Dev Gif
Figure 4: In-Dev Gif
Trees All the Way Down (The Data Structure Kind)
So, how do we generate all the trees?
Making a procedural tree at its full growth state is rather trivial; a recursive function can be used to create a set of branches. However, if we want to ‘grow’ the tree continuously or simply create a tree at a different point in its lifetime, we can’t rely on a one-shot function to create the tree. We need a way to represent a finished copy of the tree, and then build it piece by piece based on its growth state.
The growth effect was achieved by making a library of “components” that represented a tree, and then organizing those components in a tree data structure. Components in TreeEngine not only represent the base structure of a tree, but they also define the properties of those base structures as a function of age. For example, the length of a branch is defined (by default) with the function…
length = 0.5 * sin( age * π - (π / 2)) + 0.5
…where age is represented as a number within the range [0, 1], with 0 being just planted and 1 being fully grown. As these components are setup in a flexible object-oriented environment, more specific types of branches with different growth curves can be easily implemented as the project scope demands it.
TreeEngine ended up having four base components…
- TEComponent: A base class that all components derive from.
- TEBranch: Represents a generalization for a branch.
- TEAttachmentPoint: Represents something that attaches to a point on a branch, like a fruit or leaf.
- TEFruit: Just because the game that will use this tree generator needs a way to independently control the state of growth of the crops on the tree, a subclass of TEAttachmentPoint was created to make this distinction.
Then, to create a tree, we first build a model of the tree in memory by creating a hierarchy of instances of the above components. The following diagram is a visualization of the relationships of different components. Excuse my “programmer art”
This method of organizing data happens to be called a tree. 
Once we have the tree in memory, a special “parser” rendering function navigates the component hierarchy and selectively creates parts for the tree based on its current age. A model of an existing tree can also be inputted into this function, and if provided, the parser will reuse any existing parts to save on performance.
For those interested, the tree rendering function uses a breadth-first tree traversal to render each part of the tree. The traverser skips any parts that should not be rendered at the given age.
With the combination of all of these techniques, you get a tree!
For those of you wondering, cocoa trees are the only trees I included in the rendering demo because the project I am working on demands Cocoa trees before any other tree. Not my choice!
Next Steps
Well, now I have this lovely toolbox to generate all sorts of trees. I’m likely going to use this framework to create more types of trees in the near future.
Until then, this will be added to a certain game in the near future.
And that’s it!
Thanks for reading!
Is this open source?
No, nor will it likely ever be. This is proprietary. However, if you’re interested in making something like this, or just have any general conceptual questions pertaining to computational geometry or computer science, don’t hesitate to reach out! As long as you’re the one writing the actual code, I have no problem talking for hours about to conceptually accomplish stuff like this!
Acknowledgements
@gdunn2 , @mutex_lock , and @Elocore for bringing me onboard their team and being content with my pursuit of all of the trees!
@overflowed for being an awesome programmer and frequent sounding board for ideas and issues.