Hello,

I have a flat map that consists of grass and some roads. Now I want to automatically scatter trees, bushes, stones etc onto this map, in a way that
1) makes sense (no objects placed on roads) and
2) looks nice (mainly trees at the edge of the map, some tree groups on the grass and also some single trees).

Do you know any algorithm that is suitable for such a task?

Thanks for any help!

For tree groupings, you can use a simple Perlin noise fractal where the fractal is used to obtain a value that represents the probability of finding a tree at a certain location. By scaling/clamping the output range of the fractal to [0,1] then, for each location, rolling a dice or performing some other type of probability calculation and placing a tree, you end up with groupings where the fractal tends toward 1, and open areas where it tends toward 0.

For the edges, a simple mask of some sort can be used in a similar fashion. This mask could be computed per-location as the distance from the nearest edge, inverted so that locations nearer an edge tend toward a probability of 1 and locations further from the edges tend toward a probability of 0.

As far as the roads, this boils down to an iterative test of a location against all roads to determine if the point lies within a road. Instead of being a gradient of probabilities as with the group or edge-mask, this would be a simple 1 or 0 result, 0 being a road and 1 being not a road.

Multiply all of these probabilities together to get the final probability of finding a tree at a location.

That's a pretty cool idea, FLeBlanc.
Why not make the road be a mask as well, but masking to 0, the same way you had the edges mask to 1?

Yeah, that would work as well, with the proper setup. I would usually write a 1 or 0 into a buffer during the road generation phase, for an easy test of whether or not a location was a road/developed spot.

Thanks for your answer FleBlanc!

I googled a little bit about perlin noise tutorials and the first result is this: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
Is this really perlin noise? I can remember someone wrote that this is NOT real perlin noise.

Ok, so this perlin noise algorithm gives me a map with values between 0 and 1. But what does a value of 0.8 mean? The percentage of a tree a this pixel is 80%? How should I use this to determine if I should place a tree? Just using a threshold like 0.7? If value > threshold -> place tree?

Yeah, that linked site is misleading. That is actually not Perlin noise. Nevertheless, it should work just as well. Any sort of continuously varying, random noise should work. Using different noise types will net you different "shapes" of tree groupings. For instance, a ridged-multifractal noise would give you forests with lots of branching arms going all over the place.

Typically, with a probability-based solution such as this, you don't really want to use a threshold, since that results in relatively sharp edges. What I do instead is to take the probability value and turn it into a random roll:


bool isTreeHere(float probability)
{
int rollTarget=(int)(1000*probability);
int roll=randRange(1,1000); // A random routine that simulates rolling an N-sided dice
return roll<=rollTarget;
}
}


Now, for each location, you obtain the Perlin grouping probability, the edge-mask probability, and the road probability, and pass the resulting probability to isTreeHere(). If the function returns true, put a tree there. Note that I made a bit of a mistake earlier when I said to multiply them all together. This isn't actually what you want to do, if you want the map to be bounded by a solid perimeter of trees. Instead, you want to take the MAX value between the noise value and the edge-mask value, then multiply that by the 1 or 0 returned by the road mask. If you multiply the edge mask and Perlin value, then you end up with places on the edge of the map where there are no trees due to the fractal value going to 0.

Here is a quick sample map I generated a second ago:



and here is the Lua code I wrote to generate it:


rnd=random.MersenneTwister()
fbm=random.PerlinFractal("fBm", "Simplex", "smooth", 0, 1)
fbm:setFrequency(8)

function probRoll(prob)
local rollTarget=math.floor(prob*1000)
local roll=rnd:getRange(1,1000)
if roll<=rollTarget then return true else return false end
end

function edgeMask(x,y,l,t,r,b,maxdistance)
local dx1,dx2,dy1,dy2 = math.abs(x-l), math.abs(x-r), math.abs(y-t), math.abs(y-b)
local d=math.min(dx1,dx2,dy1,dy2)

local val=math.max(0, math.min(1,d/maxdistance))
return 1-val
end


img=image(512,512)

for x=0,511,1 do
for y=0,511,1 do
local fractal=fbm:get(x/511, y/511)
local prob=math.max(fractal*fractal*fractal*fractal, edgeMask(x,y,0,0,511,511, 64))
if probRoll(prob) then img:set(x,y,RGBA(255,255,255,255)) else img:set(x,y,RGBA(0,0,0,255)) end
end
end

saveImage("map.tga", img)