Random Complications

This simple model works reasonably well, but the distribution is still patchy. What's going on? Well, obviously in real-life, trees do not have "kill zones" surrounding them. Rather they have something more like an inhibit field, where the successful growth of a tree is exponentially more unlikely the closer it is to other trees. The success of a tree is a function of the sum of all the other trees' inhibit fields at that point.

Secondly, trees don't grow one at a time in nature; they grow over the course of several years, with new trees germinating every year. Old trees die and open up space, which other trees then fill, competing for the space. Over many generations, this natural renewal of trees evens out the distribution, making it even and natural.

While natural tree distribution over the course of several decades is something we could simulate, this is for most games unrealistically expensive.

We really don't want to be running a simulation of a forest ecosystem just so we can get an even distribution of trees. We need to look at creating a simple model of the results without regard for the underlying physical process.

Teleological vs. Ontogenetic

Two competing methodologies in procedural content generation are teleological and ontogenetic. The teleological approach creates an accurate physical model of the environment and the process that creates the thing generated, and then simply runs the simulation, and the results should emerge as they do in nature.

The ontogenetic approach observes the end results of this process and then attempts to directly reproduce those results by ad hoc algorithms. Ontogenetic approaches are more commonly used in real-time applications such as games. (See "Shattering Reality," Game Developer, August 2006.)

Step back for a second. What we want are trees that are randomly scattered, not overlapping, yet still evenly distributed. What if we started off with the trees perfectly evenly distributed (say on a square grid), and then simply move each tree a random amount, but not so far that they can overlap?

This solution actually works quite well. If we spread the trees out on a grid with a distance D between each tree, and we move each tree in the x and y directions by a random amount between -D*0.4 and D*0.4, then we know no two trees can be closer than D*0.2. See Figure 3 and Listing 1, which contains the algorithm.

Listing 1

void CreateScatter(float x, float y, float w, float h, int rows, int cols)
{
float xd = w/cols;
float yd = h/rows;
for (int ix = 0;ix <(cols+1);ix++) {
for (int iy = 0;iy<(rows+1);iy++) {
float p = 0.4f;
CreatePoint( Vector2(x+xd*ix+rndf(-p,p)*xd,y+yd*iy+rndf(-p,p)*yd));
}
}
}

Figure 3 looks something like a cross between the pure random scatter and the minimum distance scatter. The trees are evenly distributed, but we still see some minor clumping, including two trees that overlap slightly. But overall this algorithm produces much nicer looking results than our first attempt, and it's simpler and cheaper to implement than the second.

Figure 3: The trees here in this random perturbation-style scatter start off in a regular grid and are moved randomly by a small amount. The result is a very even distribution.

It also has another advantage: It is repeatable. Repeatability is important in a spooling environment where you want each patch of ground to look the same in the same location. When you see a couple of trees, then leave the location and return later, you would expect to see the same two trees in the same place.

We can accomplish this in a game environment by using the low order bits of the original x, y position of the tree as a seed for your random number generator.

This can then be used to generate both the positional offset and the full appearance (the geometry and textures) of our procedural tree. Thus any tree generated from that unique point will always visually be the same unique tree in the same place whenever you return to it.