Home of Ebyan Alvarez-Buylla

World Generation Breakdown

World Generation Breakdown

A large part of Dance of Death v0.6.136 was the addition of world generation. Although the world is little more than a large island at the moment, the results are rather satisfying, even considering that the current method of generating terrain is purely based on elevation. After experimenting with a number of techniques, I settled on this simple formula: 1) Generate Fractal Perlin Noise, 2) Multiply noise by a radial gradient, and 3) Apply terrain and water line. Here is the breakdown:

You can click on any of the images to view an interactive demo, and click again on the demo to generate a new map. The images were all generated randomly, so they do not correspond to a progression of the same maps (while Flash’s Perlin noise generator can be seeded, its random function cannot). Source code is available from Google Code, where you can grab it directly from SVN.

Step 1: Generate Perlin Noise

Generate a Fractal Grayscale Perlin Noise with an x-frequency of half the width, a y-frequency of half the height, and 8 octaves. For more loose islands, or for larger maps, you can drop the frequency to 1/4th of the width and height or lower, to fit your purposes. You can normalize the noise from 0-255 if you like, though normalizing now will become redundant later on. This is what we have so far:

Grayscale Fractal Perlin Noise, normalized for contrast. Click to view demo.Grayscale Fractal Perlin Noise, normalized for contrast. Click to view demo.

If we apply the terrain to the tiles at this point, we’ll end up with something like this (jump ahead for the terrain application method):

Terrain applied to noise. Looks pretty good, but it touches the edges and lacks an overall island look. Click to view demo.Terrain applied to noise. Looks pretty good, but it touches the edges and lacks an overall island look. Click to view demo.

Step 2: Generate Rolling Particle Mask

To get the island to be biased towards the center and avoid touching the edges, a straightforward solution is to multiply its values by a radial gradient mask ranging from 1 near the center, to 0 near the edges. A plain radial gradient might do the trick, since the Perlin noise already provides a healthy amount of randomness. However, I went with a modified version of the Rolling Particle algorithm to get some additional roughness. The basic algorithm goes something like this:

  • Start with a blank map, all 0s.
  • Pick a random starting spot for the particle.
  • Increment the value on the map by 1 where the particle is located.
  • Move the particle to a random adjacent position whose value is less than or equal to the current position (imagine the particle rolling downhill).
  • Repeat the last 2 steps as long as the particle is alive.
  • Repeat for a large number of particles.

A particle life of 50, with 3000 particles works well for this map size (which is 88×32, by the way), experiment to get values that work for you. If we normalize, we get this:

Basic Rolling Particle algorithm, 3000 iterations, particle life 50. Click to view demo.Basic Rolling Particle algorithm, 3000 iterations, particle life 50. Click to view demo.

While the algorithm produces inherently center-biased maps, multiplying this across the noise results in islands that are too boxy. To round out the results more, instead of picking a random starting point for particles, let’s ensure that they land closer to the center:

Rolling Particle algorithm, center-biased, particles start 12 tiles away from the edges. Click to view demo.Rolling Particle algorithm, center-biased, particles start 12 tiles away from the edges. Click to view demo.

To absolutely ensure that the islands will not reach the edges, I’ve also multiplied the outermost tiles by 0.75, and the second outermost tiles by 0.88. These tiles already have some of the lowest values of the map, and softening or “blurring” them this way ensures the final map does not touch the edges.

Step 3: Apply Terrain

Once the base noise map and the rolling particle mask have been generated, multiply the noise values times the (mask/255). Dividing by 255 ensures that the mask values will range from 0 to 1 rather than the normalized 0 to 255. This produces the following result:

Combined maps. Click to view demo.Combined maps. Click to view demo.

We’re done with the heightmap generation. Now onto determining the water line and assigning terrain.

I spent some time fussing with linear regression and other estimators to accurately place a water line, but, at the end, directly sampling the values of the map turned out to be the fastest (to program and execute), and most accurate solution. To determine the water line for the default 60% water used in this world generator, step through the map and throw all of the values into an array. Sort this array numerically. The value indexed at (array.length – 1)*0.6 marks your water line. Everything below it is water, everything above is land.

Now that the waterline is set, I pass that value into each tile’s setTypeByElevation() function, which sets the tile type according to its elevation, as follows:

If below the water line:

  • If above waterline-40: shallow water.
  • Else: deep water.

If above the water line:

  • If below waterline+15, coast/beach.
  • If between waterline+15 and waterline+35: plains.
  • If above 255-25: mountain.
  • If between 255-50 and 255-25: hills.
  • Else: forest.

Producing this:

Final result. Click to view demo.Final result. Click to view demo.

Grab the source code from Google Code, or directly from SVN. Feel free to tweak any of the values and modify the algorithms as long as you adhere to the GNU General Public License v3 and provide attribution and all that. Enjoy!