Friday, May 13, 2011

The Forest

If a voxel tree falls down in a voxel forest, does it make a sound? What if it is voxel Hellen Keller the one who falls?

Now that I had different tree species I began considering how to assemble them in a forest. In earlier screenshots and videos you could see some trees around, but they were just scattered randomly. A forest is something more. Even if it is not apparent at a first glimpse, there is some order and rules.

This post is about how I did it. I will start with a render of my first forest ever. The following image shows two different species of trees, one tall, one short, interacting together. As you may notice, while there is some randomness to it, there is also some order. Often trees of the same type appear closer to each other, but not necessarily every time.


Again the folks at http://algorithmicbotany.org/ had a pretty good idea of how to do this. There is one article about forests that helped a lot.

The approach is to simulate the forest for a long period of time, a few centuries maybe. This does not take much, since it is possible to do it in increments of many years at once.

The terrain is seeded randomly, but according to the odds for each species to prosper on a given location. Some species do not do well in high slopes, or some may get a boost from one particular type of terrain. The seeds are spread very close one to another. I found that a two-meter size grid was enough to produce realistic results.

Then the simulation starts. Each tree grows at every iteration. When a tree touches a neighboring tree, one of the two will subside. Usually the large tree will kill the smaller one. A tree will grow until it reaches its mature size.

On each turn mature trees spread their seed. A parameter in the tree class determines how far the seed can go, and what are its odds of surviving. If the seed lands on a open point in the grid, a new tree starts there.


The previous image shows the results of this algorithm over a few square kilometers of terrain. To show the properties of the algorithm, the terrain properties have no effect in this particular simulation. This is the result of 10 iterations over 300 years.

Only four tree classes appear here, but it is enough to perceive there is some character to how they spread over the land. The black dots are from a very aggressive species and will take any space they can. The cyan dots have still survived this and they have arranged themselves in some sort of vein-like pattern. The red dots belong to a species that is very large and grows fairly fast. Red dots also live longer. And you can see some yellow dots, this is a species that is doesn't compete that well so it depends on mostly on luck.


This is a fairly simple and fast method. It is somewhat reminiscent of cellular automata in the sense a tree will only interact with the neighboring space. Any order that may appear out of this is just emergent behavior. While the approach is local, it is possible to control global features by feeding different maps and having the tree classes react to it.

Once tree classes become aware of global parameters like terrain height, slope, abundance of water, shade, type of ground, even proximity to architecture, it is possible to have a single forest simulation cover the entire world. The global parameters would make a thick jungle develop in moist low grounds, while high altitudes will be covered mainly by pine trees (no, I still cannot do pine trees).

This is what I like the most about this approach. It produces a single organic layer. Even when there is a transition between different zones, it is still governed by the same rules. 

Is this the silver bullet method for forest generation? So far it looks like that.


5 comments:

  1. In answer to you first question: I hope not, that would be inefficient :P

    Seriously though, great blog. I've been fascinated with this particular topic for decades and I've done lots of experiments myself; I'd love to have a chat about your ideas.

    ReplyDelete
  2. @Kerrash: Thanks, you can reach me at my gmail account, or post right here if you want others to read our exchange.

    ReplyDelete
  3. Still lovin your stuff man. Ive gotten alot further along in my terrain generation and noise algorithms and learned that most of the questions I posed to you were obsolete before I even implemented them haha. But thank you for the input and patience. I also learned that I am not interested in using marching cubes since my game is gonna be blocky like minecraft, but I learned alot by following the marching cube academic path. I didn't realize that the marching cubes was a way to make smooth polygons from voxel data, I thought that it would make blocks. I guess the best way to learn is to do. Your organic growth stuff is awesome though I love how in depth you are. One day I hope to be as knowledgeable as you about it.

    ReplyDelete
  4. Thanks Corey. When can we see some of your stuff?

    ReplyDelete
  5. you should take a look into fractal maths , nature and the golden ratio .... its seems they found connections between the mathematics that determines growth of branches to the math that determines how the whole forest is distributed ... i guess nature works a lot with that golden ratio , The golden ratio, mathematically represented as the Greek letter phi (φ) is 1 : 1.618, or more precisely ....

    ReplyDelete