How to effeciently spread objects on a 2D surface in a "natural" way?

Question

Hello all,

i would like to effeciently generate positions for objects on a given surface. As you probably guessed this is for a game. The surface is actually a 3D terrain, but the third dimension does not matter as it is determined by terrain height.

The problem is i would like to do this in the most effecient and easy way, but still get good results. What i mean by "natural" is something like mentoined in this article about Perlin noise. (trees forming forests, large to small groups spread out on the land) The approach is nice, but too complicated. I need to do this quite often and prefferably without any more textures involved, even at the cost of worse performance (so the results won't be as pretty, but still good enough to give a nice natural terrain with vegetation).

The amount of objects placed varies, but generally is around 50. A nice enhancement would be to somehow restrict placement of objects at areas with very high altitude (mountains) but i guess it could be done by placing a bit more objects and deleting those placed above a given altitude.

Answer 1

Note you'll have to tweak the constants a bit, but you could do something like this

First, pick a random point. (say 24,50). Next, identify points of interest for this object. If it's a rock, your points might be the two mountains at 15,13 or 50,42. If it was a forest, it would maybe do some metrics to find the "center" of a couple local forests. Next, calculate the distance vectors between the the point and the points of interest, and scale them by some constant. Now, add all those vectors to the point. Next determine if the object is in a legal position. If it is, move to the next object. If it's not, repeat the process.

Adapt as necessary. :-)

Answer 2

This might not be the answer you are looking for, but I believe that Perlin Noise is the solution to your problem.

Perlin Noise itself involves no textures; I do believe that you have a misunderstanding about what it is. It's basically, for your purposes, a 2D index of, for each point, a value between 0 and 1. You don't need to generate any textures. See this description of it for more information and an elegant explanation. The basics of Perlin Noise involves making a few random noise maps, starting with one with very few points, and each new one having twice as many points of randomness (and lower amplitude), and adding them together.

Especially, if your map is discretely tiled, you don't even have to generate the noise at a high resolution :)

How "often" are you planning to do this? If you're going to be doing it 10+ times every single frame, then Perlin Noise might not be your answer. However, if you're doing it once every few seconds (or less), then I don't think that you should have any worries about speed impact -- at least, for 2D Perlin Noise.

Establishing that, you could look at this question and my personal answer to it, which is trying to do something very similar to what you are trying to do. The basic steps involve this:

1. Generate perlin noise; higher turbulence = less clumping and more isolated features.

2. Set a "threshold" (ie, 0.5) -- anything above this threshold is considered "on" and anything above it is considered "off". Higher threshold = more frequent, lower threshold = less frequent.

3. Populate "on" tiles with whatever you are making.

Here are some samples of Perlin Noise to generate 50x50 tile based map. Note that the only difference between the nature of the two are the "threshold". Bigger clumps means lower threshold, smaller clumps means a higher one.

A forest, with blue trees and brown undergrowth

A marsh, with deep areas surrounded by shallower areas

Answer 3

One thing: If you want to reject things like trees on mountains you don't add extra tries, you keep trying to place an object until you find a suitable location or you've tried it a bunch of times and you need to bail out because it doesn't look placeable.