Feature: 'Random Scattering: Creating Realistic Landscapes'

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 his example, West first details two simple but suboptimal methods for simulating randomly scattered trees, including distributing them randomly across an area then applying an exclusion zone to prevent overlap and closely-bunched objects: "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. " Though you don't want to run a simulation of a forest ecosystem just to get an even distribution of trees, you can create a simple model of the results without regard for the underlying physical process. West details two competing procedural content generation methodologies, teleological and ontogenic, describing the former approach as creating an accurate physical model of the environment and process to simulate the results, whereas the ontogenic approach observes and reproduces the end results of the process. "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. [Figure 1] 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 1: 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. You can read the full feature, which includes sample code, analyzing several methods and presenting an algorithm for procedurally scattering objects such as trees across a game level (no registration required, please feel free to link to this feature from external websites).