Gamasutra: The Art & Business of Making Gamesspacer
Random Scattering: Creating Realistic Landscapes
View All     RSS
October 22, 2014
arrowPress Releases
October 22, 2014
PR Newswire
View All





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Random Scattering: Creating Realistic Landscapes

August 6, 2008 Article Start Page 1 of 3 Next
 

[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.

Just Random?

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.

Random Nature

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).


Article Start Page 1 of 3 Next

Related Jobs

Avalanche Studios
Avalanche Studios — New York, New York, United States
[10.22.14]

UI Programmer
University of Texas at Dallas
University of Texas at Dallas — Richardson, Texas, United States
[10.22.14]

Assistant/Associate Prof of Game Studies
Avalanche Studios
Avalanche Studios — New York, New York, United States
[10.22.14]

UI Artist/Designer
Nuclear Division
Nuclear Division — Sherman Oaks, California, United States
[10.22.14]

Director of Product Management






Comments


Sebastian Bender
profile image
Interesting article especially for novice programmers since it shows nicely that complex phenomena can be coded with rather simple solutions.

Anonymous
profile image
As an artist, this just cracks me up. Looks like good tech for stub-art. Trees aren't random in any sense. The factors that put a tree in place are diverse and an artistic eye is needed to discern what makes sense and what doesn't. Trees don't grow out of rocks, trees don't grow under the shade of other trees, trees will cluster in the lower elevation ruts and water-paths along hills and mountains, not the high points...unless the dirt/rocks/angle of that particular mountain make those areas land-slide-prone. Trees will cluster along fence-lines because the saplings will get cut down by mowers or eaten by animals on one side of the fence. Trees cluster around rivers, then don't grow much at all around huge flat planes in some cases. There's so many variables that are biological that should be taken into account instead.



But if one is making an MMO and the artists don't have the time or the ability to think through that kind of thing and they need a LOT of trees in a hurry, this tech might help as a substitute for their better judgement and precious time.

David Delanty
profile image
Pretty cool insight there, Mick. I like how you emphasize the fact that there is a lot of "organization" required to make an effective "random" output. You can't just throw darts blindly at a board, the effect of random needs to be organized in such a way that it still follows a sort of order.



While I do agree with above comment that the analogy of trees does require a bit more detailing than what's in the article, and that you could probably write an entire novel on the physics of tree placement, it's the *principle* of making randomized placement of objects that I know you're going for, and it's very well explained.

Patrick Coan
profile image
There really is no such thing as "random" in my opinion, only behavior which is beyond our comprehension. So when considering a forest, all of the Anonymously mentioned factors will apply, but so does this method which Mick describes.



The described distribution model should only be used as a tool for initial plotting, if the target result is something of cinematic aesthetics. After the samples are placed, let the artists carefully move things around until the illusion is created. If you are flying a jet through the mountains, then I don't think that anyone cares about the trees along the fence.

Aaron Casillas
profile image
Anonymous is correct. Trees in nature follow two simple heuristics, follow the water and stay near mom.



If you look closely, they emerge in and out of valleys more than other areas.



Second, saplings will always be found near their parent tree. This pattern repeats over and over again.

Julius Foitzik
profile image
You must have a parent generation of trees or the trees will spread unstoppable in each direction.


none
 
Comment: