[In this technical article, originally published in Game Developer magazine, Neversoft co-founder Mick West continues his acclaimed analyses by showcasing an algorithm for procedurally scattering objects such as trees across a game level.]
In procedurally generated or procedurally augmented scenes, a common problem is how to scatter something around in a way that looks natural. For example, a landscape might have trees that are evenly scattered, either sparsely as on an African savanna or densely as in a forest. Also, trees are generally surrounded by other vegetation, which is also scattered.
Suppose you are tasked with developing algorithms to facilitate this scattering. This article looks at various approaches and problems you might encounter.
Let's say you take the simplest approach first. Given a number of trees and an area to put them in, simply scatter them randomly across that area. It's very easy to implement this to see how it looks. Just pick n random positions in a square.
Figure 1 shows the result for a group of 110 objects, in this case, dots that represent individual trees. (To see the code used to generate the figures in this article, click here.)
Figure 1: The green dots represent trees randomly scattered on a plane, viewed from above. Although the scattering is entirely random, it looks neither random nor natural.
Problems with this first solution are immediately apparent. Several of the dots on Figure 1 overlap, meaning the geometry of the trees would intersect. There is some strange clumping going on, with trees showing up in little lines of three or four.
Then there are several wide-open spaces, and a few trees off by themselves. This might work for some odd species of plant, but it's not what we were going for.
We might at first assume that there's a problem with our random number generator. Why else would these strange clumps occur? Is the random number generator tending to favor certain numbers? Unfortunately, it's not that simple.
This is what random numbers look like. If you pick a bunch of random numbers in a certain range, it's highly likely that some of the numbers will be close to each other. This is related to the birthday paradox: it only takes 23 people in a room for there to be an even chance of two people having the same birthday.
Consider what's actually being simulated. What does it look like and how has it arrived at this state? Can we model it using the underlying processes that occurred in nature? Or is it better to create some more abstract model simply based on our observations?
Let's first back up and think about what's happening.
Most plants grow from seeds. A seed falls on the ground, sprouts and grows, absorbing nutrients from the soil, air and, sun. Where each seed falls will determine whether it survives. More mature plants that are nearby will compete for the available nutrients, sucking them away from the sprouting seeds.
Mature plants can also block sunlight from seedlings and even reduce the quality of the air. Certain plants go further, releasing chemicals into the ground that inhibit the growth of other plants.
As a simplification, we can think of the area around a tree as having an exclusion zone, where other plants are not likely to survive. To implement this premise, we simply scatter the trees as before, but now for every tree that's placed, we check whether its location is too close to another tree.
If it is, then we pick another spot and try that. If we can't find a spot after a number of attempts, we would declare the area full and stop trying. Figure 2 shows the results of this implementation using the same number of dots (trees) as Figure 1.
Figure 2: If a tree is too close to another tree in a randomly scattered pattern, we can move it elsewhere. Although the result is more natural looking, clumping can still occur, which may or may not be desirable.
Figure 2 contains some very interesting differences. For example, the overlaps and strange groupings have all but vanished. However, there are still a few open spaces with what look like paths leading through the forest. I suspect these are actually artifacts of the algorithm, with spaces of 1.5 times the minimum space being unlikely to be filled, and hence growing into these paths.
This solution might also have performance implications. Since we need to check every tree against every other tree, the naive algorithm is O(n2) complexity, which can become rather expensive. However, it's reasonably straightforward to optimize this with a bucket method, essentially reducing it to O(n).