Mass-Spring Scattering

A common method in the literature of distributing objects in a non-overlapping manner is to essentially connect each object to its neighbors by a spring and then "relax" the positions of the objects so that the springs take care of the constraints and the factors influencing distance.

Figures 4 through 6 show this process:

Figure 4: The spring mass system is shown here in its initial state. Each tree is connected to its neighbors by springs of random rest length.

Figure 5: The spring mass system is shown after running 40 iterations.

Figure 6: The tree distribution pattern from the spring mass system is shown with the springs removed.

First in Figure 4, the trees are arranged in a regular grid with springs between them. Each spring has the same initial length (different for diagonals), but has a random rest length. The spring mass system is then iterated several times (40 times in this example; see Figure 5); we then remove the springs, leaving the trees in their final positions (Figure 6).

The relaxing method has a number of problems. For one, it's a more complex method to implement. Second, it requires tweaking to get good looking results. Third, there are problems at the boundaries of the area we are trying to cover.

Because the spring mass system's rest state is unlikely to be similar to the start state, the boundaries of the system end up either shrinking inward or expanding outward, unless the system wraps or additional constrains are added.

Different Sized Trees

So far, we've been trying to evenly scatter a bunch of identically sized objects. What if we want to have objects of differing sizes, with differing growth inhibit zones? The mass-spring system is not so suitable for this task, as it's not trivial to get an initial regularly spaced configuration (although it can be done).

Instead, we could change to a particle system in which each object repels every other object according to some function of distance that is in keeping with their mutual zones of exclusion-and an additional constraint is applied to keep them all together. This is obviously an expensive operation, as it requires multiple iterations of O(n2).

Alternatively, we can go back to the random scattering method where we simply move the object to a new and random position if it gets too close to any other object. This approach requires essentially a single iteration of O(n2), since there are generally very few collisions.

It can also be optimized much closer to O(n) by using buckets for proximity, as mentioned earlier. Figure 7 shows the results of such an algorithm.

Figure 7: Random scattering is shown here with proximity constraints for four different sized objects.

Of all these methods, only the random perturbation is trivially amenable to reproducible procedural landscape generation in arbitrarily small amounts. Since the other methods need to generate a specific number of trees at once, you would need to fill an entire segment of the environment.

To avoid visible boundaries between regions of trees, these segments should conform to natural boundaries within the environment, such as rivers or roads. Since simple positions are not very memory intensive, this method works well for large segments. It's also an ideal process to put on a low priority thread as part of a "procedural spooling" system (see "Procedural Spooling," Game Developer, February 2007).

The Forest, The Trees

Random scattering in nature is not really random. A complex set of underlying rules governs the pattern, even if humans can only see the results as random; however, an image of pure mathematical randomness doesn't look "natural" at all.

Sometimes simple solutions work out better than complicated ones. In this case, to scatter a forest of trees, we found that applying a very simple exclusion zone around plants achieved a nice random distribution of different sized plants.

For most situations, this is reasonably quick and compares well to more complex solutions that involve relaxing spring systems.

[EDITOR'S NOTE: This article was independently published by Gamasutra's editors, since it was deemed of value to the community. Its publishing has been made possible by Intel, as a platform and vendor-agnostic part of Intel's Visual Computing microsite.]