Procedurally generated trees in JavaScript

Over the past year I've been more and more interested in HTML5 canvas, since it allows very fast development of graphical animations using JavaScript.

Another thing that has always amazed me was procedurally generated content. Check out Steven Wittens' "Making worlds", a wonderful article on generating planets from orbit to aerial zoom.

So I decided to create a 2D tree generator in JavaScript, you can take a look at it to know exactly what I am talking about.

Before we move any further let me say that this article is aimed at people with experience using HTML5's canvas and JavaScript.

Starting up

I don't have any template for starting a new canvas project, but I do have some guidelines I like to follow. Below is the usual starting point

  1.  
  2. $(document).ready(function(e) {
  3. var ctx;
  4. var WIDTH;
  5. var HEIGHT;
  6.  
  7. var canvasMinX;
  8. var canvasMaxX;
  9.  
  10. var canvasMinY;
  11. var canvasMaxY;
  12.  
  13. var ms = {x:0, y:0}; // Mouse speed
  14. var mp = {x:0, y:0}; // Mouse position
  15.  
  16. var fps = 0, now, lastUpdate = (new Date)*1 - 1;
  17. var fpsFilter = 100;
  18.  
  19. ctx = $('#bg')[0].getContext("2d");
  20.  
  21. ctx.canvas.width = window.innerWidth;
  22. ctx.canvas.height = window.innerHeight;
  23.  
  24. WIDTH = $("#bg").width();
  25. HEIGHT = $("#bg").height();
  26. resizeCanvas();
  27.  
  28. canvasMinX = $("#bg").offset().left;
  29. canvasMaxX = canvasMinX + WIDTH;
  30.  
  31. canvasMinY = $("#bg").offset().top;
  32. canvasMaxY = canvasMinY + HEIGHT;
  33.  
  34. function clear() {
  35. ctx.clearRect(0, 0-HEIGHT/2, WIDTH, HEIGHT);
  36. }
  37.  
  38. function circle(x,y,rad,color){
  39. ctx.fillStyle = color;
  40. ctx.beginPath();
  41. ctx.arc(x,y,rad,0,Math.PI*2,true);
  42. ctx.closePath();
  43. ctx.fill();
  44. }
  45.  
  46. function fade() {
  47. ctx.fillStyle="rgba(0,0,0,0.01)";
  48. ctx.fillRect(0, 0, WIDTH, HEIGHT);
  49. }
  50.  
  51. function resizeCanvas(e) {
  52. WIDTH = window.innerWidth;
  53. HEIGHT = window.innerHeight;
  54.  
  55. $("#bg").attr('width',WIDTH);
  56. $("#bg").attr('height',HEIGHT);
  57. }
  58.  
  59. function mouseMove(e) {
  60. ms.x = Math.max( Math.min( e.pageX - mp.x, 40 ), -40 );
  61. ms.y = Math.max( Math.min( e.pageY - mp.y, 40 ), -40 );
  62.  
  63. mp.x = e.pageX - canvasMinX;
  64. mp.y = e.pageY - canvasMinY;
  65. }
  66. $(document).mousemove(mouseMove);
  67. $(window).resize(resizeCanvas);
  68. });
  69.  

I know this is not optimized, and defines all variables inside the global namespace, but I like to start with a very quick prototype before I improve code design. I also use jQuery, although only for event binding such as window resize. As for the HTML, I simply start with a blank page containing a canvas element.

The idea

The goal is to have JavaScript generate 2D trees. At first I will generate only "naked" trees, with no leaves. Canvas doesn't really have many drawing methods, we can create lines, curves, and basic shapes. Since trees aren't really curvy but tend to suddenly turn and then go straight for a while (I am thinking of this kind of tree) I have decided to use lines.

Another requirement is that we start with a thick line, until we reach final branches which should be really thin. In order to fulfill these requirements and still use a simple method I have come up with the idea of stacking lines, as if they were rectangles. The nice thing about that is that we don't need to calculate the corners, only the initial and ending point, and if we use a very small length, stacking very thin rectangles, it will almost look line one long line that is twisting.

Getting this to work

So off we go, just for now I will test the idea with a loop that draws small segments all in a row, introducing a little variation on the next point's coordinates, with an initial width of 20 for example, and reducing it by a small quantity on each iteration. We should get a long wiggly line getting thinner until it "dies" at the end. I have extracted all useful variables to outside the function so that we can easily configure it.

  1.  
  2. var loss = 0.1; // Width loss per cycle
  3. var sleep = 10; // Min sleep time (For the animation)
  4. var branchLoss = 0.9; // % width maintained for branches
  5. var mainLoss = 0.9; // % width maintained after branching
  6. var speed = 0.3; // Movement speed
  7. var scatterRange = 5; // Area around point where leaf scattering should occur
  8.  
  9. // Starts a new branch from x,y. w is initial w
  10. // lifetime is the number of computed cycles
  11. function branch(x,y,dx,dy,w,lifetime){
  12. ctx.lineWidth = w-lifetime*loss;
  13. ctx.beginPath();
  14. ctx.moveTo(x,y);
  15. // Calculate new coords
  16. x = x+dx;
  17. y = y+dy;
  18. // Change dir
  19. dx = dx+Math.sin(Math.random()+lifetime)*speed;
  20. dy = dy+Math.cos(Math.random()+lifetime)*speed;
  21. //
  22. ctx.lineTo(x,y);
  23. ctx.stroke();
  24. if(w-lifetime*loss>=1) setTimeout(function(){ branch(x,y,dx,dy,w,++lifetime); },sleep);
  25. }
  26.  

Generated tree step 1

Figure 1: Initial development

To execute we simply need to call branch(WIDTH/2,HEIGHT,0,-1,15,0), although you can change however you want the first 4 arguments. lifetime should start in 0, since it is the cycle counter. I've used the sleep variable to control how long it waits before drawing the next line, this way you get a sense of real drawing. If you set it to 0 the tree simply appears.

As you can see in Figure 1 the technique of stacking lines works very well, it even gives a little texture to the tree. We should now add some branches, the idea here is to treat the branches as new "trees", thus reusing the function branch.

In order to generate a new branch we must wait until the tree has grown enough, branches usually start 1-2 meters above ground. Since this a recursive function we don't know much on each iteration, that's why I'm using the variable lifetime. If we use lifetime along with the current width of the tree, we can know exactly the percentage of growth, in order to start a new branch.

After some testing I've ended up with this condition: w-lifetime*loss < 9. If that is met we will start a new branch, although that would mean that after that point is reached we will always start a new branch. To avoid that we add a little randomness by using: Math.random()>0.7, supposing Math.random() returns a real random number the chances of that being true are almost 30%.

  1.  
  2. if(w-lifetime*loss < 9 && lifetime > 30+Math.random()*250){
  3. setTimeout(function(){
  4. branch(x,y,2*Math.sin(Math.random()+lifetime),2*Math.cos(Math.random()+lifetime),(w-lifetime*loss)*branchLoss,0);
  5. // When it branches, it loses a bit of width
  6. w *= mainLoss;
  7. },sleep*Math.random()+sleep);
  8. }
  9.  

Step two

Figure 2: Fully developed tree

I have added some randomness to the direction in which branches start to grow by using a sine and cosine along with a random number and the current lifetime. That should give us a random direction from -1 to 1 in both axis. mainLoss is a coefficient that determines how much width is lost by the main branch.

We should now have a working tree generator, although some variable tweaking is required to get the shape right. Once I got the variables and function a little improved I moved everything to an object, so that I could use dat.gui and control the variables more easily (and also because JS people love experiments with dat.gui)

By now branches work fine (Figure 2), I've added a little jQuery snippet that will call the function branch whenever I click, generating a new tree at the x coordinate of the click.

Now that it is working pretty well I have finished improving the code, and ensuring that almost everything is configurable via variables controlled by dat.gui. In that sense it is a very good framework for prototyping and experimenting with your tests. I would like to use some sort of genetic algorithm to find the best combination of values for tree generation, but writing the fitness function is quite challenging in this case.

Please check out the final version at nuostudio's lab, it has many options that are quite fun to play with.

The next thing I'd like to do would be to use some 3D library (probably three.js) to create a "forest", and probably improve the realism of the generated trees.

Conclusion

JavaScript provides an amazing engine for graphic development, on most computers it runs really fast, this generator in particular can handle 20-30 trees being generated simultaneously with almost no hiccups.

One thing that JavaScript is still lacking, a lot, is thread support, which would be really useful for a project like this.

HTML5 canvas is an amazing technology, and after working with it for a while you realize that it probably is the future of graphics on the web.

A colorful forest

About Alex

Hello! I'm Alejandro U. Alvarez, an engineering student at Universidad de Oviedo (Spain). I started programming during my Freshman year in Brookline High School (Boston, MA), and then got more and more interested in web development. I'm almost in love with JavaScript, although I keep an open mind with other languages

Leave a Reply