Procedurally Generating Trees

When I first decided that I was going to procedurally generate some trees I had no idea what I was about to step into. I had a rough idea of how I was going to do things, but little did I know, there were some pre-existing algorithms out there. I had a very rough idea of where I wanted to go with my algorithm, here’s what I decided on:

  1. Draw a line of arbitrary length to represent a trunk
  2. Draw a line parallel, if the line is to the left hand side of the trunk, split it off to the left for a random distance before making it grow up again
  3. Continue this until the tree has reached a certain number of lines in width
  4. Draw leaves randomly from the trunk to the outermost branches

Screen Shot 2017-05-17 at 13.37.23

This wasn’t working, whilst the premise was good I was having a tough time actually implementing it, so I took to the internet in search of a better approach. I found out about something called L-systems, these were built to model plants, if you haven’t heard of L-systems before you should do a quick google search on them, they’ve got a pretty interesting history, but I won’t go into that in this post.

L-systems are pretty simple. You start with an ‘axiom’, which we can view as the ‘seed’ of our tree. The axiom is then fed into a set of rules, to produce a product. You can then feed the product back into this set of rules a number of times, and this will produce a value that can be used to determine how to model your tree.

So, if, for example we had the following values:

var axiom = 'a';
rules = {
    a: 'bc',
    b: 'ac',
    c: 'ad',
    d: 'ea',
    e: 'a'
};

And we ran our axiom through the rules once, we would have a product:

1: bc

Continuing to run the product through our rules for another five iterations:

2: acad
3: bcadbcea
4: acadbceaacadabc
5: bcadbceaacadabcbcadbceabcacad
6: acadbceaacadabcbcadbceabcacadacadbceaacadabcacadbcadbcea
7: bcadbceaacadabcbcadbceabcacadacadbceaacadabcacadbcadbceabcadbceaacadabcbcadbceabcacadbcadbceaacadbceaacadabc

As you can see, for each character in the string, the rules are applied (replacing the character with those specified in the rules) to produce another product, which grows in length with each iteration.

You can see a working JSFiddle here if you want to play with the rules yourself and mess with the axiom.

OK, so now that we’ve got that out the way we have something to work from. Now, we can decide what each of these characters mean in a string. We’ll take a look at how we can translate our string into a drawing. The easiest way of turning an L-system into a drawing is to use what’s called a ‘turtle’ engine.

A turtle engine will essentially act like a robot that carries out directional commands like move forward, turn left, turn right, etc.

For our purposes, we’ll use the following rules:

a: Draw Forward,

: Rotate Right,

[: Save our current location

]: Return to the saved location

Now we need to start drawing. We’ll start much the same as we did in the first instance, by drawing a ‘stump’, we can use the axiom for this.

We’ll start off by specifying a starting location and a direction, and then follow our axiom’s command.

Let’s start again in the middle of the screen at the bottom, we’ll say that we should always draw a number of pixels ahead, for this example, I’m using 80 pixels as my length; here’s where we’re at:

Screen Shot 2017-05-17 at 12.05.01

So now we have our trunk, we can start to build out the rest of the tree, but to do this, we have to come up with a good set of rules for our L-System.

For our purposes, I’ve just decided that I’m going to specify one rule:

a -> a[>a][<a]

So whenever we encounter an ‘a’ in our string, we’ll replace it with the string shown above.

This produces a tree that looks like this:

Screen Shot 2017-05-17 at 12.13.49

Now I’ve managed to gloss over the code here, so we’ll take a second to talk about that.

I cleaned up my code for the L-System a bit for use in this project.

var axiom = 'a';
var iterations = 5;

var rules = {
 a: 'a[>a][<a]'
};

function evaluate(product) {
  var production = '';
  for(var char of product) {
    var p = rules[char];
    if(p != undefined) {
      production += p;
    } else {
      production += char;
    }
  }
  return production;
}

The code is fairly self-explanatory and similar to the code in the fiddle linked above, the only major difference is that because we don’t have definitions of rules for every character in the alphabet, we have to check whether our rule lookup returns anything or not. If it does, we’ll add that on to the new product, if not, we just add the current character on.

Now to talk about the drawing code, as discussed before, I implemented a turtle system, using p5, this was quite simple.

for(var x = 0; x < iterations; x++) {
  product = evaluate(product);
  len *= 0.65;
  for(var y = 0; y < product.length; y++) {
    if(product[y] == 'a') {
      line(0, 0, 0, -len);
      translate(0, -len);
    }
    if(product[y] == '<') {       rotate(-Math.PI/6);     }     if(product[y] == '>') {
      rotate(Math.PI/6);
    }
    if(product[y] == '[') {
      push();
    }
    if(product[y] == ']') {
      pop();
    }
  }
}

Again, this code is fairly self-explanatory, it basically follows the rules that we set out.

It was quite fun to play with the values, for example, if I changed the amount that I rotated the cursor to

Math.PI / 3

I would end up with some cool looking hexagonal trees like this:

Screen Shot 2017-05-17 at 12.15.15

Changing the ‘len’ adjustment gave me some cool results as well:Screen Shot 2017-05-17 at 12.36.33

Using random values for this would probably give you some really cool results. You could also try to draw multiple trees instead of just one.

Here’s a working so you can have a play with it, some of the lines are commented where changing the values gives more interesting results.

Now whilst this looks good, and I could definitely generate a bunch of trees like this and put them side by side and create my own little forest, I still think it’s just going to look a bit too uniform. It doesn’t quite represent nature. This could be fixed in a number of ways, like changing my rules, or playing with the values, but there’s a better way.

Whilst reading up on algorithms for generating trees, I stumbled across something called a space colonisation algorithm, and apparently they’re really good at generating trees. In fact, if you search ‘Space Colonisation Algorithm’, there’ll be a lot of results that link to creating trees.

A space colonisation algorithm is based on a simple premise. We essentially take an area and plot random points within that area. We then start building out a tree trunk from it’s source towards the area that is filled with random points. When the trunk is tall enough, we can finally get to the meat of the algorithm. We know the trunk is tall enough because it is within a certain distance of one of our points, which we can consider ‘leaves’.

The algorithm then switches it’s focus and begins to look at our ‘leaves’. We then find the nearest branch for each leaf that is within range of the branch, and begin to ‘pull’ that branch towards this leaf. When the branch gets too close to the leaf, the leaf disappears. This is continued until no more leaves are left and we’ll have a nice winding natural looking tree.

We’ll explore the implementation details of that algorithm now.

So, to start, I want to generate a set of random points in a range.

Screen Shot 2017-05-17 at 14.12.55

In a 640 x 480 window, we’ve generated 100 points randomly in a range.

The next step is to start adding branches. This bit was really difficult for me to wrap my head around, but I got there eventually with the help of this video. Essentially, the process is to add a branch node, and then for each of our leaves we need to check if the newest branch node is within range of the leaf. If it isn’t we add another one, but if it is, we can stop there and move on to the next part of the algorithm.

Screen Shot 2017-05-17 at 15.46.44

We now have a tree trunk, and we can almost see a very rough tree shape coming from it. There’s plenty of ways to render the ‘branches’ and the ‘leaves’, although we’ll just stick to a yellow line for the branches and green dots for the leaves.

The next step is to start pulling the branches in the direction of the leaves. So, for each leaf, we can find the closest branch that’s in range.

If a branch is in range, then let’s check if it’s closest. If it is the closest, we need to add a pulling force onto the branch in the direction of that leaf. We continue to do this until all of our leaves have been ‘found’ by branches.

Here’s the final product:

Screen Shot 2017-05-17 at 17.25.06

There’s a lot more that can be done with this but I’m on the right track now. Here’s a working codepen to play with:

Interestingly enough, these algorithms aren’t only useful for generating plants, they’re also very useful for generating road networks, or trade networks, which means that you could, for example, specify a bunch of points on a map that would represent cities and link them up using a space colonisation implementation or an L-system implementation (or a hybrid if you’re brave enough).

 

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s