Procedural Forest Generation

Forest Generation

Before diving into how we are going to generate random forests in Slappy, I I wanted to give a brief reminder of the type of game that we are building. Our player is stranded in an abandoned world that has been been left to nature to rebuild. So, there are large swaths of open land and some old-growth forests that cover parts of the landscape. We already established that each level will be rectangular, and now the challenge will be to fill this area with forests without overwhelming the player.

So, why have forests in the first place? Forests provide natural cover for our enemies and so the player must choose to enter the forest and be prepared to deal with what is within. In addition to enemies hiding in the forest the player could find valuable items and useful power ups.

Background

The forest algorithm is based on some research done during my time at the University of Wyoming. Our research lab had a grant to build a multi-agent simulator and demonstrate how decentralized control of flying swarms would allow us to provide surveillance for a forested area. In the summer of 2004, I began development on the simulator and needed to devise a way to generate random forests that felt natural and covered some percentage of a rectangular area (sound familiar?). For those interested, the original paper can be found here. The rest of this post will focus just on the forest generation algorithm.

Algorithm

We decided to build an algorithm that behaved very similar to the cellular automata described in a previous post, but rather than it being on or off and switching immediately, we introduced the idea of seeding.

We start with a small set of trees that grow and seed the neighboring area. Each iteration some seeds become trees and will grow to begin expanding the seeded area. In the previous post on procedural cave generation, there were relatively few parameters that could be tuned in order to generate different caves, whereas this algorithm has more parameters that can be varied to create different types forests.

  • nf - The initial number of trees in the forest.
  • Rs - The radius that seeds can travel.
  • Ss - The amount of seeds that fall during seeding.
  • ds - The decay rate of the seeds that fall.
  • Fc - The percentage of ground to be covered with forest.

Each iteration of the forest generation algorithm we go through a seeding phase and then some portion of those seeds become trees for the next generation. If seeds do not become trees, then they will decay according to the defined decay rate.

Initial Implementation

All of the code is available on my GitHub account.

The algorihtm begins by initialzing the map with a small set of trees. One caveat is that rather than being a single pixel, each tree is a collection of pixels shown below.

Initialization of forest generation algorithm.

From the initial set of trees, we will “grow” a forest until we have covered some predefined percentage of the area. Each round of growth is divided into three steps. In the first step existing seeds decay by ds. In the next section, we will discuss what the decay is for in more depth, but the idea is that we don’t want seeds to pile up indefinitely in each grid cell because in the step we select new trees from the existing seeds. Those grid cells with more seeds in them have a higher likelihood of becoming a tree during this phase.

The final step in the forest growth algorithm is to have all of the trees (including the new ones) seed the area around them for the next round of growth. The following image represents the effects of the seeding algorithm. Seeds are spread up to Rs away from the original tree. Think of this as the canopy of a mighty oak tree and how far away seeds can drop from the base of the tree. When two trees are close to each other and their canopies overlap, then there will be twice as many seeds that fall within that area increasing the likelihood that a tree will occur in the next round of growth.

Seeding of new trees.

The following screenshots show the forest creation algorithm in action.

Small forest after just a few steps.
Same forest after a few more steps.

At this point we have reached a reasonable looking forest. Since the forest generation algorithm is supposed to work in conjunction with the cave generation algorithm we outlined earlier, we should see what it looks like overlayed on top of a randomly generated level.

Random forest overlayed with the level.

As you can see there is definitely overlap with the forest and the empty areas within the level, which is what we desired. The forest is also not limited to empty areas in the original area and can exist on top of filled in areas. I deliberately chose this route and will need to consider how the art blends these two regions together.

One last thing to note is that the forest grid seems to be much finer than the grid we used to generate the level. This is because each grid cell in the level is supposed to be about 10m by 10m. We can definitely fit more than one tree in a grid of this size and that’s reflected in the granularity of the forest grid.

Intuition

I want to try and capture what this algorithm is doing intuitively so that you you will not have to blindly vary the parameters, but you can set them and the forests that it generates are what you would expect.

  • nf - The initial number of trees in the forest often determines how many clumps of trees that you will have. If you have spent any time in the forest, you will notice that often there are stands of trees that are isolated from each other but densely populated. If we have a 10x10 grid representing our forest and we want 30% of the ground covered in forest, we could set the initial number of trees to 30 and have a uniform distribution of trees.

  • Rs - Setting the radius that seeds can travel to small number means that the forest can only grow roughly one pixel at a time. So, you will end up with very tight clusters of trees in your forest, whereas if you set this number higher, you forest could still be very densly populated but you would have small areas of light shining through.

Random forest with _Rs_=4.
Random forest with _Rs_=20.
  • Ss - In each iteration, seed is spread across the seed radius with the strength determined by this parameter. The higher the value, the higher the probability that a cell will sprout a tree. If this number is high enough, each iteration will result in a new tree in ever cell that is seeded. The result is a perfectly rounded forest.
Random forest with _Ss_=1.
  • ds - The decay rate prevents stacking seeds on top of each other forever until one becomes a tree. The idea is that if a tree does not sprout the first year, then that seed has a smaller chance of sprouting the next year and so on. A very high decay rate should result in a forest with many more patches as demonstrated below.
Random forest with _ds_=0.99.

The parameters should be relatively straightforward. Try it out for yourselves, modifying the parameters in the code and running it.

Running Demo

I included a demo of the system running (thanks to LibGDX HTML5 output).

Thanks again for taking the time to read this far, and feel free to send me any feedback.

Steam Recommender

Discussion of the technology behind steamrecommender.com. Continue reading

March 18, 2015 (1000 words)

Published on March 17, 2015

Procedural Cave Generation

Published on August 24, 2014