# Algoritm for placing trees and bushes

## Recommended Posts

endasil    138
I need to find a way of placing trees and bushes automatically over a terrain. Just using normal random to generate x and z values really make things look unnatural. So i am looking for a way of generate a more natural looking spread on things.

##### Share on other sites
venzon    256
You might be able to find some info here:
http://www.vterrain.org/Plants/distrib.html
and some specific approaches are shown here:
http://www.vterrain.org/Plants/Papers/index.html

##### Share on other sites
yahastu    154
Here is a simple method that will give you a good effect.

1) Create a Perlin noise texture
2) Iterate over the texture in raster scanline order. At each point, if "rand > intensity" then put a tree at that point with some random offset.

##### Share on other sites
Well you could for example generate a randomX and a randomY variable. Place a tree at that position, and then make like 10 other random variables (small numbers) so you can place bushes around the trees. Maybe you want to make an algorithm to cluster trees together instead of just placing them everywhere at random

So I would do it like this (my syntax can be horribly wrong)

forestPositionX = rand() % 255;forestPositionY = rand() % 255;for (int x = 0; x < 100; x++) {//generating treesTreeOffsetX = (rand() % 50) - 10;TreeOffsetY = (rand() % 50) - 10;PlaceTree(forestPositionX + TreeOffsetX, forestPositionY + TreeOffsetY);for (int y = 0; y < 3; y++) {BushOffsetX = (rand() % 5) - 10;BushOffsetY = (rand() % 5) - 10;PlaceBush(forestPositionX + TreeOffsetX + BushOffsetX, forestPositionY + TreeOffsetY + BushOffsetY);}}

I have no idea how you're calculating the Z positions of every tree/bush, so you'll have to incorporate that on your own :)

##### Share on other sites
drakostar    224
Quote:
 Original post by MadMax1992I have no idea how you're calculating the Z positions of every tree/bush, so you'll have to incorporate that on your own :)

Typically, y = 0 is the ground plane in a 3D engine. So you'd randomize x and z, then align y to your terrain.

Here's an interesting excerpt from a Python-Ogre demo:
        self.myTree = self.sceneManager.createEntity("MyTree", "tree2.mesh")        x=0        z=0        for i in range (10000):            yaw = random.randrange(0, 360)                if (random.randrange(0, 1000) <= 800):                x += random.randrange(-10.0, 10.0)                z += random.randrange(-10.0, 10.0)                if (x < 0): x = 0                 elif (x > 1500): x = 1500                if (z < 0): z = 0                 elif (z > 1500): z = 1500            else:                x = random.randrange(0, 1500)                z = random.randrange(0, 1500)                        scale = random.randrange(9, 11) / 10            self.treeLoader.addTree(self.myTree, ogre.Vector2(x, z), ogre.Degree(yaw), scale)

Note how 80% of the time, it will decide to place another tree close to the last one.

##### Share on other sites
Daerax    1207
i do believe the distribution of trees in a forest are representable using a 2D Poisson point process. Also

##### Share on other sites
yahastu    154
A Poisson process is a bad model to use for placing trees. The whole point of a Poisson process is that it is based on each event being completely independent fro m the others. In this case we specifically want trees to cluster which means that the placement of one tree (an event) is not independent from another. If you use that Poisson model, you will just get a random spacing of trees over the terrain which will not be any better than purely picking random points to begin with -- in fact it should be identical.

Drakostar and Madmax have the right "concept" in that they are trying to figure out ways to have trees cluster together, but they do not have a good mathematical framework for it and the result is not going to look good.

This is why I suggest using Perlin noise. If you take a Perlin noise map and threshold it, you get something like this:

The black areas can be considered small patches of forest or clusters of trees. Then you basically want to scatter trees randomly inside them. But you also dont want the forest to abruptly stop when you get to the edge, you want to have some probability of trees appearing nearby...which is why you should use the intensity value and not just the thresholded noise image.

The method that I described will take that into account and is very simple..

1) Create a Perlin noise texture
2) Iterate over the texture in raster scanline order. At each point, if "rand > intensity" then put a tree at that point with some random offset.

##### Share on other sites
Daerax    1207
Quote:
 Original post by yahastuA Poisson process is a bad model to use for placing trees. The whole point of a Poisson process is that it is based on each event being completely independent fro m the others.

Sometime ago, when looking for a text on a bayesian approach to Probability theory I remember reading a page from a text on Applied Probability Theory. In the section on poisson processes, it gave as an example the forest plant distribution. I do believe this is because the dispersion or arrival of seeds in some rectangular space is well modeled by a poisson distribution. If you are truly interested I can run down the library tomorrow to check the text and make a more detailed post.

##### Share on other sites
endasil    138
Thank you very much guys for taking the time to help me find resources for solving this problem. It is always gets interesting when more than one method is presented as the optimal solution.

Daerax, it would be very interesting to know the details, so if you have the time to do so, i would appreciate if you would take the time to show what it says.

##### Share on other sites
Vorpy    869
Perhaps the perlin noise and poisson process ideas can be combined. Divide the map into a number of cells, use a noise function to determine the forest density in each cell, and then use a poisson distribution to determine how many plants to randomly place inside of that cell. There also needs to be a function that maps from noise values to forest density. This function will control what the overall landscape will be (variability in forest density, minimum and maximum density, amount of map that will be unforested, etc).

##### Share on other sites
yahastu    154
Quote:
 Original post by Daerax[/i]Sometime ago, when looking for a text on a bayesian approach to Probability theory I remember reading a page from a text on Applied Probability Theory. In the section on poisson processes, it gave as an example the forest plant distribution. I do believe this is because the dispersion or arrival of seeds in some rectangular space is well modeled by a poisson distribution. If you are truly interested I can run down the library tomorrow to check the text and make a more detailed post.

They must have been talking about the distribution of where seeds fall on the ground from 1 source tree that produces the seeds. In this case, the location of each seed is independent from the others because the seeds are very small and they do not influence each other. In this case, we know that the probability of a seed falling farther from the tree reduces exponentially. In other words, the probability will look Gaussian. A Poisson process is based on exponential interrarival times so that makes sense.

However, we are not talking about the distribution of where seeds fall from 1 tree -- we are talking about the distribution of trees over a landscape, and these trees didnt all come from seeds of the same source tree! Rather, they grow up over time, and each tree has a significant impact on the distribution because each tree continues to make more trees nearby to it (as discussed in the first paragraph).

##### Share on other sites
coderx75    435
I have a homegrown method for plant/food distribution I'm using that produces great results. A few fruit objects are randomly placed to seed the forests. Each fruit is created with a time value that the application uses to track how long it will take before the fruit grows into a tree object. The tree object is created with three time values, one for the amount of time before producing fruits, one for time between the production of each fruit and one for the life length. The second time value is regenerated (randomized) after each fruit is produced. New fruits are randomly placed around the tree they came from. The number of tree and fruit objects is capped so if a fruit object attempts to spawn a tree and there is no more room, the fruit is simply destoyed.

It's a simple method and produces very natural results. It also allows the environment to change slightly over time.

##### Share on other sites
Daerax    1207
Hi, I havent been able to post because I have been busy. I was able to pop down the library for a bit 5 days ago and get a more thorough look at the concept but have not been able to sit down long enough to post. I hope this post is not too little too late.

Firstly, interestingly, this particular topic is useful for both the ecologist and the deforestation industry. The literature does not indicate that Perlin Noise is particularly well suited for creating realistic forest stands. However, one of the more popular and simpler methods for simulating forest distribution is using a 2D Spatial Poisson Process. Poisson processes are, due to their properties useful in modeling a lot of natural phenomena and ecological patterns - more on that later.

A poisson process N in the plane A with intensity λ will generally have that N(A), the number of Points in A is a poisson random variable with parameter λ|A| where |A| is the area of A. And that . Sn partitions R2 and {N(Sn)} will be a set of random variables.

Now a key thing to note is that Poisson Processes are a good model for representing the distribution of many types of forest stands but that does not mean that trees are distributed exactly like a poisson distribution. The model for example fails to take into account competition between trees. The poisson process is useful in the case where we treat the trees in a forest as being essentially randomly placed.

Poisson Point Processes have the following conditions: the number of points in each section is independent, probability of finding a point in a small section is proportional to the section's magnitude while finding more than one point is unlikely. This type of scenario occurs in nature quite frequently so we find the poisson distribution/process to be useful a lot in their modeling. For the case of the forest the independence property of poisson distribution means things are neither spaced too far apart nor tightly clumped together which seems appropriate enough when considering how trees are distributed in a forest (such an hypothesis would be tested using statistical methods on appropriate real data sets in practice).

Now here comes the maths: In a poisson forest the distance R_1 from an arbitrary fixed point r to the nearest event/point has probability density where r > 0.

An unbiased estimator of λ is given by where {X_i} is a random sample with density f_R1. The number of trees is given by λA where A is area of plane. Thus one could subdivide the plane into small areas, pick an arbitrary grid then work outwards placing objects in terms of the probability distribution.

Likely this is excursion into theory will not be sufficient for implementation. For that I link the following two papers:

The thesis: Simulating Forest Stands By Resampling One-Acre Stem Maps: Spatial Characteristics of Results and

Modeling a Poisson forest in variable elevations: a nonparametric Bayesian approach (1998)