Jump to content
  • Advertisement
Sign in to follow this  
endasil

Algoritm for placing trees and bushes

This topic is 3925 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
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 this post


Link to post
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 trees
TreeOffsetX = (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 this post


Link to post
Share on other sites
Quote:
Original post by MadMax1992
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 :)


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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by yahastu
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.


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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!