31 Aug 2013

Table of Contents

As I was studying audio signal processing, my brain started making connections back to procedural map generation. So here are some notes on how signal processing concepts relate to map generation. I don’t think any of this is new but some of it is new to me, so I wanted to write it down and share. I only cover simple topics (frequency, amplitude, colors of noise, uses of noise) and not related topics (discrete vs continuous functions, FIR/IIR filters, FFT, complex numbers). The math on this page is mostly sine waves.

I’m going to start with the basics of using random numbers and work my way up to explaining how 1D landscapes work. The same concepts work for 2D (see demo) and 3D. Try moving this slider to see how a single parameter can describe many different styles of noise:

0
1
2
3
4
Exponent: =

This article covers:

I also have some 2D noise experiments, including 3D visualization of a 2D heightmap.

#Why is randomness useful?

What we’re trying to do with procedural map generation is to generate a set of outputs that have some things in common and some things different each time. For example, all the maps in Minecraft have a lot of similarities: the set of biomes, the size of the grid, the average sizes of biomes, the heights, the average sizes of caves, the percentage of each type of rock, and so on. But they also have some differences: where the biomes are placed, the location and exact shapes of caves, the placement of gold, and so on. As a designer, you need to decide which aspects are the same and which aspects will vary, and how they will vary.

For the parts that vary, you’ll typically use a random number generator. Let’s make an extremely simple map generator: it will generate a line of 20 blocks, and one of the blocks will contain a gold treasure chest. Let’s write out some maps that we might like to see (“x” marks the treasure):

map 1 ........x...........
map 2 ...............x....
map 3 .x..................
map 4 ......x.............
map 5 ..............x.....

Note how much these maps have in common: they’re all made of blocks, the blocks are in a line, the line is 20 blocks long, there are two types of blocks, there is exactly one gold treasure chest.

But there is one thing that varies: where the block is. It can be anywhere from position 0 (leftmost) to position 19 (rightmost).

We can use a random number to choose the location of that block. The simplest thing to do is to use a uniform random selection from 0 to 19. That means every location from 0 to 19 is equally likely to be chosen. Most languages will include some function to generate random numbers uniformly. In Python it’s random.randint(0,19) but I’ll just generically say random(0,19) in these notes. Here’s some Python code:

def gen():
   map = [0] * 20  # make an empty map
   pos = random.randint(0, 19)  # pick a spot
   map[pos] = 1  # put the treasure there
   return map

for i in range(5):  # make 5 different maps
   print_chart(i, gen())
0
1
2
3
4

But suppose we wanted maps that had the treasures more likely to be on the left than the right? To do this we would use a non-uniform random selection. There are lots of ways to do this. One way is to choose a random number uniformly, then move it towards the left. For example, we might try random(0,19)/2. Here’s some Python code for that:

def gen():
   map = [0] * 20
   pos = random.randint(0, 19) // 2
   map[pos] = 1
   return map

for i in range(5):
   print_chart(i, gen())
0
1
2
3
4

However, that’s not quite what I want. I want treasures to sometimes be on the right, but more often on the left. Another way to move treasures to the left is to square the number, with something like sqr(random(0,19))/19. If it’s 0, then 0 squared divided by 20 is 0. If it’s 19, then 19 squared divided by 19 is 19. But in between, if it was 10, then 10 squared divided by 19 is 5. We’ve kept the range from 0 to 19, but we’ve moved the middle numbers like 10 over to the left. This kind of redistribution is a very useful technique on its own, and I’ve used square and square root and other functions in past projects. (This site has some common reshaping functions used for animations; hover over a function to see the demo.) Here’s Python code that uses squaring:

def gen():
   map = [0] * 20
   pos = random.randint(0, 19)
   pos = int(pos * pos / 19)
   map[pos] = 1
   return map

for i in range(1, 6):
   print_chart(i, gen())
1
2
3
4
5

Yet another way to move things to the left is to first randomly choose a range limit, then randomly choose a number from 0 to the range limit. If the range limit were 19 then we could get a number anywhere. If the range limit were 10 then we only get numbers on the left half. Here’s some Python code:

def gen():
   map = [0] * 20
   limit = random.randint(0, 19)
   pos = random.randint(0, limit)
   map[pos] = 1
   return map

for i in range(5):
   print_chart(i, gen())
0
1
2
3
4

There are lots of tricks for taking uniform random numbers and turning them into non-uniform random numbers that have the properties you want. As the game designer you get to choose the distribution of the random numbers you want. I’ve written an article about how to use random numbers for damage in role-playing games where I give a bunch of tricks like this.

To review:

  • For procedural generation we have to decide what will stay the same and what will change.
  • Random numbers are useful for filling in the parts that change.
  • Uniformly chosen random numbers are what most programming languages give us, but we often will want non-uniformly chosen numbers. There are many ways of getting them.

#What is noise?

Noise is a series of random numbers, typically arranged in a line or a grid.

In old TV sets, if you tuned to a channel that didn’t have a station, you’d see random black and white dots on the screen. That’s noise (from outer space!). On radios, if you tune to a channel that doesn’t have a station, you hear noise (I’m not sure if this comes from space or elsewhere).

In signal processing, noise is typically the unwanted aspect. In a noisy room it’s harder to hear someone than in a quiet room. Audio noise is random numbers arranged in a line (1D). In a noisy image it’s harder to see a pattern than in a clean image. Image noise is random numbers arranged in a grid (2D). You can also have noise in 3D, 4D, etc.

Although in most applications you’re trying to subtract the noise, a lot of natural systems look noisy, so if you’re trying to procedurally generate something that looks natural, you typically want to add noise. Although real systems look noisy there’s usually an underlying structure; the noise we add won’t have that same structure, but it’s much simpler than programming the simulation, so we use it and hope the end user doesn’t notice. This is a tradeoff that I’ll talk about later.

Let’s look at a simple example of where noise is useful. Let’s say we have a 1D map as before, but instead of a single treasure chest, we want to create a landscape of valleys, hills, and mountains. Let’s start by using a uniform random selection at each location. If random(1,3) is 1 we’ll set it to a valley, if 2 set it to hills, and if 3 set it to mountains. I’m using random numbers to create a height map: at each location in the array, I store the height of the landscape. Here’s Python code to create the landscape:

for i in range(5):
   random.seed(i)  # give the same results each run
   print_chart(i, [random.randint(1, 3)
               for i in range(mapsize)])

# note: I'm using Python's list comprehension syntax:
#     output = [abc for x in def]
# is shorthand for:
#     output = []
#     for x in def:
#         output.append(abc)
0
1
2
3
4

Hm, these maps look “too random” for our needs. Maybe we’d like larger areas of valleys or hills, and we’d also like mountains to be less common than valleys. Earlier we saw that uniform selection of random numbers may not be what we want; there are times we want non-uniform selection. Can that help here? We could use some random selection where valleys are more likely than mountains:

for i in range(5):
   random.seed(i)
   print_chart(i, [random.randint(1, random.randint(1, 3))
               for i in range(mapsize)])
0
1
2
3
4

That decreases the number of mountains but doesn’t really show any interesting patterns. The problem is that non-uniform random selections change what happens in each location in isolation but instead we want something where the random selection in one location is related to to the random selections in nearby locations. This is called “coherence”.

That’s where noise functions come in. They give us a set of random numbers instead of one at a time. Here we want a 1D noise function to give us a sequence. Let’s try a noise function that modifies a sequence of uniformly selected random numbers. There are lots of ways to do this but let’s take the minimum of two adjacent numbers. If the original noise was 1, 5, 2, then the minimum of (1, 5) is 1, and the minimum of (5, 2) is 2. So the resulting noise will be 1, 2. Note that it removed the high point (5). Also note that the resulting noise has one fewer value than the original. That means when we generate 60 random numbers below we will only get 59 out. Let’s apply this function to the first set of maps:

def adjacent_min(noise):
   output = []
   for i in range(len(noise) - 1):
      output.append(min(noise[i], noise[i+1]))
   return output

for i in range(5):
   random.seed(i)
   noise = [random.randint(1, 3) for i in range(mapsize)]
   print_chart(i, adjacent_min(noise))
0
1
2
3
4

Compared to the previous maps we made, these have larger areas of valleys, hills, or mountains. Mountains are often near hills. And because of the way we modified the noise (by taking the min), valleys are more common than mountains. If we had taken the max, mountains would be more common than valleys. If we had wanted neither valleys nor mountains more common, we could’ve taken the average instead of min or max.

We now have a noise modification routine that can take some noise and make some new, smoother noise.

Hey, let’s run it again!

def adjacent_min(noise):  # same as before
   output = []
   for i in range(len(noise) - 1):
      output.append(min(noise[i], noise[i+1]))
   return output

for i in range(5):
   random.seed(i)
   noise = [random.randint(1, 3) for i in range(mapsize)]
   print_chart(i, adjacent_min(adjacent_min(noise)))
0
1
2
3
4

Now our maps are even smoother and there are even fewer mountains. I think we’ve smoothed too much, since we’re not seeing mountains near hills very often. So maybe it’s better go back to just one level of smoothing in this example.

This is a common process with procedural generation: you try something and see whether it looks right, and if not, you change it back or try something else.

Side note: smoothing is called a low-pass filter in signal processing. It’s sometimes used to remove unwanted noise.

To review:

  • Noise is a set of random numbers, usually arranged in a line or grid.
  • In procedural generation we often want to add noise to produce variation.
  • Simply picking random numbers (whether uniformly or non-uniformly) leads to noise that has each number unrelated to its surroundings.
  • We often want noise with some characteristics, like having mountains be near hills.
  • There are lots of ways to make noise.
  • Some noise functions produce noise directly; others take existing noise and modify it.

Picking a noise function sometimes takes guesswork. Understanding how noise works and how you can modify it means you can make more educated guesses.

#Making noise

In the previous section we chose noise by using random numbers as the output, then smoothing them. This is a common pattern. You start with a noise function that uses random numbers as parameters. We used one where the random number picked where the gold was, and then we used another one where the random number selected valleys/hills/mountains. You can then modify existing noise to shape it to your needs. We modified the valleys/hill/mountain noise function by smoothing it. There are lots of other ways to modify noise functions.

Some of the basic 1D/2D noise generators are:

  1. Use random numbers directly for the output. This is what we did for valleys/hills/mountains.
  2. Use random numbers as parameters for sines and cosines, which are used for the output.
  3. Use random numbers as parameters for gradients, which are used for the output. This is used in Perlin Noise.

Some of the common ways to modify noise are:

  1. Apply a filter to reduce or amplify certain characteristics. For valleys/hills/mountains we used smoothing to reduce the bumpiness, increase the size of valleys, and make mountains occur near valleys.
  2. Add multiple noise functions together, typically with a weighted sum so that we can control how much each noise function contributes to the total.
  3. Interpolate between the noise values the noise function gives us, to generate smooth areas.

There are so many ways to make noise!

To some extent it doesn’t matter how the noise was made. It’s interesting but when using it in a game, focus on two things:

  1. How are you going to use the noise?
  2. For each use, what properties do you want from your noise function?

#Ways to use noise

The most straightforward way to use a noise function is to use it directly as elevation. In an earlier example I generated valleys/hills/mountains by calling random(1,3) at each location on the map. The noise value is directly used for the elevation.

Using midpoint displacement noise or Perlin noise as elevations are also direct uses.

Another way to use noise is as a movement from a previous value. For example, if the noise function returns [2, -1, 5] then you can say the first position is 2, the second is 2 + -1 = 1, and the third position is 1 + 5 = 6. Also see “random walk”. You could also do the inverse, and use the differences between noise values. You can also think of this as a modification of a noise function.

Instead of using noise for elevation you might be using it for audio.

Or maybe you’re using it to make a shape. For example, you can use noise as a radius in a polar plot. You can convert a 1D noise function like this into a polar form by using the output as a radius instead of as an elevation. Here is what that same function looks like in polar form.

Or you might be using noise as a graphical texture. Perlin noise is often used for this.

You might use noise to choose the locations of objects, such as trees or gold mines or volcanos or earthquake fault lines. In an earlier example, I used a random number to choose the location of the treasure chest.

You might use noise as a threshold function. For example, you can say that any time the value is greater than 3, then one thing happens, otherwise something else happens. One example of this is using 3D Perlin noise to generate caves. You can say that anything above a certain density threshold is solid earth and anything below that threshold is open air (cave).

In my polygon map generator I had several different uses of noise, but none of them were directly using noise for elevation:

  1. The graph structure is simplest as a square grid or a hexagonal grid (and in fact I started with a hex grid). Each tile in a grid is a polygon. I wanted to add some randomness to the grid. You can do that by randomly moving the points around. I wanted something slightly more random. I used a blue noise generator to position the polygons, and Voronoi to reconstruct them. This is a lot more work but fortunately I had a library (as3delaunay) that did all the work. But I started with a grid, which is much easier, and that’s what I recommend starting with.
  2. The coastline is a way to divide land from water. I have two different ways to generate this with noise, but you could also have a designer draw the shape directly, and I demonstrated that with the square and blob shapes. The radial coastline shape is a noise function that uses sines and cosines, and plots them in polar form. The Perlin coastline shape is a noise generator that uses Perlin noise and a radial dropoff as a threshold. Any number of noise functions could be used here.
  3. The river sources are placed randomly.
  4. The borders between polygons are changed from straight lines to noisy lines. It’s similar to midpoint displacement but I scaled it to fit within the bounds of the polygons. This is a pure graphical effect, and the code is in the GUI (mapgen.as) instead of the core algorithm (Map.as).

Most of the tutorials out there use noise in straightforward ways but there are lots of different ways to use noise.

#Frequency of noise

Frequency is the main property we want to look at. The simplest way to understand this is with sine waves. Here’s a lower frequency sine wave followed by a medium frequency sine wave followed by a high frequency sine wave:

print_chart(0, [math.sin(i*0.293) for i in range(mapsize)])
0
print_chart(0, [math.sin(i*0.511) for i in range(mapsize)])
0
print_chart(0, [math.sin(i*1.57) for i in range(mapsize)])
0

You can see that lower frequencies make wider hills and higher frequencies make narrower hills. Frequency describes the horizontal size of the features; amplitude describes the vertical size. Remember above when I said the valley/hill/mountain maps looked “too random” and I wanted larger areas of valleys or mountains? I was essentially asking for a lower frequency of variation.

If you have a continuous function such as sin that produces the noise, then increasing the frequency means multiplying the input by some factor: sin(2*x) will have twice the frequency of sin(x). Increasing the amplitude means multiplying the output by some factor: 2*sin(x) will have twice the amplitude of sin(x). In the code above you can see that I changed the frequency by multiplying the input by various numbers. We’ll use the amplitude in the next section when adding together multiple sine waves.

Try changing the frequency:


Frequency:

Try changing the amplitude:


Amplitude:

All of the above is for 1D but the same thing happens in 2D. Look at Figure 1 on this page. You’ll see examples of high wavelength (low frequency) and low wavelength (high frequency) 2D noise. Notice how the higher the frequency, the smaller the features.

When noise functions talk about frequency or wavelength or octaves, this is what they’re talking about, even when they’re not using sine waves.

Speaking of sine waves, you can do fun things by combining them in weird ways; in this example there are some low frequencies on the left and high frequencies on the right:

print_chart(0, [math.sin(0.2 + (i * 0.08) * math.cos(0.4 + i*0.3))
            for i in range(mapsize)])
0

Typically you’ll have multiple frequencies at the same time, but there’s no one right answer of what you should use. Ask yourself: what kinds of frequencies do you want? It depends of course on how you’re using it.

#Colors of noise

The “color” of noise describes what kinds of frequencies it has.

In white noise all frequencies contribute equally. We played with white noise earlier, when we picked 1, 2, or 3 to represent valleys, hills, or mountains. Here are 8 sequences of white noise:

for i in range(8):
   random.seed(i)
   print_chart(i, [random.uniform(-1, +1)
               for i in range(mapsize)])
0
1
2
3
4
5
6
7

In red noise (also called Brownian noise) the low frequencies are more prominent (have higher amplitudes). This means you’ll see longer hills and valleys in the output. We can generate red noise by averaging adjacent values of white noise. Here are the same 8 white noise samples from above, except put through the averaging process:

def smoother(noise):
   output = []
   for i in range(len(noise) - 1):
      output.append(0.5 * (noise[i] + noise[i+1]))
   return output

for i in range(8):
   random.seed(i)
   noise = [random.uniform(-1, +1) for i in range(mapsize)]
   print_chart(i, smoother(noise))
0
1
2
3
4
5
6
7

If you look closely at any of these 8 you’ll see it’s smoother than the corresponding white noise. There are longer runs of high or low values.

Pink noise is somewhere between white noise and red noise. It occurs in lots of places in nature, and it’s often what we want for landscapes: big hills and valleys, plus small bumpiness along the terrain.

On the opposite site of the spectrum, we have violet noise. The high frequencies are more prominent. We can generate violet noise by taking the difference of adjacent values of white noise. Here are the same 8 white noise samples from above, except put through the differencing process:

def rougher(noise):
   output = []
   for i in range(len(noise) - 1):
      output.append(0.5 * (noise[i] - noise[i+1]))
   return output

for i in range(8):
   random.seed(i)
   noise = [random.uniform(-1, +1) for i in range(mapsize)]
   print_chart(i, rougher(noise))
0
1
2
3
4
5
6
7

If you look closely at any of these 8 you’ll see that it’s rougher than the corresponding white noise. There are fewer long runs of high/low values, and more short variations.

Blue noise is somewhere between violet noise and white noise. It’s often what we want for object placement: no super-dense or super-sparse areas, but a roughly even distribution of objects across the landscape. The position of rods and cones in your eye have blue noise characteristics. Blue noise might also make for a cool cityscape.

Wikipedia has a page where you can listen to the different colors of noise.

We’ve seen how to generate white, red, and violet noise. But the most useful noise functions for us are white, pink, and blue. So we’ll try to generate pink and blue later on.

To review:

  • Frequency is a property of repeating signals like sine waves, but we can look at noise this way too.
  • White noise is the simplest. It has all frequencies. It’s uniformly chosen random numbers.
  • Red, pink, blue, and violet are other colors of noise that can be useful for procedural generation.
  • You can turn white noise into red noise by averaging.
  • You can turn white noise into violet noise by differencing.

#Combining frequencies

In the previous sections we looked at the “frequencies” of noise, and how there are various “colors” of noise. White noise means it has all the frequencies; pink and red have low frequencies stronger than high; blue and violet have high frequencies stronger than low.

One way to generate noise that has the frequency characteristics you want is to find some way to generate noise at specific frequencies, then combine it together. For example, suppose we had a noise function noise that generated noise at a specific frequency freq. Then if you want noise that has 1000 Hz frequencies to be twice as strong as 2000 Hz frequencies, and no other particular frequencies, we could use noise(1000) + 0.5 * noise(2000).

Now, I admit, sine does not look particularly noisy, but it’s easy to give it a frequency, so let’s start with that and see how far we can get with it.

def noise(freq):
   phase = random.uniform(0, 2*math.pi)
   return [math.sin(2*math.pi * freq*x/mapsize + phase)
         for x in range(mapsize)]

for i in range(3):
   random.seed(i)
   print_chart(i, noise(1))
0
1
2

So that’s it. Our basic building block is just a sine wave shifted sideways by a random amount (called phase). The only randomness here is how far we shifted it.

Let’s combine some noise functions together. I’m going to add 8 noise functions together, at frequencies 1, 2, 4, 8, 16, 32 (powers of two are called octaves in some of the noise functions). I’ll multiply each of those noise functions by some factor (see the amplitudes array) and add them together. I need a way to calculated a weighted sum:

def weighted_sum(amplitudes, noises):
   output = [0.0] * mapsize  # make an array of length mapsize
   for k in range(len(noises)):
      for x in range(mapsize):
         output[x] += amplitudes[k] * noises[k][x]
   return output

And now I can use the noise function from earlier and the new weighted_sum function:

amplitudes = [0.2, 0.5, 1.0, 0.7, 0.5, 0.4]
frequencies = [1, 2, 4, 8, 16, 32]

for i in range(10):
   random.seed(i)
   noises = [noise(f) for f in frequencies]
   sum_of_noises = weighted_sum(amplitudes, noises)
   print_chart(i, sum_of_noises)
0
1
2
3
4
5
6
7
8
9

Even though we started out with sine waves, which aren’t noisy looking at all, the combination of them looks reasonably noisy, no?

What if I used [1.0, 0.7, 0.5, 0.3, 0.2, 0.1] for the weights? That uses a lot more low frequencies and doesn’t have high frequencies at all:

0
1
2
3
4
5
6
7
8
9

What if I used [0.1, 0.1, 0.2, 0.3, 0.5, 1.0] for the weights? That makes the low frequencies have very little weight and the high frequencies have much more:

0
1
2
3
4
5
6
7
8
9

All we’ve done here is a weighted sum of noise functions at different frequencies, all in under 15 lines of code, and we’re able to generate a wide variety of different styles of noise.

To review:

  • Instead of choosing an array of random numbers, we’re choosing a single random number, and using it to shift a sine wave left or right.
  • We can make noise by taking a weighted sum of other noise functions that have different frequencies.
  • We can choose the characteristics of the noise by choosing the weights for the weighted sum.

#Generating the rainbow

Now that we can generate noise by mixing together noise at different frequencies, let’s revisit the colors of noise.

Look again at the Wikipedia page on the colors of noise. Notice they show the frequency spectrum. That tells you the amplitude of each frequency present in the noise. White noise is flat; pink and red are sloped downwards; blue and violet are sloped upwards.

The frequency spectrum corresponds to our frequencies and amplitudes arrays from the previous section.

Previously we used frequencies that were powers of two. The various types of colored noise have many more frequencies than that, so we’ll need a longer array. For this code I’m going to use all integer frequencies from 1 to 30, instead of only the powers of 2 (1, 2, 4, 8, 16, 32). Instead of writing out the amplitudes by hand, I’m going to write a function amplitude(f) that returns the amplitude at any given frequency, and then build the amplitudes array from that.

We can reuse the weighted_sum and noise functions from before, but this time instead of a small set of frequencies we’ll have a longer array of them:

frequencies = range(1, 31)  # [1, 2, ..., 30]

def random_ift(rows, amplitude):
   for i in range(rows):
      random.seed(i)
      amplitudes = [amplitude(f) for f in frequencies]
      noises = [noise(f) for f in frequencies]
      sum_of_noises = weighted_sum(amplitudes, noises)
      print_chart(i, sum_of_noises)

random_ift(10, lambda f: 1)
0
1
2
3
4
5
6
7
8
9

In the above code the amplitude function sets the shape. By having it always return 1, it produces white noise. How do we generate the other colors of noise? I’m going to use the same random seed but use a different amplitude function for these:

8.1 Red noise

random_ift(5, lambda f: 1/f/f)
0
1
2
3
4

8.2 Pink noise

random_ift(5, lambda f: 1/f)
0
1
2
3
4

8.3 White noise

random_ift(5, lambda f: 1)
0
1
2
3
4

8.4 Blue noise

random_ift(5, lambda f: f)
0
1
2
3
4

8.5 Violet noise

random_ift(5, lambda f: f*f)
0
1
2
3
4

8.6 Colors of noise

So that’s pretty neat. You change the exponent on the amplitude function to get some simple shapes.

  • Red noise is f^-2
  • Pink noise is f^-1
  • White noise is f^0
  • Blue noise is f^+1
  • Violet noise is f^+2

Try varying the exponent to see how the noise from sections 8.1-8.5 are all generated from the same underlying function:

0
1
2
3
4
Exponent: =

To review:

  • We can generate noise by a weighted sum of sine waves at different frequencies.
  • The various colors of noise have weights (amplitudes) that follow a function f^c.
  • By changing the exponent you can get different colors of noise from the same set of random numbers.

#More shapes of noise

To generate the various colors of noise we set the amplitudes to follow a simple exponential function, with various exponents. You aren’t limited to these shapes. This is just the simplest pattern, showing up as straight lines on a log/log plot. There are probably other sets of frequencies that produce interesting patterns for our needs. You can use an array of amplitudes and set them however you want instead of using a simple function. It’s something to explore but I haven’t done so yet.

One way to think about what we did in the previous section is in terms of Fourier Series. The main idea is that any continuous function can be represented as a weighted sum of sine and cosine waves. How you assign the weights determines what the resulting function will look like. The Fourier Transform connects the original function to its frequencies. Normally you start with the original data and ask it to tell you the frequencies/amplitudes. You see this in music players that show you the “spectrum” of the noise.

The forwards direction lets you analyze data into frequencies; the backwards direction lets you synthesize data from frequencies. For noise we’re mostly focused on synthesizing. In fact, we’ve already been doing this. In the previous section we chose some frequencies and amplitudes, and generated the noise.

The Fourier Transform has tons of cool ideas and math and applications.

This page has an explanation of how the Fourier Transform works. The diagrams on that page are interactive—you can enter the strength of each frequency and it will show you how they combine. You can form lots of interesting shapes by combining sine waves. For example, try entering 0 -1 0.5 -0.3 0.25 -0.2 0.16 -0.14 into the Cycles input field, and then uncheck the Parts checkbox. See how it looks like a mountain? The Appendix on that page has a version that also shows you how the sine waves look like in polar coordinates.

For one use of the Fourier Transform for map generation, see Paul Bourke’s Frequency Synthesis approach to landscape generation, which first generates 2D white noise, then converts it to frequencies using the Fourier Transform, then shapes that into pink noise, then converts back using the Inverse Fourier Transform.

My limited experiments with 2D so far suggest that it’s not as straightforward as the 1D scenario. If you want to take a look at my incomplete experiments, scroll down to the bottom of this page and play with the sliders.

#10  Other noise functions

In this article we’ve been using sine waves for generating noise. It’s pretty simple. We take several functions and add them together. Even though the original functions don’t look noisy, the result looks pretty good, especially for 15 lines of code.

I haven’t studied noise functions much. I just use them in my projects. I think a lot of them are generating pink noise:

  • I believe midpoint displacement is using a sawtooth wave instead of a sine wave, and then adding together higher and higher frequencies with lower and lower amplitudes. I think that’s pink noise. You end up with visible edges, which is either due to sawtooths (not as smooth as sine waves) or due to it only using frequencies that are a power of two instead of using all frequencies. I’m not sure.
  • Diamond square is a variant of midpoint displacement that attempts to somewhat hide the edges that you get with midpoint displacement.
  • A single octave of Perlin/Simplex Noise is generating smooth noise at a particular frequency. You typically add up several octaves of Perlin Noise together to make the noise pink.
  • I believe Fractal Brownian Motion is also generating pink noise by adding multiple noise functions together.
  • The Voss-McCartney algorithm seems similar to midpoint displacement. It adds up several white noise functions at different frequencies.
  • You can directly generate pink noise by calculating the Inverse Fourier Transform from the frequencies you want. That’s what the example in the previous section did. Paul Bourke describes this as Frequency Synthesis, and shows how it looks for 2D noise generating 3D heightmaps.

Some of the pages on Voss-McCartney make me think that adding up noise at different frequencies will not exactly be pink noise, but is probably close enough for map generation. The seams you get from midpoint displacement are likely from this, or maybe from the interpolation function. I don’t know.

I haven’t found as many ways to generate blue noise.

  • For my polygon map generator project, I used Lloyd Relaxation with Voronoi diagrams to generate the blue noise I needed. I already had a library that gave me Voronoi diagrams, and it was easier to reuse it than to implement a separate step.
  • Poisson Disks are another way to generate blue noise. If I don’t already have a Voronoi library in the project, Poisson Disk seems simpler. Also see this article describing some uses of it in games.
  • Recursive Wang Tiles can also generate blue noise. I haven’t studied these at all but hope to one day.
  • You should be able to directly generate blue noise by calculating the Inverse Fourier Transform from the blue noise frequency spectrum. I haven’t tried this yet.

I’m not even sure that proper blue noise is what I need for maps, but it’s described as blue noise in the literature. The blue noise I’m generating with sine waves seems somewhat like what I want but the above techniques seem to better match what I want for games.

#11  More

This page was originally notes for myself, kept in Emacs org-mode. I improved the diagrams and added a few interactive ones when publishing to the web. I spent nowhere near as much time on this as I do on most of my articles, but I’m experimenting with covering some topics with less polish, in the hopes that it will allow me to write about more things.

I also have some 2D experiments that aren’t as polished as the stuff on this page, including a 3D visualization of a 2D heightmap.

Other things I haven’t really investigated: