Have you ever tried to generate a natural-ish looking tree? I did it for a coursework assignment and turns out it's both incredibly simple while being full of strange little twists.
Generally the assignment was about manipulating 3D objects in OpenGL through user action. Otherwise known as: make a game, if it isn't a game, you're likely doing it wrong.
Since we had the whole semester to work on it, I spent nearly all of it on a little piece of the whole puzzle that seemed the most interesting - Generating trees.
Of course me and my partner both being avid dislikers of Java and Java sort of being what the class is taught in ... well we decided both to pick our favourite dialect of a functional language running on a JVM.
Scala and Clojure.
Fun ensued, but we actually did get it working and now half the project is in one language, half is in another and neither of us can read the other's code.
While @hairyfotr took care of pretty much anything, I took it upon myself to generate the data for having pretty trees that are a bit random, but always manage to look like a beautiful beautiful tree.
A night of hacking or three later, we had this:
As you can see, it wasn't so much a tree as a bunch of weird random looking lines without any sort of order to them.
Turns out not only was I calculating the tree all wrong and possibly even providing the incorrect data structure, @hairyfotr wasn't very adept at drawing what I did manage to generate either.
But eventually after quite a bit of hacking, it got better. I learned a lot about linear algebra and not being an idiot, @hairyfotr learned how to traverse a tree data structure. In the end, everyone is happier and this is what the final trees look like ... I reckon they're pretty damn shiny.
The generator
In general the idea on how to generate trees is pretty simple. You take a vector representing the direction of a branch and its length. Then you move to the end of the branch, make N new directional vectors and give them a length. Then you simply repeat the process on every branch.
Simple right?
PS: lest your eyes glaze over, there's a sketch explaining all of this at the bottom
It is. But it gets a bit complicated when you want this bunch of vectors to actually resemble something. The first concern is spacing child branches out evenly. You can think of this as a problem of evenly dividing a half sphere into N chunks.
My first approach to this failed spectacularly. I tried to take the current branch as a normal to a plane, then drawing a vector between the end of the current branch and the made up point. This would give me a perpendicular vector to the original branch. Then all you need to do is rotate this perpendicular vector around X times, using the original branch as the rotation axis.
This gives you an evenly sliced plane perched on top of the current branch. Then all you have to do is slant each new branch upwards by a certain angle and you're done. Since upwards can mean anything, you take it to mean the direction the original branch was pointing in.
Turns out this approach is brilliant, except for that calculating a plane and points and such. That is just way too concrete and not abstract enough. It doesn't really work ... to make it work you'd need data outside of the "direction of current branch" scope.
So what you do instead is this: take the current branch and make up a vector. It doesn't really matter what it is, as long as it's different from the branch. Then you calculate the cross product between the branch and the made up vector and voila. You have your first perpendicular child branch.
Then you just do the whole rotation bit.
This approach works surprisingly well. But it only ever gives you one tree and that doesn't do.
So in order to get random trees that still look like trees I made use of a very simple trick. When choosing the angle by which to turn a branch upwards, just make the angle be chosen by some sort of weighted random choice. A bit of twiddling around and everything was nice and shiny. When everything conspires just right, you even get those long branches with others splitting off of them ... even though the tree itself thinks on every level all the branches split.
It's just bloody elegant I tell you!
And when doing the rotations around the original branch I add a little noise to the angles, just a few degrees so the spacing isn't always perfectly even.
But, here comes the real beauty. When choosing how many new branches to create on every level, I just follow the progression of prime numbers. So, on the first level there are two branches, then three, then five and so on.
I use a similar progression for calculating the length of every next branch. There it's actually 1-0.prime. It works marvelously.
But this is quite a bit of text that probably doesn't make any sense to anyone. So here's a quick whiteboard sketch of what's going on:
Next step in making it even awesomer is probably applying some randomness to branch lengths.
You can also see the source for this on github.
Continue reading about Using prime numbers to generate pretty trees
Semantically similar articles hand-picked by GPT-4
- Implementing a weighed random choice in Clojure
- Animating 2048 SVG nodes in React, Preact, Inferno, Vue, Angular 2, and CycleJS – a side-by-side comparison
- Evolving a poem with an hour of python hacking
- Fractals in React
- Livecoding #38 - A faux AI that writes JavaScript
Learned something new?
Read more Software Engineering Lessons from Production
I write articles with real insight into the career and skills of a modern software engineer. "Raw and honest from the heart!" as one reader described them. Fueled by lessons learned over 20 years of building production code for side-projects, small businesses, and hyper growth startups. Both successful and not.
Subscribe below 👇
Software Engineering Lessons from Production
Join Swizec's Newsletter and get insightful emails 💌 on mindsets, tactics, and technical skills for your career. Real lessons from building production software. No bullshit.
"Man, love your simple writing! Yours is the only newsletter I open and only blog that I give a fuck to read & scroll till the end. And wow always take away lessons with me. Inspiring! And very relatable. 👌"
Have a burning question that you think I can answer? Hit me up on twitter and I'll do my best.
Who am I and who do I help? I'm Swizec Teller and I turn coders into engineers with "Raw and honest from the heart!" writing. No bullshit. Real insights into the career and skills of a modern software engineer.
Want to become a true senior engineer? Take ownership, have autonomy, and be a force multiplier on your team. The Senior Engineer Mindset ebook can help 👉 swizec.com/senior-mindset. These are the shifts in mindset that unlocked my career.
Curious about Serverless and the modern backend? Check out Serverless Handbook, for frontend engineers 👉 ServerlessHandbook.dev
Want to Stop copy pasting D3 examples and create data visualizations of your own? Learn how to build scalable dataviz React components your whole team can understand with React for Data Visualization
Want to get my best emails on JavaScript, React, Serverless, Fullstack Web, or Indie Hacking? Check out swizec.com/collections
Did someone amazing share this letter with you? Wonderful! You can sign up for my weekly letters for software engineers on their path to greatness, here: swizec.com/blog
Want to brush up on your modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com
By the way, just in case no one has told you it yet today: I love and appreciate you for who you are ❤️