This update is going to be about terrain generation, and how it affects gameplay. We're hoping it is useful to other programmers who want to explore procedural terrain generation.

The Unexplored Continent

The Dwarven motherland has become quite overcrowded. The great hill mines of the old lands have lost their pristine beauty, and have grown chock full of shantytowns, refuse dumps, and sweatshops. Lately, King Dunold has complained of the “excess Dwarves” (especially orphans) who migrate about from mine to mine, without any place to work.

Luckily, the ingenuity of Dwarven science has produced the air balloon, and great Dwarven explorers, overcoming their natural Dwarven agoraphobia have spread out across the world in search of new lands. Dwarf Corps, commissioned by the king to send those “excess Dwarves” somewhere else, and to bring back precious ores and strange creatures, have taken it upon themselves to chart these new lands and claim them for the motherland.

Procedural Generation

The continents in DwarfCorp are procedurally generated. This means a set of rules (often random) is used to create each landscape, mountain, valley, lake, river, bay, hill, and kingdom you will find in these lands. It also means that each time you play DwarfCorp, a new continent will be generated from scratch. It will be different (yet somehow more or less the same) every time. Unlike the procedural terrain in many other games, our terrain is fixed in size. This allows us to have global features on our continents (like erosion, very long rivers, and mountain chains) which get stored before play. This is very similar (though not quite as complicated) as the system in Dwarf Fortress or Realm of the Mad God (which have continents of a fixed size to explore) and less similar to Minecraft (which has infinite, but locally very repetitive terrain). Now, we’ll discuss some of the technical details of how the terrain is generated. Our procedure falls roughly into these categories: Faults, Hills, Erosion, Biomes, Landmarks, and Civilizations.

Faults

To generate a basic outline of our continent, we start by laying out a plot of land of a fixed width and height (the player can control these dimensions in the Options screen). Then, we randomly draw lines near the edges of the map, and throw in a few random lines in the middle of the map by first randomly sampling a point, and then doing a random walk of three or four steps. The result of this process is what we call “the faultlines”. It really has nothing at all to do with natural faults you might find on Earth, and more of just a catchall term we use for the process. The next step is to generate what’s called a “Voronoi Diagram” of the faultline map. To do this, we just compute the distance from every pixel to the nearest fault line, and set that as the value of each pixel. The result is called the “Fault Map”. We then apply random distortion to the Fault Map using Simplex Noise.

Hills

One of the most powerful tools in procedurally generated games is the use of Perlin (or in our case Simplex noise). Technically, this refers to a random, smooth function of one or more variables. The result of evaluating Simplex noise in 2D is a sort of “hilly” function with random highs and lows. To make our Simplex noise look more natural, we have three layers: Continent Noise, Mountain Noise, and Hill Noise. Continent noise occurs over huge scales and its magnitude is quite low. Mountain Noise occurs over smaller scales and has very high magnitude. Hill noise is quite small and is of medium magnitude. We simply go through each pixel in the map, and add together the Continent Noise, Mountain Noise, and Hill Noise. The result is called the “Noise Map.” Before moving on, we scale the Noise Map so that the lowest value is zero, and the highest value is one.

Erosion

What we have now (if we just pixelwise multiply the Fault Map by the Noise Map) is a pretty nice looking continent. It will have natural peninsulas, islands, bays, and lakes. However, it looks a bit too smooth and flat. That’s because in the real world, “nonsmooth” effects occur on the landscape which we haven’t simulated yet. One of the biggest such effects is erosion from rainfall, and weathering from other sources. To simulate rain erosion, we literally simulate large rain droplets falling on the landscape and carrying bits of dirt from one place to another. For some number of raindrops (say 5,000), we randomly sample pixels in the world. If the pixel we sample is below sea level, we just continue. Otherwise, we need to simulate a raindrop. To simulate a single raindrop, we perform what is called Gradient Descent. First, we keep track of how much material is stored in the raindrop (this starts at zero). Then, we look in the local neighborhood of the raindrop and compute an approximation of the gradient (which is the direction of steepest descent).

We then move the raindrop along the gradient, and take a random amount of material with us down the slope. When the raindrop arrives at a new destination, it leaves a small, random amount of material, and picks up a larger, random amount of material. We repeat this process until either the raindrop hits the sea level, or we run out of a fixed number of steps.

The result, after many many raindrops, is a more eroded continent, with channels, canyons, and fjords.

Rivers

Rivers work just like raindrops in the erosion step, but they erode a significantly wider area. When the actual voxels of the terrain are generated, rivers are filled with dynamic water (which in our experience, causes terrible flooding!)

Biomes

“Biomes” describe the different types of terrain and vegetation which cover the landscape. So far, we have the following Biomes: Grassland, Desert, Forest, Jungle, Taiga, Tundra and Hellish. The terrain is classified into one biome or another based on the rainfall, temperature, height, and distance to a landmark. To generate temperature, we for now just apply a gradient from north to south, mix in perlin noise, and distort it. To generate rainfall, we do the same thing. In the future these parts will be based on actual physical processes, but for now it seems to work fine. Each biome stores which blocks occur on the top surfaces of the terrain (usually 3 or 4 levels down), under the subsurface, and near the shore. Biomes also store which vegetation types and ground cover occur there. For instance, the Forest biome specifies that grass occurs at the top level, rock at the subsurface, and sand on the shores. It also specifies that large trees should be fairly common, as well as berry bushes and tall grass. The “desert” biome on the other hand specifies sand at the top level, and no vegetation whatsoever save for a few gnarled bushes.

Caves and Ores

Caves and ores are generated on-the-fly during construction of the terrain voxels. To generate caves, we just sample a 3D Perlin noise function, and threshold on an arbitrary value we call "caviness," or in the case of ores, each ore has its own threshold and scale at which to generate patches of ore. We want to change this to line up more closely with the way caves and ores are naturally created.

Landmarks

Several “landmarks” are also placed randomly around the world. These are special features which only occur in one place (such as a town, or a volcano), and which can have arbitrary effects on the terrain.

A landmark contains a bit of information: a set of “template terrains” to place around the landmark (in the case of volcanoes, a caldera), an associated biome (in the case of volcanoes, Hellish), a size, and location rules.

Civilizations

Civilizations are a tricky bit, since there isn’t a simple physical process behind how kingdoms rise and fall. (Unfortunately, civilizations haven’t made it into our prototype yet, but they will be there soon!) Our solution is to turn simulating civilizations into a problem of “Cellular Automata”. We start by randomly placing cities and towns in the world. Each city is given a random name, as is each civilization.

This is done as part of the landmark process. We give each city a few bits of information: its population, its defensive strength, and its associated race (goblin, elf, etc.). In the beginning, all cities are of race “neutral” save for a “capital” assigned to each race. We assume each civilization is made up of a continuous area of pixels. We give each pixel of the civilization a quantity called “glow” (this comes directly from an earlier game we’ve worked on called “Dots Game”). All pixels begin with zero glow. At each step, Capitals pump out glow to their neighbors. When the glow of a neighbor pixel is above 50%, it switches sides from race “neutral” to the race that caused it to glow.

When glow reaches a neutral city, it is immediately converted to the race causing the glow. Each non-capital pixel then distributes its glow to its neighbors randomly. When the glow of two civilizations meet, it causes a “battle”. In the case of countryside entering a city, the glow of the countryside subtracts from the city’s defensive strength until the strength of the city is zero. In the case of countryside vs. countryside, both sides lose some amount of glow until one is greater than the other by a fixed amount. The race of the pixel with the most glow in the battle then occupies both cells. Glow also spreads more easily along flat terrain or downhill than it does up the sides of mountains or over rivers. It also simply does not spread over water. After all of the civilizations spread, roads are randomly created between each of the nearest cities in a civilization. This is all very complicated, but the result (after many many steps of simulation), is a cool-looking civilization map! In the game, civilizations will be used to generate enemies and non-player characters. If the player spawns near a goblin city, for instance, he or she will occasionally get groups of wandering goblins coming to the colony for war or trade. If he or she spawns near the border of goblins and elves, there is a higher likelihood of seeing goblin-on-elf battles.